printer friendly pageCS 257: Introduction to Automated Reasoning
Automated logical reasoning has enabled substantial progress in many fields, including hardware and software verification, theorem-proving, and artificial in- telligence. Different application scenarios may require different automated rea- soning techniques and sometimes their combination. In this course, we will study widely-used logical theories as well as algorithms for answering whether formu- las in those theories are satisfiable. We will consider state-of-the-art automated reasoning techniques for propositional logic, first-order logic, and various first- order theories, such as linear arithmetic over reals and integers, uninterpreted functions, bit-vectors, and arrays. We will also consider ways to reason about combinations of those theories. Topics include: logical foundations, SAT-solving, techniques for first-order theorem proving, decision procedures for different first- order theories, theory combination, the DPLL(T) framework, and applications of automated reasoning in program analysis and hardware verification. Prerequisites: CS154 Introduction to the Theory of Computation, or CS106b Programming Abstractions and CS103 Mathematical Foundations of Computing, or consent of instructor
Terms: Aut
| Units: 3
CS 259Q: Quantum Computing
This course introduces the basics of quantum computing. Topics include: qubits, entanglement, and non-local correlations; quantum gates, circuits, and compilation algorithms; basic quantum algorithms such as Simon's algorithm and Grover's algorithm; Shor's factoring algorithm and the hidden subgroup problem; Hamiltonian simulation; stabilizer circuits, the Gottesman-Knill theorem, and the basics of quantum error correction. Prerequisites: Knowledge of linear algebra & discrete probability, and knowledge of algorithms OR quantum mechanics (or both)
Terms: Aut
| Units: 3
CS 261: Optimization and Algorithmic Paradigms
Algorithms for network optimization: max-flow, min-cost flow, matching, assignment, and min-cut problems. Introduction to linear programming. Use of LP duality for design and analysis of algorithms. Approximation algorithms for NP-complete problems such as Steiner Trees, Traveling Salesman, and scheduling problems. Randomized algorithms. Introduction to sub-linear algorithms and decision making under uncertainty. Prerequisite: 161 or equivalent.
Terms: Aut
| Units: 3
CS 263: Counting and Sampling
This course will cover various algorithm design techniques for two intimately connected class of problems: sampling from complex probability distributions and counting combinatorial structures. A large part of the course will cover Markov Chain Monte Carlo techniques: coupling, stationary times, canonical paths, Poincare and log-Sobolev inequalities. Other topics include correlation decay in spin systems, variational techniques, holographic algorithms, and polynomial interpolation-based counting. Prerequisites: CS161 or equivalent, STAT116 or equivalent.
Terms: Aut
| Units: 3
Instructors:
Anari, N. (PI)
;
Lecomte, V. (TA)
CS 265: Randomized Algorithms and Probabilistic Analysis (CME 309)
Randomness pervades the natural processes around us, from the formation of networks, to genetic recombination, to quantum physics. Randomness is also a powerful tool that can be leveraged to create algorithms and data structures which, in many cases, are more efficient and simpler than their deterministic counterparts. This course covers the key tools of probabilistic analysis, and application of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though we will apply this theory broadly, discussing applications in machine learning and data analysis, networking, and systems. Topics include tail bounds, the probabilistic method, Markov chains, and martingales, with applications to analyzing random graphs, metric embeddings, random walks, and a host of powerful and elegant randomized algorithms. Prerequisites:
CS 161 and STAT 116, or equivalents and instructor consent.
Terms: Aut
| Units: 3
Instructors:
Valiant, G. (PI)
;
Gurunathan, V. (TA)
;
Hanley, H. (TA)
...
more instructors for CS 265 »
Instructors:
Valiant, G. (PI)
;
Gurunathan, V. (TA)
;
Hanley, H. (TA)
;
Pabbaraju, C. (TA)
;
Villa-Renteria, I. (TA)
CS 274: Representations and Algorithms for Computational Molecular Biology (BIOE 214, BIOMEDIN 214, GENE 214)
BIOMEDIN 214: Representations and Algorithms for Computational Molecular Biology (
BIOE 214,
CS 274,
GENE 214)Topics: This is a graduate level introduction to bioinformatics and computational biology, algorithms for alignment of biological sequences and structures, BLAST, phylogenetic tree construction, hidden Markov models, basic structural computations on proteins, protein structure prediction, molecular dynamics and energy minimization, statistical analysis of 3D structure, knowledge controlled terminologies for molecular function, expression analysis, chemoinformatics, pharmacogenetics, network biology. Lectures are supplemented with assignments and programming projects, which allow students to implement important computational biology algorithms. Firm prerequisite:
CS 106B. NOTE: For students in the Department of Biomedical Data Science Program, this core course MUST be taken as a letter grade only.
Terms: Aut
| Units: 3-4
CS 279: Computational Biology: Structure and Organization of Biomolecules and Cells (BIOE 279, BIOMEDIN 279, BIOPHYS 279, CME 279)
Computational techniques for investigating and designing the three-dimensional structure and dynamics of biomolecules and cells. These computational methods play an increasingly important role in drug discovery, medicine, bioengineering, and molecular biology. Course topics include protein structure prediction, protein design, drug screening, molecular simulation, cellular-level simulation, image analysis for microscopy, and methods for solving structures from crystallography and electron microscopy data. Prerequisites: elementary programming background (
CS 106A or equivalent) and an introductory course in biology or biochemistry.
Terms: Aut
| Units: 3
Instructors:
Dror, R. (PI)
;
Bresette, L. (TA)
;
Li, D. (TA)
;
McAvity, J. (TA)
;
Sayana, R. (TA)
;
Suriana, P. (TA)
;
Xu, J. (TA)
CS 293: Empowering Educators via Language Technology (EDUC 473)
This course explores the use of natural language processing (NLP) to support educators, by discovering, measuring, and analyzing high-leverage teaching practices. Topics include computational social science methods, ethics, bias and fairness, automated scoring, causal analyses, large language models, among others. Engaging with relevant papers, students will work towards a final project using NLP methods and a critical social scientific lens. Projects are pitched to a jury of educators at the end of the course.
Terms: Aut
| Units: 2-4
Instructors:
Demszky, D. (PI)
;
Wang, R. (TA)
CS 298: Seminar on Teaching Introductory Computer Science (EDUC 298)
Faculty, undergraduates, and graduate students interested in teaching discuss topics raised by teaching computer science at the introductory level. Prerequisite: consent of instructor.
Terms: Aut
| Units: 1
Instructors:
Gregg, C. (PI)
CS 300: Departmental Lecture Series
Priority given to first-year Computer Science Ph.D. students. CS Masters students admitted if space is available. Presentations by members of the department faculty, each describing informally his or her current research interests and views of computer science as a whole.
Terms: Aut
| Units: 1
Instructors:
Reingold, O. (PI)
Filter Results: