CS 243: Program Analysis and Optimizations
Program analysis techniques used in compilers and software development tools to improve productivity, reliability, and security. The methodology of applying mathematical abstractions such as graphs, fixpoint computations, binary decision diagrams in writing complex software, using compilers as an example. Topics include data flow analysis, instruction scheduling, register allocation, parallelism, data locality, interprocedural analysis, and garbage collection. Prerequisites: 103 or 103B, and 107.
Terms: Win

Units: 34

Grading: Letter or Credit/No Credit
Instructors:
Lam, M. (PI)
CS 246: Mining Massive Data Sets
Availability of massive datasets is revolutionizing science and industry. This course discusses data mining and machine learning algorithms for analyzing very large amounts of data. The focus is on algorithms and systems for mining big data. nTopics include: Big data systems (Hadoop, Spark, Hive); Link Analysis (PageRank, spam detection, hubsandauthorities); Similarity search (localitysensitive hashing, shingling, minhashing, random hyperplanes); Stream data processing; Analysis of socialnetwork graphs; Association rules; Dimensionality reduction (UV, SVD, and CUR decompositions); Algorithms for verylargescale mining (clustering, nearestneighbor search); Largescale machine learning (gradient descent, supportvector machines, classification, and regression); Submodular function optimization; Computational advertising. Prerequisites: At least one of CS107 or
CS145.
Terms: Win

Units: 34

Grading: Letter or Credit/No Credit
Instructors:
Leskovec, J. (PI)
CS 246H: Mining Massive Data Sets Hadoop Lab
Supplement to
CS 246 providing additional material on Hadoop. Students will learn how to implement data mining algorithms using Hadoop, how to implement and debug complex MapReduce jobs in Hadoop, and how to use some of the tools in the Hadoop ecosystem for data mining and machine learning. Topics: Hadoop, MapReduce, HDFS, combiners, secondary sort, distributed cache, SQL on Hadoop, Hive, Cloudera ML/Oryx, Mahout, Hadoop streaming, implementing Hadoop jobs, debugging Hadoop jobs, TFIDF, Pig, Sqoop, Oozie, HBase, Impala. Prerequisite:
CS 107 or equivalent.
Terms: Win

Units: 1

Grading: Satisfactory/No Credit
Instructors:
Leskovec, J. (PI)
;
Templeton, D. (PI)
CS 247: HumanComputer Interaction Design Studio
Projectbased focus on interaction design process, especially earlystage design and rapid prototyping. Methods used in interaction design including needs analysis, user observation, sketching, concept generation, scenario building, and evaluation. Prerequisites: 147 or equivalent background in design thinking; 106B or equivalent background in programming. This course takes place entirely in studios; enroll in a studio section with an instructor.
Terms: Win, Spr

Units: 34

Grading: Letter (ABCD/NP)
CS 248: Interactive Computer Graphics
This course provides a comprehensive introduction to interactive computer graphics, focusing on fundamental concepts and techniques, as well as their crosscutting relationship to multiple problem domains in interactive graphics (such as rendering, animation, geometry, image processing). Topics include: 2D and 3D drawing, sampling theory, interpolation, rasterization, image compositing, the realtime GPU graphics pipeline (and parallel rendering), VR rendering, geometric transformations, curves and surfaces, geometric data structures, subdivision, meshing, spatial hierarchies, image processing, time integration, physicallybased animation, and inverse kinematics. The course will involve several indepth programming assignments and a selfselected final project that explores concepts covered in the class. Prerequisite:
CS 107,
MATH 51.
Terms: Win

Units: 34

Grading: Letter or Credit/No Credit
Instructors:
Fatahalian, K. (PI)
CS 250: Algebraic Error Correcting Codes (EE 387)
Introduction to the theory of error correcting codes, emphasizing algebraic constructions, and diverse applications throughout computer science and engineering. Topics include basic bounds on error correcting codes; ReedSolomon and ReedMuller codes; listdecoding, listrecovery and locality. Applications may include communication, storage, complexity theory, pseudorandomness, cryptography, streaming algorithms, group testing, and compressed sensing. Prerequisites: Linear algebra, basic probability (at the level of, say,
CS109, CME106 or
EE178) and "mathematical maturity" (students will be asked to write proofs). Familiarity with finite fields will be helpful but not required.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Wootters, 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: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Tan, L. (PI)
CS 255: Introduction to Cryptography
For advanced undergraduates and graduate students. Theory and practice of cryptographic techniques used in computer security. Topics: encryption (symmetric and public key), digital signatures, data integrity, authentication, key management, PKI, zeroknowledge protocols, and realworld applications. Prerequisite: basic probability theory.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Boneh, D. (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 sublinear algorithms and decision making under uncertainty. Prerequisite: 161 or equivalent.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Goel, A. (PI)
CS 270: Modeling Biomedical Systems: Ontology, Terminology, Problem Solving (BIOMEDIN 210)
Methods for modeling biomedical systems and for building modelbased 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. Students learn about current trends in the development of advanced biomedical software systems and acquire handson experience with several systems and tools. Prerequisites:
CS106A, basic familiarity with biology, probability, and logic.
Terms: Win

Units: 3

Grading: Letter or Credit/No Credit
Filter Results: