Unit 5 - Algorithms & Procedural Abstraction

From the Mobile CSP team and MIT App Inventor. Link to original: https://quizlet.com/634707564/unit-5-algorithms-procedural-abstraction-flash-cards/

binary search

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

brute force

solve by trial and error; trying every possible option

decidable problems

problems in which an algorithm can be constructed to answer 'yes' or 'no' for all inputs (e.g., 'is the number even?').

distributed computing

a computational model in which multiple networked computers are used to run a program

heuristic algorithm

finds an approximate solution for a hard problem; helpful for finding a solution in a reasonable amount of time

decision problem

a problem that has a yes or no answer

efficiency

how well an algorithm uses time and memory/space resources, CPU and RAM.

intractable problems

practically impossible to solve in a reasonable time (<b)

instance of a problem

includes specific input. For example, sorting is a problem, and sorting the list (2,3,1,7) is an instance of the problem.

more efficient

this usually means it runs faster or uses less space.

linear or sequential search

an algorithm that checks every element in a list from the start to the end of the list to find an item.

optimization problem

the goal of finding the best solution among many

parallel computing

a computational model where a program is broken into smaller sequential computing operations, some which can perform simultaneously in parallel. This is usually on one computer with multiple processors, but it could also use multiple computers.

parameters

are input variables for a procedure.

reasonable time

polynomial time

sorting algorithm

puts a list into alphabetic or numeric order.

sequential computing

a computational model in which operations are performed in order, one at a time on one processor or computer

The Halting Problem

The undecidable problem of determining whether a computer program will produce an answer at some point or loop forever on a given input

The Traveling Salesman Problem

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

speedup

For a parallel solution, this is measured in the time it took to complete the task sequentially divided by the time it took to complete the task when done in parallel

undecidable problems

have no algorithm that can be constructed that always leads to a correct yes-or-no answer

unreasonable time

exponential time that increases (as more items get added in a list)

append

adds a value to the end of the list

arguments

a function that specifies the values of the parameters when a procedure is called

index

the number or position of an element in the list.

parallel lists

Two or more lists that correspond based on their index locations of data, allowing the data to be processed simultaneously

length

the number of elements currently in a given list

insert

adds a value into a list at a certain index, moving down all other items at and after the given index.