Math 6b
 
Introduction to Discrete Mathematics
Winter 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: 
Tuesdays 4:00pm
TA: Nakul Dawra, 379 Sloan, ndawra@caltech.edu
Office Hours: Wednsedays 7:00 pm
TA:Alex Mun, 153 Sloan, dei@caltech.edu
Office Hours: Tuesdays 8:00pm

Announcements

 


We submitted the final grades. Thanks for taking this class with us! We hope that you liked it. To compute your grade, sum up all of your assignment grades and divide by 4.2 (this will normalize the grade to be out of 100). To get an A+ you need an average of at least 96. For an A, an average of at least 92. For an A-, at least 84.2. For a B+, at least 80. Feel free to contact us for any issues.

We cannot place solutions to the last assignments due to some issue. If you would like to know the solution to a question, feel free to ask any of the staff members.

 



Course Description


The course is a continuation of Ma/CS 6a, and explores various topics of discrete mathematics. A large part of the course is dedicated to graph theory, and especially to combinatorial aspects of graph theory (unlike 6a, which focuses more on graph algorithms). The course also includes error correcting codes, uses of algebra in combinatorics, and other related topics.


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 and undirected.
  • 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.

No book covers all of the material, and we rely on several sources. One main textbook is Introduction to Graph Theory, 2nd edition, Douglas West. Another is Graph Theory, 4nd edition, Reinhard Diestel. A free online version of the book can be found here.

Extra
  Top


Lecture Notes
  Top

Book sections starting with D refer to the book by Diestel. Sections starting with W refer to the book by West. Some of the relevant sections contain various topics that are not part of the course, or do not contain part of the material. 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
01/05
Graph recap
D1.1, D1.2, D1.3, D1.5
01/07
Matchings 1
D2.1 (also W3.1)
01/09
Matchings 2
D2.1 (also W3.1, W3.2)
01/12
Matchings 3
D2.1 and H3.3 (also D2.2)
01/14
Connectivity 1
D1.4 (also W4.1)
01/16
Connectivity 2
W4.2 (also D3.1 and D3.3)
01/21
Graph minors
D1.7
01/23
Plane and Planar graphs
W6.1
01/26
Euler's formula
W6.1
01/28
Kuratowski's Theorem
W6.2 (also D4.4)
01/30
More Kuratowski and coloring
W6.2, W6.3 (also D4.4, D5.1)
02/02
Adjacency matrices
W1.1 (also D1.9) but only partially :(
02/04
Counting spanning trees
W2.2
02/06
Ramsey theory
W8.3 (also D9.1)
02/09
Ramsey theory 2
W8.3 (also D9.2)
02/11
The probabilistic method
Chapter 1 of this book (also W8.5)
02/13
The probabilistic method 2
Excerpts from chapters 1-3 of this book (also W8.5)
02/18
Crossing numbers
W6.3
02/20
Extremal graph theory
Chapters 18 and 36 of this book (also D7.1)
02/23
Extremal graph theory 2
Parts of Lectures 2 and 3 here
02/25
Spectral graph theory
W8.6
02/27
Spectral graph theory 2
W8.6
03/02
Eigenvalues of regular graphs
W8.6 and this
03/04
Expanders
this (and W8.6)
03/06
Error correcting codes
Biggs (the 6a book) 24.1,24.2,24.3,24.4
03/09
Error correcting codes 2
Biggs 24.4 and this
03/11
Art galleries and politicians
Chapters 35 and 39 of this book


Homework
  Top

Due Date Homework  Average and standard dev. TA in charge Solutions
Jan 15th
Assignment #1
45.3/50, 4.9
Alex
 
Jan 22nd
Assignment #2
38.6/50, 8
Nakul
 
Jan 29th
Assignment #3
33/40, 5.9
Alex
 
Feb 5th
Assignment #4
45/50, 6
Nakul
 
Feb 12th
Assignment #5
43.7/50, 4.8
Alex
 
Feb 19th
Assignment #6
42.4/50, 5.8
Nakul
 
Feb 26th
Assignment #7
26.9/30, 2.2
Alex
 
March 5th
Assignment #8
35.64/40, 4.2
Nakul

March 12th
Assignment #9
25.25/30, 2.7
Alex

March 19th
Assignment #10
26.5/30, 3.6
Nakul



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