unit 3: algorithms and programming

35% of ap exam

variable

a placeholder for a value in a program

usually represented by letters or words

can only hold one data value at a time, which can be reassigned

global variables

defined outside of all functions and events

can be accessed anywhere in the program

local variables

defined within a specific function or event

can only be accessed in that function or event

variable’s data is deleted once its event is done

should be avoided — limited scope and can cause redundancy

data types

different categories of data a computer can represent

ex. integers, lists, strings, booleans

strings

data type that represents text instead of numbers (holds the characters in a specific sequence)

must be closed by quotation marks

substrings

a string of characters inside of a larger string

+ operator can be used to join two substrings

Slice operator can be used to split a string into substrings

lists

aka arrays

an ordered sequence of elements / values

boolean

can only represent two values: “true” and “false”

used by computers to make decisions inside if/then statements

“true” = execute next code segments

NOT operator

denoted by !

used to reverse what the condition evaluates to

condition is true: operator evaluates to false

condition is false: operator evaluates to true

AND operator

denoted by &&

used to combine two conditions (operator only evaluates if both conditions are met)

condition is true and false: false

condition is false and false: false

condition is true and true: true

OR operator

denoted by ||

operator will evaluate to true if one condition or the other is met

condition is true and false: true

condition is true and true: true

condition is false and false: false

nested conditionals

conditional statements found inside conditional statements

if/else statements

the code in the if statement is executed if the operator evaluates to true

if the operator evaluates to false, the code in the else statement is executed

element

an individual value in a list

each are assigned an index value (a number representing the order in which they are listed)

operations you can do using a list

accessing an element by index

assigning the a variable to a certain element within a list

assigning a value to an element outright

assigning the value of one element in the list to another

determine the length of a list

insert elements in a list

at a given index: increases the length of a list and shifts every index number after that element

to the end of a list: increases the length of a list and assigns a new index only to the new element(s)

removing elements from a list

decreases the length of the list and changes the index number of every element after the removal

looping through lists

used to transverse through a list (complete or partial)

assigns a variable to each element of a list, then the next statements are executed once for each assignment

filtering a list

creates a subset of elements from the original list

ex. linear search, binary search

linear search algorithm

aka sequential search algorithm

checks each value of a list in other until the desired result is found

binary search algorithm

starts in the middle of a data set and eliminates either half (including the middle value) based on what it is looking for

continues until the result is found or all values in the list have been checked

**list has to be in order

more efficient than linear search

procedures

aka methods, functions

a group of programming instructions

can reuse the same procedure without having to rewrite it

often require parameters

parameters

the input variables of a procedure

arguments

values passed into the procedure in place of parameters

return statements

specify what value should be outputted when a function is called

terminate the program and return control to the calling function

procedural abstraction

generalizes an action

a procedure is called to perform an action, then is finished

eliminates the need to write redundant code segments—improves readability

allow you to solve a large problem based on the solution to smaller subproblems

algorithm

a set of instructions used to accomplish a specific task or solve a problem

sequencing, selection, iteration

sequencing algorithm

consists of steps that are performed in order

selection algorithms

if/else statements

makes a decision based on criteria and a condition

allows the program to choose between different paths of execution

iteration algorithm

loops

the repetition of a set of instructions until a specific condition is met

allows programs to perform tasks repeatedly without having to write repetitive code

while loops

run repeatedly while a condition is met and end when that condition is no longer true

unsure how many times the code will run

n loops

loops that run a specified number of times (n)

know how many times the loop will run

for loops

aka repeat until condition loop

will continue to run until a specific condition is met

know how many times the loop will run

3 parts of a while loop

1. initializing counter variable i to 0

2. boolean expression: checks condition of a variable

   1. statment to increase or decrease the variable i++

infinite loops

loops that repeat indefinitely

the condition controlling the loop is always true or there is no condition

expressions

arithmetic operators: +, -, *, /

MOD operator: divides two values and returns the remainder

examples of existing algorithms

determining max/min

solving math problems

determining a robot’s path through a maze (route-finding algorithm)

compressing data

sorting a list

simulations

the process of creating a model or representation of a real world system or phenomenon on a computer

used to predict and plan

an example of abstraction

may include bias (based on what the creator chose to include) or be out of scale

problem vs. instance

problem: a task an algorithm is trying to solve

instance: a problem with a specific input

decision problems

aka a decidable problem

return a “yes” or “no”

optimization problem

wants the best answer

ex. finding the shortest path between two cities

algorithm efficiency

an estimate of how many computational resources an algorithm uses

power, memory, time, etc.

polynomial efficiency

an algorithm that has a time complexity that can be represented by a polynomial equation

the running time of the algorithm grows proportionally to some power of the input size

said to run at a reasonable amount of time

exponential efficiency

aka factorial efficiency

an algorithm whose running time grows exponentially to its input size

considered inefficient

heutistic

an approximate solution returned when a problem can’t be solved in a reasonable amount of time

undecidable problem

an algorithm that isn’t always capable of providing a correct “yes” or “no” answer

solvable in some cases, but no algorithm will solve it in all cases