CS40, UCSB, 2010-04/06

This is the course site for CS40, "Foundations of Computer Science", in Spring 2010 at UC Santa Barbara. This site is no longer active.

Copyright 2010 Wim van Dam (UC Santa Barbara)

Latest Information

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 Spring 2010

Professor

• Wim van Dam
• vandam@cs.____.___
• Harold Frank Hall, Room 2151

Teaching Assistants

• Lijie Ren
  • lijie@cs.____.___

Reader

This course has a required reader that will be available at The Alternative in Isla Vista. Starting Monday March 29, 11 pm, 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: vandam64

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.

Class and Office Hours

• Monday 14:00-14:50: Class in North Hall 1105
  • Monday 18:00-20:00: ACM Lower Division Tutoring in Harold Frank Hall 1152
• Wednesday 14:00-14:50: Class in North Hall 1105
  • Wednesday 15:00-17:00: Office hours WvD in HFH 2151
• Thursday 14:00-16:00: Office hours TA in Phelps 1413
• Friday 10:00-10:50: Discussion in Phelps 3505
• Friday 14:00-14:50: Class in North Hall 1105

Homeworks, Midterms and Final

There will be four homework assignments, two Midterms and one Final. The homeworks are due on Fridays at 4 pm. 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 "Counting":
• Homework 2 "Logic"
• Homework 3 "Quantifiers and Sets", due Friday May 7, at 4 pm. The relevant parts in the reader for this homework assignment are (roughly) Section 2.4 (pp. 84-101) and Sections 3.1-3.2 (pp. 123-145)
• Homework 4:
• Midterm 1 "Counting", Wednesday April 14, 2:00 - 2:50 pm in North Hall 1105
• Material: Chapter 1, "Counting", excluding Section 1.5 "Catalan Numbers"; Reader, pp. 1-35, and pp. 40-44.
  • 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.
• Midterm 2: "Sets, Etc.", Wednesday May 12, 2:00 - 2:50 pm in North Hall
• Material: Theory of sets as summarized in Section 5.1 (pp. 156-160), Section 5.2 "Relations" (pp. 160-163), Section 5.3 "Functions" (pp. 163-165). Excluding: countable vs uncountable (p. 158)
  • 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.

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 Spring 2010 quarter you can benefit from the additional tutoring for CS40 by the ACM.

• ACM Lower Division Tutoring
  • Monday evenings between 6 and 8 pm
  • Harold Frank Hall 1152

Schedule (tentative)

Week I (March 29 - April 2): "Counting 1"

• Thursday: announcement of Homework 1 "Counting"
• Discussion topic: Homework 1 "Counting"

Week II (April 3 - 9): "Counting 2"

• Discussion topics: last minute questions on HW1; preparation for MT1
• Friday, April 9, 4pm: Homework 1 due in CS40 homework box in the copy room on the 2nd floor of Harold Frank Hall

Week III (April 10 - 16): Midterm and "Logic"

• Monday class: Review session by LR on Midterm 1 material
• Wednesday class: Midterm 1 "Counting" in NH 1105 between 2:00 and 2:50 pm
  • Wednesday WvD office hours: WvD is away this week and his office hours are canceled
• Discussion topics: Return of HW1; correct answers to MT1
• Friday class: guest lecture by prof. S. Suri on Boolean logic

Week IV (April 17 - 23): "Logic"

• Thursday: announcement of Homework 2 "Logic"
• Discussion topic: Return of MT1; HW2

Week V (April 24 - 30): "Sets"

• Thursday: announcement of Homework 3 "Sets"
• Friday: Homework 2 "Logic" due at 4 pm

Week VI (May 1 - 7): "Structures"

• Friday: Homework 3 "Sets" due at 4 pm

Week VII (May 8 - 14): Midterm and "Induction"

• Wednesday, May 12: Midterm 2 on Structures

Week VIII (May 15 - 21): "Induction and Recursion"

• Thursday: announcement of Homework 4 "Induction"

Week IX (May 22 - 28): "Leftovers"

• Friday: Homework 4 "Induction" due at 4 pm

Week X (May 29 - June 4): Dead Week/Review

• Monday: No class (Memorial Day)

Finals Week (June 5 - 11): "Final Exam"

• Final exam: Monday, June 7, 4 - 7 pm in NH 1105
• Wednesday (class): review of material of final exam
• Friday (discussion): return of HW4
• Friday (class): Q&A and background on CS40