MIT OpenCourseWare
  • OCW home
  • Course List
  • about OCW
  • Help
  • Feedback
    • Support MIT OCW

 » MIT OpenCourseWare » Electrical Engineering and Computer Science » Mathematics for Computer Science (SMA 5512), Fall 2002

Calendar

This calendar shows the weekly schedule for the course, which usually includes three lecture and group problem solving sessions per week. The readings for each week are from the course textbook, Discrete Mathematics and its Applications, Fourth Edition, by Kenneth H. Rosen, and the course notes. This calendar provides links to lecture slides, class problems, course notes, problem sets, quizzes and exams, and relevant links of interest. In addition to problem sets, reading problems, related to the reading assignments for the week, are completed by students using an online tutor. The online tutor is currently not available through this site. Instructors who are interested in obtaining online tutor materials can contact MIT OpenCourseWare with their requests.
Week 1
Topics: Course Overview, Basic Proof Methods, Propositional Logic
  • Reading: Syllabus, Course Notes 1 (PDF), Rosen: 1.1-6, 2.3, 2.4 through Lemma 1, 3.1 through Example 26.
  • Due this week: Problem Set 1 (PDF), Solutions (PDF), Reading Problems 1 (Online Tutor)
  • Wednesday (First day of class)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 2
Topics: Quantifiers, Induction, Strong Induction
  • Reading: Course Notes 2 (PDF); Rosen: 3.2, 3.3 through Example 6.
  • Due this week: Problem Set 2 (PDF), Solutions (PDF), Reading Problems 2 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
Week 3
Topics: Relations
  • Reading: Course Notes 3 (PDF); Rosen: 6.1, 6.3-6.6 (ignore Warshall's algorithm and lattices).
  • Due this week: Problem Set 3 (PDF), Solutions (PDF), Reading Problems 3 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
Week 4
Topics: Graphs
  • Reading: Course Notes 4 (PDF); Supplementary (optional) Rosen: 7.1-7.4, 7.8, 8.1.
  • Due this week: Problem Set 4 (PDF), Solutions (PDF), Reading Problems 4 (Online Tutor)
  • Wednesday
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • The Four Color Theorem history and proof.
  • The Oracle of Bacon at Virginia. Can you find an actor with a Bacon number higher than 4?
Week 5
Topics: State Machines, Invariants and Termination
  • Reading: Course Notes 5 (PDF - 1.0 MB)
  • Due this week: Problem Set 5 (PDF), Solutions (PDF), Reading Problems 5 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 6
Topics: Recursive Definitions and Structural Induction
  • Reading: Course Notes 6 (PDF); Optional: Rosen 3.3
  • No Reading Problems.
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 7
Topics: Sums and Series, Products, Stirling's Formula, Asymptotics
  • Reading: Course Notes 7 (PDF); Optional: Rosen 1.7-8; a one-page derivation of Stirling's Formula (Romik, D. "Stirling's Approximation for n!: the Ultimate Short Proof?," American Mathematical Monthly, 107 (2000), 556-557.)
  • Due this week: Problem Set 6-7 (PDF) , Solutions (PDF), Reading Problems 7 (Online Tutor)
    • Notes on PS6-7, Problem 1:
      • glb ::= "greatest-lower-bound'' and lub ::= "least-upper-bound'', cf. Rosen, p. 423.
      • An example payoff tree and its max-value: (PDF)
  • Wednesday
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 8
Topics: Counting by Matching, Pigeonhole, Sum and Product Rules, Inclusion/Exclusion, Permutations
  • Reading: Course Notes 8 (PDF); Optional: Rosen 4.1-2
  • Due this week: Problem Set 8 (PDF), Solutions (PDF), Reading Problems 8 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 9
Topics: Division Rule, Combinations, Counting with Repetitions
  • Reading: Course Notes 9 (A section on the Magic Trick has been added) (PDF - 1.1 MB); Optional: Rosen 4.3, 4.6
  • Due this week: Problem Set 9 (PDF), Solutions (PDF), Reading Problems 9 (Online Tutor)
  • Monday
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 10
Topics: Introduction to Probability, Conditional Probability, Independence
  •  Reading:
    • For Reading Problems and Wed-Fri Lectures: Complete Course Notes 10 (PDF - 1.4 MB); Optional: Rosen 4.4, and 4.5 through Example 9, p. 274.
    • For Problem Set 10 (PDF) and Quiz 2 only part of the reading is necessary: Course Notes 10, sections 1--9 (PDF - 1.4 MB); Optional: Rosen 4.4, and 4.5 through Example 4, p.271.
  • Due this week: a short Problem Set 10 (PDF), Solutions (PDF), Reading Problems 10 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 11
Topics: Introduction to Random Variables: Distributions
  • Quiz 2 (PDF), Appendix (PDF), Solutions (PDF)
  • Reading For Friday Lecture: Course Notes 11-12 (PDF - 1.4 MB), Sections 1--4.
  • No Reading Problems.
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 12
Topics: Random Variables: Expectation
  • Reading: Course Notes 11-12 (PDF - 1.4 MB); Optional: Rosen 4.5 thru Example 18.
  • Due this week: Problem Set 11-12, (PDF), Solutions (PDF), Reading Problems 11-12 (Online Tutor)
  • Monday
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 13
Topics: Variance, Deviation from the Mean, Weak Law of Large Numbers
  • Reading: Course Notes 13-14 (PDF - 1.6 MB), Sections 1--6.2
  • Due this week: Problem Set 13-14 (PDF), Solutions (PDF), Reading Problems 13 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 14
Topics: Weak Law of Large Numbers, Sampling, Confidence, Random Walks, Chernoff Bound
  • Reading: Course Notes 13-14 (PDF - 1.6 MB), Sections 6.3--18
  • Due this week: Reading Problems 14 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
Week 15
Topics: Central Limit Theorem, Poisson Distribution, Strong Law of Large Numbers
  • Reading: Lecture Notes 15 (PDF)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Final Exam Appendix: (PDF)
    • Exit Self-Assessment (PDF)
Week 16
Final Exam
  • with corrections (PDF), Appendix (PDF),
  • draft solution (PDF)
  • original as used (PDF)
 
Creative Commons - some rights reserved

Your use of the MIT OpenCourseWare site and course materials is subject to the conditions and terms of use in our Legal Notices section.