AMS301.01 Finite Mathematical Structures, Spring 2011

Ning SUN   nsun@ams.sunysb.edu

Syllabus                  Schedule                Lecture Notes with Animations              Homework                  Exam

 Syllabus

Course website: http://www.ams.sunysb.edu/~nsun/Teaching/ams301_spring2011.html

Class Time & Location: MoWeFr 9:35-10:30AM @SB Union 123

Office Hour: Mo 2:30-4:30 PM@ Math Tower B-148 (7)

Direction to my office (My room is difficult to find...): Enter the math tower, take the elevator to Floor 2, make a right, you will see red stairs. Go upstairs, make a left, you will see Room B-148. Enter the door and take a right. I'm in room #7 of B-148. 

Graders

     Joeun Joo  joeun0210@gmail.com      Office Hour: Wednesday 10:40am -12:10pm@ Harriman Help Room 010

     Kevin Lin  kevinlin505@hotmail.com   Office Hour: Tuesday 2:30-4:00pm@ Harriman Help Room 010

     Crage  Lu Crage.Lu@stonybrook.edu    Office Hour: Thursday 4:00 -5:30pm@ Harriman Help Room 010

    

Textbook: Applied Combinatorics, 5th Ed., by Alan Tucker.

                   (The text part of the this version is similar with the older one, but the problem sets might be different)

Prerequisites: AMS 210 or MAT 211 or MAT 303 or AMS 361.

 

Course outline:

Part I: Graph Theory

            Basic definitions,  Isomorphism

Edge Counting, Planar graphs

Euler Cycles, Hamilton Circuits, Graph Coloring

Trees,  Traversal

Shortest Paths, Minimum Spanning Trees, Traveling Salesperson Problem

Part II: Enumeration and Counting

Basic Counting Principles, Arrangements and Selections

Binomial Coefficients, Permutations and Combinations

Generating functions

Part III: Enumeration and Counting (cont'd)

                  Recurrence Relations, Divide and Conquer

Inclusion-Exclusion formulas

 

Policies: 

  1. Homework will be due at the beginning of class (before 10:00am). No late homework will be accepted. Please staple!
  2. The two lowest homework scores will be dropped.
  3. All grades will be posted on Blackboard. Make sure you can be reached via the email address on Blackboard.
  4. Exams will be given in the regular classroom.  Don't be late.
  5. Exams are closed notes and book. A cheat sheet is allowed (4 by 6 index card, written by hand, 2-sided).


Grading: 

Homework (9 or 10 homeworks, 20%)
Midterm I (25%) -- Mar 7, in class
Midterm II (25%) -- Apr 11, in class
Final (30%) -- May 23, 11:15-1:45 PM
  

Disability Policy: If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Disability Support Services, ECC (Educational Communications Center) Building, room 128, (631) 632-6748. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information, go to the following web site: http://www.sunysb.edu/ehs/fire/disabilities.shtml

Lecture Notes with Animations (pps format)

I made a lot of animations in my PowerPoint slides. Here you can access to and play with the pps files for a better understanding of the definitions and problem solving procedures. Also in case you cannot come to the class, you won't miss the fun. 

I used PowerPoint 2007 to create all the files. However, I can open them with PowerPoint 2002. If you cannot see them, email me, or skip this part and go straight to "Schedule" part for the pdf files. 

When you use IE to access to this page and try to open or save the following files, IE might recognize them as "zip" files. So in case you are using IE, please change the extension name to ".ppsx" files and then you can use PowerPoint to open them. You can avoid those troubles by using FireFox.

Lecture 00
Lecture 01
Lecture 02
Lecture 03
Lecture 04
Lecture 05
Lecture 06
Lecture 07
Lecture 08
Lecture 09


Schedule

1st week (Jan 31 – Feb 4) 1.1  1.2  1.3

Lecture 00 (Jan 31) -- Introduction
Lecture 01 (Jan 31) -- 1.1  1.2  1.3

2nd week (Feb 7 - 11)  1.4  2.1

Lecture 02 (updated on Feb 10) -- 1.4 2.1

3rd week (Feb 14 - 18)  2.2 2.3

Lecture 03 (Feb 13) -- 2.2  2.3  2.4

4th week (Feb 21 – 28)  2.4 Chapter 3

Lecture 04 (Feb 20) -- Chapter 3

5th week (Feb 28 – Mar 4) Chapter 3 + review

6th week (Mar 7 - 11) exam 1 +  5.1

Lecture 05 (updated on Mar 13, typo fixed) -- 5.1 5.2

7th week (Mar 14 - 18) 5.2 5.3

Lecture 06 (Mar 14) -- 5.3 5.4

8th week (Mar 21 - 25)  5.3 5.4

9th week (Mar 28 – Apr 1) 6.1 6.2

Lecture 07 (Mar 27) -- 6.1 6.2

10th week (Apr 4 - 8) Chapter 6 + review

Letter questions  in class (Apr 8)

11th week (Apr 11 - 15) 

Lecture 08 (Apr 12) -- 7.1 7.2

12th week (Apr 18 - 22)  Spring break - no class   

13th week (Apr 25 - 29)  7.1 7.2

14th week (May 2 - 6)  -- 8.1 8.2 8.3

Lecture 09 (Apr 29) -- 8.1 8.2 8.3

15th week (May 9 - 13)  -- review 





Homework

Solutions:
 
Solution to hw1
Solution to hw2
Solution to hw3
Solution to hw4
Solution to hw5
Solution to hw6
Solution to hw7
Solution to hw8
Solution to hw9



Assignments:

HW9 (due on Wednesday, May 11 )  covering 8.1, 8.2
          8.1: 10, 12, 20, 24, 26, 29, 36; 8.2: 2, 6, 8

HW8 (due on Monday, May 2)  covering 7.1, 7.2
          7.1: 2, 4, 6 (a,b), 10, 18, 28; 7.2: 8 (a,b)
Note:
7.1#4: Only think about the case in which the n miles will be finished at the end of the last hour's walking/jogging/running. The total # of hours should be an integer.


HW7 (due on Wednesday, Apr 6)  covering 6.1, 6.2
          6.1: 2 (b,e), 4 (b,c,d), 8, 10, 16; 6.2: 2, 8, 18, 20


HW6 (due on Wednesday, Mar 30 )  covering 5.2, 5.3, 5.4
          5.2: 22, 34, 42 (a);  5.3: 22, 23, 26 (a) ; 5.4: 2, 7, 12, 20, 34, 48
Note:
5.4#48: The three conditions should be satisfied simultaneously


HW5 (due on Monday, Mar 20)  covering 5.1, 5.2
          5.1: 6, 18(a), 22, 32; 5.2: 4, 10, 14, 16 (b, c, d) , 25, 32, 38


HW4 (due on Friday, Mar 4)  covering 3.1, 3.2, the approximate traveling salesperson tour construction in 3.3
          hw4

Note:  In question 7: Each main diagonal entry should be infinity instead of zero.  Just use the matrix in the hw problem set.      


HW3 (due on Friday, Feb 25 )  covering 2.2, 2.3 2.4
          2.2: 4 (f, h,  l); 2.3: 1(l,n), 2(b,e), 12; 2.4: 4, 5
Hints:
          In 2.2: 12, when you are asked to model the problem as a graph-coloring problem, you need to state what the vertices and edges correspond to, and what the goal of the problem (for example, you want to find the chromatic number or edge chromatic number).


HW2 (due on Wednesday, Feb 16 )  covering 1.4, 2.1
          1.4: 3 (f, j), 4, 7 (f,  i), 16; 2.1: 2, 4(Figure 1.4 in on page 6 or page 8. In the question,  no edge can be drawn more than once)
Hints:
          In 1.4: 4, the "infinite region" refers to the region outside the graph. So try to make the circuit bounds your whole graph, then the outside region is bounded by this circuit. 
          In 2.1: 2: Kr,s is a bipartite graph in which there are two groups of vertices. Group1 has r vertices, each of which is adjacent to all the vertices in Group 2. Group 2 has s  vertices, each of which is adjacent all the vertices in Group 1. K3,3 is the special case of Kr,s.


HW1 (due on Friday, Feb 11)  covering 1.1, 1.2, 1.3
          1.1: 2, 4, 16; 1.2: 4, 5 (b c k ), 6 (a, e, f); 1.3: 4,8         
Hints:  
        In 1.1: 2 and 4, when you represent the relationship with a graph, make sure to state what the vertices correspond to and what the edges correspond to.
        In 1.2: 5 and 6, you need to explain before giving a conclusion: if two graphs are isomorphic, show the 1-to-1 correspondence (isomorphism); if they are not, show the difference between two graphs.
        In 1.3: 4, notice that in a complete graph Kn, all the vertices have degree (n-1). Think about the definition and relationship of Kn, G, and the complement of G. 

 




Exam

Final     (Monday, May 23) covering Chapter 7 (7.1  7.2), 8 (8.1 - 8.3)
             in the regular classroom, 11:15am -1:15pm
             closed notes and book, no calculators
             a cheat sheet allowed (4 by 6 index card, written by hand, 2-sided)
Practice Final
Solution to Practice Final      

Final
Solution to Final     



Exam 2 (Monday, Apr 11) covering Chapter 5 (5.1 - 5.4), 6 (6.1 6.2)
             in class, closed notes and book, no calculators
             a cheat sheet allowed (4 by 6 index card, written by hand, 2-sided)
Practice Exam 2
Solution to Practice 2

Exam 2
Solution to Exam 2

Summary (Apr 12): # took exam - 112/119, highest - 100/100 (20 of 112), lowest - 38/100, mean - 85/100
                             The stem and leaf plot:
   3 | 8
   4 | 34
   4 |
   5 | 02
   5 | 579
   6 | 123
   6 | 58899
   7 | 00124
   7 | 555678888899999
   8 | 0011234
   8 | 6666677778888999
   9 | 00111122233344444444
   9 | 5555789999999
  10 | 00000000000000000000


Exam 1 (Monday, Mar 7) covering Chapter 1, 2, 3 (3.1-3.3)
             in class, closed notes and book, no calculators
             a cheat sheet allowed (4 by 6 index card, written by hand, 2-sided)
Practice Exam 1
Solution to Practice 1

Exam 1
Solution to Exam 1

 Summary (Mar 8): # took exam - 118/119, highest - 100/100 (17 of 118), lowest - 10/100, mean - 83/100
                             The stem and leaf plot:
   1 | 0
   1 |
   2 |
   2 | 8
   3 |
   3 | 5
   4 |
   4 | 578
   5 | 3
   5 | 99
   6 | 0224
   6 | 555578
   7 | 0011223334
   7 | 5555556777888
   8 | 000112222344
   8 | 5555566888
   9 | 000000001122222222334
   9 | 5555666667788889
  10 | 00000000000000000

updated by Ning SUN on May 26, 2011