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.

Schedule

This schedule is tentative and subject to change.

WEEK	DAY	ANNOUNCEMENTS	TOPIC & READING	LABS
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
9	Nov 06	Midterm
	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	Thanksgiving
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

Grading

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.

External Links

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:43 PM