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
  Top

Grades will be based on weekly homework assignments. There will be no examinations. The problem sets are due by noon on Thursdays. Homework should be turned in to the Ma6 box outside of 253 Sloan.
 

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

Extra
  Top

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
  Top

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 DescriptionBook 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



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