CS 473

CS 473 - Algorithms

Spring 2025

Title	Rubric	Section	CRN	Type	Hours	Times	Days	Location	Instructor
Algorithms	CS473	AL2	31552	LEC	4	1230 - 1345	W F	1310 Digital Computer Laboratory	Timothy Moon-Yew Chan
Algorithms	CS473	ALU	31457	LEC	4	1230 - 1345	W F	1310 Digital Computer Laboratory	Timothy Moon-Yew Chan
Algorithms	CS473	CSP	31548	PKG	4	-			Mahesh Viswanathan
Algorithms	CS473	CSP	31548	PKG	4	1700 - 1815	R	ARR Illini Center	Mahesh Viswanathan
Algorithms	CS473	MCS	31558	PKG	4	1700 - 1815	R	ARR Illini Center	Mahesh Viswanathan
Algorithms	CS473	MCS	31558	PKG	4	-			Mahesh Viswanathan
Algorithms	CSE414	ALG	58767	LEC	4	1230 - 1345	W F	1310 Digital Computer Laboratory
Algorithms	CSE414	ALU	31560	LEC	4	1230 - 1345	W F	1310 Digital Computer Laboratory	Timothy Moon-Yew Chan
Algorithms	MATH473	ALG	58768	LEC	4	1230 - 1345	W F	1310 Digital Computer Laboratory
Algorithms	MATH473	ALU	31577	LEC	4	1230 - 1345	W F	1310 Digital Computer Laboratory	Timothy Moon-Yew Chan

See full schedule from Course Explorer

Web Page

https://courses.grainger.illinois.edu/cs473/sp2023/

Official Description

Design and analysis techniques, approximation algorithms, randomized algorithms and amortized analysis, and advanced topics such as network flow, linear programming, and dynamic data structures, among others. Course Information: Same as CSE 414 and MATH 473. 4 undergraduate hours. 4 graduate hours. Prerequisite: CS 374 or ECE 374, and one of CS 361, STAT 361, ECE 313, MATH 362, MATH 461, MATH 463 or STAT 400.

Course Director

Chandra Sekhar Chekuri
Jeff G Erickson

Learning Goals

Know definitions of "core computational problems" and be able to describe various algorithms and their time and space complexities for such problems. (1,6)

Be able to abstract key computational elements and challenges from newly encountered problems in different domains, and identify when known algorithms or variants thereof may be employed to find a solution. (1,6)

Be able to design new algorithms using a variety of algorithmic approaches, including brute force, greedy, recursion, divide-and-conquer, dynamic programming, randomization, etc. (1,6)

Be able to use appropriate data structures such as arrays, linked lists, BSTs, heaps, hash tables, adjacency matrices or lists, etc, to solve problems efficiently. (1,6)

Be able to analyze the (worst case, randomized, amortized) time and space complexity of given algorithms using techniques such as loop summations, recurrences, charging arguments, potential functions, properties of probability. (1,6)

Be able to reason formally about problem difficulty using reductions, adversary arguments, decision trees, and similar techniques. (1,6)

More generally, be able to communicate and reason about computation clearly, formally, and concisely. (3,5)

Topic List

NP Completeness.

Dynamic Programming

Divide and Conquer and FFT

Randomized algorithms, analysis, and applications

Network flows, matchings and applications

Linear programming

Approximation algorithms

Additional topics vary

Assessment and Revisions

Revisions in last 6 years	Approximately when revision was done	Reason for revision	Data or documentation available?
Reduced written homework, added online quizzes testing more basic material	Spring 2011	The instructors recognized that many students were struggling with basic material, such as the behavior of algorithms presented in class, which is necessary to make progress on the homework. Automatically graded online quizzes were introduced as an experimental measure to attempt to address this gap. Promising initial results led us to make the addition permanent.	Informal discussion
Removed oral homework grading	Spring 2011	insufficient staffing to support increasing class sizes	Informal discussion

Required, Elective, or Selected Elective

Selected Elective.

Last updated

3/9/2019