Back to course home page.

Course outline (tentative):

• Lectures 1--5. 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? Church-Turing 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 10--13: The architecture of a digital computer: logic gates, flip-flops, and memory. How they are put together in the microprocessor.
• Lectures 14--16: 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 gee-whiz world of computer games and Hollywood digital effects.
• Lecture 18: Computer music.
• Lectures 19--21: Artificial intelligence. Programs that learn. Can  robots think? The mind-body problem and the hard problem of consciousness.
• Lectures 22--23: 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.

1. 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 30-53 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.
2. Lecture 2: More examples of algorithms and pseudocode: sorting. Bubblesort. Reading assignment for Lec 3.
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
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 12-21.
5. 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. 241--267.
6. 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. Church-Turing thesis. Universal Machines. Discussion points for lecture 7.
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 116--125 of Computer Science: A breadth-first approach with C by J. Impagliazzo and P. Nagin, John Wiley 1995.
8. 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 152--165 from An invitation to computer science by Schneider and Gersting (binary arithmetic and circuits for this task). Discussion points for lecture 9.
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. n-bit adder.Discussion points for lecture 10.
10. Discussion of binary addition and n-bit 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).
11. 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.
12. Discussion of Finite State machines and how they are implemented. Discussion points for lecture 13.
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).
14. Guest lecture on Computer Music: Prof Perry Cook.
15. 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.
16. Memory hierarchy. Caching and virtual memories. The Exhausted Librarian problem. Dicussion points for lecture 17. Reading for next lecture:  How internet infrastructure works.
17. Internet infrastructure. A postal system for armies of medieval Europe. Anatomy 101: Dissecting  a computer. (Wear scrubs to class.) Discussion points for lecture 18.
18. Computationally difficult problems. Harmonius dorm floor, Clique, and Final Exam Scheduling. NP-completeness.
19. (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, 18-19 April 1998); a few photocopied pages on computer vision; edge detection algorithm (excerpts from old lecture notes by Profs. Dobkin and Sahai)
20. 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".)
21. (April 20) Guest lecturer: Prof. Ed Felten. Viruses and Worms
22. (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.
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.
24. (April 29) A free-wheeling 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

1. HW1 due Thurs Feb 12.
2. HW2 due Thurs Feb 19.
3. HW3 due Thurs Feb 26.
4. HW4 due Thurs March 4.
5. HW5 due Thurs March 11.
6. HW 6 due Thurs April 1.
7. HW 7 due Thurs April 8.
8. HW 8 due Thurs April 15.
9. HW9 due Thurs April 22.
10. 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