COMP SCI PRINCIPLES UNIT 5 VOCABULARY

append

adds a value to the end of a list

insert

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

parameters

input variables for a procedure

arguments

specify the values of the parameters when a procedure is called

length

the number of elements currently in a given list

index

the number or position of an element in the list

parallel lists

two or more lists that are setup to correspond based on the index location of the data in the lists allowing the data in the lists to be processed at the same time

binary search

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

distributed computing

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

instance of a problem

includes specific input; for example, sorting is a problem, and sorting the list (2, 3, 1, 7) is…

parallel computing

a computational model where a problem or a program is broken into multiple smaller sequential computing operations some of which are performed simultaneously in parallel (usually one on computer with multiple processors but it could also use multiple computers)

sorting algorithm

an algorithm that puts a list into alphabetic or numeric order

unreasonable time

exponential time

decidable problems

problems in which an algorithm can be constructed to answer ‘yes’ or ‘no’ for all inputs (ex. “is the number even?”)

efficiency

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

linear/sequential search

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

reasonable time

polynomial time

speedup

for a parallel solution it 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

decision problem

a problem that has a yes or no answer

heuristic algorithm

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

optimization problem

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

sequential computing

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

undecidable problems

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

brute force

solved by trial and error; trying every possible option

more efficient

usually means it runs faster or uses less space

intractable

a computational problem can be this if the only known way to solve the problem depends on an exponential algorithm

intractable problems

problem that are practically impossible to solve in a reasonable time; there are known algorithmic solutions, but the algorithms are too inefficient to solve the problem when the number of inputs grow large

The Halting Problem

the undecidable problem of determining whether a computer program will halt (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