Handouts:
Labs:
Assignment |
Exercises | Due Date |
Hwk 1 |
1.1 #4, 8; 1.2 #4, 9; 1.3 #1, 3, 4 | 1-17-11 |
Hwk 2 |
2.1 #5, 8, 9; 2.2 #2, 3 (without proof), 4a, 5, 6b | 1-24-11 |
Lab 3 |
Util (readstring, readnum) | 1-26-11 |
Hwk 3 |
2.3 #1, 2, 4, 5, 9; 2.4 #1 (exact & Q), 2, 4, 7 | 2-2-11 |
Lab 4 |
StringSort (selection, bubble) | 2-2-11 |
Lab 5 |
StringSort (merge) | 2-9-11 |
Hwk 4 |
3.1 #1, 2, 5, 6, 9bc, 10; 3.2 #5 | 2-11-11 |
Lab 6 |
Word Find | 2-18-11 |
Hwk 5 |
4.1 #1, 3, 5, 6, 7; 4.3 #1ab, 4; 4.4 #1, 4, 5 | 2-21-11 |
Lab 7 |
Binary Trees | 2-23-11 |
Hwk 6 |
5.1 #3, 4, 9; 5.2 #1, 2, 4, 6, 7; 5.4 #1, 2b Note: On 5.4 #1, also answer, using scientific notation base 10, the following questions for a set S of size 25: (i) How many permutations are there on the elements of S? (ii) How many subsets are there of S? (iii) Let P be the set of all permutations of S. How many subsets are there of P? |
3-7-11 |
Lab 8 |
Permuatations (Johnson-Trotter) | 3-9-11 |
Lab 9 |
Heaps I | 3-16-11 |
Hwk 7 |
5.5 #1, 2, 3, 4, 5, 6; 6.1 #2, 3, 5, 6 |
3-18-11 |
Lab 10 |
Heaps II | 3-30-11 |
Hwk 8 |
8.1 #2a, 4ab, 5a, 8; 9.1 #7; 9.2 #1, 2 (justify!); 9.4 #1, 3, 4 |
4-15-11 |
Exam 1 material:
1.1 What is an algorithm?
1.2 Fundamentals of algorithmic problem-solving
1.3 Important problem types
2.1 Analysis framework
2.2 Asymptotic notations and basic efficiency classes
lab 1 Java crash course
2.3 Mathematical analysis of non-recursive algorithms
lab 2 Quadratic class
lab 3 Keyboard input in Java
2.4 Mathematical analysis of recursive algorithms
Exam 2 material:
lab 4 Selection sort and bubble sort
3.1 Selection sort and bubble sort
3.2 Sequential search and brute-force string matching
4.1 Mergesort
lab 5 Mergesort
4.3 Binary search
lab 6 WordFind
4.4 Binary tree traversals and related properties
lab 7 Binary Tree algorithms
5.1 Insertion sort
5.2 Depth-first search and breadth-first search
5.4 Algorithms for generating combinatorial objects
lab 8 Generating permutations (Johnson-Trotter)
************* Exam 2 scheduled for Thursday March 10th ************
Exam 3 material:
5.5 Decrease-by-a-constant-factor algorithms
lab 9 Russian peasant multiplication
lab 10 Graph algorithms
6.1 Presorting
6.4 Heaps and heapsort
lab 11 Heaps
7.1 Sorting by counting
Exam 4 material:
lab 12 Binomial coefficients
8.1 Computing a binomial coefficient
9.1 Prim's algorithm
9.2 Kruskal's algorithm
9.4 Huffman trees
11.1 Lower-bound arguments
11.2 Decision trees
11.3 P, NP, and NP-complete problems