Introduction to Discrete Mathematics

Course Description and Grading Breakdown
6 Problem Sets         10% each
Final exam               40%


Course Meeting Time and Location
Lecture
Monday, Wednesday and Friday
1:00 - 1:55 pm
119 Kerckhoff


Course Instructor Contact Information and Office Hours
366 Linde Hall
Office Hours: Monday 3-4

TA Contact Information and Office Hours

 TA E-mail Office Hours
 Will Overman woverman@caltech.edu Sunday, 1-2pm, Linde 187
 Jack Tao    ztao@caltech.edu Sunday, 4-5pm, Linde 187
 Daniel Zhou dczhou@caltech.edu Sunday, 7-8pm, Linde 187
 Liyang Yang lyyang@caltech.edu    Sunday, 8-9pm, Linde 187
 Sara Fish sfish@caltech.edu    Monday, 8-9pm, Linde 187
 Yuhui Jin yjjin@caltech.edu Monday, 10-11pm, Linde 187


Course Schedule and Textbook

Discrete Mathematics, by Norman Biggs

 DatePowerpoint 2016 notes in pdf Main Topic
 10/2/19 Lecture 1 Lecture 1Euclidean Algorithm 
 10/4/19Lecture 2 Lecture 2 Congruences 
 10/7/19 Lecture 3Lecture 3 RSA Algorithm 
 10/9/19Lecture 4 Lecture 4 Primality Testing 
 10/11/19Lecture 5 Lecture 5 Basic Counting 
10/14/19  Lecture 6Lecture 6 Introduction to Graphs 
10/16/19 Lecture 7 Lecture 7 More BFS 
10/18/19 Lecture 8 Lecture 8  Eulerian Graphs
10/21/19 Lecture 9
 Lecture 9Colourings 
10/23/19 Lecture 10  Lecture 10Spanning Trees 
10/25/19 Lecture 11  Lecture 11Matchings 
 10/28/19Lecture 12 Lecture 12 More Matchings 
 10/30/19Lecture 13 Lecture 13  Network Flow
 11/1/19Lecture 14 Lecture 14 Flow Exercises 
11/4/19 Lecture 15  Lecture 15Flows and Bipartite Graphs 
11/6/19 Lecture 16  Lecture 16Permutations 
11/8/19 Lecture 17  Lecture 17More Permutations 
11/11/19 Lecture 18  Lecture 18Groups 
 11/13/19Lecture 19  Lecture 19 Isomorphisms
11/15/19 Lecture 20  Lecture 20 Orbits and Stabilizers
 11/18/19  Lecture 21 Lecture 21 Counting and Permutations 
 11/20/19  Power Series 
11/22/19   Generating Functions 
    
    
    


Course Policies
  • All homework should be handed in by noon on the appointed date, which will always be a Tuesday. At most one exception to this is allowed per student.
  • 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 are required to write your solution on your own and not to look at written solutions of other students.
  • You may not rely on any related tools that we did not study in class (such as the DFS algorithm). Using such tools to solve a problem may result in zero points. If you are not sure whether you are allowed to use something, please ask someone from the staff of the course.
  • 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.


Assignments
All assignments are due by noon on Tuesdays. At most one exception to this is allowed per student. 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, requesting a late submission, complaining about the grading, or reporting a mistake) . If you have any special issues, you are always welcome to email the instructor. 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 the instructor).

 Date PostedAssignment Due Date  TA in charge
 10/4/19Problem Set 1  10/15/19Sara Fish 
 10/11/19 Problem Set 2 10/22/19 Daniel Zhou
 10/18/19Problem Set 3
10/29/19  Will Overman
 11/1/19Problem Set 411/12/19  Yuhui Jin
 11/8/19Problem Set 5 11/19/19  Jack Tao
 11/15/19Problem Set 6 11/26/19  Liyang Yang


Midterm and Final Exam

There will be no midterm. Details of the final exam will be posted in due course.



Collaboration Table
 HomeworkExams
You may consult:  
Course textbook (including answers in the back)YESYES
Other booksYESNO
Solution manualsNONO
InternetYESNO
Your notes (taken in class)YESYES
Class notes of othersYESNO
Your hand copies of class notes of othersYESYES
Photocopies of class notes of othersYESNO
Electronic copies of class notes of othersYESNO
Course handoutsYESYES
Your returned homework / examsYESYES
Solutions to homework / exams (posted on webpage)YESYES
Homework / exams of previous yearsNONO
Solutions to homework / exams of previous yearsNONO
Emails from TAsYESNO
You may:

Discuss problems with othersYESNO
Look at communal materials while writing up solutionsYESNO
Look at individual written work of othersNONO
Post about problems onlineNONO
For computational aids, you may use:

CalculatorsYES*NO
ComputersYES*NO

* You may use a computer or calculator while doing the homework, but may not refer to this as justification for your work.  For example, "by Mathematica" is not an acceptable justification for deriving one equation from another.  Also, since computers and calculators will not be allowed on the exams, it's best not to get too dependent on them.