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

Copyright 2013 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

  • 2013-08-04: Grades have been submitted
  • 2013-07-31: An old Final from Fall 2010 has been posted below, as well as its answers
  • 2013-07-31: Slides with information on Final have been posted below
  • 2013-07-31: Answers to HW4 have been posted below
  • 2013-07-30: Slides on graphs and trees have been posted
  • 2013-07-25: On Thursday July 25 WvD will have no office hour; instead, on Tuesday July 30 WvD will have extended office hours between 13:00 and 15:00
  • 2013-07-25: Slides on induction have been posted below
  • 2013-07-25: Answers to HW3 have been posted below
  • 2013-07-24: Homework 4 has been posted below; it is due Wednesday, July 31, at 11:00 in the CS40 homework box, which is situated in copy room 2108 in Harold Frank Hall.
  • 2013-07-23: Slides on infinity have been posted below
  • 2013-07-22: Slides on sets, relations, and functions have been posted below
  • 2013-07-18: Answers to HW2 have been posted below
  • 2013-07-17: Homework 3 has been posted below; it is due Wednesday, July 24, at 11:00 in the CS40 homework box, which is situated in copy room 2108 in Harold Frank Hall.
  • 2013-07-12: Slides on first order logic and proofs have been posted below
  • 2013-07-12: Answers to MT have been posted below
  • 2013-07-11: The means and standard deviations of the scores of HW1 and MT have been posted below in the section "Means..."
  • 2013-07-10: Homework 2 has been posted below; it is due Wednesday, July 17, at 11:00 in the CS40 homework box, which is situated in copy room 2108 in Harold Frank Hall.
  • 2013-07-09: Recommended exercises in the reader for the midterm are: Exercises 1.1 & 1.2: 1, 11, 12, 15, 24, 28, 36; Exercises 1.3: 1, 5, 18, 23; Exercises 1.4: 1, 3, 7, 22; Exercises 2.1: 1, 10, 11; Exercises 2.2: 1, 4, 10, 14, 18; Exercises 2.3: 1, 5, 7
  • 2013-07-08: Answers to the old Midterm of Spring 2012 have been posted
  • 2013-07-04: Additional information regarding the midterm has been posted in a new section "Midterm", below
  • 2013-07-04: Answers to HW1 have been posted
  • 2013-07-03: Old Midterm on Combinatorics and Logic of Spring 2012 has been posted
  • 2013-07-03: Slides "Propositional logic" of Week II have been posted
  • 2013-06-27: Slides "Combinatorics" have been posted
  • 2013-06-26: Homework 1 has been posted below; it is due Wednesday, July 3, at 11:00 in the CS40 homework box, which is situated in copy room 2108 in Harold Frank Hall. Do not attempt to hand in your homework in class.
  • 2013-06-25: Correction: the HWs will be announced and are due on Wednesdays, not Tuesdays
  • 2013-06-25: Slides "Formaties, Introduction" posted below
  • 2013-06-19: Remember to pay your course fee before July 1, or to drop the course before June 28
  • 2013-06-18: Schedule for homework assignments, midterm, and final has been determined (see Course Schedule below)
  • 2013-06-10: The CS40 Final is scheduled for Friday, August 2, 16:00--19:00 in Phelps 1401. This may conflict with other finals that you might have; contact WvD as soon as possible if this is indeed the case.
  • 2013-05-23: Welcome to the site of CS40, Summer 2013

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

  • Victor Amelkin
    • victor@cs.____.___

Reader

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

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, 14:00--16:00, GSL (Trailer 698): office hours VA
  • Tuesday, 11:00--12:20, Phelps 1401: class
    • Tuesday, 13:00--14:00, HFH 2151: office hour WvD
  • Wednesday, 11:00: homework due
    • Wednesday, 11:00--12:20, Phelps 1401: class
    • Wednesday: announcement homework
  • Thursday, 11:00--12:20, Phelps 1401: class
    • Thursday, 13:00--14:00, HFH 2151: office hour WvD
  • Friday, 11:00--12:20, Phelps 1401: discussion

Grading

There will be 4 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 4 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: 4 Homeworks + 1 Midterm + 1 Final = 4/7 + 1/7 + 2/7. In other words, each homework and midterm counts for 1/7th, the final counts for 2/7th.
  • 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/7th, in which case the equality becomes: 3 Homeworks + 1 Midterm + 1 Final = 3/7 + 1/7 + 3/7 or 4 Homeworks + 0 Midterm + 1 Final = 4/7 + 0/7 + 3/7.

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.

  • HW1: Mean: 17.14, standard deviation: 10.63
  • HW2: Mean: 13.71, standard deviation: 11.31
  • HW3: Mean: 11.14, standard deviation: 10.16
  • HW4: Mean: 12.14, standard deviation: 11.59
  • MT: Mean: 15.36, standard deviation: 6.33

Midterm

  • Date, time, location: The Midterm will be on Wednesday, July 10, between 11:00 and 12:20 in Phelps 1401 (i.e. regular class time and location).
  • Topics: Combinatorics and Propositional Logic as discussed in class in Weeks I and II. The slides of these classes are posted below. In the Reader this is discussed in pages 2--84, excluding the topics: Binomial Theorem (Theorem 1.1 and 1.2, pp. 20--22), Catalan Numbers (Section 1.5, pp. 35--39), Duality (Definition 2.3, Theorem 2.1, p. 57), Switching Networks (Example 2.18, pp. 62--65).
  • Allowed: You are allowed to bring with you one page of notes (letter-sized, double sided, readable by human eyes), drinks, non-noisy food, tissues and a watch.
  • Not allowed: You are not allowed to bring with you: the reader, more than one page of notes, electronic devices, et cetera.
  • Importance/What to expect: For your final grade the Midterm 'weighs' the same as a homework assignment (24 points). You can expect 3 or 4 open questions, and somewhere between 3 and 6 True/False questions. An old midterm of Spring 2012 has been posted below.

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 (06-24/30): Combinatorics

  • Class topics (Tu): Introduction to CS40; Formalities of CS40; sum and product rules [Reader, §1.1, pages 2--4]
  • Class topics (We): permutations [R, §1.2, pp. 5--10]; combinations, binomials [R, §1.3, pp. 13--22]
  • (We): announcement of HW1 "Combinatorics"; due Wednesday July 3 at 11:00
  • Class topics (Th): combinations with repetitions [R, §1.4, pp. 25--33]; summary of counting techniques [R, §1.6, pp. 40--41]
  • Discussion topics (Fr): HW1 "Combinatorics"

Week II (07-01/07): Propositional Logic

  • Class topics (Tu): connectives, truth tables [R, §2.1, pp. 45--51]
  • Wednesday July 3, 11:00: HW1 "Combinatorics" due
  • Class topics (We): laws of logic, applications of propositional logic [R, §2.2, pp. 53--64]; rules of inference [R, §2.3, pp. 65--82]
  • Thursday July 4, Independence Day: no class
  • Discussion topics (Fr): return of HW1 "Combinatorics", upcoming Midterm

Week III (07-08/14): Propositional and First Order Logic

  • Class topics (Tu): logic and complexity theory, quantifiers [R, §2.4, pp. 84--98]
  • Class topics (We): Midterm on Combinatorics and Propositional Logic (all the material of Week I and II)
  • (We): HW2 "First order logic and proofs" announced; due Wednesday July 17, 11:00
  • Class topics (Th): proofs [R, §2.5, pp. 101--114]
  • Discussion topics (Fr): return of Midterm, discussion of HW2 "First order logic and proofs"

Week IV (07-15/21): Sets

  • Class topics (Tu): sets and subsets [R, §3.1, pp. 121--132]; set operations, laws of set theory [R, §3.2, pp. 134--144]
  • Wednesday July 17, 11:00: HW2 "First order logic and proofs" due
  • Class topics (We): Venn diagrams [R, §3.3, pp. 146--148]; transformations of sets [R, §5.1, pp. 156--159];
  • (We): HW3 "Sets" announced; due Wednesday July 24, 11:00
  • Class topics (Th): relations [R, §5.2, pp. 160--162]; functions and infinity [R, §5.3, pp. 163--164]; countable infinity
  • Discussion topics (Fr): return of H2 "First order logic and proofs", HW3 "Sets"

Week V (07-22/28): Sets, Et cetera; Induction

  • Class topics (Tu): infinity [R, §5.3, pp. 163--164]; countable versus uncountable infinity, Cantor's diagonalization argument
  • Wednesday July 24, 11:00: HW3 "Sets" due
  • Class topics (We): mathematical induction [R, §4.1, pp. 180--196]
  • (We): HW4 "Infinity, Induction" announced; due Wednesday July 31, 11:00
  • Class topics (Th): strong induction [R, §4.2, pp. 200--207]; recursive definitions, generalized induction [R, §4.3, pp. 210--224]
  • Thursday July 25: No office hour WvD
  • Discussion topics (Fr): return of HW3 "Sets", HW4 "Sets etc. and induction"

Week VI (07-29/08-03): Extra material; Final

  • Class topics (Tu): 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]
  • Tuesday July 30: Extended office hours WvD between 13:00 and 15:00
  • Wednesday July 31, 11:00: HW4 "Sets etc. and induction" due
  • Class topics (We): "you and your grade", grade estimation; course evaluation; formalities of the Final
  • Class topics (Th): updated grade estimation; review and Q&A on material of Final
  • Discussion topics (Fr): return of HW4 "Sets etc. and induction", Final
  • Final: Friday, August 2, 16:00--19:00, Phelps 1401
  • Material: Everything covered in class
  • Please check that the date and time of this final does not come into conflict with any other final that you might have this day. Contact WvD as soon as possible if it does.