| G5 | Grimaldi, Discrete and Combinatorial Mathematics 5th Edition |
| W3 | Weiss, Data Structures & Problem solving using Java 3rd Edition |
| W4 | Weiss, Data Structures & Problem solving using Java 4th Edition |
| L2 | Levitin, The Design and Analysis of Algorithms 2nd Edition Of course I do not expect you to have obtained your background from this book, but for some of these topics it provides an additional reference |
| L3 | Levitin, The Design and Analysis of Algorithms 3nd Edition Of course I do not expect you to have obtained your background from this book, but for some of these topics it provides an additional reference |
| 230 |
http://www.rose-hulman.edu/class/csse/csse473/<CURRENT_TERM_NUMBER>/Resources/230-materials
CURRENT_TERM_NUMBER: Summer 2017 is 201740, Winter 2016-17 is 201720, clicking the above link should work for either. |
| 0 | Never heard of it |
| 1 | Heard of it; a vague idea of what it is or how it is used |
| 2 | Basic understanding of what it is about, knew the details once, could get them again if I look it up |
| 3 | Can use it to solve problems, write proofs, or build programs, whichever is appropriate for this topic |
| 4 | Very confident about my understanding and ability |
| 5 | Believe that I can explain it well to someone else who needs to learn it |
| * | We will discuss/review this topic in 473 |
| Level | Concept/tool/structure/algorithm/technique/etc. | G5 | W3 | W4 | L2 | L3 | 230 |
Other
(or comments on previous columns) |
|---|---|---|---|---|---|---|---|---|
| 3* |
Big O, big theta, big omega, little o: formal definitions and informal computations |
5.1, 5.4, 5.8 | 5.1, 5.4, 5.8 | 2.2 | 2.2 | |||
| 4 |
big-(O theta, Omega) analysis of straightforward algorithms with nested loops (typically by nested sums) |
5.2, 5.3, 5.6 | 5.2, 5.3, 5.6 | 2.3 | 2.3 | 05,06 | ||
| 3 |
Properties of logarithms, how logarithms enter into algorithm analysis |
5.5 | 5.5, 5.6 | A | A | |||
| 3 | Heuristic algorithm analysis | 5.7-5.8 | 5.7-5.8 | 2.6 | 2.6 | |||
| 4 | Divide-and conquer algorithm - what is it? | 7.5 | 7.5 | 4 | 4 | |||
| 4 * | Divide-and-conquer analysis: setting up the recurrence for particular algorithms | 7.5 | 7.5 | |||||
| 3 | Divide-and-conquer recurrences: understand proof of Master Theorem | 10.5 | 7.5 | 7.5 | 480-485 | 488-491 |
(Weiss's approach is simpler; you may want to start with that) |
|
| 2* | Divide-and-conquer: apply Master Theorem to specific a, b, k | 10.6 |
125,127, 137 |
|||||
| 2 | Lower bound for comparison-based sorting (via decision trees) | 12.2 | 8.8 | 8.8 | 11.2 | 21 | ||
| 2* | Derivation of average case of quicksort (recurrence solution) | 10.5 | 8.6.2 | 8.6.2 | ||||
| 4 |
Dynamic array expansion: Amortized analysis of "add one
element when needed" vs. "double the array size when needed" |
2.4.2, 2.4.3 | 2.4.2, 2.4.3 | 01,02 | ||||
| 3 | Mathematical Induction: Explain why it is a valid proof technique (based, e.g., on well-ordered property of the integers) | 4.1 | 7.2 | 7.2 | 02,03,04 | |||
| 3* | Mathematical Induction: Use it to prove properties of integers, algorithms, and simple data structures | 4.1, 4.5 | 7.2 | 7.2 | 02,03,04 | |||
| 5 | Sequential Search: Algorithm and analysis | 5.6.1 | 5.6.1 | |||||
| 5 | Binary search: Algorithm and analysis | 10.6 | 5.6.2 | 5.6.2 | 135-139 | 150-152 | ||
| 2* | Interpolation search: Algorithm | 5.6.3 | 5.6.3 | 5.6 | 161-163 | |||
| 5 | Insertion sort: Algorithm and analysis | 8.3 | 8.3 | 5.1 | 4.1 | |||
| 5 | Merge sort: Algorithm and worst-case analysis | 12.3 | 8.5 | 8.5 | 4.1 | 5.1 | ||
| 4 | Quicksort: Algorithm, best case & worst case analysis, pivot choices | 8.6 | 8.6 | 4.2 | 5.2 | 22,23 | ||
| 2* | Shell's sort: Algorithm (in the Weiss book, often not done in 230) | 8.4 | 8.4 | 164 | 138 | |||
| 4* | Heap sort; Algorithm and worst-case analysis | 21.5 | 21.5 | 6.4 | 6.4 | 24 | ||
| 5 |
Stack and queue implementations (sequential and linked), simple uses of each, runtime of operations |
16 | 16 | 1.4 | 1.4 | Not much detail in Levitin | ||
| 5 |
List implementations (sequential and linked), simple uses of each, runtime of operations |
15,17 | 15,17 | 1.4 | 1.4 | Not much detail in Levitin | ||
| 5 |
Binary tree implementation, algorithms for height and size, maximum and minimum height of a binary (or m-ary) tree with N nodes |
18 | 18 | 1.4 | 1.4 | 9 | ||
| 5 | Orderings of preorder, postorder, inorder, and level-order traversals of a binary tree | 18.4 | 18.4 | 4.3 | 5.3 | 10 | http://austingwalters.com/binary-trees-traversals-everyday-algorithms/ | |
| 4 | Code for preorder, postorder, inorder, and level-order traversals of a binary tree | 18.4 | 18.4 | 4.3 | 5.3 | 10 | ||
| 2 | Algorithms for stack-based preorder, inorder, postorder iterators (different than traversals) for binary trees | 18.4 | 18.4 | 10 | ||||
| 5 |
What is the difference between a traversal and an iterator?
Why can't the above iterators be recursive? |
18.4 | 18.4 | 10 | ||||
| 2 | Algorithm for queue-based level-order iterator for binary trees | 18.4 | 18.4 | 10 | ||||
| 5 | Definition of Binary search tree, BST search and insertion algorithm | 19.1 | 19.1 | 5.6 | 4.5 | 12 | not much detail in Levitin | |
| 3 | BST node deletion algorithm | 19.1 | 19.1 | 12 | ||||
| 2 | How to calculate average-case height for BST assuming random insertion order and no re-balancing | 10.5 | 19.3 | 19.3 | Weiss's explanation is excellent | |||
| 4 | Best-case and worst-case runtimes for BST insertion, deletion, search | 19.3 | 19.3 | 5.6 | 4.5 | not much detail in Levitin | ||
| 3* | Prove properties of Binary trees using Mathematical induction | p602 | 19.3 | 19.3 | 10,12 | |||
| 2 | Relationship between internal path length and external path length of a binary tree | 19.3 | 19.3 | 143 | 186 | |||
| 5 | AVL tree definition | 19.4 | 19.4 | 6.3 | 6.3 | |||
| 2 | How to derive worst-case height for AVL tree with N nodes | 19.4 | 19.3 | 6.3 | 6.3 | 16 | http://lcm.csa.iisc.ernet.in/dsa/node112.html | |
| 3 | AVL insertion and rebalancing algorithm | 19.4 | 19.4 | 6.3 | 6.3 | 16 | ||
| 2 | AVL deletion and rebalancing algorithm | 17 | http://neil.brown.name/blog/20041124141849 | |||||
| 3* | Priority queue: Representation of a binary heap by an array, insertion and removeMin, siftUp and siftDown. | 21.2 | 21.3 | 6.4 | 6.4 | 23 | ||
| 4* | Efficiency comparison of buildHeap vs. repeated insertion. | 6.4 | 6.4 | 23-24 | ||||
| 2 | Hash table basics: role of hash function, open addressing vs. chaining, clustering, run-times | 14.3 | 20.1-20.5 | 20.1-20.5 | 7.3 | 7.3 | 24-25 | |
| 2* | Backtracking: OO solution of non-attacking queens problem. (Used to be done in 230; not recently) | 7.7 | 12.1 | 12.1 | 14-15 | |||
| 2* |
Graph representations: Adjacency matrix vs. adjacency lists (No longer in 230); we'll do it "from scratch" |
1.4 | 14.1 | 14.1 | 1.4 | 1.4 | 26-27 | Levitin's coverage is shallow |
| 2 | depth-first search and breadth-first search, similarity to which tree traversals? | 12.2 | 14.2 | 14.2 | 5.2 | 3.5 | 27 | |
| 2 | Simple approaches to solving Recurrence relations | 10 | 7.5.2,7.5.3 | 7.5.2,7.5.3 | B | B | 19-21 |