Computer Science 109:
Computers in Our World

Fall 2009
Princeton University

Brian Kernighan
Computer Science Dept.

Mon Jan 25 15:33:30 EST 2010

final answers   (also on Blackboard if you have trouble with access)

Summary of what we covered

Old exams (also on Blackboard):    2008 final     (answers)     2007 final     (answers)    

Lecture notes:    9/21    9/23    9/28-30    10/5-7    10/12    10/14    10/19    10/21    10/26-28    11/9    11/11    11/16    11/18    11/23-30    12/2    12/7-9    12/9-14    12/16   

Problem sets:    1     2     3     4     5     6     7     8    

Solutions:    1     2     3     4     5     6     7     8   

Labs:    1     2     3     4     5     6     7     8    

Old stuff:    playlist     lab schedule and rooms     survey results     Recaptcha     Unicode code charts     video with lots of numbers     Andrew's Mac programs     Nobel prize in physics     lots of colors!     binary converter     learning about binary numbers     Lab 2 pages     Toy simulator     Javascript examples     Lab 4 web pages     2008 midterm     (answers)     2007 midterm     (answers)     2009 midterm answers     final exam schedule     Happy birthday, Internet     GNU GPL     Spring courses     Intel 4004     The Feeling of Power     Lab 6 grades     public-key crypto in the comics     Babbage in the news     ATM checksum     MP3 explanation     network neutrality    

Problem sets, labs and announcements will be posted only on the web page.

You are responsible for monitoring the web page frequently.

Course summary, schedule and syllabus     What was covered in 2008
Comparison of COS 109, 116 and 126   Office hours   Labs   Problem Sets   Exams   Lateness Policy   Collaboration Policy   Textbook   Bibliography

Course Summary

Computers, computing, and many things enabled by them are all around us. Some of this is highly visible, like laptops, phones and the Internet; much is invisible, like the computers in gadgets and appliances and cars, or the programs that fly our planes and keep our telephones and power systems and medical equipment working, or the myriad systems that quietly collect and share personal data about us.

Even though most people will not be directly involved with creating such systems, everyone is strongly affected by them. COS 109 is intended to provide a broad, if rather high level, understanding of how computer hardware, software, networks, and systems operate. Topics will be motivated by current events and concerns, and will include discussion of how computers work; what programming is and why it is hard; how the Internet and the Web operate; and how all of these affect security, privacy, property and other issues. We will also touch on fundamental ideas from computer science, and some of the inherent limitations of computers.

This course is meant for humanities and social sciences students who want to understand how computing works and how it affects the world they live in. No prior experience with computers is assumed, and there are no prerequisites. COS 109 satisfies the QR requirement.

The labs are complementary to the classroom work, though intended to reinforce the basic ideas. They will cover a spectrum of practical applications; two of the labs are a gentle introduction to programming in Javascript.

The course will have fundamentally the same structure as in previous years, but lectures, case studies and examples change every year according to what's happening. More and more of our private lives are observed and recorded by business and government, sometimes with our knowledge and consent. Microsoft and Google are duking it out with each other on technical and legal fronts, and with a variety of governments. Skirmishes in the forever war between students and the entertainment industry affect Princeton students all the time. The careless, the clueless, and the criminal continue to do bad things with technology. What could possibly go wrong? Come and find out.

Schedule 

	 S  M Tu  W Th  F  S
Sep	20 21 22 23 24 25 26	first class
	27 28 29 30	
Oct	             1  2  3	problem set 1 due; lab 1 due
	 4  5  6  7  8  9 10	problem set 2 due; lab 2 due
	11 12 13 14 15 16 17	problem set 3 due; lab 3 due
	18 19 20 21 22 23 24	problem set 4 due; lab 4 due
	25 26 27 28 29 30 31	takehome midterm due 5pm (no lab or problem set)
Nov	 1  2  3  4  5  6  7	fall break
	 8  9 10 11 12 13 14	problem set 5 due; lab 5 due
	15 16 17 18 19 20 21	problem set 6 due; lab 6 due
	22 23 24 25 26 27 28	Thanksgiving
	29 30
Dec	       1  2  3  4  5	problem set 7 due; lab 7 due
	 6  7  8  9 10 11 12	problem set 8 due; lab 8 due
	13 14 15 16 17 18 19	last class
	20 21 22 23 24 25 26	winter break
	27 28 29 30 31
Jan	                1  2
	 3  4  5  6  7  8  9
	10 11 12 13 14 15 16
	17 18 19 20 21 22 23	final exam 1:30 Friend 101
	24 25 26 27 28 29 30

Syllabus

This will evolve over the semester, so check it out from time to time.

Sep 21, 23:    Introduction. What's in a computer

  • Reading: (1) A famous 1945 article by Vannevar Bush, As we may think, is often cited as predicting the Internet and the web. Think about how Bush's "Memex" relates to Google and your computer, and ask yourself what Bush got right and what he totally missed. (2) Apple has introduced a variety of ground-breaking devices, beginning with early personal computers and most recently the iPhone. Read Jonathan Zittrain's chapter on a fundamental difference between them, and think about whether his pessimistic take on the iPhone is still true in the face of the success of Apple's App Store, which opened after Zittrain's essay, and in turn Apple's disinclination to allow programs that compete with Apple's businesses.
  • Problem set 1, due Sep 30

    Sep 28, 30:    How does it work. Representation of information

  • Reading: (1) Preliminary discussion of the logical design of an electronic computing instrument. Original article by Burks, Goldstine and von Neumann. The first page is a clear description of how computers are organized, though in archaic terminology. There's no need to read much beyond that, though section 3 is also quite germane. There is also a good online talk on early computing at Princeton by George Dyson; go to October 5, 2004. (2) Sections 4 and 5 of Alan Turing's famous essay on whether machines can think, Computing machinery and intelligence, provides an alternative description of how machines operate, not so detailed as von Neumann's.
  • Lab 1: Operating systems, local and network file systems, a first web page
  • Problem set 2, due Oct 7

    Oct 5, 7:    What the components are and how they are made

  • Reading: The original article on Moore's Law. How Stuff Works has some pages on microprocessors.
  • Lab 2: HTML and web page design
  • Problem set 3, due Oct 15

    Oct 12, 14:    Software and algorithms

  • Reading: a Wikipedia article on algorithms. None of the details matter for the course, but skim it to see the different ways that basic ideas are expressed. (This article is also on the way to becoming an example of what is sometimes called "The Tragedy of the Uncommon": experts add more and more detail that can only be of use to other experts, and thus make the material inaccessible to those with little expertise.)
  • Lab 3: Advanced HTML
  • Problem set 4, due Oct 21

    Oct 19, 21:    Languages, programming; Javascript

  • Reading: some Javascript tutorials, out of many: one, two, three.
  • Lab 4: Graphics
  • Problem set 5, due Nov 11 (after break)

    Oct 26, 28:    Javascript. Operating systems

  • Reading: The late Professor Michael Mahoney's 2007 Freshman seminar on The World of the Computer points to a good collection of interesting reading, including an oral history of Unix.    
  • Take-home midterm, due Oct 30 at 5 PM. This will be handed out in class on Oct 26. A Q/A session will be scheduled, probably on Oct 25.   
  • No lab, no problem set due this week.

    [fall break]

    Nov 9, 11:    File systems, databases. Applications.

  • Reading: These articles describe some of the realities of software development: A Bug and a Crash, by James Gleick (who has written numerous other fine technical articles--see the sidebar on this link); the Therac-25 accidents (long and scary); a Mars Rover software problem (more technical, recent). Skim these and think about the many computer systems that we rely on.
  • This is an off year for elections, though NJ's governorship is up for grabs. Browse this Study of NJ voting machine problems, a troubling place to encounter the problems of software development, and hope that nothing could possibly go wrong.
  • Lab 5: Introduction to Javascript / Programming fundamentals
  • Problem set 6, due Nov 18

    Nov 16, 18:    Networks & communications, Internet

  • Reading: Skim some of the Internet history papers. Check out Ed Felten's explanation of net neutrality.
  • Lab 6: More Javascript / user interfaces
  • Problem set 7, due Dec 2 (after break):   

    Nov 23, 25:    World Wide Web

  • No problem set or lab this week, but there is class on Nov 25.
  • Reading: Cloud computing
  • Lab 7: Spreadsheets
  • Problem set 8, due Dec 9

    Nov 30, Dec 2:    Threats; security and privacy

  • Reading: what do they know about you? -- general information on privacy; the Electronic Privacy Information Center is also informative. EFF has a good article on Surveillance self-defense, and ACM Queue has a good article on Communications surveillaince.

    Dec 7, 9:    Cryptography; Compression & error detection.

  • Reading: FAQ on cryptography. Good book chapter on public key cryptography.
  • Lab 8: TBD

    Dec 14, 16:    Intellectual property. Case studies. Wrapup

  • Reading: (2) The Chilling Effects Clearinghouse is an excellent, authoritative site dealing with the legal issues around free speech, intellectual property, and online activities. The Electronic Frontier Foundation also has good coverage of these issues. James Gleick has an interesting but now a bit dated article on software patents. Finally, Your Rights Online at Slashdot points to numerous stories about online rights. (2) The original technical paper describing Google. Skip the hard bits, but get the insights. Note the comments about advertising in Appendix A.
  • No more labs or problem sets!

    [winter break]

    Jan 17:    Q/A session. (Depending on interest, we might arrange for two sessions.)

    Jan 21:    Final exam, Thursday, January 21, 1:30 pm, Friend 101   

  • Note that the final exam date is set by the registrar and I am not allowed to make any individual arrangements. Take this into account when making travel plans.
  • Registrar's Official Exam Schedule page.

    Administrative Information

    Professor: Brian Kernighan, 311 CS Building, 609-258-2089, bwk at cs dot princeton dot edu. Office hours Monday 2:30-4:00 and Tuesday 3:00-4:30, or by appointment, or just drop in if my door is open, which it usually is.

    Teaching Assistants and office hours:
    Connelly Barnes (csbarnes), CS 418B, Mon 1:30-2:30
    Melissa Carroll (mkc), CS 413, Wed 1:30-2:30
    Sean Gerrish (sgerrish), CS 413, Fri 1:30-2:30

    Send mail to cos109@princeton.edu with any questions any time.

    Lectures:

    Monday and Wednesday, 11:00-12:20, Peyton 145.

    Regular class attendance is expected and class participation helps. Frequent absences are grounds for a failing grade regardless of other performance.

    I won't absolutely prohibit the use of laptops in class unless they become a problem, but I would be most grateful if you could use computers and phones for course-related activities like following the notes, rather than for email, chat, YouTube, Twitter, Google, solitaire, poker, eBay, Facebook, or similarly compelling distractions. (Additions to this list are welcome; I can't keep up.)

    Labs:

    There will be eight labs to give hands-on practice in important aspects of computing. The labs are designed to be easily completed within three hours, if you have read through the instructions beforehand, which should take at most an hour. Undergrad lab assistants will be available to help out during scheduled lab sections. Labs are held in the Friend Center; they can be done in dorm rooms or campus clusters, but there will be lab assistants in Friend, and no help elsewhere.

    Labs are together worth about 20 percent of the course grade. To receive credit, students must complete labs by midnight Friday of the week they are assigned, unless there are extraordinary circumstances.

    Labs start the second week of classes. There will be no labs in the week before fall break, Thanksgiving week, or the last week of classes. Lab sessions are PROBABLY Monday through Friday at 1:30 and 7:30 somewhere in the Friend Center.

    Problem sets:

    Eight weekly problem sets, together worth about 20 percent of the course grade, will be assigned. Problems are intended to be straightforward, reinforcing material covered in class and providing practice in quantitative reasoning, and should take 1-2 hours to complete.

    Problem sets will be due by 5:00 PM Wednesday, one week after they are assigned. Turn in solutions in the box outside room 311 on the third floor of the CS building, or at the beginning of class. There will be no problem set due in the week before Fall break (midterm instead), Thanksgiving week, or the last week of the term. Only minimal credit will be given for late submissions unless there are extraordinary circumstances, and in no case after solutions have been posted or discussed in class.

    Lateness Policy:

    For both labs and problem sets, extracurricular activities and heavy workloads in other classes don't count as "extraordinary", no matter how unexpected or important or time-consuming. And I am unsympathetic to the appeal that "this is my fifth class," since the same could be said of any one of the others.

    Nevertheless, everyone gets truly behind from time to time. In recognition of this, you are allowed two late submissions (no more than 4 days late in each case). Please let us know ahead of time that you will be submitting late so we can keep track.

    You must complete all labs and assignments to pass the course.

    Collaboration Policy:

    You are encouraged to collaborate on problem sets, but you must turn in separate solutions; the names of all collaborators must appear on each submission.

    (This elaboration of the policy on collaboration is paraphrased from COS 126:) You must reach your own understanding of the problem and discover a path to its solution. During this time, discussions with friends are encouraged. However, when the time comes to write down the solution to the problem, such discussions are no longer appropriate -- the solution must be your own work, so you must work on the written assignment on your own. If you have a question, you can certainly ask friends or teaching assistants, but do not, under any circumstances, copy another person's work or present it as your own. This is a violation of academic regulations.

    Another way to look at this: If I asked you to explain how you got your answer, you would have no trouble doing so, because you understood the material completely.

    Examinations:

    There may well be short, unannounced, in-class quizzes to verify your existence and test your understanding. These could be worth 5-10 percent of the course grade.

    A take-home, open-book midterm examination will be given during the week before fall break. It will cover material presented and discussed in class and any relevant reading through the end of the fifth week of classes. It will be worth 20 percent of the course grade.

    An open-book final examination will be given during the January exam period. It will cover all of the relevant readings and material presented and discussed in class. It will be worth 35-40 percent of the course grade.

    There will be question and answer sessions before exams. These are not meant to be an orderly review and are not a substitute for missed lectures, but they are a chance for you to ask questions about course material.

    Sorry: no collaboration on take-home exams or the final.

    Comments on Grades:

    If you do poorly on the midterm but much better on the final, I will weight the final more heavily than usual, so a poor midterm grade is not fatal at all. But you must do acceptably well on the final exam; students who cannot answer even half the questions on the final should not expect to do well.

    Don't forget that P/D/F has three possible outcomes, only one of which is good. Attending lectures, paying attention and participating, turning work in on time, coming to office hours, studying for exams, and attending q/a sessions all help to avoid unpleasant results.

    Textbook and Readings:

    There is no assigned text for this course since I have never found anything that seems right. Notes and readings will be posted online. The weekly readings are for background, context, general education, and/or entertainment; you are not expected to know the detailed content, but you should understand the basic ideas.

    I have half a dozen books that purport to cover the same kinds of areas as the course. None feels right to me, but among them there is coverage of many class topics, so you might find it helpful to browse in them a bit. Available for short term loans; drop in to take a look. Meanwhile, check out the bibliography for other suggestions.