
Computer Science 111
Computers & Computing
Sanjeev Arora

Spring 2004

Back to course home page.
Course outline (tentative):
 Lectures 15. What is a computer? What is an algorithm? How to express an algorithm
even if you don't know a programming language. How to evaluate an algorithm.
 Lectures 6,7. What can a computer not do? Is it possible to build a fundamentally
different computer from the ones today? ChurchTuring thesis.
Unsolvability of the halting problem. Lessons from that proof.
 Lectures 8, 9: Boolean logic. How Greeks tried to formalize thought, and how their logic
permeates modern technology (and standardized tests). A "proof" of the existence
of God. Faster Google searches via logic.
 Lectures 1013: The architecture of a digital computer: logic gates, flipflops, and
memory. How they are put together in the microprocessor.
 Lectures 1416: Golden rules of computer design: abstraction, virtualization,
hierarchies. Illustrated using examples from operating systems, distributed systems, and
the internet (world wide web)
 Lecture 17: Computer graphics: an introduction to the geewhiz world of computer games
and Hollywood digital effects.
 Lecture 18: Computer music.
 Lectures 1921: Artificial intelligence. Programs that learn. Can robots think?
The mindbody problem and the hard problem of consciousness.
 Lectures 2223: Cryptography. RSA and other cryptosystems. Computer Security. Should
cryptography be restricted?
 Lecture 24: Computers in the scientific world
Schedule and Readings
(Handouts are in Adobe pdf format. To view them you should have Acrobat Reader
installed; download here.
 Lecture 1: What is a computer? What is an algorithm? How to express an algorithm
(pseudocode). Finding the lowest price shampoo on a supermarket shelf. Handout1; Lecture notes (partial);
Reading assignment for Lecture 2. There was a handout on how
to write pseudocode; pages 3053 of An invitation to computer science by
Schneider and Gersting.
Optional reading (for those who're interested): Scientific American article on Lady Ada Lovelace, the first computer
programmer. The article also contains a photo of Charles Babbage's difference engine.
 Lecture 2: More examples of algorithms and pseudocode: sorting. Bubblesort. Reading assignment for Lec 3.
 Lecture 3: Issues of efficiency. Binary search: an efficient way to search through a
phonebook or dictionary. How to
measure the "running time" of an algorithm. Reading/discussion
points for Lec 4
 Lecture 4: Continuing discussion of efficiency. Analysis of running times of bubblesort
and binary search.
Introduction to quicksort. Reading/discussion points for Lec 5.
handout for lecture 5: First four pages of Brian Hayes's article "Computer
Recreations: The cellular automaton offers a model of the world and a world unto
itself." Scientific American, March 1984, pages 1221.
 Lecture 5. Finish quicksort (cursory introduction to recursion). Discussion of how to
run simulations on a computer. Conway's Game of Life and what it teaches us. Pseudocode
for simulating "Life."
Discussion points for Lec 6. Handout: ``What is a
computation?'' by Martin Davis, from Mathematics Today:
Twelve Informal Essays (L.A. Steen, Ed.), Springer Verlag, 1978, pp. 241267.
 Lecture 6. Finished discussion of simulation and cellular automata. Saw snowflake
pictures on the web, Game
of Life simulations, and a simulation of a tornado .
Discussed Turing machines: why they were invented, what they are. ChurchTuring thesis.
Universal Machines. Discussion points for lecture 7.
 Proof that the Halting Problem is unsolvable on a computer. Some discussion of
significance of Turing's work: the fluid boundary between program, data and hardware. Discussion points for lecture 8. Handout on boolean logic:
pages 116125 of Computer Science: A breadthfirst approach with C by J.
Impagliazzo and P. Nagin, John Wiley 1995.
 Wind up discussion of TMs and computation. (Illustrative examples: the genetic code,
Java Virtual Machine, Game of Life.) Begin discussion of hardware and boolean logic.
Boole's arithmetic. Handouts: page 38 from The Universal Computer by Martin
Davis (Boole's formalization of Clarke's proof of God's existence), pages 152165 from An
invitation to computer science by Schneider and Gersting (binary arithmetic and
circuits for this task). Discussion points for lecture 9.
 Faster internet searches using logical operators. Discussion of Boole's reworking of
Clarke's proof of God's existence. Circuit simplification using Boole's arithmetic. nbit
adder.Discussion points for lecture 10.
 Discussion of binary addition and nbit adder. Control circuits: multiplexor and
decoder. Begin discussion of feedback in circuits and how it can lead to
"memory." Discussion points for lecture 11.
Handout on Flipflops and RAM (excerpted from past
COS111 lecture notes by Prof. JP Singh).
 Feedback in boolean circuits and how it leads to memory. Flipflops of various sorts. RAM
and how to "address" into it. Clocked circuits.
Handouts: Discussion points for lecture 12. 3 pages of
Brian Hayes's article on Finite State machines from Scientific American, Dec 1983. Handout1 and handout 2 on CPU
organization, excerpted from CS111 lecture notes by Prof J. P. Singh.
 Discussion of Finite State machines and how they are implemented. Discussion points for lecture 13.
 CPU organization and machine language. How to translate normal pseudocode into machine
language and some discussion of the issues involved. Discussion
points for Lecture 15 (multitasking).
 Guest lecture on Computer Music: Prof Perry
Cook.
 Multitasking and how computers (and humans!) pull it off. Discussion
points for lecture 16. Reading for next lecture: How caching works by Guy
Provost and How
operating systems work by Curt Franklin.
 Memory hierarchy. Caching and virtual memories. The Exhausted Librarian problem. Dicussion points for lecture 17. Reading for next
lecture: How
internet infrastructure works.
 Internet infrastructure. A postal system for armies of medieval Europe. Anatomy 101:
Dissecting a computer. (Wear scrubs to class.) Discussion
points for lecture 18.
 Computationally difficult problems. Harmonius dorm floor, Clique, and Final Exam
Scheduling. NPcompleteness.
 (April 13) Guest lecture by Prof. Avi Wigderson
of IAS: The digital envelope (a crash course in modern cryptography). Discussion points for lecture 20. Readings: Brian Hayes,
``Turing's Test'' (Muse, Vol. 2, No. 2, 1819 April 1998); a few photocopied
pages on computer vision; edge detection algorithm
(excerpts from old lecture notes by Profs. Dobkin and Sahai)
 Introduction to AI. Turing's test for intelligence and some discussion of its strengths
and flaws. Case study of current research in AI: computer vision. Reading for next
lecture: How computer security works by Cheswick and Bellovin. (Go to Scientific American Archive and use the search
term "computer security works".)
 (April 20) Guest lecturer: Prof. Ed
Felten. Viruses and Worms
 (April 22): Continuation of discussion on AI and machine learning. Guest lecturer: Prof.
Sanjeev Kulkarni. Reading
for lecture 23 (Hypersearching the web). Discussion points
for lecture 23.
 (April 27) What we can learn from the internet and how. Lecture on internet
searching and related topics. Guest lecturer: Prof. Jon Kleinberg of Cornell.
 (April 29) A freewheeling class discussion. How human can computers be? Searle's
objection to AI. The hard problem of consciousness.
The Captcha approach: even if AI fails, there are
reasons to be happy.
Final Exam is here. Do not read it until you
are ready to work on it. It has to be finished within 12 hours after you start reading it.
It is due in Prof. Arora's office (307 in the Computer Science Building) by 5pm on Friday
May 14.
Problem sets
 HW1 due Thurs Feb 12.
 HW2 due Thurs Feb 19.
 HW3 due Thurs Feb 26.
 HW4 due Thurs March 4.
 HW5 due Thurs March 11.
 HW 6 due Thurs April 1.
 HW 7 due Thurs April 8.
 HW 8 due Thurs April 15.
 HW9 due Thurs April 22.
 HW10 due Thurs April 29
Lab Assignments
 Lab 1 due Friday, February 13, 5:00 PM
 Lab 2 due Friday, February 20, 5:00 PM
 Lab 3 due Friday, February 27, 5:00 PM
 Lab 4 due Friday, March 5, 5:00 PM
 Lab 5 due Friday, April 2, 5:00 PM
 Lab 6 due Friday, April 9, 5:00 PM<
 Lab 7 due Friday, April 16, 5:00 PM
 Lab 8 due Friday, April 23, 5:00 PM