This course is a comprehensive introduction to the design and analysis of algorithms. Our goal is to investigate strategies for answering: how efficiently can we complete a given computational task? After this course, students should be equipped to tackle this question for a wide range of fundamental tasks arising in the practice of computer science.

The first three units of this course cover common algorithmic paradigms, familiarizing students with the principles of recursion, dynamic programming, and greedy algorithms. The next three units introduce toolkits for designing graph algorithms, continuous algorithms, and randomized algorithms, emphasizing real-world applications. The last unit, complexity theory, develops techniques for reasoning about fundamental limits on computational efficiency.

Course information: Here.

Time and location: 2:00 to 3:30 PM, Mondays and Wednesdays (GDC 1.304).

Instructor: Kevin Tian, kjtian (at) cs (dot) utexas (dot) edu.
Office hours: 3:30 to 5:00 PM, Mondays (GDC 4.720).

TA: Trung Dang, dddtrung (at) utexas (dot) edu.
Discussion section: 1:00 to 2:00 PM, Fridays (CBA 4.344)
Office hours: 4:00 to 5:00 PM, Tuesdays (GDC 4th floor bridge).

TA: Ryan Park, ryanjpark03 (at) utexas (dot) edu.
Discussion section: 12:00 to 1:00 PM, Fridays (CBA 4.330)
Office hours: 1:00 to 2:00 PM, Thursdays (GDC 4th floor bridge).

Assignments will be posted below when they become available.

Homework I (Part II except Section 6.3; Part III, Sections 1, 2, 3)
Homework II (Part III; Part IV, Sections 1, 2, 3)
Homework III (Part V)
Homework IV (Part VI)
Homework V (Part VII)
Homework VI (Erickson, Chapter 12)

Dates	Topic	Notes	Announcements
	Background	Reading
8/26	Recursion (Part I, Sections 2, 3; Part II, Sections 1, 2, 4)	Reading Lecture	HW I out
8/28	Recursion (Part II, Sections 3, 6.2)	Lecture
9/2	Labor day (no class)
9/4	Recursion (Part II, Sections 5.1, 5.2, 6.1)	Lecture
9/9	Dynamic programming (Part II, Section 5.3; Part III, Sections 1, 2)	Reading Lecture
9/11	Dynamic programming (Part III, Section 3)	Lecture	HW I due
9/16	Dynamic programming (Part III, Sections 4, 5.1)	Lecture	HW II out
9/18	Dynamic programming (Part I, Section 4; Part III, Sections 5.2, 5.3)	Lecture
9/23	Greedy algorithms (Part IV, Sections 1, 2, 3.1, 3.2)	Reading Lecture
9/25	Greedy algorithms (Part IV, Sections 3.3, 4.1)	Lecture
9/30	Greedy algorithms (Part IV, Sections 4.2, 5)	Lecture
10/2	Test 1 (in class)		HW II due
10/7	Graph algorithms (Part V, Sections 1, 2)	Reading Lecture	HW III out
10/9	Graph algorithms (Part V, Section 3)	Lecture
10/14	Graph algorithms (Part V, Sections 4.1, 5)	Lecture
10/16	Graph algorithms (Part V, Sections 4.2, 4.3)	Lecture	HW III due
10/21	Continuous algorithms (Part VI, Sections 1, 2)	Reading Lecture	HW IV out
10/23	Continuous algorithms (Part VI, Section 3)	Lecture
10/28	Continuous algorithms (Part VI, Section 4)	Lecture
10/30	Continuous algorithms (Part VI, Section 5)	Lecture
11/4	Randomized algorithms (Part VII, Sections 1, 2)	Reading Lecture	HW IV due
11/6	Randomized algorithms (Part VII, Section 3)	Lecture	HW V out
11/11	Randomized algorithms (Part VII, Section 4)	Lecture Notebook
11/13	Test 2 (in class)
11/18	Complexity theory (lecture by Trung Dang)	Reading Lecture
11/20	Complexity theory (lecture by Ryan Park)	Lecture	HW V due, HW VI out
11/25	Thanksgiving (no class)
11/27	Thanksgiving (no class)
12/2	Complexity theory	Lecture
12/4	Complexity theory	Lecture
12/9	Complexity theory	Reading Course Lecture	HW VI due
12/13	Final exam (PAI 2.48, 3:30 to 6:30 PM)

Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein). Available here.
Algorithms (Erickson). Available here.
Mathematics for Computer Science (Lehman, Leighton, and Meyer). Available here.
Algorithms (Kleinberg and Tardos). Available physically through the UT library.
Algorithms Illuminated (Roughgarden). Available for purchase here.

Please provide feedback on lectures or notes using the provided links.