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: MWF 9:30am–10:20am
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: 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.