CS109a Class Page
Introduction to Computer Science

(Winter Quarter 96-97)

This class is offered by,
Stanford University
Department of Computer Science
In association with,

Contents of this page

Late Breaking News:

Change in Final Location

Thursday March 20th
Terman Auditorium


The two-quarter sequence of CS109A/B is intended to provide a broad introduction to the fundamental theoretical and mathematical issues of computer science. Many of you will come to CS109 from CS106 and/or CS107. CS109 is not about programming; rather we will present computer science from a much more abstract perspective. There will be a small programming component to these courses, but the programming we do will serve our main goal of exploring the theory and abstractions of computer science. Much of our work in CS109 will be devoted to reasoning about problems and problem solving, in terms of both the algorithms and data models involved.


The only real prerequisite for CS109A is a working knowledge of C and the programming process. If you took CS106B or CS106X here at Stanford or scored a 5 on the Computer Science AP exam you'll be very well prepared. If you don't have this sort of background, you should think carefully before starting the CS109 sequence. Although these courses will have a theoretical and mathematical focus, we expect that this will be the first exposure to material of this nature for most students, especially from a computer science perspective. You should, however, have a mathemical maturity to the level of advanced algebra and introductory calculus. For those of you who are still afraid of the "p" word, don't worry; it is my job to ensure that, by the end of CS109B, this will no longer be the case. Please feel free to discuss any of this with us if you are at all unsure about the suitability of your background for this course.

The People:

Instructor: Todd Feldman
E-mail: feldman@cs.stanford.edu,
Office Location: Gates 195
Office Phone: 725-5303
Office Hours: Mon/Wed 4:15-5:45 in Gates 195 (and by appointment)

Teaching Assistant: Michael Goldwasser

E-mail: wass@cs.stanford.edu
Office Location: Gates 482
Office Phone: 723-4532
Office Hours:
Mon, 10:00-11:00 in Gates 482
Thur, 11:00-12:00 in Gates 482

Teaching Assistant: Julien Basch

E-mail: jbasch@cs.stanford.edu
Office Location: Gates 376
Office Phone: 723-1604
Office Hours:
Fri, 4:15-5:15 in Gates 193D
Tues, 4:00-6:00 at the Coffee House

Teaching Assistant: Neetha Ratakonda

E-mail: neetha@cs.stanford.edu
Office Hours:
Wed, 10:00-11:00am in Gates 193B (723-6077)
Fri, 10:00-11:00am in Gates 193B (723-6077)

Staff Mailing List: cs109a@cs.stanford.edu

All four of us will monitor this mail, so please use this as often as possible, as you will likely get a quicker response.

The Lectures:

Class Lectures: Todd Feldman
Time: Mon/Wed/Fri, 3:15pm-4:05pm
Location: Gates B01
Live Broadcast: Stanford Channel E2

Recitation Sections: Michael Goldwasser / Julien Basch
Choice 1:

Time: Wednesday, 4:30-5:25pm
Location: 380-380F

Choice 2:

Time: Thursday, 10:00am-10:50am
Location: Terman 156
Live Broadcast: Stanford Channel E1

Choice 3:

Time: Friday, 2:15-3:05pm
Location: Education 115

For a summary of this, see the Weekly Schedule below.

The Textbook:

There is one required text for the course: Foundations of Computer Science (C Edition) by Aho and Ullman, (W.H. Freeman), 1995.

This book is available from the Stanford Bookstore and, although it'll set you back more money than you'd like, at least we'll use it next quarter in CS109B as well. We will probably distribute additional reading material from time to time.


Course Grades:
Your final grade for the course will be calculated as follows:

Problem Sets: 65%
Midterm Exam: 15%
Final Exam: 20%

Late Policy: All assignments are due in class by 3:20 p.m. on the day that they are due. Late assignments will be accepted until the start of the next lecture (3:20 p.m.) at a penalty of 15%. Of course, I know that from time to time extenuating cirumstances do arise and in such cases extensions will be granted; requests for extensions should be e-mailed to cs109a@cs.stanford.edu.

Online grades: All of your grades will be available online using the Webclass software. To see your grades, go to the URL: http://csl.Stanford.edu/~webclass/class/cs109a/

Information Sources:

Newsgroup: su.class.cs109a
Discussions, common questions, important announcements.
Staff Mailing List: cs109a@cs.stanford.edu
For any homework questions, or questions of individual interest.
Math/CS Library:
Videotapes of lectures and sections
Web Page: www.stanford.edu/class/cs109a/
Course information, schedule, syllabus, online copies of handouts.
Online Grades: http://csl.Stanford.edu/~webclass/class/cs109a/
Grades, statistics.
CS Catacombs:
Handouts, prolog source.
FTP Site: ftp://ftp.stanford.edu/class/cs109a/
online copies of handouts.
leland: /usr/class/cs109a/
online copies of handouts.
Handout Bins:
Extra copies of all handouts will be placed in the handout bins in the lobby down the hall from Todd's office in the Gates building. If we run out of a particular handout, just let one of us know and we'll make more copies. However, copies of all electronically generated handouts will be available online, as mentioned above.

Weekly Schedule:

time Monday Tuesday Wednesday Thursday Friday
10:00-10:30 Michael's Hours
10:00 - 11:00
(Gates 482)
Neetha's Hours
10:00 - 11:00
(Gates 193B)
Section #2
(Terman 156)
Neetha's Hours
10:00 - 11:00
(Gates 193B)
11:00-11:30 Michael's Hours
11:00 - 12:00
(Gates 482)
2:00-2:30 Section #3
2:15 - 3:05
Education 115
3:00-3:30 Lecture
3:15 - 4:05
(Gates B01)
3:15 - 4:05
(Gates B01)
3:15 - 4:05
(Gates B01)
4:00-4:30 Todd's Hours
4:15 - 5:45
(Gates 195)
Julien's Hours
4:00 - 6:00
(Coffee House)
Section #1
4:30 - 5:20

Todd's Hours
4:15 - 5:45
(Gates 195)
Julien's Hours
4:15 - 5:15
(Gates 193D)

The Syllabus:

[Note: Topics of future lectures are subject to change.]

# Date Topic Reading Due Out
1 Wednesday,
January 8th
Introduction Ch. 1
2 Friday,
January 10th
Proof Techniques I
3 Monday,
January 13th
Proof Techniques II HW1
4 Wednesday,
January 15th
Induction I Ch. 2.1 - 2.4
5 Friday,
January 17th
Induction II Ch. 2.1 - 2.4
January 20th
No Class
Martin Luther King, Jr. Day
6 Wednesday,
January 22nd
Proving the Correctness of Programs Ch. 2.5 - 2.10 HW1 HW2
7 Friday,
January 24th
Propositional Logic I Ch. 12.1 - 12.6
8 Monday,
January 27th
Propositional Logic II Ch. 12.7 - 12.10
9 Wednesday,
January 29th
Propositional Logic III Ch. 12.11 - 12.12 HW2 HW3
10 Friday,
January 31st
Prediciate Logic I Ch. 14.1 - 14.7
11 Monday,
February 3rd
Predicate Logic II Ch. 14.1 - 14.7
12 Wednesday,
February 5th
Predicate Logic III Ch. 14.1 - 14.7
13 Friday,
February 7th
Predicate Logic IV Ch. 14.10 - 14.11 HW3
14 Monday,
February 10th
Logic Programming in Prolog I HW4
15 Wednesday,
February 12th
Logic Programming in Prolog II
February 13th
Midterm Exam (7:00pm - 9:00pm)
(to be held in room 420-040)
16 Friday,
February 14th
Logic Programming in Prolog III
February 17th
No Class
Presidents' Day
17 Wednesday,
February 19th
Combinatorics Ch. 4.1 - 4.8 HW 4
18 Friday,
February 21st
Probability Ch. 4.9 - 4.14 HW 5
19 Monday,
February 24th
Analysis of Algorithms I Ch. 3.1 - 3.5
20 Wednesday,
February 26th
Analysis of Algorithms II Ch. 3.6 - 3.8
21 Friday,
February 28th
Analysis of Algorithms III Ch. 3.9 - 3.11
22 Monday,
March 3rd
Set Theory I Ch. 7.1 - 7.4 HW 5 HW 6
23 Wednesday,
March 5th
Set Theory II Ch. 7.5 - 7.8
24 Friday,
March 7th
Set Theory III Ch. 7.9 - 7.12
25 Monday,
March 10th
Relations I Ch. 8.1 - 8.5 HW 6 ? HW 7 ?
26 Wednesday,
March 12th
Relations II Ch. 8.6 - 8.7
27 Friday,
March 14th
Relations III Ch. 8.8 - 8.10 HW7
March 20th
Final Exam (12:15pm - 3:15pm)
Terman Auditorium

Handouts (how to read and print file formats):

# Date Topic Format
0 Wed, January 8th Signup sheet postscript, MS Word
1 Wed, January 8th Administrivia postscript, MS Word
2 Wed, January 8th Syllabus postscript, MS Word
3 Fri, January 10th Updated Course Information postscript, MS Word
4 Mon, January 13th Problem Set 1 postscript, MS Word
5 Fri, January 17th Sample Induction Proof postscript
6 Fri, January 17th Complete Proofs from 1/10, 1/13, 1/15 postscript, MS Word
7 Wed, January 22nd Complete Proofs from 1/17 postscript, MS Word
8 Wed, January 22nd Problem Set #2 postscript, MS Word
9 Fri, January 24th Complete Proofs from 1/22 postscript, MS Word
10 Fri, January 24th Problem Set #1 Solutions
11 Mon, January 27th Complete Proofs from 1/24 postscript, MS Word
12 Wed, January 29th Problem Set #3 postscript, MS Word
13 Fri, January 31st Problem Set #2 Solutions
14 Fri, January 31st Lecture Notes from 1/29
15 Fri, January 31st Lecture Notes from 1/31
16 Mon, February 3rd Lecture Notes from 2/3
17 Fri, February 7th Lecture Notes from 2/7
18 Mon, February 10th Problem Set #3 Solutions
19 Mon, February 10th Problem Set #4 postscript, MS Word
20 Mon, February 10th Practice Midterm postscript, MS Word
21 Mon, February 10th Lecture Notes from 2/10
22 Wed, February 12th Practice Midterm Solutions postscript, MS Word
23 Wed, February 12th Lecture Notes from 2/12
24 Fri, February 14th Lecture Notes from 2/14
25 Wed, February 19th Using Open Prolog postscript, MS Word
26 Wed, February 19th Lecture Notes from 2/19
27 Wed, February 19th Midterm Solutions postscript, MS Word
28 Fri, February 21st Lecture Notes from 2/21
29 Fri, February 21st Problem Set #5 (OAG)
30 Mon, February 24th Notes from 2/24
31 Mon, February 26th Notes from 2/26
32 Fri, February 28th Problem Set #4 Solutions
33 Fri, February 28th Notes from 2/28
34 Wed, March 5th Problem Set #6
35 Wed, March 5th Notes from 3/5
36 Fri, March 7th Notes from 3/7
37 Mon, March 10th Problem Set #5 (OAG) Solutions postscript
38 Mon, March 10th Notes from 3/10
39 Wed, March 12th Notes from 3/12
40 Fri, March 14th Practice Final Exam postscript, MS Word
41 Fri, March 14th Notes from 3/14
42 Mon, March 17th Practice Final Exam Solutions postscript, MS Word
43 Mon, March 17th Problem set #6 Solutions postscript

CS109a Class Page