Computer Science 109:
Computers in Our World

Fall 2020

Princeton University

Brian Kernighan

Computer Science Dept.
Tue Dec 15 07:45:40 EST 2020
Problem sets, labs and announcements will be posted on this web page only.
You are responsible for monitoring this page.

2020 answers

2019 final exam     (answers)         2018 final exam     (answers)    

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

Problem sets:    1         2         3         4         5         6         7        

Solutions:    1       2       3       4       5       6       7      

Labs:        1         2         3         4         5         6         7        

Office hours:    Abby Th 1:00-3:00;   Francisca Th 8:00-10:00;   BWK: M 5-6, Tu 10-11, F 3:30-4:30;  TGIF F 4:30

Lecture videos: Canvas / Kaltura Media Gallery

Old stuff:    playlist     Certificate in Technology and Society     Advanced HTML lab from 2019     binary to ASCII     Lab 1 pages     Lab 2 pages     Color program     color names     Turing £50 note     Arvind Narayanan podcast     Andrew Appel talk on election security     2019 midterm   (answers)     2018 midterm   (answers)     Toy simulator     midterm answers     Foxtrot on exponentials     Google v Oracle oral arguments     binary and hex     How tall is Einstein?     DoJ v Google     BBC Radio discussion of Alan Turing     Python examples     how Google advertising works     Washington Post on Google monopoly     Comments on lab 5     Submarine cables on HN     Lab 6 pages     Lab 7 comments     ATM/ISBN checker     Spectrum allocation chart    

Quick links:    Course summary, schedule and syllabus       Office hours       Textbook       Problem sets       Labs       Lateness policy       Collaboration policy       Exams and grades


Course Summary

Computers, computing, and the many things enabled by them are all around us. Some of this is highly visible, like laptops, tablets, 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 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; programming and programming languages; the Internet and the Web; machine learning and big data; cyber-warfare; 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 QCR requirement.

QCR is the new and improved QR. I am planning to put a bit more emphasis on the C aspect, in the hope of making the content useful in an ever more computational world.

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 and/or Python.

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 social networks, businesses and governments, mostly without our knowledge, let alone consent. Major companies like Amazon, Apple, Facebook, Google and Microsoft are duking it out with each other on technical and legal fronts, and with a variety of governments. Shadowy groups and acronymic agencies routinely attack us and each other; their potential effect on things like the upcoming US elections is way beyond worrying. The Internet of Things promises greater convenience at the price of much greater cyber perils. The careless, the clueless, the courts, the congress, the crackpots, and the criminal (not disjoint groups, in case you hadn't noticed) continue to do bad things with technology. What could possibly go wrong? Come and find out.



	Su Mo Tu We Th Fr Sa  
Sep	   31  1  2  3  4  5	first class 
	 6  7  8  9 10 11 12	Sep 10: problem set 1
	13 14 15 16 17 18 19	Sep 13: lab 1; Sep 17: problem set 2
	20 21 22 23 24 25 26	Sep 20: lab 2; Sep 24: problem set 3
	27 28 29 30		Sep 27: lab 3
Oct	             1  2  3	Oct 1: problem set 4
	 4  5  6  7  8  9 10 	takehome midterm exam this week (no lab, no pset)
	11 12 13 14 15 16 17	fall "break" (no pset)
	18 19 20 21 22 23 24	Oct 18: lab 4; Oct 22: problem set 5
	25 26 27 28 29 30 31	Oct 25: lab 5; Oct 28: problem set 6
Nov	 1  2  3  4  5  6  7	Nov 1: lab 6; Nov 5: problem set 7
	 8  9 10 11 12 13 14	Nov 8: lab 7
	15 16 17 18 19 20 21
	22 23 24 25 26 27 28	last class; Thanksgiving
	29 30			reading period                 
Dec	       1  2  3  4  5  
	 6  7  8  9 10 11 12	Dean's Date; takehome final exam this week 
	13 14 15 16 17 18 19	last day of exams
	20 21 22 23 24 25 26  
	27 28 29 30 31        



The syllabus is still up in the air, and I have made some changes in the early part. The general flow is ok, but later dates are not certain. This will evolve over the semester, so check it out from time to time.

Week 1: Aug 31, Sep 2:    What is a computer?
Readings: (1) A famous 1945 Atlantic Monthly article by Vannevar Bush,
As we may think, is often cited as predicting the Internet and the web. How does Bush's "Memex" relate to Google and your computer? What did Bush get right 70+ years ago, and what did he totally miss? (2) Chapter 1 of Understanding the Digital World: What is a computer?

Week 2: Sep 7, 9:    Representation of information
Readings: (1) Chapter 2 of Understanding the Digital World: Bits, bytes, representation of information.
Problem set 1, due Sep 10
Lab 1: HTML and web page design, due Sep 13

Week 3: Sep 14, 16:    Inside the processor
Problem set 2, due Sep 17
Lab 2: Graphics, due Sep 20
Readings: (1) Chapter 3 of Understanding the Digital World: Inside the processor. (2) 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 beyond that, though section 3 is also quite germane. (3) 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 nearly so detailed as von Neumann's. (4) The original article on Moore's Law. (5) How Stuff Works has some pages on microprocessors. (They haven't been updated in a while so some numbers are dusty.)

Week 4: Sep 21, 23:    Software and algorithms
Readings: Chapter 4 of Understanding the Digital World: Algorithms
Problem set 3, due Sep 24
Lab 3: Spreadsheets, due Sep 27

Week 5: Sep 28, 30: Software Systems   
Readings: (1) Chapter 5 of Understanding the Digital World: Programs and programming languages.
(2) Chapter 6 of Understanding the Digital World: Software systems.
Problem set 4, due Oct 1

Week 6: Oct 5, 7: Operating systems, file systems, databases, big data   
Takehome midterm exam this week. There will be a Q/A session on Oct 4 at 3pm.   
No lab or problem set this week.

[Oct 12-13: fall "break"]

Week 7: Oct 14: Programming and programming languages   
Lab 4: Python, due Oct 18 (after break)
Readings: (1) Chapter 7 of Understanding the Digital World: Programs and programming languages.
(2) There are endless Javascript and Python tutorials. Do a bit of searching and exploration.

Week 8: Oct 19, 21:    Applications.
Problem set 5, due Oct 22
Lab 5: Python, due Oct 25
Readings: (1) Browse this 2008 study of New Jersey voting machine problems, a troubling place to encounter bad software development, and hope that nothing could possibly go wrong in an election year. Many NJ voting machines have not been upgraded in the intervening decade.

Week 9: Oct 26, 28:    Communications: networks and Internet
Problem set 6, due Oct 29
Lab 6: Javascript 2, due Nov 1
Readings: (1) Chapters 8 and 9 of Understanding the Digital World: Networking; The Internet. (2) Skim some of the Internet history papers. (3) Ed Felten's explanation of net neutrality.

Week 10: Nov 2, 4:    World Wide Web
Problem set 7, due Nov 5
Lab 7: Natural Language Processing and Machine Learning, due Nov 8
Readings: (1) Chapter 10 of Understanding the Digital World: The world wide web. (2) The original technical paper describing Google. Skip the hard bits, but get the insights. Note the comments about advertising in Appendix A.

Week 11: Nov 9, 11:    Artificial intelligence, machine learning
Readings: (1) Chapter 11 of Understanding the Digital World: Data and information. (2) Motherboard article on how to not be hacked. (3) James Fallows article on identity theft.

Week 12: Nov 16, 18:    Cryptography; compression and error detection
Readings: (1) Chapter 12 of Understanding the Digital World, Privacy and security. (2) New York Times Privacy Project
No more labs or problem sets!

Week 13: Nov 24:    Wrapup

[Reading period: Nov 30-Dec 8]

Q/A session some enchanted evening

Dec 9-15:    Takehome final exam during Dec 9-13 (most likely)


Administrative Information

Professor: Brian Kernighan, 311 CS Building, 609-258-2089,

Teaching Assistants: Abby Gupta '22, Francisca Weirich-Freiberg '21.

Office hours: Abby Th 1:00-3:00; Francisca Th 8:00-10:00; BWK: M 5-6, Tu 10-11, F 3:30-4:30; TGIF F 4:30    

Lectures: Monday and Wednesday, 1:30-2:50, online; the Zoom link is available on Canvas and Blackboard. I will record parts of the lectures. I encourage you to watch any recordings carefully, and to "attend" live meetings as much as possible. In return, I will do my best to make them interesting and relevant.

[This is copied from official university policy:] I plan to record (at least some parts of) our class sessions for students who are unable to attend. You may choose to opt out of any recording, in which case you should contact me to arrange alternative ways to participate. Faculty own the copyright to their instructional materials, and so students should not record any class sessions without permission. For this same reason, recordings of our class may not be posted online or shared with anyone other than students enrolled in this course.

Textbook and Readings:

The primary text for the course is Understanding the Digital World ("UDW"). The first edition is available at Labyrinth and Amazon. I am working on a new edition and have made it available for the class as PDF, so there's no need to buy the old one. If you are particularly interested in privacy and security, Bruce Schneier's Data and Goliath is highly recommended.

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 UDW is fair game.

Problem sets:

Seven 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 2-3 hours to complete.

Problem sets are due by midnight Thursday, one week after they are assigned.


Seven labs, together worth about 20 percent of the course grade, will give hands-on practice in important aspects of computing. The labs are designed to be easily completed within 2-3 hours, if you have read through the instructions beforehand, which should take at most an hour. You can do the labs wherever you want, but if you need assistance, there may be undergrad lab TAs available online; this is a bit uncertain at the moment. Further information about the lab TAs and clusters will be posted.

Labs are due by midnight Sunday of the week they are assigned.

Lateness policy:

In fairness to everyone, only reduced 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, heavy workloads in other classes don't count as "extraordinary," no matter how unexpected or important or time-consuming. I am also unsympathetic to the appeal that "this is my fifth class," since the same could be said of any one of your other classes.

If you do submit your work late, we will give you credit for it on this scale:

Regardless, you must turn in all problem sets and labs to pass the course.

If you find yourself in a tough situation, please let me know; help of various kinds is always available.

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.

In accordance with university rules, any collaboration has to be virtual even if some or all of the parties are able to be together physically. This is partly a safety measure, and also one to keep the playing field level.

(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.

Exams and grades:

An open-book takehome 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 takehome final examination will be given during the 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.

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

There will be a question and answer session before each exam. Q/A sessions 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.

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.