Ning
Syllabus Schedule Lecture Notes with Animations Homework Exam
Course website: http://www.ams.sunysb.edu/~nsun/Teaching/ams301_spring2009.html
Class Time & Location: MoWeFr
Office Hour: Mo 11:00AM-1:00 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.
TA
John La Greca johnlagreca@gmail.com
Office Hour: We 1-2pm@ 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:
Course
outline:
Graph Theory
Basic definitions, models, isomorphism
Planar graphs, Euler,
Trees/enumeration
Shortest paths, minimum spanning trees, 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
Homeworks: Homework will be assigned weekly
(approximately), and will be due at the beginning of class on the due date (before 10am).
There will be approximately 10 homework sets, equally weighted, and I will drop
the lowest two scores before computing your average.
No late homework will be
accepted. You
are allowed to collaborate on assignments with others but don’t turn in
identical solutions unless the textbook shows as a guide. Please make certain
that your writing is neat and clear, and that you have expressed your
reasoning, not just the final answer. Please staple!
Exams: There will be three exams. The
first two midterms will be in class, tentatively, Friday February 27, and Friday
April 3 (right before spring break). The third exam (final) is Friday May 15,
Grading Policy: Your grade will be based on: Homework
(15%) + in-class test (35%) +Final (50%). No collaboration is allowed in any
test. Violation of these collaboration rules will result in a “Fail” in
this course.
Disability
Policy: If you have a physical, psychological, medical or learning disability
that may impact your course work, please contact Disability Support Services,
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 23rd week (Feb 9 - 13) 2.2 2.3 2.4
Lecture 4 (Feb 09) - Section 2.2 Hamilton Circuit5.1#18 (b): You don't know the total number
of letters and digits you need to choose for the plate. But on the plate, you
should put the letters (1, 2 or 3) consecutively. For example, 5k, 5mm4, 54mm
are all possible chooses. As you learned in class, when dealing with a
"consecutive grouping" of some items, you need to glue the items
together. Here the difficulty is: you don't exactly know what to glue together.
So do it in two stages: Find the letters first (three cases: 1, 2 or 3
letters); then glue them together as a composite letter L, choose the digits
and order them. (For example, you choose 1 digit, you can have dL or Ld;
when you choose 2 digits, you can have ddL, dLd or Ldd,...)
5.3#12: Split the pool into two sets: red+white+blue; 1 pink+1 lavender+1 tan.
Pick k balls from the second set first (k=0, 1, 2, 3), then pick the
remaining (8-k) balls from the first set. For example, you choose 1 ball
from 1 pink+1 lavender+1 tan (how many ways in this stage??), and then you
choose 7 balls from red+white+blue (choosing 7 from 3 types).
5.3#16: too complicated. So you don't need to do it in the hw. I will
talk about it on Monday.
5.3#26(b): Since the order matters, you need to label the 9 rings: #1, #2... #9.
Then think about the "brain teaser" we did in class, in which I used
"x" for ice cream and "s" to differentiate the
flavors. Try to interpret this question in a similar way: use numbers for rings
and "s" to differentiate the fingers. Then you can get a sequence
to represent one arrangement, the there is a 1-to-1 correspondence between the
arrangements and such sequences. For example, 1234s79s6s58 represents a
possible arrangement: you put #1, #2, #3 and #4 rings on your index finger, #7
and #9 on your middle finger, #6 on your ring finger, and #5, #8 on your little
finger. Then you calculate how many possible sequences you can have. Note
that ring #1- # 9 are different. So in total you have 10 types of items (1, 2...
9 and "s").
Final (11:00am - 1:00 pm, May 15) covering Chapter 7(7.1-7.2), 8 (8.1-8.3)
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
Summary: # took exam - 50/52, highest - 100 (1 of 50), lowest - 5, mean - 65, median - 71
The stem and leaf plot:
0 | 5
1 |
2 | 2267
3 | 0
4 | 88999
5 | 1144789
6 | 222789
7 | 0111234456799
8 | 0124566679
9 | 27
10 | 0
Exam 2 (Friday, Apr 3) 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)
Exam2 sample
Solution to sample2
Summary: # took exam - 49/52, highest - 115 (11 students got higher than 100), lowest - 37, mean - 80, median - 82
Note:The seven questions in the sample are not
equally weighted. The last two questions are more complicated than the first
five. So you can get some extra credit by choosing them.
In the real exam 2, you will have a similar problem set with the two-question
"bonus". Please pay attention to the time. The highest score can be
115.
Exam 1 (Friday, Feb 27) 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)
Exam1 sample
Solution to sample1
Exam1 (word, pdf )
Solution to exam1 (updated on Mar 1)
Summary: # took exam - 50/52, highest - 100 (13 of 50!!!), lowest - 27, mean - 84, median - 93
See the updated solution to find some comments on the common errors.
It seems easy for most of the class.
updated by Ning SUN on May 16, 2009