Ma/CS 6a:  Introduction to Discrete Mathematics (Fall 2016-17)

ANNOUNCEMENTS


COURSE DESCRIPTION

CS/Math 6a introduces several basic combinatorial and algorithmic topics.  These include generating functions, graph theory with a focus on graph algorithms, cryptography (including some elementary number theory), and an introduction to algebraic structures.


Extras

Still not convinced that Euler is amazing? Watch the first half of this Youtube video. The second half we will study in more detail later in the course.

Is the NSA reading your RSA-encrypted messages? Possibly.

A youtube video about partitions.


SCHEDULE

MWF, 13:00 - 13:55, 201 E. Bridge.


INSTRUCTORS

Adam Sheffer
HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
276 Sloan
626-395-4347
Office hours: 4pm Mondays at Sloan 276.


TA's

Cosmin Pohoata (head TA), apohoata@caltech.edu, Kellog 307.
Office hours: 4pm and 5pm Mondays at Sloan 153.

Siqi He she@caltech.edu, Sloan 356.

Karlming Chen kchen7@caltech.edu, Sloan 158.
Office hours: 8pm Mondays at Sloan 153.


HOMEWORK POLICIES


TEXTBOOKS

Discrete Mathematics / Norman Biggs, 2nd edition, Oxford.  ISBN:  978-0-19-850717-8

Introduction to Algorithms / Cormen, Leiserson, Rivest, and Stein. Some of the algorithms are not written in detail in Biggs' book, and then more details can be found in this book. On the other hand, this book is too advanced for us since it includes running time analysis for the various algorithms. Feel free to completely ignore these.


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. Books sections starting with an "A" refer to the 2nd edition of the book "introduction to algorithms" (see above).

09/26 Introduction to modern cryptography 8.1, 8.2, 8.4, 8.5, 8.6
09/28 Congruences 8.4, 13.1, 13.2, 13.3
10/30 The RSA algorithm 10.3, 13.3, A31.7
10/03 Primality testing (Class will be given by Cosmin) A31.8
10/05 No class today This
10/10 Basic counting 11.1, 11.2, 11.3
10/12 Introduction to graphs and the BFS algorithm 15.1, 15.3, 15.4, 16.5
10/14 More BFS 16.5, A22.2
10/17 Eulerian cycles 14.5, this webpage
10/19 Coloring 15.6,15.7
10/21 Spanning trees 16.3,A23
10/24 Matchings 17.4
10/26 More matchings 17.5,17.6
10/28 Network flow 18.2,18.3,18.4,A26.1, A26.2
10/31 Flow exercises ???
11/02 Flows and Bipartite graphs A26.3,???
11/04 Permutations 10.6, 12.5
11/07 More permutations 12.6
11/09 Groups 20.1, 20.2, 20.3, 20.4
11/11 Group isomorphisms 20.5, 20.6, 20.7
11/14 Subgroups, orbits, and stabilizers 20.8 (a bit), 21.1, 21.2, 21.3
11/16 Counting with permutations 21.4,21.5
11/18 Power series 22.1,22.4,22.5, 25.1
11/21 Generating functions 25.2,25.3,25.4
11/23 More generating functions 25.5, Sec. 5 of this
11/28 Partitions 26.1,26.2,26.3,26.4
12/30 More partitions 26.4, 26.5
12/02 Shortest paths 16.6, A24.3

HOMEWORK

Unless stated otherwise, the assignments are due by noon on Tuesdays. We prefer that you send emails concerning an assignment to the TA that is in charge of that assignment (for example, when asking for a clarification, asking for a late submission, complaining about the grading, or reporting a mistake) . If you have any special issues, you are always welcome to email Adam. You may also ask any of these questions in any of the office hours (issues with the grading should go to the TA in charge or to Adam).

Due Date Homework Solution TA in charge
--- Example assignment Example solution ---
October 11th Assignment 1 Solution 1 Siqi
October 18th Assignment 2 Solution 2 Cosmin
October 25th Assignment 3 Solution 3
November 8th Assignment 4 Solution 4 Karlming
November 15th Assignment 5 Solution 5 Cosmin
November 29th Assignment 6 Solution 6 Cosmin

EXAMS