# CS 473

## CS 473 - Algorithms

### Fall 2021

TitleRubricSectionCRNTypeHoursTimesDaysLocationInstructor
AlgorithmsCS473S470159LCD41530 - 1645 T R  1404 Siebel Center for Comp Sci Sariel Har-Peled
AlgorithmsCS473S4G72165LCD41530 - 1645 T R  1404 Siebel Center for Comp Sci Sariel Har-Peled
AlgorithmsCSE414S470170LCD41530 - 1645 T R  1404 Siebel Center for Comp Sci Sariel Har-Peled
AlgorithmsCSE414S4G72228LCD41530 - 1645 T R  1404 Siebel Center for Comp Sci Sariel Har-Peled
AlgorithmsMATH473S470172LCD41530 - 1645 T R  1404 Siebel Center for Comp Sci Sariel Har-Peled
AlgorithmsMATH473S4G72229LCD41530 - 1645 T R  1404 Siebel Center for Comp Sci Sariel Har-Peled

### 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, and one of CS 361, MATH 461, or STAT 400.

### 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