Course Websites

CS 473 - Algorithms

Last offered Fall 2008

Official Description

Advanced data structures, graph algorithms, arithmetic algorithms, geometric algorithms, string problems, parallel algorithms, NP-completeness. Course Information: Same as CSE 414 and MATH 473. 3 undergraduate hours. 3 or 4 graduate hours. Prerequisite: CS 225 and CS 373. Class Schedule Information: Students must register for a lecture and a discussion section.

Related Faculty

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.

TitleSectionCRNTypeHoursTimesDaysLocationInstructor
AlgorithmsAD151491DIS01700 - 1750 T  1111 Siebel Center for Comp Sci Chandra Chekuri
Amir Nayyeri
Charles A Blatti, III
Hemanta Kumar Maji
AlgorithmsAD251492DIS01800 - 1850 T  1111 Siebel Center for Comp Sci Chandra Chekuri
Amir Nayyeri
Charles A Blatti, III
Hemanta Kumar Maji
AlgorithmsAD351493DIS01400 - 1450 W  1111 Siebel Center for Comp Sci Chandra Chekuri
Amir Nayyeri
Charles A Blatti, III
Hemanta Kumar Maji
AlgorithmsAD451494DIS01500 - 1550 W  1111 Siebel Center for Comp Sci Chandra Chekuri
Amir Nayyeri
Charles A Blatti, III
Hemanta Kumar Maji
AlgorithmsAL143365LCD31100 - 1215 T R  1404 Siebel Center for Comp Sci Chandra Chekuri
AlgorithmsNPV50495ONL0 -    Chandra Chekuri
AlgorithmsONL50457ONL0 -    Chandra Chekuri