Welcome to ITK 279: Algorithms and Data Structures
Spring, 2009
Blackboard Course Site for Grades, Assignment Submission and Other Stuff (login required)
Instructions for Using Exceed on Demand
Accessing the Suns without Exceed
| Week | Date | Reading Assignment for this class | Assignments due | Topic |
| 1 | 1/12 | None | None | Introduction |
| 1/14 | Skim Savitch, chs. 1-3 | None | C++ | |
| 1/16 | Skim Savitch, chs 4-6 |
Email |
C++, cont. | |
| 2 | 1/19 | None | None | MLK Day - No class |
| 1/21 | Skim Savitch, chs 7 and 9 Read Savitch, 11.1 |
C++ practice 1 | Classes | |
| 1/23 | Read Savitch, ch. 8 | C++ practice 2 | Strings Operator Overloading |
|
| 3 | 1/26 | Read Savitch, ch. 10 | C++ practice 3 | Pointers Dynamic Memory |
| 1/28 | Read Savitch, ch. 12 | C++ practice 4 |
Dynamic Classes Files |
|
| 1/30 | Read Weiss, ch. 1 | None |
Files Recursion |
|
| 4 | 2/2 | Read Weiss, ch. 2 | C++ practice 5 | Algorithm Analysis |
| 2/4 | Read Weiss, ch. 3, 1-5 | Recursion homework described on Blackboard in Notes and Homework | Algorithm Analysis, cont. List review |
|
| 2/6 | Finish Weiss, ch. 3 | Weiss chapter 2, exercises 7, 11 (a,c,d), 12 (a,c,d) | List review cont. Stack and Queue review |
|
| 5 | 2/9 | Read Weiss, 4.1-4.2 | List practice homework described on Blackboard in Notes and Homework | Stack and Queue Review Trees |
| 2/11 | Read Weiss, 4.6 | Weiss chapter 3, exercises 4-5 | Traversals | |
| 2/13 | Read Weiss, 6.1-6.3 | Weiss chapter 4, exercises 1-2 | Priority Queues | |
| 6 | 2/16 | Read Weiss, 6.4 | Weiss, chapter 4, exercise 8 | Heaps |
| 2/18 | Read Weiss, 7.1-7.3 | Weiss, chapter 6, exercises 2-3 (do 3 only for 2a) | Elementary sorting Shellsort |
|
| 2/20 | Read Weiss, 7.4-7.5 | Program 1 - Data Structures review | Heap sort Merge sort |
|
| 7 | 2/23 | Read Weiss, 7.6-7.8 | Elementary sorting homework described on Blackboard in Notes and Homework Weiss, chapter 7, exercise 4 |
Quicksort |
| 2/25 | Finish Weiss, chapter 7 | Weiss, chapter 7, exercises 11, 12, 15 |
Bin sort External sorting |
|
| 2/27 | None | None | Exam 1 | |
| 8 | 3/2 | Weiss, 4.3-4.4 | Quicksort homework described on Blackboard in Notes and Homework | Binary Search Trees |
| 3/4 | Weiss, 4.5 | Weiss chapter 4, exercise 9 POSTPONED |
Binary Search Trees AVL Trees |
|
| 3/6 | Finish Weiss, chapter 4 |
Weiss, chapter 4, exercise 9 (postponed from Wednesday) Program 2 - Sorting |
Splay Trees | |
| Spring Break | ||||
| 9 | 3/16 | Weiss, 5.1-5.4 | Weiss, chapter 4, exercises 19 and 27 | B+ Trees Hashing |
| 3/18 | Finish Weiss, chapter 5 | B+ tree exercise described on Blackboard in Notes and Homework | Hashing | |
| 3/20 | None | Paper 1 - Timing | Hashing | |
| 10 | 3/23 | Weiss, chapter 8 | Chapter 5, exs 1 | Extendible Hashing Disjoint Sets |
| 3/25 | Weiss, 9.1 | Chapter 5, ex. 19 | Disjoint Sets, cont. Graph introduction |
|
| 3/27 | Weiss, 9.2-9.3 | Program 3, part a | Topological sort Shortest paths |
|
| 11 | 3/30 | Weiss, 9.4 | Chapter 8, exs. 1-2 | Shortest paths Network flow |
| 4/1 | Weiss, 9.5 |
Chapter 9, exs. 1-2 |
All shortest paths Minimum Spanning Trees |
|
| 4/3 | Weiss, 9.6 | Program 3 - Dictionaries | Applications of searching | |
| 12 | 4/6 | Weiss, 9.7 | Chapter 9, ex. 5, 7a Research paper topic |
NP |
| 4/8 | No reading | Chapter 9, exs. 11, 15-16 |
Review NP, cont. |
|
| 4/10 | None | None | Exam 2 | |
| 13 | 4/13 | Weiss, 10.1 | Greedy algorithms | |
| 4/15 | Weiss, 10.2 | Exam 2 takehome | Huffman code Bin packing |
|
| 4/17 | Weiss, 10.3 |
Chapter 10, exercise 3 Program 4 - graphs |
Bin packing cont. Divide and conquer Dynamic Programming |
|
| 14 | 4/20 | Weiss, 10.4 | Chapter 10, exercise 10 | Dynamic Programming Random numbers Skip lists |
| 4/22 | Weiss, 10.5 | Chapter 10, exercise 28 | Random numbers Skip lists |
|
| 4/24 | None | Rough draft | Peer review | |
| 15 | 4/27 | Weiss, 12.2 | Chapter 10, exercise 31 Ethics exercise |
Backtracking |
| 4/29 | None | Program 5 - greedy algorithms | Alpha-beta pruning Red black trees Review |
|
| 5/1 | None | Chapter 10, exercise 43 Research paper |
Wrap-up |