specify the values of the parameters when a procedure is called.
New cards
2
binary search
a search algorithm that repeatedly divides a sorted list to narrow in on the searched-for item
New cards
3
brute force
solve by trial and error; trying every possible option
New cards
4
decidable problems
problems in which an algorithm can be constructed to answer 'yes' or 'no' for all inputs (e.g., 'is the number even?').
New cards
5
decision problem
a problem that has a yes or no answer
New cards
6
distributed computing
a computational model in which multiple networked computers are used to run a program
New cards
7
efficiency
how well an algorithm uses time and memory/space resources, CPU and RAM.
New cards
8
heuristic algorithm
finds an approximate solution for a hard problem; helpful for finding a solution in a reasonable amount of time
New cards
9
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.
New cards
10
intractable problems
practically impossible to solve in a
New cards
11
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.
New cards
12
more efficient
this usually means it runs faster or uses less space.
New cards
13
optimization problem
the goal of finding the best solution among many
New cards
14
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
New cards
15
parameters
are input variables for a procedure.
New cards
16
reasonable time
polynomial time
New cards
17
sequential computing
a computational model in which operations are performed in order, one at a time on one processor or computer
New cards
18
sorting algorithm
puts a list into alphabetic or numeric order.
New cards
19
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
New cards
20
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
New cards
21
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.
New cards
22
undecidable problems
have no algorithm that can be constructed that always leads to a correct yes-or-no answer
Studied by 6 people
