Foundations of coding

Module 1

A computer program consists of instructions executing one at a time. Basic instruction types are:

• Input: a program gets data, perhaps from a file, keyboard, touchscreen, network, etc. 

• Process: a program performs computations on that data, such as adding two values like x+y.

• Output: a program puts that data somewhere, such as to file, screen, network, etc.

Mathematical thinking became increasingly important throughout the industrial age, to enable people to successfully live and work. In the information age, many people believe __________, or creating a sequence of instructions to solve a problem, will become increasingly important for work and everyday life. A sequence of instructions that solves a problem is called an _________.

computational thinking, algorithm

When an algorithm is put into code that a computer can process, it is called a _________.

program

what’s an algorithm?

An algorithm describes a sequence of steps to solve a computational problem or calculation. An algorithm can be described in English, pseudocode, a programming language, hardware, etc.

what’s a computational problem?

A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output.

Algorithm

A set of instructions that describes how to get the exact result you want

Array

a collection that groups pieces of data in a certain order and assigns the collection a name

class

A detailed description or template of what an object will be in object-oriented programming

constructor function

A function whose purpose is to specify the properties to sue when you create an object

Debug

the process of identifying and fixing bugs in a program

For loop

A programming construct that lets you specify iteration to a specified endpoint

regular expression

An encoded description of a pattern that you want to match within a string

computational problem

A computational problem is a problem that can be solved using a computer. A computational problem specifies the problem input, a question to be answered, and the desired output

which can be used as the problem input?

1) String for user-specified word

2) Array of unique words and string for user-specified word

3) Array of all words and string for user-specified word

Array of all words and string for user-specified word

What is the problem output?

1) Integer value for the frequency of most frequent word

2) String value for the most frequent word in input array

3) Integer value for the frequency of specified word

integer value for the frequency of specified word

An algorithm to solve this computation problem must be written using a programming language.

True or False

False

how do you get the frequency desired?

The input must include a list of all words and the specific word for which determining the frequency is desired.

how is an algorithm described as?

An algorithm can be described in English, pseudocode, a programming language, hardware, etc., as long as the algorithm precisely describes the steps of a computational procedure. (This doesn't need to be written in a programming language.)

Longest common substring

the longest common substring algorithm determines the longest common substring that exists in two inputs strings

how is DNA sequences represented?

DNA sequences can be represented using strings consisting of letters A, C, G, and T to represent the four different nucleotides

Binary search

The binary search algorithm is an efficient algorithm for searching a list. The list's elements must be sorted and directly accessible (such as an array).

Dijkstra’s shortest path

Dijkstra's shortest path algorithm determines the shortest path from a start vertex to each vertex in a graph

The possible routes between two locations can be represented using a graph, where vertices represent specific locations and connecting edges specify the time required to walk between those two locations.

Polynomially

this means that the time it takes for an algorithm to run increases at a reasonable rate as the size of the problem it’s solving gets bigger.

NP-complete

NP-complete problems are a set of problems for which no known efficient algorithm exists.

NP-complete problems have the following characteristics:

• No efficient algorithm has been found to solve an NP-complete problem.

• No one has proven that an efficient algorithm to solve an NP-complete problem is impossible.

• If an efficient algorithm exists for one NP-complete problem, then all NP-complete problems can be solved efficiently.

By knowing a problem is NP-complete, instead of trying to find an efficient algorithm to solve the problem, a programmer can focus on finding an algorithm to efficiently find a good, but non-optimal, solution.

An algorithm with a polynomial runtime is considered efficient

True or false

True

An efficient algorithm is generally one whose runtime increases no more than polynomially with respective to the input size. In contrast, an algorithm with an exponential runtime is not efficient.

An efficient algorithm exists for all computational problems

True or false

False

Many computational problems exist for which an efficient algorithm is unknown. Such problems are often encountered in real applications.

An efficient algorithm to solve an NP-complete may exist.

True or false

True

Whether or not an efficient algorithm exists for NP-complete problems is an open research question. However, the current consensus is that such an algorithm is unlikely.

what is an algorithm?

 in daily life serve as guiding principles that facilitate decision-making, problem-solving, and task execution. They streamline processes, enhance efficiency, and contribute to overall organization and coherence in daily routines and activities.

what’s another way an algorithm can be understood as?

Algorithms in daily life can be understood as step-by-step procedures or sequences of tasks that we follow to accomplish various goals.

Which characteristics do algorithms in daily life share with computer algorithms?

They offer a structured approach for navigating tasks

Both algorithms in daily life and computer algorithms provide a structured methodology for accomplishing objectives, ensuring tasks are carried out logically and organized, leading to desired outcomes.

what the foundation of computer programming?

Algorithms form the foundation of computer programming, enabling developers to solve complex problems efficiently. Understanding and implementing algorithms effectively is essential for writing efficient and maintainable code.

Here are some best practices and principles to consider when working with algorithms in programming

understand the problem, choose the right algorithm, use pseudocode, modularize your code, handle edge cases, optimize for readability, test and validate, optimize for performance, document your algorithm, iterate and refine

understand the problem

Before writing any code, thoroughly understand the problem you are trying to solve. Break down the problem into smaller parts and identify the input, output, and constraints. This ensures clarity and helps in selecting the appropriate algorithm.

choose the right algorithm

Selecting the correct algorithm is crucial for efficient problem-solving. Choose an algorithm that is appropriate to the complexity and that is appropriate to the problem size. Consider factors such as time complexity, space complexity, and the nature of the problem (sorting, searching, graph traversal, etc.). Use established algorithms from libraries or textbooks whenever possible.

use pseudocode

Before diving into coding, sketch out your algorithm using pseudocode. Pseudocode is a high-level description of the algorithm's logic, independent of any programming language syntax. It helps in refining your approach and ensures clarity before implementation.

modularize your code

Break down your algorithm into smaller, modular components. Each component should perform a specific task or operation. Modular code is easier to understand, test, and maintain. Functions or methods are excellent tools for achieving modularity in programming.

Handle edge cases

Consider edge cases and corner cases in your algorithm. Edge cases are inputs that are at the extreme ends of the input domain or represent unusual scenarios. Ensure your algorithm handles these gracefully to avoid unexpected behavior or errors.

optimize for readability

Write code that is clear and easy to understand. Use meaningful variable names, comment your code effectively, and follow consistent coding conventions. Good readability reduces the chances of bugs and aids in debugging and maintenance.

test and validate

Test your algorithm with a variety of input cases, including typical cases, edge cases, and large inputs (if applicable). Verify that the algorithm produces correct outputs for all scenarios and meets the desired performance criteria. Unit tests and integration tests are valuable tools for validating algorithms.

optimize for performance

After verifying correctness, optimize your algorithm for performance if necessary. Consider the time complexity O() notation) and space complexity of your algorithm. Look for opportunities to reduce unnecessary computations, use efficient data structures, and leverage algorithmic techniques like memorization or dynamic programming.

document your algorithm

Document your algorithm's purpose, inputs, outputs, and key steps. Include any assumptions or constraints. Good documentation helps other developers (including future you) understand the algorithm's logic and purpose without needing to delve into the code itself.

Iterate and refine

Algorithm design is often an iterative process. Don't hesitate to revisit and refine your algorithm based on feedback, performance profiling, or changes in requirements. Continuous improvement ensures that your algorithms remain effective and efficient over time.

Are algorithms everywhere?

Yes algorithms are everywhere, helping with things like sorting laundry and following a driving route.

when you learn about ______, you're learning step-by-step ways to solve problems.

Algorithms

Computers follow encoded algorithms called _____ to handle data quickly

programs

Learning about _______ helps you understand how computers solve problems effectively

algorithms

what’s it like designing algorithms?

Designing algorithms is like having a structured plan for solving tricky problems. It's about breaking down problems into smaller, manageable steps, finding smart solutions, and then putting them into action using a set order of steps.

what techniques do algorithms use?

Algorithms use techniques like repeating a set of actions until a certain condition is met (called iteration), solving problems by calling a function within itself (called recursion), and making decisions based on certain conditions.

what does using algorithms help with?

Using algorithms helps make problem-solving smoother, faster, and more efficient. It allows people to deal with all kinds of problems in different areas. In the end, solving problems with algorithms lets people handle tough problems using a structured method, which can lead to new ideas and breakthroughs.

______ solve problems. before writing a program, a programmer must first create an algorithm to correctly solve the given problem

programs

An ________ is a sequence of steps that solves a problem, generating correct output for any valid input values. Ensuring an algorithm's correctness is a key job for a programmer.

Algorithm

Pseudocode

A high-level description of the actions of a program or algorithm, using a mixture of English and informal programming language syntax

______ is a high-level, interpreted programming language known for its simplicity, readability, and versatility, supporting multiple programming paradigms. With an extensive standard library and active community, ____ enables rapid development of diverse software projects across various domains.

Python

search algorithms

Search algorithms explore the problem space to find a solution by systematically examining possible states or configurations. Examples include depth-first search (DFS), breadth-first search (BFS), and A* search algorithm.

Dynamic programming

Dynamic programming breaks down a problem into smaller subproblems and solves each subproblem only once, storing the solutions to avoid redundant computations. This technique is particularly useful for problems with overlapping subproblems. example: Fibonnaci Sequence, Shortest Path Problems

Greedy algorithms

Greedy algorithms make decisions based on the current best option without considering the global optimal solution. While they may not always produce the most optimal result, greedy algorithms are often simple and efficient for certain types of problems. example: Dijkstra's Algorithm, Huffman Coding

Route planning

suppose you’re developing a navigation app that needs to find the shortest route between two locations on a map. You can use algorithms like Dikstra’s algorithm or the A* search algorithm to calculate the optimal path considering factors like distance, traffic conditions, and road closures. 

Task scheduling

in task scheduling applications, you may need to assign tasks to resources or processors while minimizing the overall completion time or maximizing resource utilization. Algorithms like the earliest deadline first (EDF) algorithm or the shortest job next (SJN) algorithm can help optimize task scheduling.

Resource allocation

When allocating resources such as memory or network bandwidth in a system, you can use algorithms like the banker's algorithm for deadlock avoidance or the first-fit algorithm for memory allocation to efficiently manage resource utilization and prevent conflicts

Algorithm efficiency

Choose algorithms that are appropriate for the problem size and complexity. Consider factors like time complexity, space complexity, and scalability when selecting planning algorithms.

Problem decomposition

Break down complex problems into smaller, more manageable subproblems to facilitate the application of planning algorithms. This approach simplifies problem-solving and improves algorithm efficiency.

Algorithm validation

Test and validate planning algorithms using various test cases to ensure correctness and reliability. Use techniques like unit testing, integration testing, and performance testing to evaluate algorithm performance.

Optimization and refinement

Continuously optimize and refine planning algorithms based on feedback and real-world data. Consider factors like algorithm parameters, heuristics, and tuning to improve algorithm effectiveness and efficiency.

Using _______ for planning in programming is a fundamental skill for developers to master. By understanding the principles of planning _______, applying them effectively in programming, and following best practices and considerations, you can solve complex problems, optimize resource utilization, and develop robust and efficient software systems

algorithms

A ________ is a visual representation of a process or algorithm, using symbols and arrows to illustrate the sequence of steps and decisions involved in completing a task or solving a problem

flowchart

Flowcharts can represent more complex algorithms by incorporating various symbols, decision points, and branching paths to capture the intricacies of the algorithm. Here's how flowcharts handle complexity:

Symbols and shapes, sequential steps, decision points, conditional statements, loops and iterations, parallel processing. By combining these elements, flowcharts can effectively represent the complexity of algorithms, providing a visual roadmap for understanding and implementing the logic and sequence of steps involved in solving a problem or completing a task. They allow programmers, analysts, and other stakeholders to visualize the algorithm's structure, identify potential bottlenecks or issues, and optimize the algorithm for efficiency and clarity.

symbols and shapes

Flowcharts use different symbols and shapes to represent various actions and decisions within the algorithm. For example, rectangles typically represent process steps, diamonds represent decision points, and arrows indicate control flow between steps.

sequential steps

Flowcharts can depict sequential steps in an algorithm, showing the order in which actions are performed. Each step leads to the next one, creating a clear path for executing the algorithm from start to finish

decision points

Flowcharts incorporate decision points where the algorithm branches based on certain conditions or criteria. These decision points are represented by diamond-shaped symbols, with different paths leading to different actions depending on the outcome of the decision.

conditional statements

Complex algorithms often include conditional statements such as if-else or switch-case statements. Flowcharts represent these statements as decision points, with arrows branching out to different paths based on the conditions specified in the algorithm

loops and iterations

Flowcharts can depict loops and iterations within an algorithm, where certain steps are repeated multiple times until a specific condition is met. Looping constructs such as for loops, while loops, and do-while loops are represented using specific symbols and arrows in the flowchart

parallel processing

Complex algorithms sometimes involve parallel processing or simultaneous execution of multiple tasks. Flowcharts can represent parallelism by using parallel lines or multiple paths running concurrently to show how different algorithm parts are executed in paralle

what is a flowchart?

A visual representation of a process or algorithm

__________ helps people see the steps of the plan without needing to know a specific programming language

pseudocode

Using _______ to show how algorithms work gives a clear picture of what steps to take. ________ make it easier to understand and explain complex plans

flowcharts

___________________ are the bedrock of computer science, enabling developers to communicate instructions to computers effectively.

programming languages

Programming Languages

Programming languages are used to provide instructions to a computer. Each language has its own syntax (rules) and semantics (meaning).

Syntax Differences

Examples of "Hello, world" programs in C++, JavaScript, and Python highlight the differences in syntax between languages.

Purpose of Different Languages

Different programming languages exist because each has its own strengths and weaknesses, suited for various tasks such as programming small devices or handling complex computations.

High-Level Languages

These languages are closer to human languages and easier for us to understand, compared to machine language, which is complex and consists mostly of numbers.

what is programming language?

Statements, operators and expressions, order of operations

Statements

These are the building blocks of any program, representing individual actions that the program will take

Operators and Expressions

Operators (like +, -, *, /) are used to perform actions on inputs (operands). Expressions combine operators and operands to produce a single value.

Order of Operations

Programming follows the same order of operations as mathematics (PEMDAS - Parentheses, Exponents, Multiplication/Division, Addition/Subtraction)

A __________________ is a set of instructions and syntax used to create software programs. Some of the key features of programming languages include the following: Syntax, data types, variables, operators, control structures, libraries and frameworks, paradigms.

programming language

Syntax

the specific rules and structure used to write code in a programming language.

Data types: the type of values that can be stored in a program, such as numbers, strings, and Booleans.

Data types

the type of values that can be stored in a program, such as numbers, strings, and Booleans.

Variables

named memory locations that can store values.

Operators

symbols used to perform operations on values, such as addition, subtraction, and comparison.

Control structures

statements used to control the flow of a program, such as if-else statements, loops, and function calls.

Libraries and frameworks

collections of pre-written code that can be used to perform common tasks and speed up development

Paradigms

the programming style or philosophy used in the language, such as procedural, object-oriented, or functional

JavaScript

Widely used for web development, JavaScript is essential for creating interactive and dynamic web pages. It's also increasingly popular for server-side development (Node.js), mobile app development (React Native), and desktop app development (Electron).

Python

Known for its simplicity and readability, Python is used for web development, data analysis, artificial intelligence (AI), machine learning, scientific computing, automation, and more. Its vast ecosystem of libraries and frameworks contributes to its popularity.

Java

A versatile language used for developing enterprise applications, Android apps, web servers, and large-scale systems. Java's platform independence, strong community support, and robust tools make it a popular choice in many industries.

C/C++

C and C++ are powerful languages used for system programming, game development, embedded systems, performance-critical applications, and low-level development. Despite being older languages, they remain vital in various domains where performance is crucial.

C#

Developed by Microsoft, C# is widely used for building Windows applications, web applications (with ASP.NET), game development (with Unity), and enterprise software. It's known for its simplicity, type safety, and integration with the .NET framework.

PHP

Primarily used for server-side web development, PHP is a popular choice for building dynamic websites and web applications. It powers many content management systems (e.g., WordPress, Drupal) and e-commerce platforms

Swift

Developed by Apple, Swift is the preferred language for iOS and macOS app development. It's known for its safety features, modern syntax, and performance. SwiftUI, a declarative UI framework built with Swift, has further increased its popularity.