CS40, UCSB, 2008-08/09

Copyright 2008 Wim van Dam (UC Santa Barbara)

Announcements

  • [Sep 9] The answers to Homeworks 3 and 4 have been posted.
  • [Sep 8] Regarding Homework 4, Question 3: the equality sign should be interpreted as an "element of" symbol when you view Omega(2^n) as a set of functions.
  • [Sep 8] Office hours of the last Week: WvD Monday 3:30-4:30, PK Tuesday 3:30-4:30.
  • [Sep 8] Extra slide about functions of big O posted below.
  • [Sep 8] Slides with information about the Final posted below.
  • [Sep 3] Slides of Week 5, "Induction", have been posted.
  • [Sep 2] New homework "Induction" has been posted below. It will be due Tuesday, September 9, before 11 am.
  • [Aug 27] Slides of Week 4, "Structures", have been posted.
  • [Aug 26] New homework "Structures" has been posted below. It will be due Wednesday, September 3, before 11 am.
  • [Aug 26] Office hours of WvD have moved to Tuesday 3:30 - 4:30 pm.
  • [Aug 25] The new homework assignment "Structures" will be posted on Tuesday the 26th. It will be due on Wednesday September 3, before 11 am.
  • [Aug 20] Notes on the Midterm and some recommended Exercises have been posted. Please read this as you are preparing for Monday's Midterm examination.
  • [Aug 20] Slides of Week 3, "Sets", have been posted.
  • [Aug 20] There was a small mistake in the answer to "Logic" Question 4 (Designing circuits), which has been corrected.
  • [Aug 19] Answers to Homework "Logic" have been posted below.
  • [Aug 19] For practice purposes an old CS40 Midterm and its answers has been posted below.
  • [Aug 19] Answers to Homework "Counting" have been posted below.
  • [Aug 13] Slides of Week 2, "Logic", have been posted.
  • [Aug 13] Here is a link describing IBM's research on logic optimization.
  • [Aug 13] Here is a link to the Clay Millennium Problem: P versus NP.
  • [Aug 11] Homework "Logic" has been posted below.
  • [Aug 6] Last sequence of slides on counting are posted below.
  • [Aug 5] The slides on Counting of Monday and Tuesday have been posted in the Schedule and Slides section below.
  • [Aug 5] Please remember to do the home-experiment before Wednesday's class: flip a coin 100 times and record how many times "heads" comes up. We will be using these statistics to test the predictive powers of the binomial distribution.
    • [Aug 5] The original homework assignment had a typo: the summation of Question 4 should use the variable k, not j. The current version has this corrected.
    • [August 4] The Homework "Counting" and the slides "Formalities and introduction" have been posted (see below at the Schedule and Slides section); the slides on counting will be posted later this week.
    • [July 17, 2008] Welcome to the course site of CS40, "Foundations of Computer Science", UC Santa Barbara, Summer 2008

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 Summer 2008

Professor:

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

Teaching Assistant:

  • Pegah Kamousi
    • pegah@cs.____.___

Reader:

This course has a required reader that will be available at The Alternative in Isla Vista.

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)

Weekly Schedule:

    • Monday 11:00-12:25: Class in PHELPS 1401
    • Tuesday before 11 am: homework typically due
    • Tuesday 11:00-12:25: Class in PHELPS 1401
    • Tuesday 3:30-4:30 pm: office hours WvD in HFH 2151
    • Wednesday 11:00-12:25: Class in PHELPS 1401
    • Wednesday 2:00-3:00: office hours PK in HFH 2120b
    • Thursday 11:00-12:25: Discussion in PHELPS 1401
    • Friday 2:00-3:00: office hours PK in HFH 2120b

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 by: 4 x 10% (Homeworks) + 30% Midterm + 30% Final Exam.

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 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 and Slides

Week 1 (August 4-10): "Counting"

Week 2 (August 11-17): "Logic"

Week 3 (August 18-24): "Sets"

Week 4 (August 25-31): "Structures"

Week 5 (September 1-7): "Induction"

Week 6 (September 8-10): "the final stretch"

  • Monday and Tuesday: last minute issues, odds & ends, leftovers, Q&A, and so on
  • Slides: Information on Final Exam
  • Wednesday September 10: Final Examination