EECS 215: Design and Analysis of Algorithms, Fall 2011

Syllabus

Logistics

Instructor: Athina Markopoulou
Lectures: Tuesday and Thursday, 11:00am-12:20pm, PSCB 140
Office Hours: Thu 3:30-5:30 in EH 4207
Mailing List:
Messageboard:
valign=“top” Textbook:
valign=“top” Additional Reading:
valign=“top” Prerequisites:

• Familiarity with algorithms, data structures and discrete math, at undergraduate level.
• Programming in python is useful for the optional programming assignments.


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 (a) recognizing and formulating an algorithmic problem within a broader practical context (b) 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. There are going to be a few optional programming assignments to help clarify the concepts, but programming is not the emphasis of this class.


Deliverables and Grading

What Grade % When
Homeworks 30% ~bi-weekly
Programming Assignments(*) +10% every 1-2 homeworks
Typing of Homeworks (*) +5%
Midterm Exam 30% Thu, Oct 27th, in class
Final Exam 40% Tue, Dec 6th, 10:30-12:30pm

(*) Optional.


Policies

  • Communication: Please post all class-related questions on the messageboard. Avoid personal emails to the instructor! We will check the message board once a day and reply. Usually students have similar questions and everybody can benefit from the same answer.
  • Homeworks: Homeworks will consist mostly of theoretical exercises. There are going to be optional programming assignments for an extra +10% points (instructions to be posted later). The default format is to hand-written homeworks. You can also type and submit them electronically for +5% bonus points. (In that case, here are more detailed instructions and here is the corresponding template latex file.) These extra points are computed out of the total grade, not out of each individual homework.
  • Late policy: no late homeworks will be accepted. Solutions will be posted online shortly after the deadline. Homeworks not submitted by the deadline will get zero points. However, 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 are allowed to discuss with your classmates, but you are supposed to do your homework individually. If you work closely with somebody, please indicate their name on your homework. If we notice that two homeworks are identical, both students will get 0 grade; they will also be subject to the rules of UCI Academic Honesty Policy.