Math 6a
 
Introduction to Discrete Mathematics
Fall 2010-11
 
MWF 1:00 PM, 151 Sloan
Course Description | Policies | Textbooks | Lecture Notes | Handouts | Homework | Sections

Instructor:  Richard Wilson,  364 Sloan, 626-395-4362, rmw@its.caltech.edu
Office Hours:  TBA


Lead TA: Yitao Wu, 385 Sloan, 626-395-1732, yitaowu@caltech.edu
Office Hours: Saturday 2 -3pm

Grader: Jin Du, 356 Sloan, 626-395-4353 du@caltech.edu
Office Hours: Sunday 5 - 6pm
Feedback Form
Announcements

 


 
 



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 midnight on Mondays.
 
You may discuss homework problems with other students (unless marked otherwise). Solutions must be written up individually, in your own words. Some problems on each assignment may be marked "NO COLLABORATION".

Some use of Mathematica (or Maple, Matlab, etc.) will be encouraged or required. Help will be given for Mathematica.

Homework should be turned in to the Ma 6 box outside of 253 Sloan.
 

Textbooks
  Top

Discrete Mathematics, 2nd edition, Norman Biggs, Oxford. 0198507178

Lecture Notes
  Top

Date Description
11/11/10 "The 15-Puzzle"
   
   

Handouts
  Top

Date Description
9/27/10 "The Euclidean algorithm"
9/27/10 "The RSA public key crytosystem"
9/27/10 "Chapter 1 of The Theory of Numbers by G. B. Mathews(1892)"
10/04/10 "Primality testing"
10/11/10 Counting and Binomial Numbers revised 10/11
10/15/10
 Notes on Inclusion
10/18/10 Generating functions
10/18/10 Linear recurrences
10/18/10 Binary strings
10/20/10 Random partitions
11/08/10 revised Permutation groups revised 11/15/10
11/09/10 Action & rotation
11/11/10 "Alternating Paths"
11/29/10 Flows in networks
12/02/10 Ternary Codes
12/03/10 "One-error-correcting codes; the counterfeit coin problem"



Homework
  Top

Due Date Homework  Solutions
October 5 @ 8am
Homework 1 updated 9/30/10
  
October 12 @ 8am
 Homework set 2 revised 10/11/10
  
October 19 @ 8am
 Homework set 3 revised 10/14/10
  
October 26 @ 8am
 Homework set 4 revised 10/21/10
  
November 2 @ 8am
 Homework set 5
  
Wed. November 10 @ 8am
 Homework set 6 revised 11/04/10
  
Wed. November 17 @ Noon Homework 7  
Wed. Nov. 24 @ noon Homework 8  
Wed. Dec 1 @ noon
 Homework 9
  
Wed. Dec 8 @ noon
 Homework 10




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