ECS 122A
Algorithm Design and Analysis
Summer Session 2 2017
Announcements:
  • [9/18] Finished grading.
  • [9/13] Uploaded lecture15 notes. If you have any question, please send an email to me directly.
  • [9/11] Uploaded lecture14 notes. For homework4 problem 4, you can assume that the graph is connected.
  • [9/8] Uploaded lecture13 notes.
  • [9/6] Uploaded lecture12 notes. Homework4 is posted. The due date is 9/12.
  • [9/1] Uploaded lecture11 notes.
  • [8/30] Uploaded lecture10 notes. Homework3 is posted.
  • [8/28] Uploaded lecture9 notes. Homework3 will be posted on 8/30, and its due date is 9/5.
  • [8/23] Uploaded lecture8 notes.
  • [8/21] Uploaded lecture7 notes.
  • [8/18] Uploaded lecture6 notes. Updated the schedule for week 3. The instructor's office has been changed.
  • [8/17] Homework2 is posted.
  • [8/16] Uploaded lecture5 notes.
  • [8/14] Uploaded lecture4 notes. Homework2 will be posted on 8/17, and its due date is 8/23.
  • [8/11] Uploaded lecture3 notes. Homework1 is posted.
  • [8/9] Uploaded lecture2 notes. Homework will be released on every Friday.
  • [8/7] Uploaded lecture1 notes. If you would like to know the course code for gradescope, please send an email to either the instructor or the TA.
  • [8/6] Welcome to 122A!

Instructor:
Qirun Zhang,
Office: 1031 Academic Surge Building 3027 Kemper Hall
Email: qrzhang at ucdavis.edu

Teaching Assistant:
Thong Le,
Office: 55 Kemper Hall
Email: thmle at ucdavis.edu

Lectures:
M.W.F. 10:00am - 11:40am
1 Wellman

Discussions:
M. 12:10pm - 1:50pm
1 Wellman

Office Hours:
  • Mon.: 2:00pm-4:00pm (55 Kemper, Thong)
  • Wed.: 2:00pm-4:00pm (1031 Academic Surge Building 3027 Kemper Hall, Qirun)

Course Objectives:
The notion of an algorithm is fundamental to all of computer science. In this course, we study methods for designing efficient algorithms, evaluating their performance, and ways of establishing precise limits on the possible effectiveness of classes of algorithms.

Textbook and lecture notes:
  • Textbook: Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R. Rivest and C. Stein, MIT Press, 2009
  • Updated lecture notes will be posted on this site.

Course Outline
  1. Introduction and foundations (Ch.1-3)
  2. Algorithm design paradigms:
    • Divide-and-conquer (Ch.4)
    • Dynamic programming (Ch.15)
    • Greedy algorithms (Ch.16)
  3. Algorithms on graphs and trees (Ch.22-25)
  4. NP-completeness and approximate algorithms (Ch.34-35)

Homework Assignments:
  • There will be four homework assignments. The material in this class can only be learned by doing lots of problems, so the homework is very important.
  • Your homework should be your own work. It is a matter of intellectual honesty to write your homework strictly by yourself. Using solutions from any other source is not allowed.
  • Homework assignments are to be turned in at gradescope.
  • No late homework will be accepted! No email homework!

Exams (tentative) (All exams are closed-book, no notes allowed):
  • Midterm: August 25
  • Final: September 15

Grading:
Grading breakdown:
  • Homeworks: 40%
  • Midterm exam: 30%
  • Final exam: 30%
Grading may reflect the clarity of your presentation as well as the correctness of your answers.

Online Info:
Announcements, handouts and homework assignments will be posted at this site. It gets updated frequently throughout the SS2.

Lecture-by-Lecture summaries, handouts and homework assignments

Date Topics Handouts/Homework
8/7 Introduction and getting started
  • Notes
  • Readings: CLRS 1, 2.1, 2.2.
  • Review proof by induction.
8/9 Asymptotic notations and merge sort
  • Notes
  • Readings: CLRS 2.3, 3
8/11 Solving recurrences and the master method
8/14 Fast matrix multiplication, the master method and introduction to heap sort
  • Notes
  • Readings: CLRS 4.2, 6.1
8/16 Heapsort and priority queue
8/18 Quicksort and its analysis
8/21 Graph algorithms: basics
  • Notes
  • Readings: CLRS 22
8/23 Graph algorithms: minimum spanning trees
  • Notes
  • Readings: CLRS 23
8/25 Midterm
8/28 Single-source shortest paths: Bellman-Ford and Dijkstra's algorithms
  • Notes
  • Readings: CLRS 24.1-24.3
8/30 All-pairs shortest paths and transitive closure
9/1 Union-find data structures
  • Notes
  • Readings: CLRS 21.1-21.3
9/6 Dynamic programming (1)
9/7 Dynamic programming (2)
  • Notes
  • Readings: CLRS 15.4, 15.3 (optional) and 15.5 (optional).
9/11 NP-completeness (1)
  • Notes
  • Readings: CLRS 34.1-34.3.
9/13 NP-completeness (2)
  • Notes
  • Readings: CLRS 34.4 and 34.5 (optional).



If you have any concern, please send an email to the instructor. This link could help to send anonymous messages.