Math 55, Summer 2017

Syllabus and Course Policies

Homework

• June 23:
  § 1.1: 7, 9bdf, 12bdf, 18, 23, 27
  § 1.2: 5, 16, 18
  § 1.3: 7, 9, 11, 21
  § 1.4: 7, 9, 15, 19, 43
  Bonus: Three gods A, R, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, R, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for "yes" and "no" are "da" and "ja," in some order. You do not know which word means which.
• June 27:
  § 1.5: 9ace, 20, 25, 30
  § 1.6: 2, 3bd, 6, 7, 15, 19
  § 1.7: 1, 8, 12, 16, 18, 24
  § 1.8: 10, 14, 18, 24, 34
  Bonus: Get together with a classmate or friend and play a game of Shake-A-WFF. Record your moves and staple to the back of this homework.
• June 30:
  § 2.1: 10, 18, 22, 26, 42, 46.
  § 2.2: 12, 16de, 26bc, 48.
  § 2.3: 1, 4bc, 14, 28, 34, 40, 44.
  § 2.5: 2, 10, 20
  Bonus: 2.5.27
• Wednesday, July 5:
  § 2.4: 26ace, 32, 34, 46.
  § 4.1: 16, 24, 30, 37, 38, 39.
  § 4.2: 2, 4, 28, 32.
  Bonus: 4.2.55
• July 14:
  § 4.3: 4aef, 11, 16ad, 28, 32abc, 40, 49, 52
  § 4.4: 2, 6bc, 7, 12bc, 16, 17, 20, 29, 30, 38.
  § 5.1: 4, 10, 19, 36, 49, 64
  § 5.2: 4, 9, 12, 14, 36
  Bonus: 5.1.53
• July 18th:
  § 5.3: 4, 6, 8, 12, 14, 17, 20
  § 6.1: 8, 16, 22a-f, 26, 40.
  Bonus: 5.3.47
• July 21th:
  § 6.2: 4, 10, 23, 26, 27, 31
  § 6.3: 12, 16, 18, 21, 24
  § 6.4: 8, 10, 14, 16, 20, 22.
  Bonus: 6.1.70
• July 25th: § 6.5: 10, 11, 16, 18, 20, 24, 47.
  § 8.5: 6, 14, 17
  § 8.6: 2, 8, 13, 16
  Bonus: 8.6.18
• Aug 1st: § 7.2: 34
  § 7.3: 6, 10, 12, 16
  § 7.4: 7, 10, 12, 24, 25, 37, 48
  § 8.1: 1, 3, 8, 12
  Bonus: 7.4.43
• Aug 4th: § 8.2: 17
  § 8.4: 6cd, 8ad, 10b, 32, 34.
• Aug 9th: § 10.1: 11, 13
  § 10.2: 5, 26, 53
  § 10.3: 34, 35, 39
  § 10.4: 28, 32, 34
  § 10.5: 2, 4, 10
  Bonus: The complement of a simple graph G=(V,E) is the graph
  G'=(V,{ {u,v} : {u,v} is not an element of E} },
  i.e., the graph whose edges are the non-edges of G. Show that for every graph G, if G is not connected then its complement must be connected.

Schedule of Quizzes

• Quiz 1: June 23rd
• Quiz 2: June 30th
• Midterm I: July 6th
  One page of double sided max 8.5x11in cheat sheets will be permitted for each midterm.
• Quiz 3: July 14th
• Quiz 4: July 21st
• Midterm II: July 27th
• Quiz 5: August 4th
• Final: August 10th
The final may include any or all topics covered in lecture, with particular emphasis on those also discussed in the textbook.
Two pages of double-sided, max 8.5x11in cheat sheets will be permitted for the final.

Outline of Topics Covered

• June 19th: Introduction
• June 20th: Predicates and Quantifiers (1.4, 1.5) worksheet
• June 21st: Rules of Inference (1.5, 1.6) worksheet
• June 22nd: Proofs (1.7, 1.8) worksheet
• June 23rd: Sets (2.1)
• June 26th: Set Operations (2.1, 2.2) worksheet
• June 27th: Functions, Recurrences (2.3, 2.4) worksheet
• June 28th: Cardinality (2.5) worksheet
• June 29th: Algorithms (3.1, 3.2) worksheet
• June 30th: Intro to Number Theory (4.1, 4.2)
• July 3rd: Primes, GCDs (4.3) worksheet
• July 5th: Euclidean Algorithm (4.3)
• July 6th: Midterm I
• July 7th: Chinese Remainder Theorem (4.4) worksheet
• July 10th: Exponentiation, Fermat's Little Theorem (4.4) worksheet
• July 11th: Induction (5.1) worksheet
• July 12th: Strong Induction (5.2) worksheet
• July 13th: Recursion, Structural Induction (5.3, 5.4) worksheet
• July 14th: Intro to Counting (6.1)
• July 17th: Pigeonhole, Binomial Theorem (6.2, 6.4) worksheet
• July 18th: Permutations and Combinations (6.3) worksheet
• July 19th: Balls and Bins, Advanced Counting (6.5) worksheet
• July 20th: Inclusion-Exclusion (8.5, 8.6) worksheet
• July 21th: Intro to Probability (7.1, 7.2) worksheet
• July 24th: Bayes' Theorem (7.3) worksheet
• July 25th: Expected Value (7.4) worksheet
• July 26th: Variance (7.4)
• July 27th: Midterm II
• July 28th: Recurrence Relations (8.1)
• July 31st: Linear Homogeneous Recurrences (8.2) worksheet
• Aug 1st: Linear Nonhomogeneous Recurrences (8.2, 8.3) worksheet
• Aug 2nd: Generating Functions (8.4) worksheet
• Aug 3rd: More Generating Functions (8.4) worksheet
• Aug 4th: Intro to Graph Theory (10.1)