Instructor:

Shane Scott

Jack Olinde

 

 

Email:

 

 

Office:

Skiles 252

Clough 280

 

 

Hours:

T,Th 4:30-6

W 12-1 & 5-6

 

Date

Topic

Text

Links

Slides

Thu 26 April 2:50 - 5:40 PM

Final

Tell Yourself

Ask Jeopardy

Sol

12 April

Network Flows

13

Edmund Karp Bipartite Matching

 Day 22

10 April

Network Flows

13

Ford Fulkerson

 Day 21

 

Homework 9: Read 13 and 14. Excercises § 13.7 #9,10, and § 14.4 #1,4,9, Due 19 April.

5 April

Midterm Exam 3

§ 8, 9, 15

Ask Yourself

Sol

3 April

Minimal Weight Subgraphs

12 and Postman Addendum

Kruskal's Dijkstra's Postman Problem

 Day 20

 

Homework 8: Read 12 and Postman Addendum. Excercises § 12.5 #5,7,10,12, and A) Find a minimal weight closed walk which contains every edge of the graph in Figure 12.22. Due 12 April.

29 March

Recurrence

Linear Addendum or 9

Fractals Xaos

 Day 19

27 March

Linear Recurrence

Linear Addendum or 9

Recurrence Iterated Function Systems

 Day 18

 

Homework: Read the Linear Addendum. Ask yourself the Ask Yourself.

 

Spring Break Mathematical Advice on Vacation Toilets (or Dating!)

15 March

Polya Counting

15 or Lynn

Burnside TicTacToe Polya

 Day 17

13 March

Permutation Groups

15 or Sheffer

Perms

 Day 16

 

Homework 7: Read Lynn's very good write up of hexagonal necklace counting. Excercises § 15.6 #4,11 Due 29 March. Did you know Sage can compute Polya indices? The Burnside TicTacToe video is a great hint for 11.

8 March

Generating Functions

8 or Levin 5.1

Generating Funcs Z-Partitions McNugget Problem

 Day 15

 

Homework 6: Read § 8 or Levin 5.1. Excercises § 8.8 #2bkl, 3beh, 6, 10 Due 15 March. This Sage CoCalc sheet might help you with polynomial algebra.

6 March

Midterm Exam 2

§ 4, 5, 6.1-3, 7

Ask Yourself 12fold

Sol

1 March

Generating functions

8

FibGen

 Day 14

27 Feb

Totient

7.5, B.13, Levin 5.2

EquivRels Totient Mod

 Day 13

22 Feb

Inclusion-Exclusion

7.1-4

IE Derangements

 Day 12

20 Feb

Trees vs Posets

6.1-3

Binary Relations

 Day 11

 

Homework 5: Read § 6.1-3 § 7 . Excercises § 5.9 #40 § 6.10 #3, 8 § 7.7 #3,8,14. Due 1 March.

15 Feb

Planarity, Trees

5.5-6

Planarity Game Planarity

Day 10

 

This Sage CoCalc sheet has some examples of Sage computing 3012 problems.

13 Feb

Coloring

5.4-5

ColorBacktracking

Day 9

 

Homework 4: Read § 5.4-8. Excercises § 5.9 #15, 24, 29, 34. Due 22 Feb.

8 Feb

Graphs

5.1-3

EulGame Isomorphic Konigsberg

Day 8

6 Feb

Complexity

4.2-5

P vs NP

Day 7

 

Homework 3: Read § 5. Excercises § 4.6 # 1.a,d,j,m, § 5.9 # 4,7,9
Problem A: The Enigma Machine (watch) was used during WWII to encrypt messages character by character. Decrypting a message requires using the same machine setting as the encryption. Determine the bigO complexity class of decrypting an Enigma encoded message by trying every possible setting in terms of the input alphabet size n=2k. (For English letters n=26, k=13). The setting cosists of 1) a choice of 1st, 2nd, and 3rd rotor from 5 rotors, each of which has n-rotary starting positions corresponding to the letters and 2) a 'plug setting' which swaps 10 pairs of letters with exactly one partner.
Due 15 Feb.

1 Feb

Midterm Exam 1

B,2,3,4.1

Ask Yourself An Old Exam Another Old Exam

Sol

25 Jan

Pigeonhole Principle

4.1

PHP

Day 6

23 Jan

Induction

3

Induction

Day 5

 

Homework 2: Read § 3 & 4. Excercises: § 3.11 #3,4,12.
Problem A: Ten points are chosen inside a square with sidelength 1. Prove that it is always possible to find a pair of points that are at most √2/3 apart. (Hint: Make some square holes for your pigeon-points.)
Due 1 Feb.

18 Jan

Binomial Coefficients

2.5-7

Pascals

Day 4

16 Jan

Perms & Combs

2.1-4

PermsCombs

Day 3

 

Homework 1: Read § 2. Excercises: § 2.9 #3, 8, 18, 20, 30. Due 25 Jan.

11 Jan

Functions

§ B

Functions

Day 2

8 Jan

What is Combinatorics?

1

Stable Marriage

Day 1

 

Homework 0: Introduce yourself by replying to this note on Piazza. Read Backgroupd material sections § B.1-6 of Keller and Trotter. B7+ is optional, but fun. Create a CoCalc Account.