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.
Final exam, Monday, December 16th, 6:50-8:40 pm, Business Bldg 106
Office hours in 424 McAllister, Friday and Monday 9-5 (except for lunch)
Topics for the final exam
- Groups
- 2-row permutation arithmetic
- permutation representation of symmetries
- definition of a group and applications
- subgroups, Hasse diagrams of subgroups
- solvability of equations
- symmetry groups of geometry objects in flatland and sphereland
- equivalence relations created using group actions
- Lagrange’s theorem
- stars and invariants
- Congruence class arithmetic
- solutions of linear congruence equations
- congruence class arithmetic
- totient
- Euler’s theorem
- zero divisors and invertible congruence classes
- orders of congruence classes
- RSA encryption theory
- Logic
- definitions of basic logical operations
- converse, inverse, and contrapositive
- proofs by truth-table and deduction
- translation between common language and formal logic
- Sets, functions, relations
- Basic set operations (union,intersection,complement)
- Partitions
- Cartesian product
- sizes of sets
- definition of a relation
- common properties of relations
- ordering and equivalence relations
- domain, target, image
- surjective, injective, bijective
- pigeon-hole principle for finite functions
- graph of a function
- Elementary number theory
- Euclidean algorithm
- classic results
- irrationality of square roots and logs
- infinitely many prime numbers
- prime-factorization theorem
- Euclid’s lemma
- Axioms and principles
- organization of math in definitions, axioms, propositions, theorems, proofs, and algorithms
- proof-by-induction
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)
- Quiz 5, Friday, October 18th (solutions)
- Exam 2, Monday, November 4th (solutions)
- Quiz 6, Friday, November 8th (solutions)
- Quiz 7, Wednesday, November 20th (solutions)
- Quiz 8, Monday, December 9th (solutions)
- Final exam, Monday, December 16th, 6:50-8:40 pm, Business Bldg 106
Homework
- Wednesday, December 4
- Practice with cycle-notation for 1-row notation.
- Draw the Hasse diagram for the subgroups of the symmetry transformations of a 15-gon in flatland. (Think about the previous question on star-classification in 15-gons, when doing so)
- complete these problems about isomorphism
- Monday, December 2
- Draw the Hasse diagram for the subgroups of the symmetry transformations of a hexagon in flatland.
- Draw the Hasse diagram for the subgroups of the symmetry transformations of a hexagon in sphereworld.
- Friday, November 22
- Determine all the values of n for which regular n-gons there is exactly one single-orbit n-pointed star.
- Classify all the stars that can be drawn inside a regular 15-gon. picture and 12-gon picture
- What is the relationship between Euler’s totient function, and the number of single-orbit stars in a regular n-gon?
- Monday, November 11
- Friday, November 8
- Friday, November 1
- 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
- Monday, September 23th
- 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
Handouts
These are math-related links fished from the data-torrents as the semester progresses. Feel free to pass on your own.
