Computer Science 109:
Computers in Our World

Fall 2014

Princeton University

Brian Kernighan

Computer Science Dept.

Mon Jan 5 11:31:59 EST 2015

The Q/A session will be in CS 105 on Sunday Jan 18 at 7pm

2013 final exam       (answers)       2012 final exam       (answers)      
(These are also accessible through Blackboard, in case you're off campus.)

Lecture notes:    9/10    9/15    9/17-22    9/24-29    10/1    10/6    10/8    10/13    10/15    10/20-22    11/3    11/5    11/10-12    11/17-19    11/24-12/1    12/3    12/8    12/10   

Problem sets:    0         1         2         3         4         5         6         7         8        

Solutions:    0         1         2         3         4         5         6         7         8        

Labs:        1         2         3         4         5         6         7         8        

Old stuff:    Playlist     Lab session information     survey     survey results     Toy simulator     RGB colors     New Yorker: right to be forgotten     Distractions in class     ENIAC women programmers     A Turing machine     Turing test     NPR story on women programmers     Lab 2 pages     Lab 3 pages     semiconductor manufacturing     final exam schedule     Lab 4 pages     2013 midterm     (2013 answers)     2012 midterm     (2012 answers)     2014 midterm answers     IP law book 1     IP law book 2     GNU GPL     EFF amicus brief     Javascript examples     Ed Felten on net neutrality     Submarine cable map     alternative view     DNS in the news     New Yorker article on HTML5     Potential follow-on courses     Alice, Bob, Eve     Bitcoin primer       Original bitcoin paper       Spectrum allocation       original Google paper       Summary of what we covered       ATM checksum algorithm      

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

You are responsible for monitoring these pages.

Course summary, schedule and syllabus
  Office hours   Textbook   Problem Sets   Labs   Lateness Policy   Collaboration Policy   Exams and Grading   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, share and sometimes leak vast amounts of 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 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 are built and operate; 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 computers and communications systems work and how they affect the world we 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 lectures, 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. Stunning amounts of our private lives are observed and recorded by business and governments, mostly without our knowledge, let alone consent. Major companies like Apple, Google, Microsoft and Amazon 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, the courts, the congress, and the criminal continue to do bad things with technology. What could possibly go wrong? Come and find out.


	Su Mo Tu We Th Fr Sa
Sep	    1  2  3  4  5  6
	 7  8  9 10 11 12 13	first class
	14 15 16 17 18 19 20	problem set 0 due 9/17
	21 22 23 24 25 26 27	problem set 1; lab 1
	28 29 30
Oct	          1  2  3  4	problem set 2; lab 2
	 5  6  7  8  9 10 11	problem set 3; lab 3
	12 13 14 15 16 17 18	problem set 4; lab 4
	19 20 21 22 23 24 25	takehome midterm due 5 pm 10/24; no lab or problem set
	26 27 28 29 30 31	fall break
Nov	                   1
	 2  3  4  5  6  7  8	problem set 5; lab 5
	 9 10 11 12 13 14 15	problem set 6; lab 6
	16 17 18 19 20 21 22	problem set 7; lab 7
	23 24 25 26 27 28 29	Thanksgiving
Dec	    1  2  3  4  5  6	problem set 8; lab 8
	 7  8  9 10 11 12 13	last class
	14 15 16 17 18 19 20	winter break
	21 22 23 24 25 26 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 24	final exam 1:30 Friend 101
	25 26 27 28 29 30 31


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

Week 0: Sep 10:    Warmup
Problem set 0, due Sep 17
Reading: A famous 1945 Atlantic Monthly article by Vannevar Bush, As we may think, is often cited as predicting the Internet and the web. This page links to a version with original illustrations. Think about how Bush's "Memex" relates to Google and your computer, and ask yourself what Bush got right and what he totally missed.

Week 1: Sep 15, 17:    What's in a computer
Problem set 1, due Sep 24
Reading: Chapter 1 of D is for Digital: what's in a computer?
(1) The Computer History Museum site has a lot of interesting material, including descriptions of Babbage's mechanical computers.

Week 2: Sep 22, 24:    How does it work. Representation of information
Problem set 2, due Oct 1
Lab 1: Operating systems, local and network file systems, a first web page
Reading: Chapter 2 of D is for Digital: bits, bytes, representation of information.
(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, provide an alternative description of how machines operate, not so detailed as von Neumann's.

Week 3: Sep 29, Oct 1:    What the components are and how they are made
Lab 2: HTML and web page design
Problem set 3, due Oct 8
Reading: Chapter 3 of D is for Digital: Inside the CPU
(1) The original article on Moore's Law. How Stuff Works has some pages on microprocessors.

Week 4: Oct 6, 8:    Software and algorithms
Lab 3: Advanced HTML
Problem set 4, due Oct 15
Reading: Chapter 4 of D is for Digital: Algorithms

Week 5: Oct 13, 15:    Languages, programming; Javascript
Lab 4: Graphics
Problem set 5, due Nov 5 (after break)
Reading: Chapter 5 of D is for Digital: Programs and programming languages
(1) A number of Javascript tutorials, out of many: Codecademy, Khan Academy, Javascript Kit. You should also look at if programming interests you.

Week 6: Oct 20, 22:    Operating systems, file systems, databases.
Take-home midterm, due Oct 24 at 5 PM. This will be handed out in class on Oct 20. A Q/A session will be scheduled, probably on Oct 19.   
No lab or no problem set due this week.
Reading: Chapter 6 of D is for Digital: Software systems

[fall break]

Week 7: Nov 3, 5:    Javascript. Applications.
Lab 5: Introduction to Javascript / Programming fundamentals
Problem set 6, due Nov 12
Reading: Chapter 7 of D is for Digital: Javascript
(1) 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.
(2) 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 in an election year.

Week 8: Nov 10, 12:    Networks & communications, Internet
Lab 6: More Javascript / user interfaces
Problem set 7, due Nov 19
Reading: Chapters 8 and 9 of D is for Digital: Networking; The Internet
(1) Skim some of the Internet history papers.
(2) Check out Ed Felten's explanation of net neutrality.

Week 9: Nov 17, 19:    World Wide Web
Lab 7: Spreadsheets
Problem set 8, due Dec 3
Reading: Chapter 10 of D is for Digital: The world wide web

Week 10: Nov 24:    Threats; security and privacy
No problem set or lab this week.
Reading: Chapter 11 of D is for Digital: Data, information and privacy
(1) EFF has a good article on Surveillance self-defense, and ACM Queue has a good article on Communications surveillance.
(2) James Fallows has a great article on identity theft in The Atlantic.
(3) Ed Felten's Freshman Assembly talk (9/9/12): TMI: Information, Identity, and Privacy

Week 11: Dec 1, 3:    Cryptography; Compression & error detection.
Lab 8: Privacy
Reading: Good book chapter on public key cryptography.

Week 12: Dec 8, 10:    Intellectual property. Case studies. Wrapup
No more labs or problem sets!
(1) 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. There's a good article on software patents in the Economist. 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.

[winter break]

Q/A session probably Jan 18 evening

Jan 21:    Final exam at 1:30 in 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. (The final exam dates are usually posted around midterm week.)
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 are tentatively Monday 2:30-4:30 and Tuesday 2:30-4:30, or by appointment, or just drop in if my door is open, which it usually is.

Teaching Assistants:
  Annie Liu (, CS 317, Mon 4:30-5:30
  Qinxiang Cao (, CS 242, Thu 2:00-3:00
    (TA office hours may be in CS 003)


Monday and Wednesday, 11:00-12:20, Friend 006.

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

Please, no laptops, phones or tablets except for taking notes and other class purposes. Regrettably, computers and phones appear to be primarily used for email, chat, YouTube, Twitter, Google, solitaire, poker, eBay, Facebook, and similarly compelling diversions, all of which distract you, your neighbors, and me. (Additions to this list are welcome; I can't keep up.)

Textbook and Readings:

The text for the course is D is for Digital, available at Labyrinth and Amazon.

Notes and readings will be posted online. The weekly readings beyond the text 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. Anything in the text is fair game. Check out the bibliography for other suggestions.

Problem sets:

Eight or nine 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.


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.

Labs will start the second full week of classes. There will be no labs in the week before fall break, Thanksgiving week, or the last week of classes.

Lateness Policy:

In fairness to everyone, only minimal credit can be given for late submissions unless there are extraordinary circumstances, and in no case after solutions have been posted or discussed in class.

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 your other classes.

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). You must let us know ahead of time that you will be submitting late so we can keep track.

You must turn in all problem sets and labs 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, for which the penalties are draconian.

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

As it is for problem sets, so it is for labs: collaboration to understand the material is encouraged, but the work you turn in has to be your own.


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 material presented and discussed in class throughout the semester and any relevant reading. It will be worth 35-40 percent of the course grade.

There will be a question and answer session before each exam. 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 exam, 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; students who cannot answer even half the questions should not be surprised to get a D, and an F is not impossible, especially if other work is also inadequate.

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