Introduction to Discrete Mathematics

Course Description and Grading Breakdown
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.

The final grade will be determined based upon 6 written assignments, each worth 1/6 of the total grade. There will be no midterm or final exam. The conversion scheme from the homework average to the letter grade will not be determined in advance.

Course Meeting Time and Location
Lectures 
Monday, Wednesday and Friday
1:00 - 1:55 pm
B122 Gates Chemical Laboratory (GCL)


Course Instructor Contact Information and Office Hours
Martino Lupini
lupini@caltech.edu
210-1 Math Building (Building 15)


TA Contact Information and Office Hours

Andrei Frimu (head TA)
afrimu@caltech.edu
8-10pm Sunday - 107 Downs

Aaron Anderson
awanders@caltech.edu
4-5pm Saturday - 103 Downs

Luke Juusola    
ljuusola@caltech.edu
5-6pm Friday - 103 Downs

Surya Mathialagan
surya.math@caltech.edu
3-4pm Saturday - 103 Downs

Course Schedule
 DateTopic 
 09/25/2017        Lecture 1: Introduction to graphs and the BFS algorithm. See 15.1, 15.3, 15.4, 16.5.
 09/27/2017         Lecture 2: More BFS. See 16.5, A22.2                                                      
 09/29/2017      Lecture 3: Shortest path graphs and Eulerian Cycles. See 14.5 and also this chapter.        
 10/02/2017    Lecture 4: Coloring. See 15.6,15.7.
 10/04/2017    10/06/2017Lecture 5 and Lecture 6: Spanning Trees. See 16.3, and this problem. More information can be found in Chapter 23 of Introduction to Algorithms of Cormen, Leiserson, Rivest, and Stein.
 10/09/2017 Lecture 7: Matchings. See 17.4.        
 10/11/2017        Lecture 8: More matchings. See 17.5,17.6.    
 10/13/2017    Lecture 9: Network flow. See 18.2,18.3,18.4. More information can be found in Chapter 26 of  Introduction to Algorithms of Cormen, Leiserson, Rivest, and Stein.
 10/16/2017     Lecture 10: Euclidean division. See 8.1, 8.2, 8.4, 8.5, 8.6
 10/18/2017     Lecture 11: Congruences. See 8.4, 13.1, 13.2, 13.3
 10/20/2017     Lecture 12: The RSA Algorithm. See 10.3, 13.3. More information can be found in Chapter 31 of Introduction to Algorithms of Cormen, Leiserson, Rivest, and Stein.
 10/23/2017     Lecture 13: Primality testing. See Chapter 31 of  Introduction to Algorithms of Cormen, Leiserson, Rivest, and Stein.
 10/25/2017     Lecture 14: Basic counting. See 11.1, 11.2, 11.3.
 10/27/2017     Lecture 15: Permutations. See 10.6, 12.5.
 10/30/2017    Lecture 16: More permutations. See 12.6.        
 11/01/2017     Lecture 17: Combinatorial designs. See 11.6, 11.7, and these lecture notes.    
 11/03/2017     No lecture today    
 11/06/2017     Lecture 18: Groups. See 20.1, 20.2, 20.3, 20.4.
 11/08/2017     Lecture 19: Isomorphisms. See 20.5, 20.6, 20.7.
 11/10/2017     Lecture 20: Orbits and stabilizers. See 20.8, 21.1, 21.2, 21.3.
 11/13/2017   11/15/2017    Lecture 21 and Lecture 22: Counting with permutations. See 21.4,21.5.
  11/17/2017     Lecture 23: Power Series. See 22.1,22.4,22.5, 25.1.
 11/20/2017     Lecture 24: Generating functions. See 25.2,25.3,25.4.    
 11/22/2017     Lecture 25: More generating functions. See 25.5.    
 11/27/2017     Lecture 26: Partitions. See 26.1,26.2,26.3,26.4.
 11/29/2017     Lecture 27: More partitions. See 26.4, 26.5.

Textbook
Discrete Mathematics / Norman Biggs, 2nd edition, Oxford

Course 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 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. 
  • Unless stated otherwise, every given graph is simple.
  • There is no need to write pseudocodes for algorithms - we even prefer a description in words.
  • 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 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).

Assignments

Assignments are due on Monday at 4pm, to be submitted in the corresponding drop box, which is located in Downs, near classroom 113, directly across from the elevator.

 Date PostedAssignment Due Date  Solutions Class average
 October 1 Assignment 1         October 16 Solutions 1 22.5 out of 30
 October 10     Assignment 2 (hints) October 23 Solutions 2 24.8 out of 30
 October 23 Assignment 3 (hints) November 6 Solutions 3 27.1 out of 30
 October 27     Assignment 4 (hints) November 13 Solutions 4 
 November 12 Assignment 5 (hints) November 27     
 November 22 Assignment 6 (hints) December 4  

Practice sets
 Date posted     Practice set
 October 16 Practice set 1
 October 23 Practice set 2 (solutions)
 October 28         Practice set 3 (solutions)
November 12    Practice set 4 (solutions)
November 27     Practice set 5 (solutions)




Midterm and Final Exam
There will be no midterm nor final exam

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.