Math 6a Introduction to Discrete Mathematics Fall 2014-15
 MWF 1:00 PM, 151 Sloan
 Course Description | Policies | Extra | Lecture Notes | Homework

 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.
 Announcements

 The grades were submitted. To compute them, we calculated your average question grade in the HW and normalized it to be out of a 100 (e.g., sum up all of your grades, divide by the number of questions, and multiply by 100). A grade of at least 96.5 got A+. At least 93.2 got A. At least 88.5 got A-. At least 83 got B+. At least 79 got B. There were various special circumstances that caused us to round some grades up.

 Course Description
 CS/Math 6a and 6b cover topics from elementary number thoery, an introduction to algebraic structures, enumeration theory and elementary combinatorics, and graph theory, all from an algorithmic/constructive point of view. Most of the graph theory will be in the second term.

 Policies

 Extra

 Still not convinced that Euler is awesome? Watch the first half of this Youtube video. The second half we will study in more detail later in the course. A world-famous combinatorist just placed this riddle in his blog. You're welcome to take a look and vote (the only thing that we did not define was "two generators" but this should not be too hard to understand).

 Lecture Notes

 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

 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

 | © California Institute of Technology | Questions?  kaubry @ caltech.edu