EECS 215: Design and Analysis of Algorithms, Fall 2014



Instructor: Athina Markopoulou
Lectures: Mon, Wed, 11:00am-12:20pm, MDE
Office Hours: Wed 1-3pm in EH 4207
valign=“top” Textbook:
valign=“top” Additional Reading:

Algorithms by R.Sedwick and K. Wayne.
"Introduction to Algorithms".
Paper copies will also be on reserve in the Science Library.

valign=“top” Prerequisites:

Familiarity with algorithms, data structures and discrete math, at undergraduate level.
Familiarity with basic features of Java programming.

TA: David Carrillo Cisneros (carrild1 at uci edu)
Discussion: Fri 3-3:50pm
Office Hours: TBD

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 20% every ~2-3 weeks
Midterm Exam 30% Wed, Nov. 12, in class
Final Exam 50% Fri, Dec 19th, 8-10am


  • 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.
  • Late policy: no late assignments will be accepted. Solutions will be posted online shortly after the deadline. Assignments 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 supposed to do your assignments in teams of two. You are allowed to discuss with other classmates. If you work too closely with people from other groups, please indicate their name. If we notice that two assignments are identical, both groups will get 0 grade; they will also be subject to the rules of UCI Academic Honesty Policy.