CS 161 - Design and Analysis of Algorithms

CS 161 - Design and Analysis of Algorithms - Spring, 2024

Course staff

Instructor:

Ioannis Panageas

Email: ipanagea at ics dot uci dot edu.
Office hours: Wednesday 02:00 - 04:00pm, via zoom

Teaching Assistants:

Navin Velazco (Head TA)

Email: nvelazco at uci dot edu.
Office hours: Monday 2:00 - 03:00pm, via zoom

Nikolas Patris

Email: npatris at uci dot edu.
Office hours: Wednesday 01:00 - 02:00pm, via zoom

Parnian Shahkar

Email: shahkarp at uci dot edu.
Office hours: Friday 05:00 - 06:00pm, via zoom

Stelios Stavroulakis

Email: sstavrou at uci dot edu.
Office hours: Wednesday 11:00 - 12:00pm, via zoom

Class announcements

Class announcements will be made on canvas and Edstem. Please check there frequently.

Class meetings

Lectures: 05:00 - 06:20pm TuTh ALP 1300

Tests will be given during the lecture time.

Discussion sections:

(A1) 04:00 - 04:50pm MW HG 1800
(A2) 06:00 - 06:50pm MW RH 101
(A3) 07:00 - 07:50pm MW RH 101

Edstem - Gradescope:

Questions of general interest about the course material, the homework, and the tests should be posted on Edstem.
Regrade requests on the homework and midterm will be handled by TAs on Gradescope. For any other requests you need first to send an email to the Head TA (Navin).

Syllabus

The syllabus, including grading policy, schedule of hws/exams and academic honor code can be found here.

Textbook

Required textbook. [GT] Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia.
Recommended textbook. [CLRS] Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Schedule of classes and slides

Lecture no.	Topics	Slides (PDF)	Slides-annotated (PDF)	Slides (PPT)	Reading - Comments
Lecture 1 (4/2)	Administrivia, Introduction	L1		L1
Lecture 2 (4/4)	Review of basic concepts	L2	L2	L2	[GT] Sections 1.1, 1.2, 1.3, Chapter 2, Sections 3.1, 5.2.2
Lecture 3 (4/9)	Divide and conquer, mergesort, counting intersections	L3	L3	L3	[GT] Sections 8.1, 8.2, 11.1, 11.2, 11.3, 11.4
Lecture 4 (4/11)	Divide and conquer (continued)	L4	L4	L4	[GT] Sections 8.1, 8.2, 11.1, 11.2, 11.3, 11.4
Lecture 5 (4/16)	Divide and conquer (continued)	L5	L5	L5	[GT] Sections 8.1, 8.2, 11.1, 11.2, 11.3, 11.4
Lecture 6 (4/18)	Divide and conquer (continued)	L6	L6	L6	[GT] Sections 8.1, 8.2, 11.1, 11.2, 11.3, 11.4
Lecture 7 (4/23)	Midterm 1
Lecture 8 (4/25)	Dynamic Programming: Introduction. Memoization, Rod cutting and 0/1 Knapsack problems	L8	L8	L8	[GT] Chapter 12
Lecture 9 (4/30)	Dynamic Programming: 0/1 Knapsack (cont.), Bellman-Ford, Interval Scheduling	L9	L9	L9	[GT] Chapter 12
Lecture 10 (5/2)	Dynamic Programming (cont.)	L10	L10	L10	[GT] Chapter 12
Lecture 11 (5/7)	Midterm 2
Lecture 12 (5/9)	Max flow, bipartite matching	L12	L12	L12	[GT] Sections 16.1, 16.2, 16.3, 16.4
Lecture 13 (5/14)	Max flow, bipartite matching, further examples	L13	L13	L13	[GT] Sections 16.1, 16.2, 16.3, 16.4
Lecture 14 (5/16)	Greedy method, Fractional Knapsack	L14	L14	L14	[GT] Sections 10.1, 10.2
Lecture 15 (5/21)	Minimum spanning trees	L15	L15	L15	[GT] Sections 15.1, 15.2, 15.3
Lecture 16 (5/23)	More problems on greedy	L16	L16	L16	[GT] Sections 10.1, 10.2
Lecture 17 (5/28)	Midterm 3
Lecture 18 (5/30)	NP-completeness, reductions	L18	L18	L18	[GT] Chapter 17, NOT part of the final exam
Lecture 19 (6/4)	Recap	L19	L19	L19	Dynamic Programming, Divide and Conquer
Lecture 20 (6/6)	Recap	L20	L20	L20	Greedy, Maxflow, MSTs

Homework Assignments

The homework assignments will be posted in Edstem, Canvas and Gradescope.