This is the course site for CS40, "Foundations of Computer Science", in Fall 2010 at UC Santa Barbara. This site is no longer active.
Copyright 2010 Wim van Dam (UC Santa Barbara)
Dec 5: The answers to Midterms 1 and 2 have been posted below
Dec 1: Information on Final has been posted below
General Course Information
- Course No.: CS 40
- Course Title: Foundations of Computer Science
- Total Credits: 4
Catalog Description
- Propositional predicate logic, set theory, functions and relations, counting, mathematical induction and recursion (generating functions).
Prerequisites
- Computer Science 10 or 12; and Mathematics 3C.
Course Goals
- To explain the basic concepts of discrete mathematics as they arise in computer science and, whenever practical, show how they are applied. Learn mathematical induction and proof techniques. Learn mathematical reasoning.
Course Information for Fall 2010
Professor
- Wim van Dam
- vandam@cs.____.___
- Harold Frank Hall, Room 2151
Teaching Assistants
Reader
This course has a required reader that is available at The Alternative in Isla Vista. You can order it online as follows
(1) Go to www.alternativecopy.com
(2) Go to 'Order Readers' (top right corner)
(3) Use the username: ucsbcs40 and password: vandam23
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), which you should be able to get in the library. Here is the table of content of the whole reader.
Typical Weekly Schedule
- Monday 9:00-9:50 am: Class by WvD in Phelps 3515
- Monday 11:00-12:00: Office hour WvD in Harold Frank Hall 2151
- Tuesday 10:00 am - noon: Office hours TA in Phelps 1413
- Wednesday 9:00-9:50 am: Class by WvD in Phelps 3515
- Wednesday 11:00-12:00: Office hour WvD in Harold Frank Hall 2151
- Thursday 1:00-3:00 pm: Office hours TA in Phelps 1413
- Thursday: Announcement of homework
- Friday 9:00-9:50 am: Class by WvD in Phelps 3515
- Friday 10:00-10:50 am: Discussion by TA in Phelps 1440
- Friday 12:00-12:50 pm: Discussion by TA in 387 101
- Friday 3 pm: Homework due
Homeworks, Midterms and Final
There will be four homework assignments, two Midterms and one Final. The CS40 homework box is situated in Harold Frank Hall, room 2108 (copy room); do not put your homework in WvD's mailbox. Late homeworks will not be graded.
- Homework 1 "Counting" (grader: Gang Wang): posted as an attachment to this site; due Friday October 8, before 3 pm. Material: Sections 1.1, 1.2 and 1.3 in the Reader.
- Midterm 1 "More Counting": Wednesday October 13, 9:00 - 9:50 am in Phelps 3515
- Material: Reader Chapter 1, excluding Section 1.5 "Catalan Numbers" (pp. 1-35 and pp. 40-44)
- Note: The answers to some of the exercises of Chapter 1 are posted below. Yuanyang Zhang will be the grader.
- Rules: Calculators and other electronic tools are not allowed; you are allowed one sheet of notes (US letter sized, double-sided, readable by the human eye); you are not allowed to consult additional notes, the Reader, homework assignments, etc.
- Recommended exercises in Reader: Exercises 1.4: 1, 3, 7, 19, 23 and Supplementary Exercises 5, 7, 11, 17, 21, 27
-
- Homework 2 "Logic": (Gang Wang): posted as an attachment to this site; due Friday October 22, before 3 pm. Its material is Sections 2.1 and 2.2 in the Reader.
- Homework 3 "More Logic" (Yuanyang Zhang): posted as an attachment to this site; due Friday October 29, before 3 pm. Its material is Sections 2.1, 2.2, 2.3 and 2.4 in the Reader (excluding "duals").
- Homework 4 "Functions and Induction" (Yuanyang Zhang): posted as an attachment to this site; due Tuesday November 23, before 3 pm. Its material is Sections 5.3 (pp. 163-164) and Sections 4.1 and 4.2 (pp.180 - 207) in the Reader (excluding "well-ordering property").
- Midterm 2 "Sets etc.": Wednesday November 10, 9:00 - 9:50 am in Phelps 3515
- Material: Reader Chapter 3, §§ 3.1, 3.2, 3.3 (pp. 121 - 148), and Chapter 5, §§ 5.1, 5.2, 5.3 (pp. 156 - 164); all this excluding: Gray codes (p. 126), duality (p. 139), countable versus uncountable infinity (p. 158), surjection, injection, one-to-one (correspondence), bijection, permutation, inverse (p. 164)
- Note: The answers to some of the exercises of Chapter 3 are posted below. Gang Wang will be the grader.
- Rules: Calculators and other electronic tools are not allowed; you are allowed one sheet of notes (US letter sized, double-sided, readable by the human eye); you are not allowed to consult additional notes, the Reader, homework assignments, etc.
- Recommended exercises in the Reader: Exercises 3.1 (p. 132): 3, 7, 15, 17; Exercises 3.2 (p. 144): 3, 7, 13, 19; Exercises 3.3 (p. 148): 1; Exercises 5.2 (p. 162): 1, 3, 5.
- Final "CS40 Fall 2010": Thursday December 9, 8:00 - 11:00 am in Phelps 3515
- Rules: Calculators and other electronic tools are not allowed; you are allowed one sheet of notes (US letter sized, double-sided, readable by the human eye); you are not allowed to consult additional notes, the Reader, homework assignments, etc. See the pdf below for more information on the final.
Grading
Assignments will be graded using the following scale:
- 3 points: Exemplary; student applies knowledge with virtually no conceptual or procedural errors
- 2 points: Adequate; student applies knowledge with no significant conceptual errors and only minor procedural errors.
- 1 point: Minimal; student applies knowledge with occasional conceptual errors and only minor procedural errors.
- 0 points: Unsatisfactory; student makes significant conceptual and/or procedural errors when applying knowledge.
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
- You are not allowed to copy or transcribe answers to homework assignments from others or other sources.
- Although you are allowed to discuss homework assignments with others, you should write down your answers independently. You should always be able to argue and explain your answers when asked for clarifications.
- During the Midterm and Final Examination no electronics are allowed, additional notes are only allowed to the extent described prior to the test.
- When you will be unable to hand in the homework in time you should report this to WvD as soon as possible, but always before the deadline. No matter the reason, you will always be asked to present documentation.
- When in doubt, ask.
- Students violating the rules of Academic Honesty will receive an "F" for the course and will be reported to the Dean of Students Office.
ACM Tutoring
This quarter, ACM offers tutoring for lower division courses like CS40. This free service will be available at the following times and location.
- Mondays and Wednesdays, between 8 and 10 pm in Harold Frank Hall, room 1152
Week nulla (Sep 23 - Sep 26): Intro
- Class topics: formalities of CS40, intro to counting
- Discussion topics: no discussion
Week I (Sep 27 - Oct 3): Counting 1
- Class MWF topics: counting
- Discussion topics: HW1 (Gang Wang)
- TA office hours: Yuanyang Zhang
- Homework 1, "Counting", will be announced Thursday September 30 and will be due next Friday October 8
Week II (Oct 4 - Oct 10): Counting 2
- Class MWF topics: counting
- Discussion topics: Midterm 1 "More Counting" (Yuanyang Zhang)
- TA office hours: Gang Wang
- Homework 1, "Counting", is due Friday October 8 at 3 pm
Week III (Oct 11 - Oct 17): Logic 1
- Wednesday October 13: Midterm 1 "Counting"
- Class MF topics: logic (§§ 2.1, 2.2)
- Discussion topics: HW2, return of HW1 (Gang Wang)
- TA office hours: Yuanyang Zhang
- Homework 2, "Logic", will be announced Thursday October 14 and will be due Friday October 22
Week IV (Oct 18 - Oct 24): Logic 2
- Class MWF topics: logic (§§ 2.3, 2.4)
- Discussion topics: HW3, return of Midterm 1 (Yuanyang Zhang)
- TA office hours: Gang Wang
- Homework 3: "More Logic", will be announced on Thursday October 21 and will be due on Friday October 29
- Homework 2, "Logic", is due Friday October 22 at 3 pm
Week V (Oct 25 - Oct 31)
- Class MW topics: sets (§§ 3.1, 3.2, 3.3)
- Class F topics: Sets etc.
- Discussion topics: return of HW2 (Gang Wang)
- TA office hours: Yuanyang Zhang
- Homework 3, "More Logic", is due Friday October 29 at 3 pm
- Halloween: Yes, I (WvD) know, it's Halloween
Week VI (Nov 1 - Nov 7)
- Class MWF topics: structures
- Discussion topics: MT2, return of HW 3 (Yuanyang Zhang)
- TA office hours: Gang Wang
Week VII (Nov 8 - Nov 14)
- Wednesday November 10: Midterm 2 "Sets etc"
- Class M topics: applications of sets and questions regarding MT2
- Class F topics: counting with functions
- Discussion topics: answers to MT2 (Gang Wang)
- TA office hours Yuanyang Zhang
Week VIII (Nov 15 - Nov 21)
- Class MWF topics: induction and recursion
- Homework 4, "Induction", will be announced Tuesday November 16 and is due on Tuesday November 23 at 3 pm
- Discussion topics: HW 4 (Yuanyang Zhang)
- TA office hours: Gang Wang
Week IX (Nov 22 - Nov 28)
- Class M topics: strong induction
- Homework 4, "Induction", is due Tuesday November 23 at 3 pm
- Due to Thanksgiving, there will be no class, office hours or discussions on Wednesday Nov 24, Thursday Nov 25 and Friday Nov 26.
- Discussion topics: no discussion
- TA office hours on Tuesday Yuanyang Zhang
Week X (Nov 29 - Dec 5)
- Class MWF topics: structural induction and big O notation; review of material
- Discussion topics: Final exam (Gang Wang)
- TA office hours: Yuanyang Zhang
Finals Week (Dec 6 - Dec 11)
- Final: Thursday December 9, 8:00 - 11:00 am
- Material: Everything covered in class, see the slides below for more information
- Monday December 6, 1:00 - 2:00 pm: Office hour WvD
- Tuesday December 7, 11:00 am - 12 pm: Office hour GW
- Wednesday December 8, 11:00 am - 12 pm: Office hour ZY
- Wednesday December 8, 1:00-2:00 pm: Office hour WvD