CS 249A: ObjectOriented Programming from a Modeling and Simulation Perspective
Topics: largescale software development approaches for complex applications, class libraries and frameworks; encapsulation, use of inheritance and dynamic dispatch, design of interfaces and interface/implementation separation, exception handling, smart pointers and reference management, minimalizing dependencies and valueoriented programming. Inheritance: when and why multiple inheritance naming, directories, manager, and disciplined use of design patterns including functors, event notification and iterators. Prerequisites: C, C++, and programming methodology as developed in 106B or X, and 107 (107 may be taken concurrently). Recommended: 193D.
Terms: Aut

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Linton, M. (PI)
CS 254: Computational Complexity
An introduction to computational complexity theory. Topics include the P versus NP problem; diagonalization; space complexity: PSPACE, Savitch's theorem, and NL=coNL; counting problems and #Pcompleteness; circuit complexity; pseudorandomness and derandomization; complexity of approximation; quantum computing; complexity barriers. Prerequisites: 154 or equivalent; mathematical maturity.
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Williams, R. (PI)
CS 261: Optimization and Algorithmic Paradigms
Algorithms for network optimization: maxflow, mincost flow, matching, assignment, and mincut problems. Introduction to linear programming. Use of LP duality for design and analysis of algorithms. Approximation algorithms for NPcomplete problems such as Steiner Trees, Traveling Salesman, and scheduling problems. Randomized algorithms. Introduction to online algorithms. Prerequisite: 161 or equivalent.
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Roughgarden, T. (PI)
CS 262: Computational Genomics (BIOMEDIN 262)
Applications of computer science to genomics, and concepts in genomics from a computer science point of view. Topics: dynamic programming, sequence alignments, hidden Markov models, Gibbs sampling, and probabilistic contextfree grammars. Applications of these tools to sequence analysis: comparative genomics, DNA sequencing and assembly, genomic annotation of repeats, genes, and regulatory sequences, microarrays and gene expression, phylogeny and molecular evolution, and RNA structure. Prerequisites: 161 or familiarity with basic algorithmic concepts. Recommended: basic knowledge of genetics.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Batzoglou, S. (PI)
CS 263: Algorithms for Modern Data Models (MS&E 317)
We traditionally think of algorithms as running on data available in a single location, typically main memory. In many modern applications including web analytics, search and data mining, computational biology, finance, and scientific computing, the data is often too large to reside in a single location, is arriving incrementally over time, is noisy/uncertain, or all of the above. Paradigms such as mapreduce, streaming, sketching, Distributed Hash Tables, Bulk Synchronous Processing, and random walks have proved useful for these applications. This course will provide an introduction to the design and analysis of algorithms for these modern data models. Prerequisite: Algorithms at the level of
CS 261.
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Goel, A. (PI)
CS 264: Beyond WorstCase Analysis
This course is motivated by problems for which the traditional worstcase analysis of algorithms fails to differentiate meaningfully between different solutions, or recommends an intuitively "wrong" solution over the "right" one. This course studies systematically alternatives to traditional worstcase analysis that nevertheless enable rigorous and robust guarantees on the performance of an algorithm. 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 will be drawn from online algorithms, online learning, constraint satisfaction problems, graph partitioning, scheduling, linear programming, hashing, machine learning, and auction theory. Prerequisites:
CS161 (required). CS261 is recommended but not required.
Terms: Aut

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Roughgarden, T. (PI)
CS 266: Parameterized Algorithms and Complexity
An introduction to the area of parameterized algorithms and complexity, which explores multidimensional methods for measuring the difficulty and feasibility of solving computational problems. Topics include: fixedparameter tractability (FPT) and its characterizations, FPT algorithms for hard problems, the Whierarchy (W[1], W[2], W[P], and complete problems for these classes), and the relationships between parameterized questions and classical theory questions. Prerequisites:
CS 154 and 161 or the equivalent mathematical maturity.
Terms: Aut

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Williams, R. (PI)
CS 267: Graph Algorithms
An introduction to advanced topics in graph algorithms. Focusing on a variety of graph problems, the course will explore topics such as small space graph data structures, approximation algorithms, dynamic algorithms, and algorithms for special graph classes. Topics include: approximation algorithms for shortest paths and graph matching, distance oracles, graph spanners, cliques and graph patterns, dynamic algorithms, graph coloring, algorithms for planar graphs. Prerequisites: 161 or the equivalent mathematical maturity.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Williams, V. (PI)
CS 270: Modeling Biomedical Systems: Ontology, Terminology, Problem Solving (BIOMEDIN 210)
Methods for modeling biomedical systems and for making those models explicit in the context of building software systems. Emphasis is on intelligent systems for decision support and Semantic Web applications. Topics: knowledge representation, controlled terminologies, ontologies, reusable problem solvers, and knowledge acquisition. Recommended: exposure to objectoriented systems, basic biology.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Musen, M. (PI)
;
Mortensen, J. (TA)
CS 272: Introduction to Biomedical Informatics Research Methodology (BIOE 212, BIOMEDIN 212, GENE 212)
Handson software building. Student teams conceive, design, specify, implement, evaluate, and report on a software project in the domain of biomedicine. Creating written proposals, peer review, providing status reports, and preparing final reports. Guest lectures from professional biomedical informatics systems builders on issues related to the process of project management. Software engineering basics. Because the team projects start in the first week of class, attendance that week is strongly recommended. Prerequisites:
BIOMEDIN 210 or 211 or 214 or 217 or consent of instructor.
Terms: Spr

Units: 3

Grading: Medical Option (MedLtrCR/NC)
Instructors:
Altman, R. (PI)
Filter Results: