Design and Analysis of Algorithms
Introduction
Welcome to CS41: Algorithms! This course is a more formal study of basic algorithms and data structures commonly used in many areas of computer science and other disciplines.
This course will consist of numerous homework exercises and a few programming projects. The course format will be a mixture of lecture and seminar formats. Students should be prepared to present and discuss homeworks or readings in class.
Announcements
- The next homework assignment is due Thursday Dec 4.
- The Final Exam Schedule is posted. The final exam for this course is Thursday December 18th from 2pm-5pm.
- Another round of interesting problems is posted. Submissions must be received by Thanksgiving break.
- Homework for Thursday November 6 is posted
Class info
Room: Science Center 264Time: TR 2:40pm–3:55pm
Text: Intro to Algorithms, 2nd edition by Cormen, Leiserson, Rivest, and Stein. (CLRS)
Instructor info
Professor: Andrew DannerOffice: Science Center 253
Phone: (610) 328-8665
Office hours: by appointment
Schedule
| WEEK | DAY | ANNOUNCEMENTS | TOPIC & READING | HOMEWORK |
| 1 | Sep 02 | Intro. Math review — Induction, summations, logarithms Interesting problems. |
|
|
| Sep 04 | ||||
| 2 | Sep 09 | Asymptotic notation Solving recurrences Presentations on interesting problems. |
HW 1 | |
| Sep 11 | Drop/add ends (Sep 12) | |||
| 3 | Sep 16 | Invariants, Sorting, Sorting lower bounds. | HW 2 | |
| Sep 18 | ||||
| 4 | Sep 23 | Linear time sorting Order statistics |
HW 3 | |
| Sep 25 | ||||
| 5 | Sep 30 | Finals Schedule Posted (Oct 01) | Red-black trees B-trees Augmented data structures |
HW 4 |
| Oct 02 | ||||
| 6 | Oct 07 | Dynamic programming, Greedy algorithms. | HW 5 | |
| Oct 09 | ||||
Oct 14 |
Fall Break |
|||
Oct 16 |
||||
| 7 | Oct 21 | Amortized analysis | |
|
Oct 23 |
Midterm Exam |
|||
| 8 | Oct 28 | Amortized analysis (continued) | HW 6 | |
| Oct 30 | Sets, Union-find | |||
| 9 | Nov 04 | Intro to graph Algorithms | |
|
| Nov 06 | ||||
| 10 | Nov 11 | MST, SSSP | |
|
| Nov 13 | ||||
| 11 | Nov 18 | Range Mimimum Queries and LCA | |
|
| Nov 20 | ||||
| 12 | Nov 25 | Interesting Problems | HW 7 | |
Nov 27 |
Thanksgiving Break |
|||
| 13 | Dec 02 | Universal Hashing | |
|
| Dec 04 | ||||
| 14 | Dec 09 | Wrapup | |
|
Dec 18 |
Final Exam 2pm-5pm |
|||
Grading
Grades will be weighted as follows:40% Homework assignments
15% Class presentations and participation
20% Midterm Exam
25% Final Exam (Scheduled by the Registrar)
Homework policy
Written homework will typically be due at the beginning of class. As we will be discussing solutions in class, late homeworks will not be accepted. Exceptions will be made only in extreme situations and only if you inform me ot the situation well before the homework due date. Even if you do not fully complete an assignment, you may submit what you have done to receive partial credit.Academic integrity
Academic honesty is required in all work you submit to be graded. You may not submit work done with (or by) someone else. You may not examine or use work done by others to complete your own work. You may discuss ideas problems with others on a general level and such discussions are encourages, but you must credit any collaborators or resources used in the completion of you assignment. "It is the opinion of the faculty that for an intentional first offense, failure in the course is normally appropriate. Suspension for a semester or deprivation of the degree in that year may also be appropriate when warranted by the seriousness of the offense." - Swarthmore College Bulletin (2008-2009, Section 7.1.2) Please see me if there are any questions about what is permissible.External links
Have any good algorithms links that are relevant to the course? Let me know, and I'll add them here.Wikipedia entry for Algorithms
Proceedings of Symposium on Discrete Algorithms
Professor Jokes? in CLRS. Surely you can find better links than this.