CS41: Algorithms

Fall 2012

Announcements | Class info | Schedule | Grading | Academic Integrity | Links
Design and Analysis of Algorithms


Class Info

Lecture: TR 9:55—11:10am, Science Center 183
Lab Section 1: W 1:00—2:30pm, Science Center 240
Lab Section 2: W 2:40—4:10pm, Science Center 240
Professor: Andrew Danner
Office: Science Center 247
Office hours: by appointment
Text: Algorithm Design by Kleinberg and Tardos. See also "Intro to Algorithms 3ed" Cormen, Leiserson, Rivest and Stein.

CS41 explores algorithmic design and analysis in a more formal approach than CS21 or CS35. Algorithmic problems arise in many diverse areas of computer science. Often, one must take open ended, abstract, real-world problems and extract a clean mathematical problem that can be approached algorithmically. Designing a solution requires knowing the rules and common techniques of the model of computation used. Multiple models represent various abstractions of real computer systems and may result in very different solutions. Regardless of the model however, good algorithmic design requires careful analysis of complexity and proofs of correctness. Topics covered include asymptotic notation, graph algorithms, greedy algorithms, divide and conquer, dynamic programming, approximation algorithms, and parallel algorithms.


This schedule is tentative and subject to change.
1 Sep 04   Stable Matching Lab 01-Interesting problems
HW 01
Sep 06  
2 Sep 11   Analysis / Graph Intro
Sep 13 Drop/add ends (Sep 14)
3 Sep 18   Graph Algorithms In Lab Exercises
HW 02
Sep 20  
4 Sep 25   Greedy Algorithms/Union Find (Chapter 4.1-4.7) In Lab Exercises
HW 04
Sep 27 Final Exam Schedule (Oct 01)
5 Oct 02   Divide and Conquer (Chapter 5, skip 5.5/5.6) In Lab Exercises
HW 05
Oct 04  
6 Oct 09   Dynamic Programming (Chapter 6) In Lab Exercises
Oct 11  

Oct 16

Fall Break

Oct 18

7 Oct 23   Alternate Models of Computation (CLRS Ch 18,27)
Oct 25  
8 Oct 30   Sandy - No Class
Nov 01   Parallel Algorithms

Nov 06


Nov 08 CR/NC/W Deadline (Nov 09) No Class In Lab Exercises
10 Nov 13   Computational Geometry
Nov 15   In Lab Exercises
11 Nov 20   LCA Problem

Nov 22


12 Nov 27   Intractability In Lab Exercises
HW 07
Nov 29  
13 Dec 04   Approximation Algorithms In Lab Exercises
Dec 06  
  Dec 11   Wrap up

Dec 14

Finals Exams Start


Dec 22

Finals Exams End


Grades will be weighted as follows:
50% Homework assignments
5% 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. 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 Accommodations

If you believe that you need accommodations for a disability, please contact Leslie Hempling in the Office of Student Disability Services, located in Parrish 130, or e-mail lhempli1 to set up an appointment to discuss your needs and the process for requesting accommodations. Leslie Hempling is responsible for reviewing and approving disability-related accommodation requests and, as appropriate, she will issue students with documented disabilities an Accommodation Authorization Letter. Since accommodations may require early planning and are not retroactive, please contact her as soon as possible. For details about the Student Disabilities Service and the accomodations process, visit the Disability Services webpage.

To receive an accommodation for a course activity, you must have an Accomodation Authorization letter from Leslie Hempling and you need to meet with me to work out the details of your accommodation at least one week prior to the activity.

You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through Leslie Hempling in the Office Of Student Disability Services.

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, or examine or use work done by others to complete your own work.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's solution or let anyone else read your solutions. You may discuss assignment specifications and requirements with others in the class to be sure you understand the problem. In addition, you are allowed to work with others to help learn the course material. However, with the exception of partners in group assignments, you may not work with others on your assignments in any capacity.

``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.'' - Student Handbook (2010-2011, pg20 Section A.3.b.i)

Please see me if there are any questions about what is permissible.