CS40, UCSB, 2012-04/06: "Foundations of Computer Science" (Wim van Dam)

Copyright 2012 Wim van Dam (UCSB) · It is forbidden to copy, distribute, or transit this work, nor is it allowed to alter, transform, or build upon this work. For example, it is not allowed to upload this document to sites such as coursehero.com.

Announcements

  • 2012-06-19: Enjoy your summer

Piazza

We will use piazza for questions and answers related to the course. You can access it here: http://piazza.com/ucsb/spring2012/cs40

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.

Professor

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

Teaching Assistants

  • Abhishek Misra
    • amishra@cs.____.___

Reader

This course has a required reader that is available at The Alternative. You can order it online as follows

(1) Log on to www.alternativecopy.com

(2) Go to 'Order Readers' (top right corner)

(3) Use the username: ucsbcmpsc40 and password: vandam77

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.

Typical Weekly Schedule

  • Monday, 12:30--13:45: Class in PHELPS 1440
  • Monday, 14:00--15:00: Office hours WvD in HFH 2151
  • Wednesday, 12:30--13:45: Class in PHELPS 1440
  • Wednesday, 14:00--15:00: Office hours WvD in HFH 2151
  • Thursday, 13:00--15:00: Office hours AM in GSL = trailer 698 (in front of HFH)
  • Thursday: Announcement of homework
  • Friday, 9:00--9:50: Discussion in PHELPS 1445
  • Friday, 16:00: Homework due

ACM Tutoring

ACM Tutoring for lower division courses such as CS40 will be available this quarter on Mondays, 17:00--18:30; Harold Frank Hall 1152.

Grading

There will be 5 Homework assignments, 1 Midterm, and 1 Final. See "Course Schedule" below when these are scheduled during the quarter.

All questions of the HW Assignments, Midterm and Final will be graded using the following scale:

  • 6 points: Exemplary; student applies knowledge with virtually no conceptual or procedural errors
  • 4 points: Adequate; student applies knowledge with no significant conceptual errors and only minor procedural errors.
  • 2 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.

Your ultimate score for the course is determined as follows.

  • The 5 Homeworks and 1 Midterm all count for an equal amount; the final counts for 2 Homeworks. This means that your total grade will be determined according to: 5 Homeworks + 1 Midterm + 1 Final = 5/8 + 1/8 + 2/8. In other words, each homework and midterms counts for 1/8th, the final counts for 2/8th.
  • However, during the Final you are allowed to decide whether you want to drop your lowest score among your homeworks and midterms and let your final count for 3/8th, in which case the equality becomes: 4 Homeworks + 1 Midterm + 1 Final = 4/8 + 1/8 + 3/8 or 5 Homeworks + 0 Midterm + 1 Final = 5/8 + 0/8 + 3/8.

Means and Standard Deviations of HWs, MT, and F

The scores for the HWs, MT and F will be normalized before being added together. To calculate your 'normalized score', you take your score, subtract the mean, and divide by the standard deviation. The relevant means and standard deviations will be listed here as the quarter progresses.

  • Homework 1 has mean 15.62, standard deviation 7.44, minimum 1, and maximum 24
  • Homework 2 has mean 15.21, standard deviation 6.33, minimum 5, and maximum 24
  • Homework 3 has mean 16.90, standard deviation 6.56, minimum 11, and maximum 24
  • Homework 4 has mean 16.38, standard deviation 8.91, minimum 13, and maximum 24
  • Homework 5 has mean 12.90, standard deviation 6.85, minimum 2, and maximum 20
  • Midterm has mean 11.66, standard deviation 5.15, minimum 3, and maximum 20

As an example, if you scored 20 points for HW1, then your normalized score for HW1 is (20 - 15.62)/7.44 = 0.59. If you scored 9 points for HW2, then your normalized HW2 score is (9 - 15.21)/6.33 = -0.98.

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.

Course Schedule

Week I (April 2--8): Combinatorics 1

  • Class topics (Monday): Introduction to CS40; Formalities of CS40; sum and product rules [Reader, §1.1, pages 2--4]
  • Class topics (Wednesday): permutations [R, §1.2, pp. 5--10]; combinations, binomials [R, §1.3, pp. 13--22]
  • Discussion topics: HW1; Exercises 1.1, 1.2 [R, p. 10]
  • Homework announcement: HW1 on Combinatorics 1 will be announced Thursday April 5 (due Friday April 13)

Week II (April 9--15): Combinatorics 2

  • Class topics (Monday): combinations, multinomials [R, §1.3, pp. 5--22]; combinations with repetitions [R, §1.4, pp. 25--33]; summary of counting techniques [R, §1.6, pp. 40--41]
  • There will no Class or Office Hours of WvD on Wednesday, April 11
  • Homework announcement: HW2 on Combinatorics 1 and 2 will be announced Thursday April 12 (due Friday April 20)
  • Discussion topics: HW2 and last minute questions about HW1
  • Homework due: HW1 is due Friday April 13 at 16:00

Week III (April 16--22): Propositional Logic 1

  • Class topics (Monday): connectives, truth tables [R, §2.1, pp. 45--51]
  • Class topics (Wednesday): laws of logic, applications of propositional logic [R, §2.2, pp. 53--64]
  • Homework announcement: HW3 on Propositional Logic 1 will be announced Thursday April 19 (due Friday April 27)
  • Discussion topics: return of HW1, HW3, last minute questions about HW2
  • Homework due: HW2 is due Friday April 20 at 16:00

Week IV (April 23--29): Propositional Logic 2

  • Class topics (Monday): rules of inference [R, §2.3, pp. 65--82]
  • Class topics (Wednesday): proofs [R, §2.5, pp. 101--114]
  • Discussion topics: return of HW2, last minute questions about HW3
  • Homework due: HW3 is due Friday April 27 at 16:00

Week V (April 30--May 6): First Order Logic; Sets

  • Class topics (Monday): quantifiers [R, §2.4, pp. 84--98]; proofs [R, §2.5, pp. 101--114]
  • Class topics (Wednesday): sets and subsets [R, §3.1, pp. 121--132]; set operations, laws of set theory [R, §3.2, pp. 134--144]
  • Discussion topics: return of HW3, next week's Midterm

Week VI (May 7--13): Sets

  • Monday May 7: Midterm on Combinatorics and Logic; 12:30--13:45 in PHELPS 1440
  • Material: Everything on Combinatorics and Logic of Weeks I--V.Monday; the slides, HW1--3 and old Midterm should give you an idea what to expect
    • Amount: The MT will have 3 open questions and 3 True/False questions, for 3 x 6 + 3 x 2 = 24 points (= one HW)
    • Allowed: One, double-sided, US letter-sized paper of notes, readable by the human eye
    • Not allowed: More notes than allowed, any kind of electronics
  • Class topics (Wednesday): Venn diagrams [R, §3.3, pp. 146--148]; transformations of sets [R, §5.1, pp. 156--159];
  • Homework announcement: HW4 on Sets will be announced Thursday May 10 (due Friday May 18)
  • Discussion topics: past Midterm, HW4

Week VII (May 14--20): Sets, Et Cetera

  • Class topics (Monday): relations [R, §5.2, pp. 160--162]; functions [R, §5.3, pp. 163--164]
  • Class topics (Wednesday): functions and infinity [R, §5.3, pp. 163--164]
  • Discussion topics: last minute questions about HW4; Midterm
  • Homework due: HW4 is due Friday May 18 at 16:00

Week VIII (May 21--27): Induction

  • Class topics (Monday): mathematical induction [R, §4.1, pp. 180--196]
  • Class topics (Wednesday): strong induction [R, §4.2, pp. 200--207]; recursive definitions, generalized induction [R, §4.3, pp. 210--224]
  • Homework announcement: HW5 on Induction will be announced Thursday May 24 (due Friday June 1)
  • Discussion topics: return of HW4, HW5

Week IX (May 28--June 3): Recursion

  • Monday May 28 is Memorial Day, hence there will be no class this day
  • Class topics (Wednesday): graphs [R, §5.4, pp. 165--169], trees [R. §5.5, pp. 170--175]; more on recursive definitions, generalized induction [R, §4.3, pp. 210--224]
  • Discussion topics: last minute questions about HW5
  • Homework due: HW5 is due Friday June 1, at 16:00

Week X (June 4--8): "Dead week"

  • Class topics (Monday): "you and your grade", grade estimation; course evaluation; formalities of the Final
  • Class topics (Wednesday): updated grade estimation; review and Q&A on material of Final
  • Discussion topics: return of HW5, Final

Finals Week (June 9--15)

  • Final: Tuesday, June 12, 12:00--15:00
  • Material: Everything covered in class