printer friendly pageCS 161: Design and Analysis of Algorithms
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: 103 or 103B; 109 or
STATS 116.
Terms: Aut, Spr, Sum
| Units: 3-5
| UG Reqs: GER:DB-EngrAppSci, WAY-FR
CS 166: Data Structures
Techniques in the design, analysis, and implementation of data structures. Isometries between data structures (including red/black trees and 2-3-4 trees), amortized analysis (including Fibonacci heaps and splay trees), and randomization (including count-min sketches and dynamic perfect hash tables). Data structures for integers and strings (including van Emde Boas trees and suffix trees). Possible additional topics include functional data structures, concurrent data structures, and spatial data structures. Prerequisites: CS107 and
CS161.
Terms: Spr
| Units: 3-4
Instructors:
Schwarz, K. (PI)
CS 167: Readings in Algorithms
Recent research in the design and analysis of algorithms. Readings cover both classical and emerging topics, such as: computational models for massive data sets; data privacy; dimensionality reduction; exact and approximate algorithms for NP-hard problems; graph algorithms; hashing; online learning; search trees; streaming and sketching. Students are expected to respond to research papers, deliver an oral presentation, and complete a reading or programming project. Limited enrollment; preference given to undergraduates. Prerequisites:
CS161.
Terms: Spr
| Units: 3
Instructors:
Roughgarden, T. (PI)
CS 161L: Implementation of Algorithms
Optional companion course to
CS 161; provides an opportunity to practice implementing algorithms covered in the lectures and problem sets of
CS 161. Students learn implementation details, distinguish practical runtime from asymptotic runtime, and explore the tradeoff between code complexity and runtime complexity. Students are expected to be proficient in either C++ or Java at the 106 level.
Instructors:
Nguyen, A. (PI)
Filter Results: