Invitation to Computer Science Ch.1,2,3

algorithm

a set of steps that describe how to perform a task

the formal criteria for a true algorithm

well-ordered, unambiguous, effectively computable, produces a result when executed, halts in a finite amount of time

computer science

the study of algorithms, including their formal and mathematical properties, their hardware and linguistic realizations, and their applications

computing agent

the machine, the robot, the person, or thing carrying out the steps of an algorithm

conditional operation

an operation that chooses between multiple actions based on some specified criteria

effectively computable operation

an operation that a given computing agent can perform, often called a primitive operation

infinite loop

a loop that does not terminate

iterative operation

an operation that specifies that a particular set of operations can be repeated multiple times

primitive operation

an operation that a given computing agent can perform

sequential operation

an operation that performs some calculation and exists in a sequence with other operations in describing an algorithm

unambiguous operation

an operation that has only one meaning, and therefore is well-understood

abstraction

the ability to separate the high-level view of an entity from the low-level details; a central intellectual tool in computer science

algorithm discovery

creating an algorithmic solution to a given problem

computation

a sequential operation that calculates some value and saves the result

control operations

operations used in an algorithm that alter the top-to-bottom flow of control; usually, conditional and iterative operations

formal programming language

a restrictive language used to describe an algorithm in terms that a computer can execute

infinite loop

a loop where the continuation condition never becomes false

input

a sequential operation for receiving data from the outside world

loop

the repetition of a block of instructions

natural language

a language that is spoken and/or written by people in everyday life; e.g., English

output

a sequential operation for presenting results to the outside world

pattern matching

the problem of finding one pattern within a larger string

post-test loop

a loop in which the continuation condition is tested at the end of each pass through the loop (ex. repeat...until or do...while)

pretest loop

a loop in which the continuation condition is tested at the beginning of each pass through the loop (ex. while...)

primitive operation

the instructions we assume the computing agent for an algorithm understands and can execute

pseudocode

a notation for describing algorithms that lies between a formal program and plain natural language; typically, is highly structured and uses well-understood and computable statements

sequential algorithm

an algorithm that contains only sequential operations so that it is executed from top to bottom without any choice points or loops (a.k.a. straight-line algorithm)

sequential search

the algorithm for searching an unordered collection of data for a particular value

top-down design

the process of viewing an operation at a high level of abstraction, then later filing in the details required to implement the high-level operation

variable

a named location for storing data values

analysis of algorithms

the process of determining the time and space efficiency of an algorithm, resulting in a function described with ? notation

approximation algorithm

a solution to a possibly intractable problem that is not guaranteed to give the best answer, but gives a good approximation to the best answer, in a tractable amount of time

benchmarking

the process of timing an algorithm on a particular machine and system in order to determine how it performs; this process is usually used to evaluate a machine and system, rather than a particular algorithm

best case

for a particular size of input, the least work an algorithm could do, based on the configuration of the input values

binary search algorithm

an algorithm that searches for a particular value in a sorted list of values, running in ?(lg n) time in the worst case

brute force algorithm

an algorithm that tries all possible solutions in order to find the optimal solution

correctness

an attribute of an algorithm that says that it solves the correct problem in the correct way

ease of understanding

an attribute of an algorithm that describes how easy it is to understand and modify the algorithm

efficiency

an attribute of an algorithm that captures the time and space requirements of the algorithm

elegance

an attribute of an algorithm that captures the cleverness and sophistication of the algorithm

exponential algorithm

an algorithm that runs in ?(2?) or worse

Hamiltonian circuit

a graph problem that is probably intractable: the task is to find a path through the graph that visits each node in the graph once and returns to the start node

bin-packing problem

a difficult, probably intractable problem: given a list of objects and some bins, the task is to find the minimum number of bins required to contain the objects

intractable

a description of a problem or algorithm where the best known performance is ?(2?)

order of magnitude

the general form of the curve that a particular function exhibits, for instance, linear, quadratic, polynomial, or exponential

polynomially bounded

a problem that has a known polynomial time algorithm

program maintenance

the task of maintaining and updating a piece of software once it has been created and released for public use

searching

the problem of finding a particular value in a list of values

selection sort algorithm

an algorithm for sorting a collection of values that repeatedly finds the largest values in the unsorted section of the list and moves them into the correct position

sorting

the problem of ordering a collection of values into some specified order: alphabetic, numeric, etc

worst case

for a particular size of input, the most work an algorithm might have to do, based on the configuration of the input values