CS40, UCSB, 2010-01/03

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

Latest Information

March 31: This site is now closed; all attachments have been deleted

General Course Information

Course Number: 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.
There is an official waiting list; please contact the Undergraduate Program Coordinator (Benji Dunson) about this.

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

Professor

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

Teaching Assistants

Eyrun Eyjolfsdottir
- eyrun@umail.____.___
- David Johnson
- davidj@cs.____.___
- Harold Frank Hall, Room 2152A

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

Monday 13:00-13:50: Class in 387 101
Monday 14:00-15:00: Office hour WvD in HFH 2151
Wednesday 13:00-13:50: Class in 387 101
Wednesday 14:00-15:00: Office hour WvD in HFH 2151
Thursday 13:00-15:00: Office hours TA in Phelps 1413
Friday 9:00-11:00: Office hours TA in Phelps 1413
Friday 11:00-11:50: Discussion in Phelps 1401
Friday 13:00-13:50: Class in 387 101
Friday 14:00-14:50: Discussion in 387 101
Friday 16:00: deadline homework

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.

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:

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.

Schedule (tentative)

Week I (Jan 4-10): "Counting 1"

Class topics: Introduction to CS40; Introduction to counting, counting using sum and product rules; factorial, counting permutations, P(n,r), counting combinations
Reader: pp. 1 - 20
Thursday: announcement of Homework 1: "Counting 1": Homework 1
TA Office hours topics (Eyrun Eyjolfsdottir):
Discussion topics (David Johnson): questions on Homework 1

Week II (Jan 11-17): "Counting 2"

Class topics: Binomial theorem, multinomials, combinations with repetitions
Reader: pp. 20 - 45
TA Office hours topics (DJ): Homework 1
Friday: Homework 1 due
Discussion topics (EE): last minute issues with Homework 1, preparation for Midterm 1

Week III (Jan 18-24): "Boolean Logic"

Monday: No class (Martin Luther King Day)
WvD will not have office hours on Monday or Wednesday.
TA Office hours topics (EE): NOTE: Thursday office hours moved to Tuesday this week - Topic will be Midterm 1.
Wednesday January 20, 1:00-1:50 pm: Midterm 1 on "Counting 2"
Friday's Class topics (guest lecture by prof. Ömer Egecioglu): statements/propositions, conjunction, disjunction, implication, negation, biconditional, truth tables, tautology, contradiction, (logical equivalence: the laws of logic)
Reader: pp. 45 - 53
Discussion topics (DJ): return of Homework 1, correct answers to Midterm 1

Week IV (Jan 25-31): "Propositional Logic"

Class topics: logical equivalence: Laws of Logic, logical implication: Rules of Inference; existential and universal quantifiers, open statement, proofs,
Reader: pp. 53 - 120
Thursday: announcement of Homework 2: "Logic"
TA Office hours topics (DJ):
Discussion topics (EE): return of Midterm 1, questions for Homework 2

Week V (Feb 1-7): "Sets"

Class topics: sets, operations on sets, counting sets
Reader: pp. 121 - 154
TA Office hours topics (EE): Homework 2
Discussion topics (DJ): last minute issues with Homework 2, preparation for Midterm 2
Friday: Homework 2 due

Week VI (Feb 8-14): "Sets, Etc."

Class topics (Monday): sets, inclusion/exclusion principle
Wednesday February 10, 1-1:50 pm: Midterm 2 on "Sets"
Class topics (Friday): Cartesian product, probability theory, relations and functions
Reader: pp. 156 - 177
TA Office hours moved to Tuesday February 9, 1-3 pm in Phelps 1413
TA Office hours topics (DJ): Midterm 2 on "Sets"
Discussion topics (EE): return of Homework 2, correct answers to Midterm 2

Week VII (Feb 15-21): "Structures"

Monday: No class (Presidents' Day)
Class topics (Wednesday and Friday): relations and functions
Reader: pp. 156 - 165
Thursday: announcement of Homework 3 on "Structures"
TA Office hour topics (DJ):
Discussion topics (DJ): questions for Homework 3, (return of Midterm 2)

Week VIII (Feb 22-28): "Induction and Recursion"

Class topics: proofs by induction, inductions and recursion
Reader: pp. 277 - 307 (but the emphasis will be on pp. 277 - 297)
Thursday: announcement of Homework 4 on "Induction"
TA Office hours topics (DJ): Homework 3
Discussion topics (EE): last minute issues with Homework 3, homework 4
Friday 4 pm: Homework 3 due

Week IX (March 1-7): "Leftovers and Review"

Class topics: complexity of algorithms, big O notation, hardness of problems, cryptography, halting problem
TA Office hours topics (EE): Homework 4
Friday 4 pm: Homework 4 due
Discussion topics (DJ): return of Homework 3, last minute issues with Homework 4, leftovers

Week X (March 8-12): "Review"

Class topics Monday: counting through functions, countable infinity, uncountable infinity, uncomputability again
Class topics Wednesday: Relational databases, information on Final
Class topics Friday: Final review session, tentative grade calculation
TA Office hours topics (EE):
Discussion topics (EE): return of Homework 4; review

Finals Week (March 14-12): "Final Exam"

Thursday March 18, 4-7 pm (room 387 101)