Course Information

• Course Outline: The course is intended as a first graduate course in the design and analysis of algorithms. The main focus is on developing an understanding for the major algorithm design techniques. At times, the practical side of algorithm design is also explored with interesting examples of their usage in solving industry problems.

• Textbook:
  * Algorithm Design
          Jon Kleinberg/Eva Tardos
  The class will be relying mostly on the textbook, but additional material will occasionally be drawn from the following:
  * Introduction to Algorithms (second Edition)
          Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest and Cliff Stein published by MIT Press and McGraw-Hill.

Students in the class are expected to have a reasonable degree of mathematical sophistication, and to be familiar with the basic notions of algorithms and data structures, discrete mathematics, and probability. Undergraduate classes in these subjects should be sufficient. If you have doubts about meeting these prerequisites, please contact the instructor.

Class Structure

• Homework: There will be weekly homework assignments.
• Exams: There will be two in-class midterm exams and a final exam.

Syllabus

This syllabus is meant as an outline. Depending on progress, material may be added or removed. Also, there will often be interesting tangents to follow.

week 1        intro, stable matching                  	                 chapter 1 

week 2        Asymptotic notation, BFS, DFS, greedy algorithms           chapter 2, 3, 4

week 3        Greedy algorithms, heaps                                	 chapter 4, suplemental text chapter 6,19

week 4        MST, shortest path, divide and conquer                     chapter 4, 5

week 5        divide and conquer                                         chapter 5

week 6        midterm I, dynamic programming                             chapter 6

week 7        dynamic programming, network flow (max flow)               chapter 6, 7

week 8        network flow                                               chapter 7

week 9        circulation, midterm II                                    chapter 7

week 10       NP-completeness                                            chapter 8

week 11       NP-completeness                                            chapter 8, supplemental text chapter 34

week 12       approximation algorithms, LP                               chapter 11, supplemental text chapter 29, 35

week 13       final exam

Exam Schedule

Grading

There will be two midterm and one final exam in this course. Each midterm exam worth 30% and the final 40%. There will be homework assigned from the textbook roughly every 1-2 weeks. The homework will be collected and graded but Will NOT be accounted in your grade; Solutions to the homework will become available shortly after the deadline.

Additional Policies

• Academic Integrity Policies of the University will be strictly enforced. You are encouraged to review these policies, for example in SCampus.
• Please visit course homepage and check Announcements regularly.
• No late homework will be accepted unless approval is granted from the instructor in advance.

Academic Integrity

In this course we encourage students to study together. This includes discussing general strategies to be used on individual assignments. However, all work submitted for the class is to be done individually.

Some examples of what is not allowed by the conduct code: copying all or part of someone else's work (by hand or by looking at others' files, either secretly or if shown), and submitting it as your own; giving another student in the class a copy of your assignment solution; consulting with another student during an exam. If you have questions about what is allowed, please discuss it with the instructor.

Students who violate University standards of academic integrity are subject to disciplinary sanctions, including failure in the course and suspension from the University. Since dishonesty in any form harms the individual, other students, and the University, policies on academic integrity will be strictly enforced. We expect you to familiarize yourself with the Academic Integrity guidelines found in the current SCampus.

Violations of the Student Conduct Code will be filed with the Office of Student Conduct, and appropriate sanctions will be given.