CSci 4041: Algorithms and Data Structures
Spring 2007 Course Summary
Instructor:
|
See me first for general questions about lecture material!
William Schuler (schuler at cs.umn.edu) -- please type '4041' in subject
Office: 5-225F EE/CSci Building,
Ph: (612) 626-7502
Office Hours: 12:30-1pm Tues,Thus (after our class) + 2pm-3pm Tues (after the class that's after our class)
|
Teaching Assistants:
|
See us first for specific questions about assignments and grading!
Tim Miller (tmill at cs.umn.edu)
Office Hours: Wednesday 2:15 PM - 3:15 PM, Friday 11:00 AM - 12:00 PM EE/CS 2-209
Shaonan Tian (tian at cs.umn.edu)
Office Hours: Wednesday 9:00 AM - 10:00 AM , Friday 10:00 AM - 11:00 AM EE/CS 2-209
|
Textbook:
|
"Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein. 2nd Edition, McGraw Hill, 2001
|
Course Time and Location:
|
- Lecture : T,Th, 11:15 A.M. - 12:30 P.M. EE/CSci 3-230
- Discussion (002): W 11:15 A.M. - 12:05 P.M. EE/CSCI 3-115
- Discussion (003): W 12:20 P.M. - 1:10 P.M. EE/CSCI 3-115
- Discussion (004): W 1:25 P.M. - 2:15 P.M AmundH 162.
|
Course Schedule
| Wk |
Tuesday |
Thursday |
Friday |
Reading |
| 1 |
1/16 Course introduction, Correctness and complexity of iterative algorithms (insertion sort) |
1/18 Correctness and complexity of recursive algorithms (merge sort) |
1/19 Homework 0 due - Solution |
Chapters 2,3 |
| 2 |
1/23 Trees, Heaps (heapsort) |
1/25 Complexity of tree operations (heapsort), Priority queues |
|
Chapter 6 |
| 3 |
1/30 Average case complexity (quicksort) |
2/1 Lower Bounds on Sorting |
2/2 Homework 1 due - Homework 1 solutions |
Chapters 7,8 |
| 4 |
2/6 Linear time sorting algorithms, counting sort, radix sort |
2/8 Bucket sort |
|
Chapter 8 |
| 5 |
2/13 Hashing with chaining |
2/15 Hashing with open addressing |
2/16 Programming project 1 due - Data - Solution |
Chapter 11 |
| 6 |
2/20 Binary Search Trees (BST insert, delete) |
2/22 Binary Search Trees complexity |
|
Chapter 12 |
| 7 |
2/27 Red-Black Trees (RBT insert) |
3/1 Red-Black Trees correctness |
3/2 Homework 2 due - Solution |
Chapter 13 |
| 8 |
3/6 Review (study guide) |
3/8 Midterm exam |
|
|
| - |
3/13 No class; spring break |
3/15 No class; spring break |
|
|
| 9 |
3/20 Dynamic Programming (fastest way) |
3/22 Dynamic Programming: string compare |
|
Chapter 15 |
| 10 |
3/27 Dynamic Programming: tree search given string (matrix chain multiply) |
3/29 Limits of Dynamic Programming |
|
Chapter 15 |
| 11 |
4/3 Greedy algorithms |
4/5 Greedy algorithms continued |
4/6 Programming project 2 due - Sample input - Sample output - Solution |
Chapter 16 |
| 12 |
4/10 Elementary graph algorithms (BFS, DFS) |
4/12 Elementary graph algorithms continued |
|
Chapter 22 |
| 13 |
4/17 Minimum Spanning Trees (Kruskal, Prim) |
4/19 Single Source Shortest Paths (Bellman-Ford, DAG, Dijkstra) |
|
Chapters 23, 24 |
| 14 |
4/24 All-Pairs Shortest Paths (slow apsp) |
4/26 All-Pairs Shortest Paths (Floyd-Warshall) |
4/27 Homework 3 due - Solutions |
Chapter 25 |
| 15 |
5/1 Other Graph Algos |
5/3 Review |
|
|
| Finals |
5/8 Final exam 8:00 A.M. - Study guide |
|
|
|
Course Evaluation:
There will be three (3) homework assignments. Homework solutions
will be posted shortly after the due date, so due dates for the
homeworks are strict: All homeworks must be received prior to their
deadline in order to receive credit.
There will be no partial credit for late homeworks.
There are going to be two (2) programming assignments. These assignments can be
completed in either C/C++ or Java.
There is going to be one midterm exam. The date of the exam will be announced
in class and posted to the announcements page. It will be CLOSED book and CLOSED
notes. There will be one final exam held from 8:00am - 10:00am Tuesday, May 8, in the same
room as the lecture. It will be closed book and closed notes.
Grading:
| Homeworks |
25% |
| Programming Assignments |
25% |
| Midterm |
20% |
| Final Exam |
30% |
Incompletes (or make up exams) will in general not be given. These options
will be considered only when a provably serious family or personal emergency
arises, proof is presented, and the student has already completed all but a
small portion of the work.
Scholastic Conduct
You must do your homeworks, programming assignments, and examinations
yourself, ON YOUR OWN.
Copying another's work, or allowing (even negligently) others to
copy your work, or possession of electronic computing devices in the
testing area, is cheating and grounds for penalties according to the
IT Bulletin.
|
