CS 70, Fall 2005
Discrete Mathematics for Computer Science


Announcements

[Announcements] [Lectures] [Assignments] [Midterm Study Questions] [Course Overview] [Contact Information]

Grading Summary

Taking Third Midterm.

  • 53 points: Homeworks (average of all but your lowest hw score, with the average capped at 50 pts).
  • 42 points: Midterm I (held in class).
  • 42 points: Midterm II (held in class).
  • 42 points: Midterm III (Dec 12, 5:30-7:00 pm).
  • A+: [*]         A: 143-179      A-: 134-142
    B+: 125-133     B: 116-124      B-: 107-115
    C+: 98-106     C: 89-97      C-: 80-88
    D: 71-79        F: 0-70
    [*] A+ awarded at instructors' discretion
    
    The instructors reserve the right to add extra points to your grade at the end of the class (for instance, if the final exam was unexpectedly harder than intended).

    Taking Normal Final.

    Grading will be on an absolute scale. Your final grade will be in the range 0-200 and will be computed as the sum from five categories:

    The grading standard is available and has been fixed at the beginning of the course:

    A+: [*]         A: 160-200      A-: 150-159
    B+: 140-149     B: 130-139      B-: 120-129
    C+: 110-119     C: 100-109      C-: 90-99
    D: 70-89        F: 0-69
    [*] A+ awarded at instructors' discretion
    
    The instructors reserve the right to add extra points to your grade at the end of the class (for instance, if the final exam was unexpectedly harder than intended).

    Practice for Midterms/Final


    Instructors:
      Satish Rao

    TA:
      Kenji Obata

    Addresses:
      Contact address: cs70@cory.eecs
      Web page: http://www-inst.eecs.berkeley.edu/~cs70/

    Lectures:
      TuTh, 3:30-5:00, 9 Lewis

    Sections:
      101. W 2:00-3:00, 6 Evans
      102. Th 10:00-11:00, 51 Evans

    Office Hours:
      Rao: Mon 1:15-2:15pm, Th 11-12am 681 Soda.
      Obata: Mon 2:15-3:30pm, 5th floor alcove or 587 Soda.

    Homework Preparation



    Course Overview

    The goal of this course is to introduce students to ideas and techniques from discrete mathematics that are widely used in Computer Science. The course aims to present these ideas "in action"; each one will be geared towards a specific significant application. Thus, students will see the purpose of the techniques at the same time as learning about them.

    Broadly speaking the material is similar to that in Math 55; however, Math 55 covers a wider range of topics in less depth and with fewer applications, and is less closely tailored to Computer Science. You should take this course as an alternative to Math 55 if you are intending to major in Computer Science and if you found the more conceptual parts of CS 61A enjoyable and relatively straightforward.

    List of course topics:


    Assignments, and Exams

    All homeworks, except the first one, are due on Thursday at 3:30pm. The deadlines will be enforced strictly. Late homework will be accepted only in extraordinary circumstances, and may in any case be penalized. The lowest homework grade will be dropped.

    Homeworks will be submitted online (no paper submissions accepted). We require PDF or text submissions. We recommend using LaTeX to compose your homeworks. (We do not accept raw Microsoft Word .doc files; if you must use Word, please convert to PDF and then submit the PDF file.)

    Homeworks:

    Homework solution templates are also available as filename ~cs70/templates/templateXX.tex on Instructional machines. Also available: information about latex, and information on grading, and feedback from the reader on your homeworks.

    Exams:

    Old exams from previous semesters are available.


    Lectures

    The following portion of the schedule is tentative and subject to change. Readings in Rosen are optional but advisable, in case you want extra background on the subject or a different presentation from a second point of view.

    Topic Readings
    1 Aug 30 Overview; intro to logic Notes [ps] [pdf].
    [Rosen 1.1, 1.2]
    2 Sept 1 Propositional logic; quantifiers [Rosen 1.3-1.5]
    3 Sept 6 Induction Notes [ps] [pdf].
    [Rosen 3.3]
    4 Sept 8 Strong induction Notes [ps] [pdf].
    [Rosen 3.3]
    5 Sept 13 Structural induction Notes [ps] [pdf].
    [Rosen 3.4]
    6 Sept 15 Proofs about algorithms Notes [ps] [pdf].
    [Rosen 3.5]
    7 Sept. 20 Stable marriages External notes
    8 Sept 22 Algebraic algorithms Notes [ps] [pdf].
    [Rosen 2.1]
    9 Sept 27 Number theory (continuing from same notes as last time).
    [Rosen 2.4,2.5]
    10 Sept 29 Primality testing Notes [ps] [pdf].
    [Rosen 2.6]
    11 Oct. 4 Cryptography/RSA Notes [ps] [pdf]. Also [ps] [pdf].
    [Rosen 2.6] More Notes on Digital Cash.
    12 Oct 6 Algebra I: Polynomials, Finite Fields, Secret Sharing [ps] [pdf]
    13 Oct. 11 Algebra II: Error Correcting Codes Notes [ps] [pdf]
    Oct. 13 Midterm
    14 Oct. 18 Graph Theory I: Introduction to Graphs, Eulerian and Hamiltonian circuits Notes [ps] [pdf] [Rosen 8.1,8.2,8.5]
    15 Oct. 20 Graph Theory II: Hypercubes Notes [ps] [pdf]
    16 October 25 Basic Combinatorics Notes:
    [Rosen 4.1,4.3-4.5]
    17 October 27 Probability I: Sample Spaces and Events Notes: [ps] [pdf] [Rosen 5.1,5.2]
    18 November 1 Probability II: "Two Killer Apps," Union Bound, Bose-Einstein and Fermi-Dirac Statistics Notes: [ps] [pdf]
    19 November 3 Probability III: Conditional Probability Notes: [ps] [pdf] [Rosen 5.2]
    20 November 8 Probability IV: Random Variables Notes: [ps] [pdf] [Rosen 5.2]
    21 November 10 Probability V: Some Distributions Notes: [ps] [pdf] [Rosen 5.2]
    22 November 15 Probability VI: Markov, Chebyshev Notes: [Rosen 5.2] [ps] [pdf]
    23 November 17 Probability VII: Idependently and Identically Dist. Variables Notes: [ps] [pdf] [Rosen 5.2]
    November 22 Midterm II
    24 November 29 How to Lie with Statistics. Notes: [pdf]

    25 December 1 Infinity and Diagonalization Notes: [CMU course] Look at lectures on Cantor and Turing.

    26 December 6 Turing Notes: [CMU course] Look at lectures on Cantor and Turing.

    27 December 8 Quantum Computing

    Extra optional reading:


    Textbooks

    Unfortunately, there is no book that adequately covers all the material in this course at the right level. We will provide lecture notes for most of the lectures. The book Discrete Mathematics and its Applications, 5th Edition (Kenneth H. Rosen, McGraw-Hill, Inc., New York, 2003) is recommended but not required.

    Note that you should not view the availability of lecture notes as a substitute for attending class: our discussion in class may deviate somewhat from the written material, and you should take your own notes as well.


    Prerequisites

    You must have taken CS 61A, Math 1A and Math 1B (or equivalents).

    The homeworks will be graded by the course reader; depending on the time available, we reserve the right to grade some of the problems in more detail than others, and to award correspondingly more credit for them. Thus, if you turn in incomplete homeworks you are gambling on your grade.


    Collaboration

    Collaboration on homeworks is welcome and warmly encouraged. You may work in groups of at most three people; however, you must always write up the solutions on your own. Similarly, you may use references to help solve homework problems, but you must write up the solution on your own and cite your sources. You may not share written work or programs with anyone else. You may not receive help on homework assignments from students who have taken the course in previous years, and you may not review homework solutions from previous years.

    You will be asked to acknowledge all help you received from others. This will not be used to penalize you, nor will it affect your grade in any way. Rather, this is intended only for your own protection.

    If you work in a group, you'll be required to change group partners after the first midterm.

    In writing up your homework you are allowed to consult any book, paper, or published material. If you do so, you are required to cite your source(s). Simply copying a proof is not sufficient; you are expected to write it up in your own words, and you must be able to explain it if you are asked to do so. Your proofs may refer to course material and to homeworks from earlier in the semester. Except for this, all results you use must be proved explicitly.

    Copying solutions or code, in whole or in part, from other students or any other source without acknowledgment constitutes cheating. Any student found to be cheating in this class will automatically receive an F grade and will also be referred to the Office of Student Conduct.

    We believe that most students can distinguish between helping other students and cheating. Explaining the meaning of a question, discussing a way of approaching a solution, or collaboratively exploring how to solve a problem within your group is an interaction that we encourage. On the other hand, you should never read another student's solution or partial solution, nor have it in your possession, either electronically or on paper. You should write your homework solution strictly by yourself. You must explicitly acknowledge everyone who you have worked with or who has given you any significant ideas about the homework. Not only is this good scholarly conduct, it also protects you from accusations of theft of your colleagues' ideas.

    Presenting another person's work as your own constitutes cheating, whether that person is a friend, an unknown student in this class or a previous semester's class, a solution set from a previous semester of this course, or an anonymous person on the Web who happens to have solved the problem you've been asked to solve. Everything you turn in must be your own doing, and it is your responsibility to make it clear to the graders that it really is your own work. The following activities are specifically forbidden in all graded course work:

    Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students.

    In our experience, nobody begins the semester with the intention of cheating. Students who cheat do so because they fall behind gradually and then panic. Some students get into this situation because they are afraid of an unpleasant conversation with a professor if they admit to not understanding something. We would much rather deal with your misunderstanding early than deal with its consequences later. Even if you are convinced that you are the only person in the class that doesn't understand the material, and that it is entirely your fault for having fallen behind, please overcome your feeling of guilt and ask for help as soon as you need it. Remember that the other students in the class are working under similar constraints--they are taking multiple classes and are often holding down outside employment. Don't hesitate to ask us for help--helping you learn the material is what we're paid to do, after all!


    Contact information

    If you have a question, your best option is to post a message to the ucb.class.cs70 newsgroup. The staff (instructor and TAs) will check the newsgroup regularly, and if you use the newsgroup, other students will be able to help you too. When using the newsgroup, please do not post answers to homework questions before the homework is due.

    If your question is personal or not of interest to other students, you may send email to cs70@cory.eecs.berkeley.edu. Email to cs70@cory is forwarded to the instructor and all TAs. We prefer that you use the cs70@cory address, rather than emailing directly the instructor and/or your TA. If you wish to talk with one of us individually, you are welcome to come to our office hours. If the office hours are not convenient, you may make an appointment with any of us by email.

    The instructor and TAs will post announcements, clarifications, hints, etc. to this website and to the class newsgroup. Hence you should read the newsgroup regularly whether you post questions to it or not. If you've never done this before, there is online information about how to access UCB newsgroups (see also here for more).

    We always welcome any feedback on what we could be doing better. If you would like to send anonymous comments or criticisms, please feel free to use an anonymous remailer to send us email without revealing your identity, like this one.


    Accounts and grading software

    We will perhaps use 'class' accounts this semester. We will account forms in class. Lab machines may be found in 2nd floor Soda. Further information is here.

    After you have obtained your account, you will need to register with our grading software. See these instructions.


    Miscellaneous

    In addition to office hours for the class instructors, HKN (the Eta Kappa Nu honor society) offers free drop-in tutoring. Contact them for more information.

    Mail inquiries to cs70@cory.eecs.berkeley.edu.