A systematic study of algorithms and their complexity, including searching and sorting algorithms, mathematical algorithms, scheduling algorithms, tree and graph traversal algorithms, P, NP, NP-complete and intractable problems.
This course satisfies both the critical thinking and the quantitative reasoning requirements.
Homework 2: Written assignment on recurrences from the text: 4.1-1, 4.1-6, 4.2-1, 4.3-1
Due Monday 13 February at 1:20 p.m.
Homework 3 - Due Wednesday 1 March
Homework 4 - Due Wednesday 29 March
Homework 5 - Due Monday 24 April
Instructor: Karen T. Sutherland
Office: Sverdrup 203E
Email: suther@navigation.augsburg.edu
Phone: 612-330-1341
Office Hours: M,W,F 12:00 - 13:00; T,Th 14:00 - 15:00 or by appt.
Text:
T. Corman, C. Leiserson, R. Rivest & C. Stein
Introduction to Algorithms,, 2nd Edition, McGraw Hill.
Requirements:
| Assignments: | 1/4 | Midterm exam: | 1/4 | Final exam: | 1/2 |
|---|
| Week | Topics | Chapter(s) |
|---|---|---|
| 1/18 - 1/20 | Analyzing Algorithms | 1, 2 |
| 1/23 - 1/27 | Growth of functions, Recurrences | 3, 4 |
| 1/30 - 2/3 | Sorts | 6-8 |
| 2/6 - 2/8 | Elementary Data Structures | 10 |
| 2/10 | No class | |
| 2/13 - 2/17 | Hash Tables | 11 |
| 2/20 - 2/24 | Binary Search Trees (BST) | 12 |
| 2/27 - 3/1 | More on BST | |
| 3/3 | Midterm Exam | |
| 3/6 - 3/10 | AVL Trees, more on time complexity | |
| 3/13 - 3/17 | Greedy Algorithms | 16 |
| 3/20 - 3/24 | Spring Break - No class | |
| 3/27 - 3/31 | B Trees | 18 |
| 4/3 - 4/5 | Binomial Heaps | 19 |
| 4/7 | No class | |
| 4/10 - 4/12 | Graphs | 22 |
| 4/14 | No class - Easter | |
| 4/17 - 4/21 | Minimum Spanning Trees | 23 | 4/24 - 4/28 | Shortest Path Algorithms | 24 |
The final exam is scheduled for Monday, 1 May, 13:00 - 15:00