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

Class info

Room: Science Center 264
Time: TR 2:40pm–3:55pm
Text: Intro to Algorithms, 2nd edition by Cormen, Leiserson, Rivest, and Stein. (CLRS)

Instructor info

Professor: Andrew Danner
Office: 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. 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.