[Ma6a - Fall 14 - 15] - Introduction to Discrete Mathematics

MWF 1:00 PM, 151 Sloan

Instructor: Adam Sheffer, 276 Sloan, 626-395-4347, adamsh@caltech.edu
Office Hours: Wednesdays 4:00pm
TA: Victor Kasatkin, Sloan 385, vkasatki@caltech.edu
Office Hours: Tuesdays 7:00pm
TA: Henry Macdonald, Sloan 158, hmacdona@caltech.edu
Office Hours: Wednesdays 7:00pm
Grader: Alex Mun.

Homework policies:

Please staple a blank page containing only your name at the front of the assignment.
You are encouraged to work in groups on the assignments. However, you must do on your own problems that are marked "NO COLLABORATION". Moreover, do not ask about these questions in office hours. You are of course allowed to ask for a clarification if the question is not clear, or if you think that it contains a mistake. It is also fine to ask about the material from class that is related to the problem.
There is no need to formally prove anything, unless the question specifically asks for a proof. However, you do need to explain what you did. The grader needs to see that you did not just write an algorithm/answer without understanding how to get to it or why it works.
Unless stated otherwise, every given graph is simple.
There is no need to find the running time of the algorithms that you create in your homework. However, the running times must be polynomial in the size of the input.
There is no need to write pseudocodes for algorithms - we even prefer a description in words.
There is no need to reprove anything that was proven in class. On the other hand, you are not allowed to refer to any other sources, including the course's text book (answers of the form "The proof can be found in page X of the book" will receive no points).
Make sure that you submit your assignments in the LOCKED 6a mailbox, and not in the open box for graded assignments.

The textbook of the course is Discrete Mathematics, 2nd edition, Norman Biggs, Oxford. 0198507178

The book covers most of the material but not all of it. Also, some of the relevant sections contain various topics that are not part of the course. Thus, please do not rely only on the book sections stated below. To see what is missing/redundant, compare with the lecture notes.

Date	Description	Book Sections
09/29	Introduction to number theory	8.1, 8.2, 8.4, 8.5, 8.6
10/01	Congruences	8.4, 13.1, 13.2, 13.3
10/03	The RSA algorithm	10.3, 13.3
10/06	Primality testing	None :(
10/08	Basic counting	11.1, 11.2, 11.3
10/10	Introduction to graphs and the BFS algorithm	15.1, 15.3, 15.4, 16.5
10/13	More BFS	16.5
10/15	Eulerian cycles	14.5, but only for the end of the class :(
10/17	Coloring	15.6,15.7
10/20	Spanning trees	16.3
10/22	Matchings	17.4
10/27	More matchings	17.5,17.6
10/29	Network flow	18.2,18.3,18.4
10/31	Flow exercises	None :(
11/03	Flows and Bipartite graphs	None :(
11/05	Permutations	10.6, 12.5
11/07	More permutations	12.6
11/10	Groups	20.1, 20.2, 20.3, 20.4
11/12	Isomorphisms and subgroups	20.5, 20.6, 20.7
11/14	Subgroups, orbits, and stabilizers	20.8 (a bit), 21.1, 21.2, 21.3
11/17	Counting with permutations	21.4,21.5
11/19	Power series	22.1,22.4,22.5, 25.1
11/21	Generating functions	25.2,25.3,25.4
11/24	More generating functions	25.5, Sec. 5 of this
11/26	Partitions	26.1,26.2,26.3,26.4
12/01	More partitions	26.4, 26.5
12/03	Shortest Paths	16.6 or 24.3 of this
12/05	Latin Squares	Chapter 32 of this

Homework

Top

Some solutions can be found here.

Due Date	Homework	Average and standard dev.
10/09	Assignment #1	42.5/50, 5.6
10/16	Assignment #2	45.5/50, 6
10/23	Assignment #3	43.4/50, 6.2
10/30	Assignment #4	45.9/50, 3
11/06	Assignment #5	46.7/50, 5.4
11/13	Assignment #6	31.9/50, 8.6
11/20	Assignment #7	47/50, 3.4
12/1	Assignment #8	32.3/40, 6.3
12/4	Assignment #9
12/11	Assignment #10

Math 6a
Introduction to Discrete Mathematics
Fall 2014-15