Big-O, Big-Theta,
Big-Omega
What is the meaning of them?
What are the definitions?
What are the meanings of the parameters in the definitions?
Basic operational Unit, what are its criteria?
Best case, worst case, average case
Iterative Algorithm
How to identify from pseudo code?
What is initial step? A sum, more properly called a series.
How to solve the series? Basic series: series of constant, series of linear sequence
Recursive Algorithm
How to identify from pseudo code?
What is initial step? Write the recursive formula. Do not forget IC.
How to solve the recursive formula?
Backward substitution
Variable substitution and Smoothness rule
Masters Theorem
Not much interesting, except interesting problems
String Matching
Closest-Pair and Convex-Hull
Knapsack and Assignment
What is the algorithmic technique?
Merge Sort
What is the technique? What is the merge?
What is the basic operation? What is the cost? How to
determine it?
Quick Sort
What is the technique? What is the partitioning?
What is the basic operation? What is the cost? How to
determine it?
Binary Search
What is the technique? Why must it use an Array?
What is the basic operation? What is the cost? How to
determine it?
Binary Tree
What algorithm did we discuss? Height.
What kind of algorithm?
What is the basic operation? Why?
How did we solve? Counted internals and externals. What is the relationship?
Closest-Pair
What is the basic algorithm? How did it get started?
What is the important to check and show?
Any other important details?
What is the recursive formula? T(n) = 2T(n/2) + M(n)
Convex-Hull
What is the basic algorithm? How did it get started?
What did it look for? Pmax
What are the different regions?
What is the cost?
How is this different from divide and conquer algorithms?
Insertion Sort
What is the basic algorithm?
What is the cost?
When to use?
Depth First Search,
Breath First Search
What kind of algorthms?
Topological Sort
What kind of graphs?
What is it?
What are the algorithms? There are two.
Generating
Permutations
Why generate permutations?
What algorithms? There are two.
What is the problem with bottom up?
What is the general technique of Johnson Trotter?
What annotation and definition does it use?
Selection Problem
What is the k-th satistics?
What is the basic algorithm? What algorithm is it similar to?
What is the trick?
What is the cost?
What part of the problem can we transform? The instance, the data structure, problem
Presorting
What is the technique? What is typically the cost?
How to compute the mode?
What is the basic Algorithm?
Can it be done in place?
What is the cost?
What is it for?
What is the cost difference?
What is it?
What is this concept?
Funny that memory is more constrained then processor hardware.
Horspool's Algorthim
For what problem?
What is the space? The shift table
What is the basis of the Algorthim?
How does the shift table work?
What is the cost of constructing the shift table?
What is the worst case cost?
Boyer-Moore Algorthim
For what problem?
What is the space? The shift tables
What is the basis of the Algorthim?
What are the shift tables?
How due they differ from Horspool's
What is the cost of constructing the shift table?
What is the worst case cost?
Not part of the mid semester exam
1. Definitions, Theorems and Formulas
2. Determine Cost
3. Illustrate algorithms
4. Create Algorithms
An analysis by problem type
These are more or less rote problems.
What are the important Definitions, Theorems and Formulas?
Naturally this comes from the Analysis of Algorithm Efficiency
What algorithm?
Closest Pair
Convex hull
Sorts
DFS, BFS
Topological Sorting
Selection
Johnson Trotter
Bottom-up Heap construction
Horspool
Boyer-Moore
No suggestions, but if you have done the home work it should not be to difficult.