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

decidable problems

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

decision problem

a problem that has a yes or no answer

distributed computing

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

efficiency

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

heuristic algorithm

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

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.

intractable problems

practically impossible to solve in a <b

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.

more efficient

this usually means it runs faster or uses less space.

optimization problem

the goal of finding the best solution among many

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

unreasonable time

exponential time