MC 215 MATHEMATICAL REASONING
AND DISCRETE STRUCTURES
FALL 2008 HOME PAGE

  • Class Meetings:
    • Mondays 11:15-12:10;
    • Wednesdays and Fridays 11:15-12:35
  • Instructor:
    • Alice Dean, Professor, Mathematics & Computer Science
    • Email
    • Phone: 580-5286
    • Home Page
  • Course Info Sheet

 

 

DATE
TOPICS

CLASS SLIDES
READING, EXERCISES, ASSIGNMENTS, AND OTHER FILES
Wednesday, 12/3/08
Permutations and Combinations
Combinatorial Identities
Binomial Coefficients
  • READING: 6.2, 6.7
  • EXERCISES: pp. 288-291: 1-4, 10-11, 25-26, 43-44; pp. 324-325: 1-4
Monday, 12/1/08
Combinatorics
Addition and Multiplication Principles
Inclusion-Exclusion Formula
  • READING: 6.1
  • EXERCISES: pp. 274-276: 4, 6, 10, 17, 19, 86-888
Monday, 11/24/08
Linear Homogeneous Recurrence Relations
Friday, 11/21/08
Recurrence Relations (also called Difference Equations)
Wednesday, 11/19/08
Return, go over Exam #2
More on recursion
Euclidean Algorithm
  • READING: 5.3 “lite”
  • EXERCISES: pp. 258-259: 1-4, 16, 17
Monday, 11/17/08
Recursive functions and algorithms
  • READING: 4.4
  • EXERCISES: pp. 219-220: 13, 14, 26, 27
Friday, 11/14/08
More on order of growth
  • READING: 4.3
  • EXERCISES: pp. 207-210: 1-15, and also put all these functions into increasing Big Theta-order, giving each class a simple Big Theta-label
Wednesday, 11/12/08
EXAM #2
No new slides
Monday, 11/10/08
Review HW #4
No new slides
Friday, 11/7/08
Big-Oh and the Hierarchy of Functions
  • READING: Still 4.3
  • EXERCISES: pp. 207-210: 16, 18, 19, 20
Wednesday, 11/5/08
INFO ABOUT EXAM #2
Analysis of Algorithms
  • READING: 4.3
  • EXERCISES: pp. 207-210: 1, 2, 7, 8
Monday, 11/3/08
Review HW #3; more on sorting
No new slides
Friday, 10/31/08
Selection Sort and
Insertion Sort
  • Hand-in Homework #4
  • READING: Still 4.2
  • EXERCISES: pp. 192-193: 6-8, 19 (When they say
    “Algorithm 4.2.3,” you should replace it with “Selection Sort”)
Wednesday, 10/29/08
Searching and Sorting
  • READING: 4.2
  • EXERCISES: pp. 192-193: 1, 3, 14, 16
Monday, 10/27/08
Algorithms; Pseudocode
  • READING: 4.1, Appendix C
    (Omit 3.5, 3.6)
  • EXERCISES: pp. 185-186:
    4, 6, 9, 11
Wednesday, 10/22/08
Equivalence Relations
Monday, 10/20/08
Partial Orders
  • READING: Still 3.3
  • EXERCISES: pp. 158: 34, 35
Friday, 10/17/08
Relations
  • Hand-in Homework #3
  • READING: 3.3
  • EXERCISES: pp. 158: 20-23, 32 (see text for defs. of R-1 and partial order)
Wednesday, 10/15/08

Return Exam #1;
More on cardinality and countability
No new slides
Monday, 10/13/08
Strings
Friday, 10/10/08
Sequences
Wednesday, 10/8/08
EXAM #1
No new slides
Monday, 10/6/08
Exam review
No new slides
  • No new reading or exercises
Friday, 10/3/08
Bijections and inverses
Composition of functions
Wednesday, 10/1/08
INFO ABOUT EXAM #1
Floor and ceiling functions
One-to-one and onto functions
  • READING: Still 3.1
  • EXERCISES: pp. 132-134: 10, 12, 16, 17, 23, 27, 106
Monday, 9/29/08
Functions
  • READING: 3.1
  • EXERCISES: pp. 131-134--You may omit (for now) the questions about one-to-one, onto, inverse: 1-5, 51, 52
  • Optional: See the text, pp. 121-122, for two nice applications that use the mod function.
  • Summary of Proof Techniques, Ver. 1 (required)
Friday, 9/26/08
Strong and weak induction
Monday, 9/22/08 &
Wednesday, 9/24/08
Existence and uniqueness
Proof by induction
  • READING: 2.4 (omit 2.3)
  • EXERCISES: pp.86-87: 12, 14, 15,
    47; pp. 102-105: 1, 4, 17, 29, 30
Friday, 9/19/08
Problem session on basic proof techniques
Wednesday, 9/17/08
Monday, 9/15/08
2.1-2.2: Disproof; Proof by cases; Indirect proof =
proof of
contrapositive; Proofs of
equivalence = “if
and only if” proofs
  • READING: 2.2
  • EXERCISES: pp. 86-87: 3, 6, 21, 30, 31, 41
Friday, 9/12/08
2.1: Theorems and Proofs
Direct Proofs
  • READING: 2.1
  • EXERCISES: pp. 75-76: 7, 12, 13, 18, 19
Wednesday, 9/10/08
1.5-1.6: Predicates (Propositional Functions)
Quantifiers:
“For all”
“There exists”
  • READING: 1.5-1.6
  • EXERCISES: pp. 50-51: 7-20;
    p. 59: 2-45, plus #60 for these problems
Monday, 9/8/08
1.3-1.4: Converse, Inverse, Contrapositive, Biconditional, Logical Identities, Proofs and Rules of Inference
  • READING: 1.3-1.4
  • EXERCISES: pp. 30-31: 1-5, 70-71, 76; pp. 35-36: 1-3, 11-12
Friday, 9/5/08
1.2-1.3: Propositions, Logical Operators, Truth Tables,
Equivalence
  • READING: 1.2-3
  • EXERCISES: pp. 20-21: 1-5, 17, 19, 22, 24; pp. 30-31: 21-23, 60- 61
Wednesday, 9/3/08
1.1: Sets