|Lectures:||Mon, Wed, 11:00am-12:20pm, RH101|
|Office Hours:||Wed 1-3pm in EH 4207|
"Algorithm Design" by J.Kleinberg and E.Tardos.
Familiarity with algorithms, data structures and discrete math, at undergraduate level.
|TA:||Balint Tillman (tillmanb at uci edu)|
|Discussion:||Fri 11-11:50am, RH101|
Fri 3-5pm in EH 4404
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.
|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%|