Instructor:
Shane Scott
Jack Olinde

Email:

Office:
Clough 280

Hours:
T,Th 4:30-6
W 12-1 & 5-6

### The Course

#### Slides

Thu 26 April 2:50 - 5:40 PM
Final

12 April
Network Flows

10 April
Network Flows

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

3 April
Minimal Weight Subgraphs

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

27 March
Linear Recurrence

15 March
Polya Counting
15 or Lynn

13 March
Permutation Groups
Perms

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

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

1 March
Generating functions
8

27 Feb
Totient
7.5, B.13, Levin 5.2

22 Feb
Inclusion-Exclusion
7.1-4

20 Feb
Trees vs Posets
6.1-3

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

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

13 Feb
Coloring
5.4-5

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

8 Feb
Graphs
5.1-3

6 Feb
Complexity
4.2-5

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

25 Jan
Pigeonhole Principle
4.1

23 Jan
Induction
3

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

16 Jan
Perms & Combs
2.1-4

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

11 Jan
Functions
§ B

8 Jan
What is Combinatorics?
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.