This is the course site for CS40, "Foundations of Computer Science", in Winter 2010 at UC Santa Barbara. This site is no longer active.
Copyright 2010 Wim van Dam (UC Santa Barbara)
March 31: This site is now closed; all attachments have been deleted
Catalog Description
Prerequisites
Course Goals
Professor
Teaching Assistants
Reader
This course has a required reader that will be available at The Alternative in Isla Vista.
To order online: (1) Go to www.alternativecopy.com (2) Go to 'Order Readers' (top right corner) (3) Use the username: ucsbcs40 and password vandam7
For those who can't wait: the first few weeks we will be using Chapters 1 and 2 ("Fundamental Principles of Counting" and "Fundamentals of Logic") from Discrete and Combinatorial Mathematics, Ralph P. Grimaldi, 5th edition, Addison-Wesley (2004). Here is the table of content of the whole reader.
Class and Office Hours
Homeworks and Midterms
There will be four homework assignments and two Midterms. The homeworks are due on Friday 4 pm in Weeks II, V, VII and VIII; the two Midterms are on Wednesday January 20 and February 10 in class, i.e. between 1:00 and 1:50 pm in 387 101. The TA Eyrun Eyjolfsdottir is responsible for Homeworks 2 and 4 and Midterm 1; David Johnson is responsible for Homeworks 1 and 3 and Midterm 2. The CS40 homework box is situated in Harold Frank Hall, room 2108 (copy room); do not put your homework in WvD's mailbox.
Homework 1: Due Friday January 15, 4 pm (Answers to Homework 1)
Homework 2: Due Friday February 5, 4 pm (Answers to Homework 2)
Note that when using combinations of AND and OR, you are not allowed to assume that AND has priority over OR. This means that you can not write (p AND q OR r); instead you should explicitly specify whether you mean ((p AND q) OR r) or (p AND (q OR r)).
Regarding Question 4 in HW2; note that the := in "r:=NOT(q)" is an assignment, meaning that the value of r gets changed into the value NOT(q).
Homework 3: Due Friday February 26, 4 pm (Answers to Homework 3)
Homework 4: Due Friday March 5, 4 pm
Midterm 1: Wednesday January 20, 1-1:50 pm in class (Answers to Midterm 1)
Material: Sections 1.1-1.4, pp. 2-35 in the Reader; Section 1.5, "Catalan numbers", is not part of Midterm 1.
You are allowed to bring with you: pen, paper, 1 letter-size, double-sided page of notes. You are not allowed to bring with you: the reader, print outs of the slides, or any other kind of information besides the single page. Electronic tools like iPhones, calculators, etc. are also not allowed.
To practice you should work on the relevant Exercises in the reader; here are the answers to some of them.
Midterm 2: Wednesday February 10, 1-1:50 pm in class
Material: Sections 3.1 - 3.3, pp. 121 - 148 in the Reader; Section 3.4, "A First Word on Probability", is not part of Midterm 2.
You are allowed to bring with you: pen, paper, 1 letter-size, double-sided page of notes. You are not allowed to bring with you: the reader, print outs of the slides, or any other kind of information besides the single page. Electronic tools like iPhones, calculators, etc. are also not allowed.
To practice you should work on the relevant Exercises in the reader; here are the answers to some of them. Especially useful ones are: from Exercises 3.1: 7, 9, 13, 15; from Exercises 3.2: 3, 7, 9, 17; from Exercises 3.3: 1, 2, 4, 6.
Final: Thursday March 18, 4-7 pm
Material: Everything we covered in class. The amount of questions will be approximately two midterms.
Grading
Assignments will be graded using the following scale:
The course grade is determined as follows.
The 4 Homeworks and 2 Midterms all count for an equal amount; the final counts for 2 Midterms. This means that your total grade will be determined according to:
4 Homeworks + 2 Midterms + 1 Final = 4/8 + 2/8 + 2/8. In other words, each homework and midterms counts for 1/8th, the final counts for 1/4th.
Before the final you are allowed to decide whether you want to drop your lowest score among your homeworks and midterms, in which case the equality becomes:
3 Homeworks + 2 Midterms + 1 Final = 3/8 + 2/8 + 3/8 or 4 Homeworks + 1 Midterm + 1 Final = 4/8 + 1/8 + 3/8.
Academic Honesty
The following applies to every course you attend at UC Santa Barbara (from UCSB Campus Regulations, Chapter VII: "Student Conduct and Discipline"):
It is expected that students attending the University of California understand and subscribe to the ideal of academic integrity, and are willing to bear individual responsibility for their work. Any work (written or otherwise) submitted to fulfill an academic requirement must represent a student’s original work. Any act of academic dishonesty, such as cheating or plagiarism, will subject a person to University disciplinary action. Using or attempting to use materials, information, study aids, or commercial “research” services not authorized by the instructor of the course constitutes cheating. Representing the words, ideas, or concepts of another person without appropriate attribution is plagiarism. Whenever another person’s written work is utilized, whether it be a single phrase or longer, quotation marks must be used and sources cited. Paraphrasing another’s work, i.e., borrowing the ideas or concepts and putting them into one’s “own” words, must also be acknowledged. Although a person’s state of mind and intention will be considered in determining the University response to an act of academic dishonesty, this in no way lessens the responsibility of the student.
Specifically for the current CS40 course this means that
Week I (Jan 4-10): "Counting 1"
Week II (Jan 11-17): "Counting 2"
Week III (Jan 18-24): "Boolean Logic"
Week IV (Jan 25-31): "Propositional Logic"
Week V (Feb 1-7): "Sets"
Week VI (Feb 8-14): "Sets, Etc."
Week VII (Feb 15-21): "Structures"
Week VIII (Feb 22-28): "Induction and Recursion"
Week IX (March 1-7): "Leftovers and Review"
Week X (March 8-12): "Review"
Finals Week (March 14-12): "Final Exam"