EECS 215: Design and Analysis of Algorithms, Winter 2017

Syllabus

Logistics

Instructor: Athina Markopoulou
Lectures: Mon, Wed, 12:30am-1:50pm, ICS180
Office Hours: Thu 11:30-1pm in EH 4207
Textbook: "Algorithm Design" by J.Kleinberg and E.Tardos. (A book is on reserve in the Science Library.
Additional Reading: Algorithms by R.Sedwick and K. Wayne.
"Introduction to Algorithms".
Prerequisites: Familiarity with algorithms, data structures and discrete math, at undergraduate level.
A plus: familiarity with Python (or Java) programming.
Office Hours: Thu 11:30-1pm in EH 4207


Course Description

Algorithms provide a powerful way of thinking about problems within and beyond computer science and engineering. The goal of this class is to train graduate students in recognizing and formulating an algorithmic problem within a broader practical context, designing and analyzing algorithms that solve the problem. The textbook will be instrumental in presenting the materials from this perspective. After an introduction (Ch.1), we will first review basic materials such as asymptotic growth rates and graphs (Ch.2-3). Second, we will cover four major algorithm design techniques: greedy algorithms, design and conquer, dynamic programming and network flow (following Ch. 4,5,6,7 respectively). Third, we will discuss NP and computational intractability (described in Ch.8). Time permitting, we will touch upon ways to effectively deal with NP-complete problems in practice, namely with inputs that exhibit special structure, approximation algorithms, and local search algorithms (in Ch.10,11, and 12 respectively).

Note: The emphasis of the class will be on the design and analysis of algorithms. Part of the assignments will involve programming, but programming is not the emphasis of this class.


Deliverables and Grading

What Grade % When
Homework Assignments 30% every ~2-3 weeks
Midterm Exam 30% Wed, Feb. 15th, in class
Final Exam 40% Mon, March 20th, 1:30-3:30pm


Policies

  • Communication: Please post all class-related questions on the messageboard. Avoid personal emails to the instructor! We will check the messageboard once a day and reply. Usually students have similar questions and everybody can benefit from the same answer.
  • Late policy: no late assignments please. Solutions will be posted online shortly after the deadline. To accommodate for unforseen circumstances, your homework with the lowest grade (including 0 for a missing one) will be dropped; this means that you can skip one homework without asking permission.
  • Collaboration: you should submit your assignments individually. You are allowed to discuss with other classmates. If you work too closely with other students people, please indicate their name. (If we notice that two assignments are identical, both students will get 0 grade; they will also be subject to the rules of UCI Academic Honesty Policy.) If programming assignments are given (not the focus here), you can work in teams of two (for the programming part only).