Catalog Description: Computational applications of randomness and computational theories of randomness. Approximate counting and uniform generation of combinatorial objects, rapid convergence of random walks on expander graphs, explicit construction of expander graphs, randomized reductions, Kolmogorov complexity, pseudo-random number generation, semi-random sources.

Units: 3

Also Offered As: COMPSCI 271

Related Areas:

• Security (SEC)
• Theory (THY)

Prerequisites: 170 and at least one course numbered 270-279.

Formats:
Fall: 3.0 hours of lecture per week
Spring: 3.0 hours of lecture per week

Grading Basis: Student Option

Final Exam Status: No

---

Class Schedule (Fall 2026):
CS 271 – TuTh 09:30-10:59, The Gateway Building B1022 – Alistair J Sinclair

Class Notes
- This class assumes a solid undergraduate background in Mathematics (especially probability) and Algorithms. Suitably qualified PhD students in all departments, and MEng students in EECS, may enroll or waitlist. All others, including suitably qualified undergraduates, should email the instructor for permission to enroll. Priority enrollment is given to graduate students.

Links:

• EECS Course Archives (CalNet authentication required)
• CS enrollment policies
• EE enrollment policies
• HKN course maps