runestone academy ap csp unit 5

procedural abstraction

organizing and encapsulating algorithms in named procedures that can then be invoked by name

parameter

\-input variable for a procedure

\-allows procedures to be generalized

\-enables procedures to be reused with a range of arguments (input values)

argument

specifies the value of a parameter when a procedure is called

function

procedure that returns a result

sequential (linear) search

\-algorithm that checks every element in a list from the start to the end to find the searched-for item

\-running time grows proportional to a __linear__ curve as N grows larger \[f(N) = N\]

binary search

\-algorithm that repeatedly divides a sorted list to narrow in on the searched-for item

\-starts at the middle to eliminate half of the data

\-running time grows proportional to a __logarithmic__ curve as N grows larger \[f(N) = log N\]

sorting algorithm

algorithm that puts a list in numerical or alphabetical order

comparison sort

algorithm that repeatedly compares 2 elements

radix (base) sort

algorithm that sorts numbers by their digits, placing them in each of their respective buckets

bubble sort

\-algorithm in which the highest value “bubbles” to the top after each pass

\-running time grows proportional to a __quadratic/squared__ curve as N grows larger (N^2)

merge sort

\-algorithm in which sorted piles are continuously made & merged together until there is 1 complete pile

\-running time grows proportional to an __N log N__ curve as N grows larger

\-uses more memory

bucket sort

\-algorithm that uses each element’s value to place it into its appropriate bucket

\-running time grows proportional to a __2N__ curve as N grows larger

\-uses more memory for the buckets

index

number or position of an element in a list

parallel lists

\-2 or more lists that are setup to correspond based on the index location of the data in the lists

\-allows the data in the lists to be processed

list traversal

loops used to visit every single item in a list

for each item in aList

\-variable item is assigned the value of each element of aList sequentially

\-code in block of statements is executed once for each assignment of item.

insert

adds a value into a list at index i, moving down all other items at & after i in the list.

length

evaluates to the number of elements in a given list

append

adds a value to the end of a list

remove

removes item at index i, moving up all items after the ith item

efficiency

how well an algorithm uses time & memory/space resources (CPU & RAM) for a given input (N)

correctness

whether or not an algorithm contains errors

clarity

how well an algorithm is expressed

worst case analysis

maximum number of guesses required to find or not find the target

reasonable time

\-polynomial time (N^2, 3, 4, etc.)

\-constant time

\-linear time

\-square time

\-cube time

unreasonable time

\-exponential time

\-factorial time

intractable problem

\-Problem that is impossible to solve within a reasonable amount of time

\-Algorithmic solutions are too inefficient/slow to solve it when its inputs grow large (requires exponential time/space to run)

\-Can be used as protection in cryptography & password protection

heuristic algorithm

\-Algorithm that finds an approximate solution for a hard problem

\-Helpful for finding a solution to an intractable problem in reasonable time

\-Produces a fast & often correct solution, but it cannot be proven optimal

decidable (decision) problem

problem in which an algorithm can be constructed to answer “yes” or “no” for all inputs

undecidable problem

\-problem in which no algorithm can be constructed that will always lead to a correct yes or no answer

Halting problem

\-Undecidable problem of whether a computer program will halt (produce an answer) or loop on a given input

\-Given an arbitrary (chance) computer program with an arbitrary input, decide whether it has an infinite loop

\-Undecidable problem proven by Alan Turing in the 1930’s

optimization problem

problem with the goal of finding the best (optimal) solution among many

Traveling Salesman Problem (TSP)

Given a list of cities & the distances between them, find the shortest path visiting each city once & returning to the start

dictionary attack

looks up the user’s password in a dictionary

brute force attack/search

\-tries every possible password

\-If there are M different letters & symbols used for a password, then for a password of length N, guessing it would take M^N guesses

sequential computing

\-computational model in which operations are performed one at a time on a processor or computer

\-takes as long as the sum of all of its steps

parallel computing

\-Computational model in which a problem or program is broken into smaller sequential operations that are performed in parallel

\-Usually on a computer with multiple processors

\-Takes as long as its sequential tasks (i.e. splitting up a deck of cards into 4 stacks) plus the longest of its parallel tasks (i.e. finding a card in parallel)

\-At some point, adding parallel portions will no longer meaningfully increase efficiency

distributed computing

\-Computational model in which multiple networked computers are used to run a program

\-Allows problems to be solved that could not be solved on a single computer (required processing time/storage needs)

\-Allows problems to be solved quicker than on a single computer.

speedup

\-Measured in the time it took to complete the task sequentially divided by the time it took to complete the task in parallel (parallel solutions)

syntax error

a character or string __incorrectly__ placed in the syntax of a sequence of characters, causing failure in execution

semantic error

bug in a program that causes it to operate incorrectly, producing unintended/undesired output

search engine

\-useful for efficiently finding information

\-can record & maintain a history of searches made by users

\-can use search history to suggest websites or targeted marketing.

Search Engine Optimization (SEO)

\-Seeks to improve how particular web pages rank within major search engines, intending to increase traffic to them

\-Tweaks their algorithms in order to see through disguises (fake legitimate results)

relevance

search engine’s job to provide results that match the intent of the query.

recall

\-The finding of all relevant documents

\-Total recall is unachievable, but it is unimportant

\-Degree of relevance always trumps level of recall, as users want to find a few good results, not all possible results.

PageRank (Google)

\-measure of the “importance” of each page that takes into account the external references to it

\-A page is judged more important if a lot of important pages link to it

cloaking

\-the deception of users/the presentation of different content to search engines than as displayed to users

CAPTCHA

\-type of challenge-response test used in computing to determine whether the user is human

\-purpose of preventing spam/bot raiding

spider (web crawler)

\-Software that crawls around the Web

\-Retrieves HTML text to index the information it contains

\-Creates Internet traffic, imposing a load on the web server

bot

program that endlessly performs some intrinsically repetitive task, often an information-gathering task.

visit

the downloading of a copy of every web page a spider visits

cache

\-The retainment of a copy after it has been indexed

\-Can still be accessed even if the original document has been deleted

\-Makes it possible for people to have information that no longer exists/a version older than the updated information.

Logo

\-programming language invented in the 1960s by Seymour Papert

\-used to draw simple and complex geometric shapes.