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

Course staff

  • Instructor:
    • Ioannis Panageas
      • Email: ipanagea at ics dot uci dot edu.
      • Office hours: Wednesday 1:30-2:30pm, DBH 4072
  • Teaching Assistants:
    • Fivos Kalogiannis
      • Email: fkalogia at uci dot edu.
      • Office hours: Monday 3:00-4:00pm, ICS1 458A
    • Raj Mohanty
      • Email: mohantyk at uci dot edu.
      • Office hours: Thursday 5:00-6:00pm, via zoom
    • Nikolas Patris
      • Email: npatris at uci dot edu.
      • Office hours: Wednesday 3:00-4:00pm, ICS1 458A
    • Renascence Tarafder Prapty
      • Email: rprapty at uci dot edu.
      • Office hours: Wednesday 12:00-1:00pm, via zoom
    • Stelios Stavroulakis (Lead TA)
      • Email: sstavrou at uci dot edu.
      • Office hours: Monday 12:00-1:00pm, ICS1 458A

Class announcements

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

Class meetings

  • Lectures (A): 12:30-01:50pm TuTh SSLH 100
  • Lectures (B): 3:30-04:50pm TuTh DBH 1100
    • Tests will be given during the lecture time.
  • Piazza - Gradescope:
    • Questions of general interest about the course material, the homework, and the tests should be posted on piazza.
    • Regrade requests on the homework and midterm will be handled by TAs on Gradescope. For regrade requests you need first to send an email to the Lead TA (Stelios).

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.TopicsReading
Lecture 1 (4/4)Administrivia, Introduction
Lecture 2 (4/6) Recap of basic discrete math tools, slides [GT] Sections 1.1, 1.2, 1.3
Lecture 3 (4/11), Lecture 4 (4/13) Recap of basic data structures, binary search slides [GT] Chapter 2, Sections 3.1, 5.2.2
Lecture 5 (4/18) Continue of binary search, insertion/selection sort, av. case of quicksort slides [GT] Chapter 2, Sections 3.1, 5.2.2, 8.2
Lecture 6 (4/20) Divide and conquer, mergesort, counting intersections slides [GT] Sections 8.1, 8.2, 8.3
Lecture 7 (4/25) Divide and conquer (cont.), master theorem, integer multiplication, maxima set slides [GT] Sections 11.1, 11.2, 11.3
Lecture 8 (4/27) Priority Queues, Heaps, Heapsort, Optimality slides [GT] Chapter 5, Section 8.3
Lecture 9 (5/2) Counting sort, Bucket sort, median select slides [GT] Section 9.1
Lecture 10 (5/4) Midterm 1
Lecture 11 (5/9) Graphs, DFS, BFS, topological sort slides [GT] Sections 13.1, 13.2, 13.3, 13.4
Lecture 12 (5/11) Shortest path algorithms slides [GT] Sections 14.1, 14.2, 14.3, 14.4, 14.5
Lecture 13 (5/16) MSTs: Prim, Kruskal slides [GT] Sections 15.1, 15.2, 15.3
Lecture 14 (5/18) Maxflow, bipartite matching slides [GT] Sections 16.1, 16.2, 16.3, 16.4
Lecture 15 (5/23) Greedy method slides [GT] Sections 10.1, 10.2
Lecture 16, (5/25), Lecture 17 (5/30) Dynamic Programming slides [GT] Chapter 12
Lecture 18 (6/1) Midterm 2
Lecture 19 (6/6) NP-completeness slides [GT] Chapter 17
Lecture 20 (6/8) NP-completeness reductions slides [GT] Chapter 17

Homework Assignments

  • The homework assignments will be posted in Gradescope.
    • .