Design and Analysis of Algorithms

Download as PDF

Course Description

Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching. Prerequisite: 106B or 106X; 103 or 103B; 109 or STATS 116.

Grading Basis

ROP - Letter or Credit/No Credit

Min

3

Max

5

Course Repeatable for Degree Credit?

No

Course Component

Discussion

Enrollment Optional?

Yes

Course Component

Lecture

Enrollment Optional?

No

Courses

CS161 is a prerequisite for:
  • (from the following course set: )

Programs

CS161 is a completion requirement for:
  • (from the following course set: )
  • (from the following course set: )