CS331: Algorithms and Complexity, Spring 2020

Logistics: Lecture: Mon/Wed 2:00 - 3:30, UTC 3.104
Discussion section: Fri 10:00 - 11:00 CBA 4.348, 11:00 - 12:00 GAR 1.126
Course web page: http://www.cs.utexas.edu/~ecprice/courses/331/
Unique number: 50450 / 50455
Professor: Eric Price
Email: ecprice@cs.utexas.edu
Office: GDC 4.510
Office Hours: 3:45-4:45pm Monday
TA: Shivam Gupta
Email: shivamgupta@utexas.edu
Office Hours: 3:30-4:30pm Friday
GDC basement, TA station 2.
Problem Sets:
Course Notes: Lecture notes will be provided after class, but you should keep your own notes: topics will be covered in more detail in class than in the posted notes. The class will also follow Jeff Erickson's book.
DateTopicCorresponding book chapters
Jan 22 Multiplication and Fibonacci numbers Chapter 0
Jan 27 Recursion Chapter 1 and Chapter 2
Jan 29 Dynamic programming Chapter 3
Feb 3 DP exercises
Feb 5 Tree DP; More DP exercises
Feb 10 Knapsack; Last DP exercises
Feb 12 Greedy algorithms Chapter 4
Feb 17 Stable marriage
Feb 19 Exam 1
Feb 24 Graph searching Chapter 5
Feb 26 Graph reductions
March 2 DFS and topological sort Chapter 6
March 4 Strongly connected components
March 9 Minimum spanning trees: Boruvka, Kruskal Chapter 7
March 11 Prim; start shortest paths
March 30 Shortest Paths: Bellman-Ford, Dijkstra, slides video Chapter 8
April 1 A* search: slides video
April 6 APSP: Floyd-Warshall and Johnson's algorithm slides video
April 8 Network Flow video Chapter 10
April 13 Min-Cut Max-Flow Theorem video
April 15 Applications of Network Flow video Chapter 11
April 20 Linear programming notes slides video Appendix H
April 22 Linear programming duality slides video
April 27 Complexity theory video Chapter 12
April 29 NP-hardness reductions slides video
May 4 Larger complexity classes and computability slides video Supplemental chapter
May 6 Approximation algorithms notes video Supplemental chapter
Content: This undergraduate course will cover the basics of algorithms. The tentative outline for the course is as follows, with one week per topic:
  • Introduction; multiplication
  • Recursion; fibonacci numbers
  • Basic dynamic programming
  • Advanced dynamic programming
  • Test 1; Introduction to graphs
  • Shortest paths, minimum spanning trees
  • Test 2; Network flows, maximum matching, and minimum cut
  • Linear Programming
  • NP-completeness
  • Advanced topics
Prerequisites: The following coursework with a grade of at least C-: CS 311, 311H, 313H, or 313K; CS 307, 314, 314H, 315, or 315H; CS 310, 310H, 429, or 429H; M362K or SSC321; and credit with a grade of at least C- or registration for M340L or SSC329C.
Grading: 50%: Homework
30%: Two in-class exams
20%: Final exam
Key dates:
  • Exam 1: Wednesday, February 19.
  • Exam 2: Wednesday, April 8.
  • Final exam: take-home after last class.
Text: The course will generally follow Jeff Erickson's book, which is freely available online.
Homework
policy:
There will be a homework assignment every week.

Collaboration policy: You are encouraged to collaborate on homework. However, you must write up your own solutions. You should also state the names of those you collaborated with on the first page of your submission.
Students with
Disabilites:
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.
Additional Class Policies

You should read the CS Department Code of Conduct. The policies described there will be followed in this class.