EECS 215: Design and Analysis of Algorithms, Fall 2015

Syllabus

Logistics

Instructor: Athina Markopoulou
Lectures: Mon, Wed, 11:00am-12:20pm, RH101
Office Hours: Wed 1-3pm in EH 4207
Textbook: "Algorithm Design" by J.Kleinberg and E.Tardos.
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.
A plus: familiarity with Python (or Java) programming.

TA: Balint Tillman (tillmanb at uci edu)
Discussion: Fri 11-11:50am, RH101
Office Hours: Fri 3-5pm in EH 4404


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. 4
Final Exam 50% Fri, Dec 11th, 8-10am
Extra Credit up to 6%


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 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 can submit your assignments individually or 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.
  • Extra Credit: Up to +5% extra credit may be given for advanced (but optional) homework assignments. +1% may be given for evaluations and other class participation. Details TBA.