Algorithms & Programming

Algorithms & Programming

Algorithms are solutions designed to create something new or solve problems. They are fundamental to programming. All programming languages use similar programming structures & commands. These building blocks are combined to form algorithms & abstractions in one language.

Foundations of Computer Programming

• Algorithms

• Variables & Assignment Statements

• Data Types

• Lists

• Program Statements

• Iteration

• Procedures (Methods or Functions)

Algorithms

Definition: a set of steps to complete a task or solve a problem. Examples: recipes, directions, and instructions. Some existing algorithms include:

~determining the max or min value of two or more numbers

~computing the sum or average of two or more numbers

~identifying if an integer is or is not evenly divisible by another integer

~determining a robot's path through a maze

Benefits of using existing algorithms when creating new ones: reduces development time, reduces testing, and simplifies the identification of errors.

Algorithms (continued)

Programming languages are very strict with their syntax, which is like its grammar & structure. Pseudocode is a combination of natural and programming languages used to plan a program prior to coding. Pseudocode cannot run on computers (due to its natural language) and needs to be translated to a programming language to run.

Flowcharts - diagramming an algorithm before programming. Help visualize how the program will be structured; you can see how requirements are met & how some may work better in a certain order or in combination with future code.

Algorithms (continued)

Programmers use the basic shapes in the image to the right for creating flowcharts.

Algorithms (continued)

An important feature of any algorithm & program is how easy it is to read, follow, and clarity. Clarity refers to how easy it is to understand. Readability is important to help programmers understand a program. This is important when the current programmer is using existing code or if there is a long time span between writing the program and modifying/correcting the code.

There is more than one correct algorithm to solve a problem or to create something new. Finding different algorithmic solutions can be helpful in identifying new insights; they may also have different levels of efficiency and clarity.

Variables

Definition: a placeholder for values that a program needs to use. Can be used in expressions; both mathematical & textual. Most important aspect of variables is giving them a good name, that is descriptive enough for other programmers to understand and even update. This also helps manage the complexity of the program.

Variables are data abstractions because we do not need to know the details of how and where the values are stored in memory.

Variables can hold a single data value or a collection of values (list).

Variables (continued)

The assignment operator is used to assign a value to a variable. In many programming languages, the = is used, like in Java & JavaScript. For the AP Exam, you will see the  $\leftarrow$  used to assign a variable.  The variable name is always on the left of the  $\leftarrow$  sign.  The programming language will evaluate the right side of the assignment operator and then place the value into the variale on the left side of the assignment operator.  A new assignment statement will override a previous value stored in a variable.  The value of a variable can be printed or displayed on the screen.

Data Types

Data types are used to assign some meaning to binary digits for the data to be stored. There are 4 main data types:

~Strings (text)

~Numbers (whole & decimal)

~Lists (ordered sequence of elements)

~Booleans (true/false)

DATA TYPE: Strings (text)

Any character, number, or symbol can be part of a string. Must be denoted with quotation marks (" ") around the string field. Concatenating strings means adding string fields together.

Example:

msg1 = "Coding"

msg2 = "is great!"

*Exam questions may use a format and pass the two strings to be concatenated as parameters. The concatenated value would be returned by the procedure.

Concatenate (firstName, lastName)

This procedure would take two strings and return the concatenated version as one string holding a person's full name.

DATA TYPE: Strings (continued)

Substrings are sections of strings.

You can reference a character in a string using its index (position in the string). In this course, we are using JavaScript in Code.org, where index starts at zero. The first letter is the index 0, the second character is the index 1, and so on. Spaces also get their own index.

On the AP Exam, INDEX STARTS AT 1!

DATA TYPE: Strings (continued)

Example of AP Exam Question format:

Substring(string, start, length)

Substring is the name of the procedure. First parameter, string, would be the variable to use in the substring operation. Second parameter, start, tells us the first index position of new substring. Last parameter, length, how many index positions to include in the new substring.

If a variable msg1 = "Coding", then calling this procedure Substring with the following start & length:

Substring (msg1, 1, 3) would give us "Cod".-

DATA TYPE: Numbers

Integers & Fractional Numbers

Integers are whole numbers (not decimal); used in mathematical expressions.

Fractional numbers are those with a decimal point, even if that is zero (example: 23.0).

DATA TYPE: Lists

Lists are a collection of items (numbers, words, phrases, or a combination of these). Usually it only contains one type of data in a single list; some programming languages do allow different types in a list.

Benefit: provides the ability to store more than one value in the same variable (separated by commas) when the variable is defined as a list. Makes designing a solution and processing items much easier.

A list is an abstraction and in some programming languages, called arrays.

Elements are individual items in a list and are accessed by position using an index.

DATA TYPE: Lists (continued)

As you learned with Strings, JavaScript & Java start with an index of 0. However, for the AP CS PRINCIPLES EXAM, THE LIST STARTS AT 1.
~~To access an element in a list: listName[ i ]
~~To assign a value to a list position in an index:

 listName [ i ]  $\leftarrow$  variable

~~To assign the value stored in a list to another variable:
 variable  $\leftarrow$  listName
~~To assign the value of one list element to another list element, use the same format.  The current value in the list element is overwritten with the new one.
listName [ i ]  $\leftarrow$   listName [ j ]

Lists Commands

~~INSERT: Adds an item to a specific position in a list.

INSERT (listName, i, value)

~~APPEND: adds a new element to the end of the list.

APPEND (listName, value)

~~REMOVE: deletes the element at the provided index and shifts the remaining elements to the left.

REMOVE (listName, i)

~~LENGTH: returns the number of elements in the list.

LENGTH (listName)

Checking Each Item in a List

The FOR EACH loop (see slide 29) will automatically repeat the code for each element in the list. This is called traversing a list.

DATA TYPES: Boolean Values

The last data type, Booleans, are important for writing, correcting, reading, and creating efficient code. Booleans can only be true or false, needing only one bit to represent each value. Relational operators (=equal,  $\ne$ not equal,  $<$  less than, and so on) are used with Boolean values.  

Two values are compared based on the relational operator & determined to be true or false.  

For example: num1  $\leftarrow$  5 and num2  $\leftarrow$  10. 
num1 > num2 evaluates to false.

Conditional Statements

Boolean expressions can be simple or compound. Multiple expressions can be combined using logical operators: AND, OR, and NOT. These also evaluate to either true or false.

AND Operator

To be true, both operands on either side of the AND must be true when evaluated individually.

Conditional Statements (continued)

OR Operator

Either or both of the operands can be true for the condition to be true.

NOT Operator

If a condition is true, the NOT operator makes it false. If a condition is false, the NOT makes it true.

Nested (Compound) Conditional Statements

Example: (time = 1800) AND (dog = true AND currentTemp<80)

time=1800 evaluates to true or false as a single Boolean value.

dog=true AND currentTemp<80 both have to be evaluated first and compared with AND. The result of that as a Boolean is then used as the right side operand of the first AND.

Solution: Assume the time is 6pm (1800), so that's true. Then assume there is a dog, so that is true. The currentTemp is 82, so (currentTemp<80) is false. Since the operands on the right are true & false, they evaluate to false. Now both sides are false.

Math Operators

+ add

- subtract

* multiply

/ divide

The order of operations (PEMDAS) is used in programming languages. Use ( ) to ensure the correct order of processing.

MOD - modulus (returns only the remainder after dividing). Mod is used by programmers mostly to find even or odd numbers. A number that is divisible by 2 with a remainder of 0 is even.

Mod (modulus)

The % is the mod operator.

Program Statements

All programs can be written using a combination of only 3 types of statements:

1~Sequential

2~Selection

3~Iteration

Sequential & Selection

Sequential statements are those that are executed as written in order in the program.

Selection statements are key components to many programs. These are "if" statements and the evaluation of the condition uses Boolean values. Program statements only run when the condition at that moment evaluates to true. When the condition evaluates to false, the code within braces is skipped. Else statements are used when another condition is used.

Iterative

Iterative statements are repetitive statements or loops, which changes the sequence of execution.

Benefits: code will be shorter, avoids duplication, makes code more readable, easier to understand, and easier to update (only have to do in one place).

Types of Iteration

1) REPEAT n TIMES loop

This loop will repeat a specified number of times: "n" is a variable that must be set to a positive integer for the loop to run. The code that is repeated is indented underneath the REPEAT statement & within braces { } , just like with the IF/ELSE statements. The { } are required.

This loop will repeat 5 times since num is currently 5.

Types of Iteration

2) REPEAT UNTIL (condition) Loop

The REPEAT UNTIL loop has a condition to evaluate at each iteration of the loop. The loop will continue to run while the condition evaluates to "false". REPEAT UNTIL loops can execute multiple times or not at all, depending on the condition. Each iteration must change the loop, otherwise, it would be an infinite loop.

Types of Iteration

3) FOR EACH Loop

FOR EACH item IN list

Automatically repeats the code for each element in the list. This is called traversing a list. The programmer chooses the name for the iteration variable "item". Each pass of the loop will assign the value of the next element in the list to the variable "item".

Benefit: takes advantage of features of both structures.

Procedures (Methods or Functions)

Procedures are also called methods in other programming languages (such as Java). However, in JavaScript, we refer to them as functions. Procedures are sections of code that will be executed only when they are called by the main program or another procedure.

Benefits: 1) reuse of code reduces the length & complexity of programs by not duplicating code. 2) they increase the ease of maintaining or fixing programs because you only have one place to update code rather than several. 3) by using shorter blocks of code to do only a few tasks makes the code more readable & easier to understand.

Procedures (Methods or Functions)

They should have descriptive names to help identify their purpose. The code for the procedure goes between the braces { }.

Parameters (arguments): allow the calling program to send values to the procedure. They are passed to the procedure when it is called. The parameters must be sent in the same order as they are defined and must be the same data type. The number and type of parameters are identified when the function is defined.

PROCEDURE procedureName (parameter1, parameter2)

{

         <block of statements>

}

Procedures (Methods or Functions)

Calling a procedure: when a procedure is "called" the program will pause at that location & execute the code in the procedure. When the procedure finishes, it returns back to the line of code where the call occurred. Therefore, the sequential flow of the program is modified. Call a procedure by its name & include (). Any arguments are passed in the () separated by commas.

*Procedures are abstraction since details are abstracted away, procedure is more general, and can be used multiple times. You only need to know the name of procedure, number & type of parameters, and expected output.

Procedures (Methods or Functions)

Return: 1) ends a function before the end of the procedure is reached. No coding in the procedure will be executed after the return statement. 2) sends a value back to the calling program.

Procedures may perform a calculation or collect data in the procedure & need to send it back to the calling program.

Procedures (Methods or Functions)

~~The RETURN statement below calculates the area of a circle but does not store it in a variable. It sends the value calculated back to the code where it was called.
Example:
RETURN 3.14 * radius * radius

~~The RETURN statement below sends back the value currently stored in the variable, area.
Example:
area  $\leftarrow$  3.14 * (radius * radius)
Return (area)

Built-in Procedures

DISPLAY ()

used for this course on the exam to "print".

Format: DISPLAY (expression)

*in Code.org, we will be using console.log for RETURN & DISPLAY.

API's & "LIBRARIES"

Prewritten programs to provide commonly needed functionality, the "libraries" are folders with several programs. These are used to share with others, post to a trusted website, or to reuse in a different program. Some are included in the programming language, others that you can import when needed. API (Application Programming Interface) is documentation that provides information & directions needed to set up interface & use the new program.

Built-in Procedures

RANDOM (a, b)

Used to generate random numbers. Most programming languages have a library of prewritten code for a variety of random number generators.

Example: variable named num

num  ← RANDOM(1, 10)



Needs two values passed to it using arguments, the beginning & ending range for the selected random number. Each time the code is executed, a random number is generated.

Built-in Procedures

INPUT()

The programming language sees this command & pauses/waits for something to be typed on the keyboard. As soon as it detects that the "Enter" key has been pressed, it will capture the keystrokes up to that point. This user input is stored in a variable for a program. Otherwise, what is typed is not saved and can not be available for decisions, select options, display messages, or other features.

Example: name, is a variable assigned to INPUT()

name   ← INPUT()

Common Algorithms

1) Determining the maximum or minimum number from 2 or more numbers.

2) Calculating sum & average of a group of numbers.

3) Mod math - find if one number is divisible by another.

4) Finding the largest or smallest number in a list.

5) Finding the sum and average of the values in a list.

6) Determine a robot's path.

Linear Search

Also called sequential searches, check each individiual record, starting at the beginning and going to the end, one after the other in order to either find the desired data or to determine it is not in the dataset.

Benefits: easy to understand, simple to implement, and does not matter if data is sorted.

Best case is if the item is first in the list; worst case is if it is not in the list at all.

Easily implemented using the FOR EACH loop.

Binary Search

Far more efficient than linear searches; however, data must be sorted. Considered the "divide & conquer" algorithm because it divides the dataset into two equal parts. For example, if searching through a list of numbers 1-100 for 42, the method would divide the list in half (50) and decide if the value of 42 is lower or higher than 50. Since 42 is lower, it will throw out 50-100 and divide the remaining 1-49 in half and continue until the value of 42 is found.

Robots

This course & exam covers the movements of robots through a grid. There are four commands that you must understand and use. The triangle represents the robot's starting point and the direction it is facing.

Robots (continued)

MOVE_FORWARD

The robot moves one step forward in the direction it is already facing. If the command would place the robot in a blacked out box or past the border of the maze, the command cannot be executed.

ROTATE_LEFT () and ROTATE_RIGHT ()

The robot can also rotate left or right. This does NOT move it forward.

CAN_MOVE

This is used to determine if the robot can make a valid move forward before moving. It returns a Boolean value, true or false. This can also be used in an IF statement.

Backward - you must turn left or right twice, each turn is 90 degrees.

Robot Example

Some exam questions will ask where the robot would end up after the code executes (you will choose from 4 possible solutions). *Do not forget which way the robot would be facing at the end!

Another question will provide a maze with beginning & end points with choices of coding solutions to choose from that would move the robot correctly through the maze.

Simulations

Designed to represent and mirror the real world for testing. This is an example of abstraction at a very high level. Details are removed to focus on the impact of the conditions to be measured or evaluated during the simulation. The tests & results enable insights, knowledge, and discoveries to be made without constraints that would exist in the real world. Hypotheses can be evaluated and then refined without real-world impact. This reduces cost and saves time. Can be used to test potentially dangerous situations without putting anyone at risk. To introduce the variability of the real world, simulations often use a random number generator as a factor.

Analyzing Algorithms

Problem - task that can or cannot be solved with an algorithm.

Instance of a problem - a specific example.

Decision problem - has a yes or no answer.

Optimization problem - one that should find the best solution for the problem.

Efficiency of algorithms deals with resources needed to run it in terms of how long it will take & how much memory will be needed. Can be determined by mathematically proving it & informally measured by actually running it on datasets of different sizes & measuring how long it took & memory resources needed.

Wrapping Up Algorithms

Algorithms have limits and there are some problems for which we do not have efficient enough algorithms to solve. These algorithms can't run in a reasonable amount of time with current technology. As a dataset grows larger, the algorithm becomes too inefficient to process the data, then data may become unsecure.

Heuristic approach - an approach to problem solving that uses a practical method or various shortcuts in order to produce solutions that may not be optimal but are sufficient given a limited timeframe or deadline.

Wrapping Up Algorithms (continued)

Decidable problem is one where an algorithm can be written that results in a correct "yes" or "no" answer for all inputs. Example: determining if a number is prime.

Undecidable problem does not have an algorithm that can give a correct "yes" or "no" for all cases of the problem. An algorithm may work for some cases, but not all.