Background material for MA/CSSE 473
(Under Construction: Your suggested sources are welcome)

Key to sources:
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
230 http://www.rose-hulman.edu/class/csse/csse473/<CURRENT_TERM_NUMBER>/Resources/230-materials
CURRENT_TERM_NUMBER:  Summer 2010 is 201040, Fall 2010 is 201110, clicking the above link should work for either.

Key to expected levels of understanding after taking CSSE 230 and MA 375 :
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

Background topics and sources of info:
Level Concept/tool/structure/algorithm/technique/etc. G5 W3 W4 L2 230 Other
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  
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 05,06  
3 Properties of logarithms, how
logarithms enter into algorithm analysis		   5.5 5.5, 5.6   A    
3  Heuristic algorithm analysis   5.7-5.8 5.7-5.8 2.6    
4 Divide-and conquer algorithm - what is it?   7.5 7.5  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     
2 Divide-and-conquer: apply Master Theorem to specifc 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 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      
2  Interpolation search: Algorithm   5.6.3  5.6.3    5.6    
5 Insertion sort: Algorithm and analysis     8.3   8.3   5.1    
5 Merge sort: Algorithm and worst-case analysis   12.3   8.5   8.5   4.1    
4 Quicksort: Algorithm, best case & worst case analysis,
pivot chouiices		     8.6  8.6   4.2 22-23  
2 Shell's sort: Algorithm     8.4   8.4   164    
4  Heap sort; Algorithm and worst-case analysis   21.5   21.5   6.4 24  
5 Stack and queue implementations (sequential
and linked), simple uses of each, runtime of operations		   16   16     CSSE 220 
5 List implementations (sequential
and linked), simple uses of each, runtime of operations		   15,17  15,17     CSSE 220
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   4.4 9  
5 Orderings of preorder, postorder, inorder, and level-order traversals of a binary tree   18.4  18.4 4.3 10  http://nova.umuc.edu/~jarc/idsv/lesson1.html
4 Code for preorder, postorder, inorder, and level-order traversals of a binary tree    18.4 18.4   10  
2 Algorithms for stack-based preorder, inorder, postorder iterators 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 levelorder 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  12  
3 BST node deletion algorithm   19.1 19.1 5.6 12  
2 How to get average-case height for BST< assuming random insertion order and no re-balancing 10.5 19.3 19.3      
4 Best-case and worst-case runtimes for BST insertion, deletion, search   19.3 19.3      
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    
5 AVL tree defintion   19.4 19.4      
2 How to derive worst-case height for AVL tree with N nodes   19.4 19.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 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 23  
4 Efficiency comparison of buildHeap vs. repeated insertion.       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 24-25  
2 Backtracking:  OO solution of non-attacking queens problem.   7.7   12.1 14-15  
2 Graph representations: Adjacency matrix vs. adjacency lists 1.4 14.1 14.1   26-27  
2 depth-first search and breadth-first search, similarity to which tree traversals? 12.2 14.2 14.2 5.2 27  
3 Huffman codes for data compression: Analyzing input and building the tree 12.4 12.1 12.1 9.4 25  
2 Huffman codes: Using the tree to build table and encode data 12.4 12.1 12.1 9.4 25-26  
2 Approaches to solving Recurrence relations 10 7.5.2,7.5.3 7.5.2,7.5.3 B 19-21