Chapter 2 Flashcards
What is involved in the process of program development?
Problem description
- Input
- Result (output)
Algorithm
- Pseudocode is fine
Program
- Java, C, Python
Machine instructions (executable)
How is pseudocode created?
It’s created from using components of natural language to express algorithms
- Pseudocode = “Not real” Code
What are some issues with using natural language to represent algorithms?
- Natural language can be extremely verbose
- Lack of structure makes it difficult to locate specific sections of the algorithm
- Natural language is too “rich” in interpretation and meaning
- Not sufficiently precise to represnt algorithms
Why is using pseudocode beneficial?
- Used to design and represent algorithms
- A compromise between the two extremes of natural and formal languages
- Will not be unique
Define:
Sequential Algorithm
Sometimes called a straight-line algorithm; the order is followed in a linear fashion.
Define:
Control Operations
- Conditional and iterative
- Allow us to alter the normal sequential flow of control in an algorithm
Define:
Conditional Statements
- The “question-asking” operations of an algorithm
- If/then/else
Define:
Loop
- The repetition of a block of instructions
- While or For loop statement
Define:
Continuation Condition
Determines if statement is true or false
- if/elif statements
Give an example of a loop.
Define:
Pretest Loop
Continuation condition is tested at the beginning of each pass through the loop
Define:
Posttest Loop
Continuation condition is tested at the end of the loop body, not the beginning.
Define:
Primitives
Instructions that computing agent understands and is capable of executing without further explanation.
Define:
Pattern Matching
- Process of searching for a special pattern of symbols within a larger collection of information.
- Is assisting microbiologist and geneticists studying and mapping the human genome.
Give examples of higher-level constructs.
- Sort the entire list into ascending order.
- Attempt to match the entire pattern against the text.
- Find a root of the equation.
Define:
Abstraction
Use of high-level instructions during the design process
Define:
Top-down Design
Viewing an operation at a high level of abstraction
How to test efficiency of algorithms?
Run Time Analysis
- Worst Case
- Average Case
Big Oh
- Constant run time O(1)
- Logarithmic run time O(logn)
- Linear run time O(n)
- Linearithmic run time O(nlogn)
- Quadratic run time O(n2)
How to test efficiency of direct sequecing algorithms?
For a sequence of instructions, the cost of executing the sequence of instructions is, asymptotically speaking, the same as the maximum cost of the individual instructions.
For three instructions a, b and c:
- O({a, b, c}) = max (O(a), O(b), O(c))
where {a, b, c} represents direct sequencing of the three individual instructions.
How to test effeciency for conditional execution algorithms?
For a conditional statement, the cost of execution is the maximum of the cost of evaluating the condition and the cost(s) of the alternate instruction sequences
- O(if {condition} then {sequence1} else {sequence2}) = max (O(condition), O(sequence1), O(sequence2))
How to test the effeciency of iterative construct algorithms?
Applies to an iterative construct ( e.g., loop, for, while) that will cause the execution of a subset of instructions to be repeated a specified number of times.
The trick is to understand how many times the instructions will be repeated.
For k iterations, the general rule is:
- O(loop (k) {sequence}) = O(k*sequence)
