Math 311w-001 - Concepts of Discrete Mathematics

Introduction

This is the web page for section 1 of Math 311w taught by Tim Reluga in the autumn of 2024.

This course introduces students to the ideas of formal knowledge, and its central roll in mathematics. Using a theorem-proof framework much like that used by Euclid millenia ago, we will study elementary number theory advances from ancient times to our current technological age. Theories of modular arithmetic, set theory, formal logic, abstract algebra, and other discrete-math topics will be covered, with applications to encryption and digital information encoding. The course will include several writing assignments to help students develop their communications skills.

Course syllabus, including class data, contact information, office hours, and grading policies (subject to change)

Our textbook is Numbers, Groups, and Codes, by Humphreys and Prest, (library link) (publisher link) and partial solutions courtesy of Prof. Gary Mullen.

Quizes

Quiz dates and past quizes, posted with their answers. (updated Oct. 28th)

• Quiz 1, Friday, September 6rd (answers)
• Quiz 2, Friday, September 13th (download here)
• Quiz 3, Friday, September 20th (answers)
• Exam 1, Friday, October 4th (solutions)
• Quiz 4, Friday, October 11th (solutions)
  • Olympics example
• Quiz 5, Friday, October 18th (solutions)
• Exam 2, Monday, November 4th (solutions)
• Quiz 6, Friday, November 8th (solutions)
• Quiz 7, Wednesday, November 20th
• Quiz 8, Wednesday, December 6th
• Final exam, Monday, December 16th, 6:50-8:40 pm, Business Bldg 106

Homework

• Monday, November 11
  • Symmetry group practice on pentagons
• Friday, November 8
  • Group identification practice
  • Try out our sudoku puzzles for group-theory Cayley tables.
• Friday, November 1
  • Problems 7-15 on function inverses and composition in this practice set
  • These problems on solving function composition equations.
• Wednesday, October 21
  • Read section 1.6 of H+P
  • Practice calculating totient and orders here
  • Practice homework: Section 1.6, problems 1,2,5,6
• Monday, October 14
  • Section 1.4, #1
  • Section 1.5, #1
  • practice with congruence arithmetic
• Monday, October 7
  • Practice homework: Section 2.3, problems 1,2,3,4,6,7,9
  • extra practice with relations
• Wednesday, October 2nd
  • Read sections 2.2 and 2.3 of H+P
  • Problems 2, 5i, 8 from section 2.2 of H+P
  • Problems 1, 2, 3 from section 2.3 of H+P
• Wednesday, September 25th
  • Problems 6-8 on deduction proofs with sets
• Monday, September 23th
  • Read section 2.1 of H+P
  • Do these set practice on set operations and cartesian products and power sets
• Friday, September 20th
  • Problems 1-5 here
  • Section 3.1, #4
  • Section 3.2, #1,2
• Monday, September 16th
  • Do 2 problems from here
  • Classify all the statements here, with proofs when appropriate
• Friday, September 13th
  • Section 1.2, #12
  • Do this proof practice
  • Read section 3.1 of H+P on propositional logic
  • Truth table practice here and here
• Monday, September 9th
  • Read section 1.2 of H+P on induction
  • Do some practice here and - 1-3 here
• Friday, September 6th
  • Read section 1.1 of H+P.
  • Do some of the problems 5-19 here to get practice calculating linear combinations and gcd’s.
  • Use the gcd duality theorem to prove that gcd (ax, ay) = agcd (x, y).
  • How do we know that Euclid’s algorithm will always terminate in a finite number of steps?
• Friday, August 30th
  • Read section 1.1 of H+P.
  • Do problems 1-4 here
• Wednesday, August 28th
  • Read section 1.3 of Humphreys and Prest. Do problems 2,3,4, and 8.
  • Peruse books 7,8,and 9 of Euclid’s elements in one of the oldest surviving forms.
  • Read the the “Guide” sections for books VII,VIII, and IX of the cleaner online version of Euclid.
  • Prove log₃8 is not a rational number.

Handouts

• Coset examples: Z12,add, (Z21,x) A, (Z21,x) B
• Midterm topics found here
• Online tools to experiment with permutation groups
  • Permutation groups
  • Group explorer
• Theorems on Order and Totient
• Congruence Class Equations Theory
• Cayley table (multiplication table) for ℤ₁₅. Also, ℤ₁₆, ℤ₁₇, ℤ₂₄, ℤ₂₅.
• Midterm 1 topics
• Some solutions for the practice problems on deduction
• Quick reference on sets and logic
• List of logic identies
• Guide to definitions and theorems on GCD’s
• Pretty version of Euclid’s prime number theory

Extra Links

These are math-related links fished from the data-torrents as the semester progresses. Feel free to pass on your own.

• (10-31) Here’s the paper no one read before declaring the demise of modern cryptography - Ars Technica
• (10-10) n-dimensions are bigger than you think - the sphere-packing example (and also see here)
• (10-1) Lectures on the Icosahedron
• (9-25) Collatz Trajectories and busy beavers (Busy beavers are the smallest programs that run for the longest times before stopping in a Turing machine)
• (9-19) Turbulent skies of Vincent Van Gogh’s ‘The Starry Night’ may align with a scientific theory | CNN 2024-09-19
• (9-17) Centrality of stupidity in math and the related The importance of stupidity in science (good essay, title a little off the mark)
• (9-17) Why Gauss Wanted a Heptadecagon on His Tombstone | Scientific American
• (9-4) A translation of Euclid from Arabic to Latin
• (9-3) Fourier principle of uncertainty
• (8-28) Poor foundations of Geometric Algebra
• (8-25) Euclid
• (8-25) Work hard by Terry Tao