Unit 5 - Algorithms & Procedural Abstraction

arguments

specify the values of the parameters when a procedure is called.

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

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

intractable problems

practically impossible to solve in a

linear or sequential search

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

parallel computing

a computational model where a problem or program is broken into multiple smaller sequential computing operations some of which are performed 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

sequential computing

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

sorting algorithm

puts a list into alphabetic or numeric order.

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

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.

undecidable problems

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