MATH 181: A Mathematical World




A Caesar cipher decoder ring

Course info

Time: MWF 2:00 - 2:50 pm
Place: 141 Altgeld Hall *new*
Syllabus: link
Instructor: Ruth Luo
Office: Coble Hall B2
Office hours: Thursdays 2:00 - 4:00 pm or by appointment
Email: ruthluo2(at)illinois.edu

Login to check your grades
Emergency info

Important Dates

9/28 - Midterm 1
Topics include:
Eulerian walks and circuits
Hamiltonian cycles
Traveling Salesman Problem
Graph coloring
Isomorphisms
Planar graphs
Stable Marriage Problem
Matchings
Practice exam
Midterm 1 [Solutions]

10/26 - Midterm 2
Topics include:
Voting systems for 2 candidates
May's Theorem (no proof)
Voting systems for 3 candidates
Arrow's Impossibility Theorem
Examples of how to manipulate elections
Fair Division (cake cutting procedures)
Proportional vs. envy-free procedures
Gerrymandering
Probability (introduction)
Practice exam
Midterm 2 [Solutions]

11/30 - Midterm 3
Topics include:
Conditional probability
Expected value
Game Theory
Prisoner's Dilemma
Stag Hunt
Nash equilibria
Modular arithmetic
Practice exam
Midterm 3 [Solutions]

12/14 - Final Exam
Topics include:
All previous topics
Caesar cipher
Decimation cipher
Basic idea of RSA
Additional questions [Solutions]

Group Project

Guidelines
10/29 - Group proposals due
12/7 - Group projects due (if presenting, have presentations ready)

Homework

Homework 1 - Now complete! - Due 9/24
Homework 2 - Now complete! - Due 10/29
Homework 3 - Now complete! - Due 12/03
Homework 4

Quizzes

Quiz 1 [Solutions]
Quiz 2 [Solutions]
Quiz 3 [Solutions]
Quiz 4 [Solutions]
Quiz 5 [Solutions]
Quiz 6 [Solutions]
Quiz 7 [Solutions]
Quiz 8 [Solutions]
Quiz 9 [Solutions]

Class Log

8/27 - Seven Bridges of Konigsberg, into to Graph Theory, Eulerian walks and circuits; Introduction slides
8/29 - Eulerian walks and circuits (cont.), complete graphs, cycles, paths, connected graphs, Euler's Theorem; WS 1 Solutions
8/31 - Finding Eulerian walks and circuits, Hamiltonian cycles, TSP
9/5 - Hamiltonian cycles, TSP (cont.); WS 2 Solutions
9/7 - P vs. NP, graph coloring, chromatic number; Slides
9/10 - Graph coloring (cont.), isomorphisms, planar graphs
9/12 - Planar graphs (cont.), Euler's formula; WS 3 solutions
9/14 - Planar graphs (cont.)
9/17 - Kuratowski's Theorem, Four Color Theorem, stable marriage problem; WS 4 solutions
9/19 - Stable matchings, Gale-Shapley algorithm; WS 5 solutions
9/21 - Matchings (maximal, maximum, perfect matchings, augmenting paths, Berge's Theorem)
9/24 - Practice exam 1
9/26 - Exam 1 review
9/28 - Exam 1
10/1 - Voting systems
10/3 - Voting systems (cont.)
10/5 - Voting systems (cont.), proof of May's Theorem; Proof writeup, WS 6 solutions
10/8 - Cake-division, divide-and-choose
10/10 - Cake-division (cont.), lone-divider
10/12 - Cake-division (cont.); WS 7 solutions
10/15 - Last-Diminisher method, Selfridge-Conway method
10/17 - Gerrymandering, Last-Diminisher WS; WS 8 solutions; WS 9 solutions
10/19 - Introduction to probability
10/22 - Introduction to probability (cont.), conditional probability
10/24 - Exam 2 review
10/26 - Exam 2
10/29 - Conditional probability, expected value
10/31 - Expected value (cont.); WS 10 solutions
11/2 - WS 10 cont., Introduction to Game Theory
11/5 - Prisoner's Dilemma, Stag Hunt, Nash Equilibria (pure vs. mixed)
11/7 - Calculating mixed Nash equilibria; WS 11 solutions
11/9 - Hawk/Dove game; WS 12 solutions
11/12 - Introduction to Number Theory
11/14 - Modular arithmetic WS 13 solutions
11/26 - Modular arithmetic (cont.)
11/28 - Exam 3 review
11/30 - Exam 3
12/3 - Cryptology, Prime number contest (details to be sent)
12/5 - Cryptology (cont.); WS 14 solutions
12/7 - Group project presentations
12/10 - RSA

Helpful Resources

Glossary of graph theory terms
Graph Creator - draw graphs, drag around vertices (useful for showing two graphs are isomorphic)
Random map generator/coloring demo

Department of Mathematics     University of Illinois at Urbana-Champaign     College of Liberal Arts & Sciences