Princeton University
Computer Science Dept.

Computer Science 111
Computers and Computing

Andrea LaPaugh

Fall 1997

Directory

This course is intended for students from the humanities and social sciences who want a one-course introduction to computers, and have little or no computer experience. No mathematics or science background is assumed. The course is a broad introduction to computer science, including topics from hardware design, algorithms, data structures, and theory.

The laboratory is complementary to the classroom work, uses PCs, and is based on the Internet and the World Wide Web. Students will ``surf'' the internet and construct their own home pages in the first three weeks. They will add to their home pages throughout the semester, while exploring a broad spectrum of practical applications, including graphics and digital sound. The final three labs are a gentle introduction to programming in Java.

General Information

Lectures: MWF at 11:00--11:50am, room 105 (small Auditorium) CS building.

Professor: Andrea LaPaugh, 304 CS Building, 258-4568, aslp@cs.princeton.edu, Office hours, Monday 3-4pm or by appointment.

Course secretary: Sandra Barbu, 323 CS building, 258-4562, barbu@cs.princeton.edu

Graduate teaching assistants:

Jie Chen, 317 CS building, 258-1796, jennifer@cs.princeton.edu,
Jon Forsyth, 317 CS building, 258-1796, jforsyth@cs.princeton.edu,
Anil Ruia, 413 CS building, 258-1797, ruia@cs.princeton.edu,

The easiest way to reach any of us to make an appointment or ask a quick question is by email. Feel free to call, but many of us check our email more often than our voice mail.

Reading

Required

Computer Science: An Overview, by Glenn Brookshear.
This book is the course's basic text. We will read most of it, skipping chapters 6, 8, and 9. The book is an overview of the field of computer science, and does not focus on programming in any particular language. Success in the course will require a thorough understanding of the assigned sections of this book.

The following supplementary texts have been put on reserve in the Engineering Library:

The New Turing Omnibus, by A. K. Dewdney.
The Dewdney book is a collection of short, mostly self-contained chapters covering a large number of discrete topics in computer science. Many of the topics we cover in this course are discussed, often at a level of mathematical sophistication or background well beyond the level of this course. It is intended for student enrichment.

Principles of Computer Science by Cullen Schaffer.
This is a text that has been used as the primary text in COS 111 in the past. It is also an overview of computer science, but with a somewhat different emphasis than the text by Brookshear. Some students may find it helpful for alternative explanations of material.

Java How to Program by H. M. Deitel and P. J. Deitel.
This is a serious text on programming with Java. It is well beyond the level of discussion in this course. It is provided for the student who wants to do some in-depth exploration of programming.

Communication

This course will be essentially ``paperless''. After the first week, all assignments will be posted only on the course Web site. (See details below.) ``Hand-outs'' will be posted on the course Web site as well. Important announcements on all aspects of the course will be made under the ``What's new'' heading accessible from this course home page (``General Information''). Students are responsible for monitering the postings under ``What's new''. Schedule changes will be made in this course home page and announced under ``What's new''. The only paper we will exchange is your solutions to the problem sets, which we will grade and hand back.

You are encouraged to use electronic mail to set up appointments, leave messages, and ask quick questions (like ``What was that reference you gave today in class?'' or ``I've been at McCosh Infirmery all week, what do I do to make up my lab?'') However, old fashioned face-to-face talking is still best for clarifying confusions and other tecnical discussions.

Problem sets (10)

Ten problem sets, drawn mainly from the Brookshear text, will be assigned. They are intended to be straightforward and should take at most 2 hours to complete, not counting the reading. Problem sets are due by 5 PM sharp on Tuesdays, starting the second week of class. No credit will be given for late assignments, unless there are extraordinary circumstances and/or prior arrangements. Students may collaborate on problem sets, but must turn in separate solutions. The problems assigned can be found each week on the course Web site, accessible from this course home page under the heading ``Problem Sets''. After the first assignement, this is the only place the assigment will appear and students are responsible for looking up each assignment on the Web. The first assignment is appended to the general handout (a snapshot of this course home page) distributed at the first class.

Labs (10)

There will be ten hands-on computing laboratory exercises to be done during a scheduled laboratory period. Labs begin Monday, September 15, 1997. Students will use Intel PCs with Windows NT. The labs are designed to be easily completable in two-and-a-half hours or less, during the scheduled lab sections. Students obtain the lab assignments from the course Web site, accessible from this course home page. Printed copies of only the first lab assignment will be distributed. To receive credit, students must complete labs in the week they are assigned, unless there are extraordinary circumstances and/or prior arrangements.

Lab Sections, all in room E-203 of the Engineering Quadrangle:

Assistants will be in the labs to help out. Most labs require about one hour of preparatory reading. Lab section assignments for students who have preregistered are available here and will be posted at the first lecture. Students who are adding COS 111 at the beginning of the semester (including freshmen) need to sign into a lab. Lab assignments can be made and changed by contacting the course secretary, Sandra Barbu either by email (preferred), by telephone, or in person at her office listed above.

Guest lectures

We will have several guest lecturers, some from other university departments, who will speak about their own uses of computers. The normal day for a guest lecturer will be Friday.

Examinations

Grading

Course grades will be computed as follows:

Schedule

Major update on 12/2/97 indicating actual progress through syllabus to date.
Major change in order of presentation indicated in brown.

Subject to change. Be sure to check readings and homework assignments for changes up to a week before due.

lab prob. set due date Topics Readings in Brookshear
- -- Fri 9/12 Introduction to the course Preface, Chapter 0
1 intro -- Mon 9/15 Overview of computer systems pp. 111-116
9/17 Representations in bits Sections 1.4, 1.5
9/19 continuation of 9/17 --
2 Web search 1 Mon 9/22 Gates , Boolean logic Section 1.1
9/24 Flip-flops, memories Sections 1.2, 1.3
9/26 Binary arithmetic Sections 1.6, 1.7, Appendix B
3 home pages 2 Mon 9/29 Guest lecture: Prof. Ed Felten on the Internet and World-Wide Web
10/1 Error correction Section 1.8
10/3 CPU, machine instructions Section 2.1
4 graphics 3 Mon 10/6 Assembly-language programming Sections 2.2, 2.5, pp. 184-6, App. C
10/8 Program execution Section 2.3
10/10 continuation of 10/8 --
5 adv. HTML 4 Mon 10/13 Input/Output Sections 2.4, 2.6
10/15 Operating system basics Sections 3.1, 3.2
10/17 Guest lecture: Prof. Adam Finkelstein on searching artwork databases and undergraduate projects in graphics
- 5 Mon 10/20 Processes Sections 3.3, 3.4
10/22 Exam review and discussion
10/24 Midterm Examination -- covers reading and lectures through 10/20
Fall Break
6 sound -- Mon 11/3 Algorithms Sections 4.1, 4.2, 4.3
11/5 Iteration Section 4.4
11/7 Recursion Section 4.5
7 logic 6 Mon 11/10 Efficiency and correctness Section 4.6, Section 11.5
11/12 Programming languages Sections 5.1, 5.2
11/14 Guest lecture: Prof. Michael Mahoney(History) on a history of computing topic
8 Java intro 7 Mon 11/17 Programming languages (cont.) Section 5.3, App. D
11/19 Arrays Section 7.1
11/21 Guest lecture:Prof. Margaret Martonosi (Elec. Eng.), ``Silicon to Supercomputers: How Computer Hardware is Built''
- 8 Mon 11/24 Lists, stacks, queues Sections 7.2, 7.3, 7.4
11/26 continuation of 11/24 Section 7.7
11/28 Thanksgiving break
9 sorting 9 Mon 12/1 continuaton of 11/24 and more on algorithm efficiency --
12/3 Networks: dangers, security, social and legal issues Sections 3.5, 6.6; paper handed out
Section 3.6 changed from required to optional
12/5 Trees (skipping hash tables) Section 7.5
10 recursion 10 Mon 12/8 Reasoning and large searches Sections 10.1, 10.3, 10.4, 10.5
background Turing machines and computation Sections 11.1, 11.2
12/10 Computable and noncomputable functions Sections 11.3, 11.4
12/12 Complexity Section 11.6 (Review 11.5 assigned 11/10)
Thurs. Jan. 15, 1998 Review session, 4:30pm, Room CS 105 (small auditorium where class met)
Mon. Jan. 19, 1998 Review session, 11:00am, Room CS 103 (NOTE DIFFERENT ROOM)
Tues Jan. 20, 1998 Final Exam, 8:30am, Room CS 104 (large auditorium)
A.S. LaPaugh Tue Jan 6 17:17:42 EST 1998