Princeton University
Computer Science Department

Computer Science 116
The Computational Universe

Sanjeev Arora

Spring 2006

General Information | Readings | Handouts | Assignments | Labs | Extras | Videos

MIDTERM AVAILABLE HERE [Graders: Dave (Q1-Q5) and Umar (Q6-Q9)]

Course Summary

Computers have brought the world to our fingertips. We will try to understand at a basic level the science -- old and new -- underlying this new Computational Universe. Our quest takes us on a broad sweep of scientific knowledge and related technologies: propositional logic of the ancient Greeks (microprocessors); quantum mechanics (silicon chips); network and system phenomena (internet and search engines); computational intractability (secure encryption); and efficient algorithms (genomic sequencing). Ultimately, this study makes us look anew at ourselves -- our genome; language; music; "knowledge"; and, above all, the mystery of our intelligence.

This course satisfies Princeton's Science and Technology (with Lab) Distribution requirement.


Administrative Information

Lectures: Tues and Thurs, 1:30pm - 2:50pm, 16 Robertson Hall

Professor: Sanjeev Arora, 307 CS Building, 258-3869,

Teaching Assistants: J. Alex Halderman (Head TA), Umar Syed and David Xiao

Course staff email: (Please use this address to contact the course staff)

Office Hours:
Prof. Arora: Tue 3 - 4pm, Fri 1:15 - 2:15pm, CS 307
Umar: Wed 4:30 - 6pm, CS 001C
Dave: Thu 3 - 4:30pm, CS 103B

Umar: Mon 6:15 - 7pm, Friend 005
Dave: Tue 6:15 - 7pm, Friend 005

Session 1: Mon 7pm - 10pm, Friend 005
Session 2: Tue 7pm - 10pm, Friend 005
Session 3: Wed 1:30pm - 4:20pm, Friend 005

Course blog:


Lab reports and homeworks are due in the appropriately marked box at the start of lecture. Lab reports on Tuesday the week after the lab was finished. Homeworks on Thursdays, collected in the same fashion. Please do not send us emailed reports and homework---we cannot handle the email volume. (Please ignore any instructions to the contrary you may have been given by mistake. We will try to process anything you already emailed us, but it will be safest if you also print it out and put it in the bin on the due date.)

Extensions will be available if you send email to before the assignment/lab is due, explaining the circumstance that necessitates it. (Illness, absences due to sports, etc., must be documented with a note/email from a college administrator or suitable official.) Otherwise late homeworks/reports will receive  50% of the points (or even less if very late).

Missed a lab? Please try to make it up during another scheduled session the same week. If there is a reason you cannot attend any lab session during that week, please send email to explaining the circumstance and we will work out an alternative arrangement.

Collaboration policy: You may discuss the labs and assignments with other students, and you may ask for help from the professor or the TAs. However, you are not allowed to copy another student’s programs or answers. Any violations will be reported.

Course Plan (tentative)


Lecture Topic

Lab topic


Intro: Computer science, a new way of looking at the world.
(CS is not just Programming!) slides

Blogs and HTML

Telling a robot how to behave. slides


Telling a computer how to behave. (Via pseudocode). slides

Introduction to Pseudocode

“Everything’s a number.”
(Simulation. Creating new worlds. Games and Life.) slides


“It ain’t no good if it ain’t snappy enough.”
 (Efficient computations; viewing the world via efficiency.) slides

Controlling the Robot I

“It sure is clever, but can it swing?” (Computer music.) slides


"Seek and Ye shall find."  (The continuum of computer “intelligence”.) slides

Digital Sound and Music

What is a computation? The fluid boundary between program and data. slides


Universal machines. What computers just cannot do. slides

Controlling the Robot II

Self-reproducing programs. Introduction to logic. slides


Logic: From Greeks to philosophers to circuits. slides 

No lab session. Instead, Blogging Assignment 3

More Boolean logic and combinational circuits; Boolean circuits and memory. slides


Sequential and clocked circuits; Finite state machines. slides

Digital Logic I

Computer organization: CPUs and RAM. slides


How to streamline your life (Lessons from computer architecture). slides

Lab cancelled.

What computers talk about and how. (Networking & the Internet.) slides


The science that drives modern computers. slides

Digital Logic II: Sequential and Synchronous Circuits

How can computers help cure cancer?
(Computational biology and bioinformatics) slides


What is the computational cost of automating brilliance or serendipity?
(P vs NP question and related musings) slides

Internet Structure and Congestion Control

Secrets and Lies, Knowledge and Trust. (Modern cryptography.) slides


Viruses, worms, zombies, and other beasties. slides

 Special precept, and a Turing Test.

Self-improvement for dummies. (Machine Learning.) slides


Can machines think? (A rigorous examination of Searle's objection.) slides

Virus and Worm Propagation in Networks

 What have we learnt in this course? slides