| Instructor - Robert Hochberg Office- STC C-121 Phone- 328-9685 Email- hochberg@cs.ecu.edu |
Text - Introduction to Algorithms second edition by: Cormen, Leiserson, Rivest and Stein. |
Office Hours M 9-10 and 11-12 W 8-10 and 11-12 |
|
|
|
Friday |
| 1/6 - Course Overview, and
solution to problem 4-2, page 85 |
||
| 1/9 - Introduction to asymptotic
notation, section 3.1 in the book Homework #1 assigned - due Wed., 1/18 Problems 2-2 and 2-4, pages 38-40 in book, as well as This program. |
1/11 - Introduction to various sorts | 1/13 - More sorts. |
| 1/16
- No Class, Martin Luther King Day |
1/18 - Loop invariants and
selection sort |
1/20 - Loop invariants and
selection sort analysis. |
| 1/23 - Asymptotic notation Do the four problems 3.1-{1, 3, 4, 7} on pg. 50, and 3.2-3 on page 57. This is for personal study, not to hand in. Homework #2: Do hand in problems 3-2, 3-3 and 3-4 parts a and h, on pages 58 and 59. These are due on Friday, 1/27, at the test. |
1/25 - Recurrences Do problems 4.1-{1, 5} on page 67. This is for personal study, not to hand in. |
1/27 - Exam I
on Chapters 1 to 3. (Not on Chapter 4, as previously stated.) Sample Exam |
| 1/30 - |
2/1 - |
2/3 - |
| 2/6 - |
2/8 - |
2/10 - Some examples of the
substitution method, proving big-O and big-Omega bounds. Notes from class |
| 2/13 - Tree Recurision. Notes from class. |
2/15 - The
Master Method |
2/17 - Master
Method Examples |
| 2/20 - Recursion
tricks Homework #3 assigned: 4-1 on pg. 85 and 4-4 on pg. 86. due Monday, 2/27 |
2/22 - Heaps |
2/24 - More heaps |
| 2/27 - Analysis
of max heaps and heap sort |
3/1 - Max-priority-queues |
3/3 - Variants of quicksort,
min-priority-queues Homework to do, not hand in: 6.1-all, 6.2-1, 3, 4, 5, 6, 6.3-1, 3 6.4-1, 3 6.5-1, 2, 7, 8 Homework #4: to hand in on 3/24 6-1, page 145. (Largely done in class) 6-2, page 143 6-3 parts 1-3, page 143. And this program, which is due 3/22 |
| 3/6 - Introduction to Graphs |
3/8 - Minimum weight spanning
tree algorithms |
3/10 - Lab day for programming assignment. |
| 3/13
- Spring Break |
3/15 - Spring Break | 3/17 - Spring Break |
| 3/20 - Proof of Kruskal's
Algorithm |
3/22 - Tree Theory |
3/24
- Review for Exam |
| 3/27
- Searches in Trees Homework: do (but don't hand in) 22.1-1, 2, 4, 6 22.2-1, 3, 5 22.3-2, 3, 4, 7 Homework #5: Hand in on Monday, 4/3: 22.2-7 22.3-1 22.4-2 22.5-1 22.5-3, and prove your answer or give a counter-example. |
3/29 - Depth
first search |
3/31
- Exam II Sample Exam Notes from Review Session Solutions for Exam II |
| 4/3 - Strongly
Connected Components |
4/5 - Topological
Sorts of dags |
4/7 - Some
DFS theorems |
| 4/10 - Proof
of our SCC algorithm |
4/12 - End
of SCC proof, and
start of disjoint data structures. Homework #6, due 4/21 Do these three problems: Also, write this program. |
4/14
- Good Friday, no
class. |
| 4/17 - Disjoint
Data Structures |
4/19 - Dynamic
Programming Intro |
4/21 - Longest
Common Substring |
| 4/24 - DP
on a dag |
4/26 - Review
Session Nothing prepared. Please come with questions from the study guide. |
4/28
- Final Exam 8-10:30am, in the
usual room. |