CS103: Mathematical Foundations of Computing

Winter 2011-12 Course Information

Announcements

  • February 22: Solutions to the Midterm are available on Coursework under Materials.
  • February 22: The problems and solutions for Section 6 are now available.
  • February 21: The location of the final has been finalized. It will take place in 420-40 (our lecture room)
  • Febuary 17: Homework 6 (Due Feb 24) and three challenge problems have been posted.
  • February 15: Update: Midterm is open-laptop, closed-network, meaning you can download the notes (with restrictions described below), but your wifi must be turned off during the exam.
  • February 15: Midterm: The midterm (which is on Thursday, Feb 16 in Annenberg Auditorium) is designed to be a 75 minute exam, and you have two hours to take it. The questions on the midterm will focus on: There will be no more problems on System F (Fitch) for the rest of the quarter.
  • February 15: The problems and solutions for Section 5 are now available.
  • February 12: Solutions to the sample midterm are now posted.
  • February 11: Homework 4 Solutions are now posted.
  • February 11: Homework 3 Solution are now available.
  • February 11: HW5 is now posted. Notice the due date has been extended to Tuesday Feb. 21, but HW6 will be due Friday Feb. 24 as usual.
  • February 11: The midterm will be open book/open notes. Specifically, course textbooks, my lecture notes, handouts such as problem set solutions and problem session notes, and your own homeworks and notes all ok. NO use of other textbooks, web pages, etc. is allowed. And, of course, there is to be no collaboration with other humans during the exam.
  • February 10: HW3 has been graded. Graders 1: Le/Qiao. 2: Rakesh/Mirek. 3,4: Le. 5: Qiao. 6: Zavain/Rakesh. 7: Mirek 8: Zavain. Please visit our respective OH with questions
  • February 10: A Sample Midterm is now posted. Solutions will be posted on Sunday. Selected questions will be discussed in the second half of an extended problem session on Monday evening.
  • February 9: Corrected typo in Problem 4 of HW4 that simplifies base case.
  • February 7: The problems and solutions for Section 4 are now online.
  • February 6: Qiao's Office Hours changed to Thursday 2:30-5:30pm.
  • February 4: Homework 4 is now posted.
  • February 4: HW2 Solutions are now posted.
  • February 3: Graded HW 2s were handed out in lecture today. Graders: 1,2,3: Rakesh. 4,5: Qiao. 6,7: Le. 8,9: Zavain. 10: Mirek. Please visit our respective OH with questions
  • February 2: The course staff has noticed that a large subset of the class is not signed up on PIAZZA.COM. Please sign up now!
  • January 30: The problems and solutions for Section 3 are now online.
  • January 28: Homework 3 is now posted. Sorry about the delay.
  • January 25: You can now view HW1 Solutions.
  • January 25: The problems and solutions for Section 1 and Section 2 are now online.
  • January 24: Zavain's OH today have been cancelled. Circumstances permitting they may be redone at a time later this week.
  • January 23: Problem Session room has changed to Meyer Forum.
  • January 23: Lecture room has changed to 420-041.
  • January 21: Do not do problem 11 from homework 2. The answer is already in the readings.
  • January 20: Homework 2 is now online.
  • January 20: Do not email in homework solutions. Either give them in class or drop them off in the submission box in Gates. Thanks.
  • January 19: Hrysoula's Office Hours tonight have been cancelled. As a substitute Zavain will be holding extra Office Hours in Gates B26B from 7:30 to 9pm.
  • January 18: "predicate logic" in problem 4 of HW1 should be "propositional logic".
  • January 18: Office Hours times and rooms are now finalized below!
  • January 18: Yesterday's section notes are available here.
  • January 15: Office Hours have been posted. They start Tuesday Jan 17.
  • January 15: Typos have been fixed on HW1. Please refer to current version.
  • January 15: Section this week will be on Tuesday evening as Monday is a holiday. (Happy playoffs watching!)

    • General Information

  • Class URL: The class webpage is http://www.stanford.edu/class/cs103 where all material will be posted.
  • Lectures: Monday, Wednesday, Friday 12:50 -- 2:05 420-041
  • Sections: Monday, 7:00 -- 8:30PM Meyer Forum. (NOTE: The week of the Jan 16th and Feb 20th sections will be held on Tuesdays at the same time and location.)
  • Midterm: Feb 16th, 7:00 -- 9:00PM Annenberg Auditorium
  • Instructor: Prof. David Dill (dill AT cs.stanford.edu). Office: Gates 344; Phone: 725-3642; OH: Wednesday 3:30 - 5:30
  • Admin: Mary Jane Swenson (mswenson AT cs.stanford.edu). Office: Gates 269; Phone: 723-0748
  • Course Assistants:
  • Prerequisites: CS106A. CS103 is not a programming class. We only require some programming knowledge because we like to use examples from programming, and we appeal to intuition from programming, like recursion and data structures, in explaining some of the material.
  • Questions and help:
  • Textbooks: There are two textbooks for the class. Both are available in the Stanford Bookstore, although you can get them anywhere that sells them (of course). The first part will be based on Chapter 1 only of "Discrete Mathematics and its Applications", sixth edition, by Kenneth R. Rosen. My understanding is that the bookstore sells copies of that chapter alone. The second textbook is "Introduction to the Theory of Computation" by Michael Sipser (I think it's the second edition).
  • Grading: There will be weekly homeworks, a midterm, and a final exam. Grades will be based upon Homeworks (60%), Midterm (15%), and Final (25%). Students may use the course texts and all handouts (including lecture notes, course notes, and solutions) and their own notes and homework solutons during exams, but no other materials. Students may not use the internet or collaborate with others, electronically or in any other way, during exams.
  • Homeworks: There will be weekly homeworks that will be posted on the web page. Homeworks must be handed in by the beginning of the lecture when they are due. If you want to hand them in earlier, you can drop them off in the CS103 cabinet in the third floor of Gates. Late homeworks will not be accepted unless you are sick or injured, or something of that ilk. However, the lowest homework grade will not be considered in the grades computation.
  • Challenge problems: Occasionally, we will propose challenge problems for students who are interested. Good solutions to these problems will be considered in grading, but only for raising an A to an A+ grade. It would be a strategic error to students to spend significant time on these problems at the expense of thoroughly understanding the basic material.
  • Reading Assignments: There will be reading assignments associated with each lecture. There will occasionally be material in the lectures that does not appear in the textbooks, or that is presented differently. Homework and exam questions may be based on material from the lectures and in the textbooks.
  • Honor Code and Collaboration: It should go without saying that you must comply with Stanford's honor code. Please, let's have no more articles like this: New York Times

    Our policies about collaboration and use of materials are intended to promote our most important goal, which is that you learn the concepts and skills of the course well. The other, closely related goal, is that we be able to assess reasonably accurately how well the first goal was met.

    The primary way that you learn this material is by working problems on homeworks (and the studying that you have to do to be able to work those problems). The problems give practice, help you understand your comprehension of the material, and (importantly) the creative part of problem solving helps you to remember and appreciate that material.

    So, only very limited collaboration is allowed on homeworks. You should first try to work through them by yourself, thoroughly and carefully. Of course, Prof. Dill and the TAs will be available to you if you are stuck or want to know if there is a better way to solve a problem. It's ok to discuss problems with others, but please make sure you are doing your best to solve them yourself.

    Another way to undermine the value of homework problems is to look up answers on the internet, find answers in other textbooks, copy answers from homeworks from previous classes at Stanford or elsewhere, etc. Don't do these things. If you use material from sources other than the lectures, office hours, or course textbooks to understand a problem better, write down what you used and how you used it in your homework solutions. Any assistance received (both from human and from inanimate sources) that is not given proper citation may be considered a violation of the Honor Code.

    In any case, you are responsible for understanding and being able to explain all of the statements in your assignments and examinations. Solutions must be written up independently of other students.

    Assigned sections should be read (at least quickly) before the lecture.

    Course Calendar

    This schedule is subject to change. Please check it frequently.


    DateDayEventTopicReadingsAssignments
    9-Jan Mon Lecture 1 Intro, Propositional logic Rosen 1.1-1.2 (5th, 6th ed),
    1.1-1.3 (7th ed)
    11-Jan Wed Lecture 2 Propositional logic, sat solvers
    13-Jan Fri Lecture 3 Predicate logic I Rosen 1.3, 1.4 ( 5,6th ed),
    1.4-1.5 (7th ed)    		 HW1 assigned
    16-Jan Mon Holiday (MLK day)
    18-Jan Wed Lecture 4 Predicate logic II
    20-Jan Fri Lecture 5 Proof techniques Rosen 1.5 (5th ed), 1.5-1.7 (6th ed),
    1.6-1.8 (7th ed), Sipser 0.3-0.4    		 HW1 due, HW2 assigned
    23-Jan Mon Lecture 6 Sets Sipser 0.2
    25-Jan Wed Lecture 7 Graphs & relations
    27-Jan Fri Lecture 8 Functions HW2 due, HW3 assigned
    30-Jan Mon Lecture 9 Cardinality and infinite sets Notes
    1-Feb Wed Lecture 10 Induction I Notes, Sipser 0.4
    3-Feb Fri Lecture 11 Induction II HW3 due, HW4 assigned
    6-Feb Mon Lecture 12 Trees and structural induction Notes
    8-Feb Wed Lecture 13 Regular languages I Sipser 0.1, 1.1-2
    10-Feb Fri Lecture 14 Regular languages II Sipser 1.3 HW4 due, HW5 assigned
    13-Feb Mon Lecture 15 Regular languages III Sipser 1.4
    15-Feb Wed Lecture 16 Regular languages IV Notes
    16-Feb Thur Midterm 7PM - 10 PM, location Annenberg Auditorium
    17-Feb Fri Lecture 17 Pumping Lemma and Closure Properties Notes HW5 due, HW6 assigned
    20-Feb Mon President's Day
    22-Feb Wed Lecture 18 Turing Machines Sipser Ch. 3
    24-Feb Fri Lecture 19 Undecidability I Sipser Ch. 4 HW6 due, HW7 assigned
    27-Feb Mon Lecture 20 Undecidability II
    29-Feb Wed Lecture 21 Undecidability III Sipser Ch. 5
    2-Mar Fri Lecture 22 P and NP Sipser 7.1-7.3 HW7 due, HW8 assigned
    5-Mar Mon Lecture 23 NP Completeness I Sipser 7.4-7.5
    7-Mar Wed Lecture 24 NP Completeness II
    9-Mar Fri Lecture 25 Context-free Grammars Sipser 2.1 HW8 due, HW9 assigned
    12-Mar Mon Lecture 26 Cook's theorem Sipser section 7.4
    14-Mar Wed Lecture 27 More complexity
    16-Mar Fri Lecture 28 Review HW9 due
    23-Mar Fri Final Exam 8:30 AM -- 11:30 AM, Location: 420-40

    Page Created: January 6, 2012
    Comments and Suggestions: staff mailing list