CS Test 1
Terms
undefined, object
copy deck
-
"While" Statement
-
While ("a true/false condition") do step i to step j
-
Algorithm Discovery
-
Finding a solution to a given problem.
- Approximation Algorithm
- Algorithm that doesn't solve the problem, but provides a close approximation to the solution.
- Best Case
- Requiring the least work.
- Computation
-
Set the value of "variable" to "arithmetic expression."
-
Computing Agent
- The machine, robot, person, or thing carrying out the steps of the algorithm.
-
Conditional Operation
-
These are the "question-asking" instructions of an algorithm. They ask a question, and the next operation is selected on the basis of the answer to that question.
-
Continuation Condition
-
The "true/false condition" in a "while" statement.
-
Control Operations
- Conditional and iterative operations used together. Allow us to alter the normal sequential flow of control in an algorithm.
-
Definition of an Algorithm
-
A well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.
-
Definition of Computer Science
-
The study of algorithm, including
- Their formal and mathematic properties
- Their hardware realizations
- Their linguistic realizations
- Their applications
-
Do/While Statement
-
Do
Operation
. . .
While ("a true/false condition")
-
Effectively Computable
-
There exists a computational process that allows the computing agent to complete the operation successfully.
- Efficiency
-
An algorithm's careful use of resources.
-
Exponential Algorithm
-
Theta(2totheN)
Hamiltonian circuit
- If/Then/Else
-
If "a true/false condition" is true then
first set of algorithmic operations
Else (or otherwise)
second set of algorithmic operations
-
Infinite Loop
- An algorithm that makes no provision to terminate.
- Input
-
Submits to the computing agent data values from the outside world that it may then use in later instructions.
Get values for "variable," "variable," . . .
- Intractable
-
Problem is solvable, but the solution algorithms all requrie so much work as to be virtually useless.
-
Iterative Operations
-
The "looping" instructions of an algorithm. They tell us not to go on to the next instruction but, instead, to go back and repeat the execution of a previous block of instructions.
- Loop
-
The repetition of a block of instructions.
-
Loop Body
-
The block of operations executed in a "while" statement while the continuation condition is satisfied.
-
Natural Language
-
The language we speak and write in our everyday lives.
-
Order of Magnitude
-
Anything that varies as a constant times n.
- Output
-
Sends results from the computing agent to the outside world.
Print the values of "variable," variable," . . .
-
Posttest Loop
-
The continuation condition is tested at the end of each pass through the loop. Expressed using the "Do/While" statement.
-
Pretest Loop
-
The continuation condition is tested at the beginning of each pass through the loop, and therefore it is possible for the loop body never to be executed.
- Primitive
- An unambiguous operation in an algorithm. An algorithm must be composed entirely of primitives.
- Pseudocode
-
A set of English language constructs designed to resemble statements in a programming language but that do not actually run on a computer.
-
Sequential Operation
-
A set of sequential instructions that carry out a single well-defined task. When that task is finished, the algorithm moves on to the next operation.
-
Sequential Search
-
The standard algorithm for searching an unordered list of values.
-
Straight-Line Algorithm
-
Executes its instructions in a straight line from top to bottom and then stops.
-
The Three Basic Sequential Operations
-
- computation
- input
- output
- Theta(lgn)
-
Binary Search
- Theta(n)
-
Sequential Search
- Theta(nsquared)
-
Selection Sort
-
Two Criteria for Operations used in an Algorithm
-
- They must be unambiguous
- They must be effectively computable
-
Unambiguous Operation
-
An operation that can be understood and carried out directly by the computing agent without further simplification or explanation.
-
Unsolvable Problem
-
A problem for which no generalized algorithmic solution can possibly exist.
- Variable
-
A named storage location that can hold a data value.
- Why are formal algorithms so important in computer science?
-
If we can specify an algorithm to solve a problem, then we can automate its solution.
-
Worst Case
-
Requiring the most work.