Welcome to ITK 279: Algorithms and Data Structures
Fall, 2005
Grades on WebCT (login required)
| Week | Date | Reading Assignment for this class | Assignments due | Topic |
| 1 | 8/22/05 | None | None | Introduction |
| 8/24/05 | Read 1.1-1.4 | None | Review of Recursion | |
| 8/26/05 | Finish Chapter 1 |
Questionnaire |
Recursion Program Performance |
|
| 2 | 8/29/05 |
Read 2.1-2.3 |
Chapter 1, ex. 5, 6, and 8(a and b only) |
Algorithm Analysis |
| 8/31/05 | Finish Chapter 2 | None | Algorithm Analysis | |
| 9/2/05 | Read 3.1-3.2 |
Chapter 2, exs. 7, 11(a,c,d), 12 (a,c,d) |
List ADT Pointers |
|
| 3 | 9/5/05 | No Class | Labor Day | |
| 9/7/05 | No new reading | Chapter 3, ex. 1 | Dynamic Memory Management | |
| 9/9/05 | No new reading | None | Linked Lists | |
| 4 | 9/12/05 | 3.3 | See slides for last class for assignment | Linked Lists cont. Stacks |
| 9/14/05 | Finish chapter 3 | Chapter 3, exs. 2, 9 & 10 | Queues Intro to trees |
|
| 9/16/05 | Read 4.1-4.2, 4.6 | None | Trees | |
| 5 | 9/19/05 | Read 6.1-6.3 | Chapter 4, exs 1 & 2 | Tree Traversals Priority Queues |
| 9/21/05 | Read 6.4 | Chapter 4, ex 8 | Priority Queues cont. Sorting |
|
| 9/23/05 | Read 7.1-7.5 | Chapter 6, exs 2 and 3 | Sorting | |
| 6 | 9/26/05 | Read 7.6-7.7 | Chapter 7, ex 1 for insertion, selection, and bubble sorts Program 1 |
Sorting |
| 9/28/05 | Read 7.8-7.10 | Chapter 7, ex. 4, 11, 12 | Sorting | |
| 9/30/05 | No new reading | Chapter 7, ex 15, 19 | Sorting | |
| 7 | 10/3/05 | None | Exam 1 | |
| 10/5/05 | Read 4.3-4.4 | None | Binary Search Trees | |
| 10/7/05 | Read 4.5 |
Chapter 4, ex 9 |
AVL Trees Splay Trees |
|
| 8 | 10/10/05 | Read 4.7 | Chapter 4, ex 19 | B-Trees |
| 10/12/05 | Read 5.1-5.4 | Chapter 4, ex 27 | Hash tables | |
| 10/14/05 | Finish chapter 5 |
Paper 1
B-tree exercise from slides |
Hashing, cont. Extendible hashing |
|
| 9 | 10/17/05 | Read 8.1-8.3 | Chapter 5, ex 1 | Disjoint sets |
| 10/19/05 | Finish chapter 8 | None | ||
| 10/21/05 | Read 9.1-9.2 |
Chapter 5, ex 19 Prog 3 part 1 |
Disjoint sets cont. Graphs |
|
| 10 | 10/24/05 | Read 9.3 | Chapter 8, exs 1 and 2 | Topological Sort Shortest Paths |
| 10/26/05 | Read 9.4 | Chapter 9, ex 1 | Graphs cont. | |
| 10/28/05 | Read 9.5 | Chapter 9, ex. 5 and 7 Program 3 |
Network Flow Minimum Spanning Trees |
|
| 11 | 10/31/05 | Read 9.6 | Chapter 9, ex. 11 | Graph searching |
| 11/2/05 | Read 9.7 | Chapter 9, exs 15-16 | Exam Review NP-Complete problems |
|
| 11/4/05 | None | None | Exam | |
| 12 | 11/7/05 | None | Take home part of exam | NP-Complete problems |
| 11/9/05 | Read 10.1 | Topic paragraph | Greedy algorithms | |
| 11/11/05 | Read 10.2 | Chapter 10, ex. 3 | Greedy algorithms | |
| 13 | 11/14/05 | Read 10.3 | Chapter 10, ex. 10 | Divide and Conquer |
| 11/16/05 | None | Program 4 | Divide and Conquer, cont. Dynamic Programming |
|
| 11/18/05 | Read 10.4 | Chapter 10, ex. 28 | Dynamic Programming Random numbers |
|
| Thanksgiving Week | No school | |||
| 14 | 11/28/05 | Read 10.5 | Chapter 10, ex. 31 Ethics Exercise |
Skip lists Backtracking |
| 11/30/05 | Chapter 10, ex. 36 | Backtracking cont. | ||
| 12/02/05 | Research paper rough draft | Peer review | ||
| 15 | 12/05/05 | Read 12.2 | Chapter 10, ex. 43 | Red-black trees |
| 12/07/05 | Program 5 | |||
| 12/09/05 | Research Paper due |
Final Exam: Tuesday December 13 at 7:50 am.