AMS301 Summer2009

AMS301.01 Finite Mathematical Structures, Summer 2009

Syllabus Schedule Lecture Notes with Animations Homework Exam

Syllabus

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

Class Time & Location: TuTh 6:00PM-9:25PM @ Earth & Space 069

Instructor: Ning Sun nsun@ams.sunysb.edu

Office Hour: Tu 3:00PM-5:00PM @ 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.

Grader: Kenzley Alphonse kenzley.alphonse@stonybrook.edu

Office Hour: TuTh 5:00PM-6:00PM @ Harriman Help Room 010

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

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

Course outline:

Graph Theory

Basic definitions, models, isomorphism
Planar graphs, Euler, Hamilton circuits, coloring
Trees/enumeration
Shortest paths, traveling salesperson

Enumeration and Counting

Basic counting principles; Arrangements and selections
Binomial coefficients, permutations, combinations
Generating functions
Recurrence relations/Divide and conquer
Inclusion-Exclusion formulas

Policies:

Homework will be assigned weekly, and will be due at the beginning of class (by 6:30) on Tuesdays. No late homework will be accepted.
The lowest hw grade will be dropped.
All grades will be posted on Blackboard. Make sure you can be reached via the email address on Blackboard.
Exams will be given at the beginning of a class in the regular classroom.
Exams are closed notes and book, no calculators. However, you will be allowed a cheat sheet.

Grading:

Homework (20%)
Midterm I (25%)-- Jul 30
Midterm II (25%) -- Aug 11
Final (30%) -- Aug 20

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 will make 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 1
Lecture 2
Lecture 3
Lecture 4
Lecture 5
Lecture 6
Lecture 7
Lecture 8
Lecture 9

Schedule

1st week (Jul 13 - 17) 1.1-1.4; 2.1

Lecture 1 (Jul 14) - Section 1.1 - 1.3
Lecture 2 (updated on Jul 16) - Section 1.4 - 2.1

2nd week (Jul 20 - 24) 2.2-2.4; 3.1-3.3

Lecture 3 (updated on Jul 21) - Section 2.2 - 2.4
Lecture 4 (updated on Jul 23) - Section 3.1 - 3.3

3rd week (Jul 27 - 31 ) Midterm I; 5.1-5.2

Lecture 5 (updated on Jul 29) - Section 5.1 - 5.2

4th week (Aug 3 - 7 ) 5.3-5.5; 6.1-6.2

Lecture 6 (updated on Aug 4) - Section 5.3 - 5.4
Summary of Chapter 5 (Aug 5) - About how to check the formula table
Lecture 7 (updated on Aug 6) - Section 6.1 - 6.2
Exercises (Aug 7) - All the in class exercises with solutions

5th week (Aug 10 - 14 ) Midterm II; 7.1-7.2

Lecture 8 (updated on Aug 11) - Section 7.1 - 7.2
Lecture 9 (updated on Aug 18, typo corrected) - Section 8.1 - 8.3

6th week (Aug 17 - 20 ) 8.1-8.3; Final

Homework

Solution:

hw1 solution (Jul 21)
hw2 solution (Jul 28)
hw3 solution (updated on Aug 6, typo corrected)
hw4 solution (Aug 11)
hw5 solution (Aug 18)

HW5 (due on Tuesday, Aug 18) covering 7.1 - 7.2; 8.1 - 8.2
7.1: 2, 10; 7.2: 8 (a,b); 8.1: 10, 12, 20, 26, 36; 8.2: 2, 6, 8
Find a recurrence relation for the number of n-digit binary sequences with (a) no "11"; (b) no "10".
Find a recurrence relation for the number of n-digit ternary sequences with (a) no "10"; (b) any 1 not in the last position is followed by a 0.

Hints:

in 7.2:8, please rethink about how many more comparisons you need when you have the largest and second largest numbers in each half of the set. In our class, one said "three". Actually there's is a better way involving 2 more comparisons.

HW4 (due on Tuesday, Aug 11) covering 5.3 - 5.4; 6.1 - 6.2
5.3: 2, 22; 5.4: 2, 12, 34, 48; 6.1: 2 (b,e), 4 (b, d), 8; 6.2: 2, 8, 18(a), 20

HW3 (due on Tuesday, Aug 4) covering 5.1 - 5.2
5.1: 6, 18(a), 22, 32; 5.2: 4, 10, 14, 16 (b, c, d) , 25, 32, 38

HW2 (due on Tuesday, Jul 28) covering 2.2-2.4; 3.1 - 3.2
2.2: 4 (f, h); 2.3: 1(l, n), 2(b,e), 12; 2.4: 4, 5; 3.1: 16, 28; 3.2:1(d), 4, 26(a,b).
Note: Since I didn't finish 3.2 today, only do 26(a,b) in 3.2.

HW1 (due on Tuesday, Jul 21) covering 1.1- 1.4; 2.1
1.1: 4; 1.2: 4, 5 (b c k ), 6 (a, e); 1.3: 4,8; 1.4: 3 (f, j), 7 (f, i), 16; 2.1: 2.
Hints:
In 1.1: 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, when determine whether two graphs are isomorphic, you need to explain: if they are isomorphic, show the 1-to-1 correspondence; 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.
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 connects with all the vertices in Group 2. Group 2 has s vertices, each of which connects with all the vertices in Group 1. K3,3 is the specical case of Kr,s.

Exam

Exam 3 (Tursday, Aug 20, 6:00 - 7:30 pm) covering Chapter 7,8
in class, regular classroom
closed notes and book, no calculators
a cheat sheet allowed (4 by 6 index card, written by hand, 2-sided)
     Exam3 sample
   Solution to sample3
Solution to Exam 3

Exam 2 (Tuesday, Aug 11, 6:00 - 7:00 pm) covering Chapter 5, 6
in class, regular classroom
closed notes and book, no calculators
a cheat sheet allowed (4 by 6 index card, written by hand, 2-sided)
     Exam2 sample
   Solution to sample2

Exam2
Solution to Exam 2

Summary (Aug 12): # took exam - 26/28, highest - 110/110 (4 of 26), lowest - 30, mean - 91.5
The stem and leaf plot:

   3 | 0
   4 |
   5 |
   6 | 359
   7 | 577
   8 | 47
   9 | 489
10 | 0001112557
11 | 0000

Exam 1 (Thursday, Jul 30, 6:00 - 7:00 pm) covering Chapter 1, 2, 3 (3.1-3.3)
in class, regular classroom
closed notes and book, no calculators
a cheat sheet allowed (4 by 6 index card, written by hand, 2-sided)
Exam1 sample
Solution to sample1

Exam1
Solution to Exam 1

Summary (Aug 4): # took exam - 28/28, highest - 100 (6 of 28), lowest - 54, mean - 87
The stem and leaf plot:

   5 | 4
   5 |
   6 |
   6 | 667
   7 | 0
   7 |
   8 | 1244
   8 | 58
   9 | 001222234
   9 | 78
10 | 000000

updated by Ning SUN on Aug 20, 2009