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
- This course has ended
- The Registrar scheduled the Final Exam for Wednesday 20 Dec from 9:00am to noon.
Class info
Room: Science Center 264Time: MWF 9:30am–10:20am
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: Tu/Th 9:00am-12:00pm or by appointment
Schedule
| Day | Notes | Topic | Homework | Reading |
|---|---|---|---|---|
| Sep 4–8 | Introduction to algorithms Math review - Induction, summations, fun with logarithms Some interesting(?) problems |
Hw 1 (Due Sep 6) Hw 2 (Due Sep 8) Hw 3 (Due Sep 11) Hw 4 (Due Sep 13) |
Ch. 1,2, and App. A |
|
| Sep 11–15 | Asymptotic notation, growth of functions Solving recurrences Sketch of solutions to interesting problems by students |
Hw 5 (Due Sep 15) Hw 6 (Due Sep 18) Hw 7 (Due Sep 22) |
Ch. 3, 4 | |
| Sep 18–24 |
Review of sets, relations, graphs, trees Heapsort, Quicksort |
Ch. 6,7,8,9, and App. B |
||
| Sep 24–29 |
Sorting lower bounds Linear time sorting Order statistics Review of basic data structures Binary search trees Linear time majority |
Hw 8 (Due Sep 27) Hw 9 (Due Sep 29) Hw 10 (Due Oct 2) Hw 11 (Due Oct 4) |
Ch. 10, 12, 13 | |
| Oct 2–6 |
Red-black trees, B-trees |
Hw 12 (Due Oct 6) Hw 13 (Due Oct 9) Hw 14 (Due Oct 11) |
Ch. 18 | |
| Oct 9–13 | Dynamic programming, Greedy algorithms | Practice problems for midterm pdf | Ch. 15 and 16 | |
| Oct 16–20 | No Class — Fall Break | |||
| Oct 23–27 | Exam Friday |
Amortized analysis Sets, Union-find |
Hw 15 (Due Oct 25) Hw 16 (Due Oct 30) Hw 17 (Due Nov 1) |
Ch. 17 and 21 |
| Oct 30–Nov 3 | BFS, DFS, Topological sort |
Hw 18 (Due Nov 3) Hw 19 (Due Nov 8) |
Ch. 22, 23 | |
| Nov 6–10 | Minimum spanning trees, Shortest paths |
Hw 20 (Due Nov 15) |
Ch. 24, 25 | |
| Nov 13–17 | Computational Geometry Convex hull Line segment intersection |
Hw 21 (Due Nov 22) |
Ch. 33 | |
| Nov 20–22 | Computational Geometry Intro to Hard/Unsolvable Problems |
Ch. 34 | ||
| Nov 27–Dec 1 | NP-Completeness |
Hw 22 (Due Dec 6) |
Ch. 34 | |
| Dec 4–8 | Approximation algorithms | Ch. 35 | ||
| Dec 11 | Wrap-up | |||
| Dec 20 | Final Exam: Wed 9:00am-noon | |||
Grading
Grades will be weighted as follows:40% Homework assignments
10% Class presentations and participation
20% Midterm Test (during week of Oct 23–27)
30% Final Exam. Scheduled by registrar for Wed 20 Dec 9am-noon.
Homework policy
Written homework will typically be due at the beginning of class on Wednesdays. Late homework will be penalized at least 10% depending on lateness and material covered in class.Academic integrity
Strong academic integrity is expected of every student. Plagiarism, cheating, and academic dishonesty will be reported to the College Judiciary Committee and dealt with severely. You may not hand in work done by someone else as your own. You may discuss ideas and problems with others on a general level and such discussions are encouraged, but you must credit any collaborators or resources used in the completion of your assignments.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
Professor Jokes? in CLRS. Surely you can find better links than this.