CS 349C: Topics in Programming Systems: Readings in Distributed Systems
Discussion of research publications that are of current interest in distributed systems. Students are expected to read all papers, and sign up for presentation of one paper. The course itself is 1 unit. Those interested in working on a project along with the readings should enroll for 3 units.
Terms: not given this year

Units: 13

Grading: Letter or Credit/No Credit
CS 358: Topics in Programming Language Theory
Topics of current research interest in the mathematical analysis of programming languages, structured operational semantics, domain theory, semantics of concurrency, rich type disciplines, problems of representation independence, and full abstraction. See Time Schedule or Axess for current topics. May be repeated for credit. Prerequisites: 154, 157, 258, or equivalents. (Staff)
Terms: offered occasionally

Units: 3

Repeatable for credit

Grading: Letter or Credit/No Credit
CS 359: Topics in the Theory of Computation
Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.
Terms: offered occasionally

Units: 3

Repeatable for credit

Grading: Letter or Credit/No Credit
CS 361A: Advanced Algorithms
Advanced data structures: unionfind, selfadjusting data structures and amortized analysis, dynamic trees, Fibonacci heaps, universal hash function and sparse hash tables, persistent data structures. Advanced combinatorial algorithms: algebraic (matrix and polynomial) algorithms, number theoretic algorithms, group theoretic algorithms and graph isomorphism, online algorithms and competitive analysis, strings and pattern matching, heuristic and probabilistic analysis (TSP, satisfiability, cliques, colorings), local search algorithms. May be repeated for credit. Prerequisite: 161 or 261, or equivalent.
Terms: not given this year

Units: 3

Repeatable for credit

Grading: Letter or Credit/No Credit
CS 361B: Advanced Algorithms
Topics: fundamental techniques used in the development of exact and approximate algorithms for combinational optimization problems such as generalized flow, multicommodity flow, sparsest cuts, generalized Steiner trees, load balancing, and scheduling. Using linear programming, emphasis is on LP duality for design and analysis of approximation algorithms; interior point methods for LP. Techniques for development of strongly polynomial algorithms. Prerequisites: 161 or 261, or equivalent.
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Plotkin, S. (PI)
CS 362: Algorithmic Frontiers: Effective Algorithms for Large Data
The increasing sizes of the data sets around us have sparked an effort from the theory community to develop new frameworks for understanding algorithms. In many cases, the questions have become "What can we compute in time sublinear in the size of data?" or "What can we compute if we are given only several passes over the data, with relatively little memory?". In a related vein, we are also facing the challenge of trying to understand extremely large, and complex objectsfrom social networks and gene interactions, to complex distributions over enormous domainsin these settings, we often only have access to a tiny fraction of the underlying object we hope to understand. What properties of graphs and distributions can be inferred from such sparse samples? The course will cover a variety of topics at this research frontier; topics will include the theoretical work on property testing, sampling, sketching, and streaming. Prerequisites: A good background in probability theory, linear algebra, and algorithms. A high level of mathematical maturity will be assumed.
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Valiant, G. (PI)
CS 364B: Topics in Algorithmic Game Theory
Topics on the interface of computer science and game theory. May be repeated for credit. Prerequisites: 364A or instructor permission.
Terms: Win

Units: 3

Repeatable for credit

Grading: Letter or Credit/No Credit
Instructors:
Roughgarden, T. (PI)
CS 369: Topics in Analysis of Algorithms
Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.
Terms: offered occasionally

Units: 3

Repeatable for credit

Grading: Letter or Credit/No Credit
CS 369N: Beyond WorstCase Analysis
Analysis of algorithms and problems for which worstcase complexity in uninformative. Topics include: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); averagecase analysis; robust distributional analysis; resource augmentation; planted and semirandom graph models. Motivating problems drawn from online algorithms, online learning, constraint satisfaction problems, graph partitioning, scheduling, linear programming, hashing, and auction theory.
Terms: not given this year

Units: 3

Grading: Letter or Credit/No Credit
CS 371: Computational Biology in Four Dimensions (CME 371)
Computational approaches to understanding the threedimensional spatial organization of biological systems and how that organization evolves over time. The course will cover cuttingedge research in both physicsbased simulation and computational analysis of experimental data, at scales ranging from individual molecules to entire cells. Prerequisite:
CS 106A or equivalent, and an introductory course in biology or biochemistry. Recommended: some experience in mathematical modeling (does not need to be a formal course).
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Dror, R. (PI)
Filter Results: