AMS 303 GRAPH THEORY
Class Time and Place: TuTh1:00-2:20 Frey 104.
Instructor: Prof. Alan Tucker
Office: Eng 127 (room at back right of suite)
Tu 2:30-3:45 pm, Wed 11 am - 1 pm, and Fr 10 am - noon or by appointment
Course Texts:Introduction to Graph Theory, Fifth Edition,
by R. Wilson, customized for Stony Brook, and
Applied Combinatorics, Sixth Edition, by A.Tucker, John Wiley & Sons.
Tests: one quiz (10% of grade), two hour tests (about 30% each of grade), and take-home final (about 17% of grade).
Homework: Assigned weekly or bi-weekly and submitted in class (15% of grades); graded out of 5 points max;
Sum of HW points minus lowest HW equals 15% of course grade; Solutions to all problems available before tests.
weekly Assignments Listed Below.
Course Graders Unless otherwise noted, office hours are in the AMS Help Room Harriman 132.
Barnwal.Avinash@stonybrook.edu, office hrs Wed 1 - 3 pm, grading A-G of odd-numbered HWs
Peter.Gonatas@stonybrook.edu, office hrS Mon 4-6 pm, grading H-P of odd-numbered HWs
Michael.Labarbera@stonybrook.edu , office hrs MW 10-11 am, grading Q-Z of odd-numbered HWs
Qi.Lu@stonybrook.edu, office hrs Mon 11am-1pm, grading A-G of even-numbered HWs
Eleanor.Newberg@stonybrook.edu, office hrs Mon 1-2 pm, Wed 4-5 pm, grading H-P of even-numbered HWs
Huizhen.Wen@stonybrook.edu, office hr Tu 9:30-11:30 am, grading Q-Z of even-numbered HWs
Americans with Disabilities Act: 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, if
any, are necessary and appropriate. All information and documentation
Academic Integrity: Each student must pursue his or her academic
goals honestly and be personally accountable for all submitted work.
Representing another person's work as your own is always wrong.
Faculty is required to report any suspected instances of academic
dishonesty to the Academic Judiciary. Faculty in the Health Sciences
Center (School of Health Technology & Management, Nursing, Social
Welfare, Dental Medicine) and School of Medicine are required to
follow their school-specific procedures. For more comprehensive
information on academic integrity, including categories of academic
dishonesty please refer to the academic judiciary website at
Critical Incident Management: Stony Brook University expects students
to respect the rights, privileges, and property of other people.
Faculty are required to report to the Office of University Community
Standards any disruptive behavior that interrupts their ability to
teach, compromises the safety of the learning environment, or
inhibits students' ability to learn.
Learning outcomes for AMS 303
1.) Develop skill with proofs in graph theory (this is the only Applied Math course that teaches proofs), including:
* the careful use of definitions and stated conditions, and their consequences;
* direct arguments;
* indirect arguments, i.e., proof by contradiction;
* proof with generalized figures.
2.) Examine graph theory topics in greater depth (than AMS 301) with a focus on studying and extending theoretical results:
* general graph properties;
* planar graphs;
* graph coloring, including edge and face coloring.
3.) Understand the theory behind Polyabs Enumeration Formula and use this understanding in applied problem-solving.
4.) Develop the network algorithms for:
* maximal minimal flows;
* maximal matching;
* the transportation problem.
5.) Understand the set-theoretic constructions underlying the theory of progressively finite games and apply this knowledge to develop winning strategies for such games:
* kernel of a game;
* level-by-level construction;
* Grundy functions;
* direct sums of games, including Nim.
6.) Use combinatorial reasoning to efficiently solve cryptograms based on keyword transpose encodings; extend this reasoning to solve polyalphabetic codes.
Week 1-- Jan 23-30: Intro to Graph Theory, Chapt 1&2 (skip sect 1.3)
Homework 1 (due 2/1):Chapt 1: #15,16,29 (skip k-cube), 31, Chapt 2: #3(skip part v),5 ,9(i), plus #33 on p. 48 of the Applied Combinatorics text.
Week 2-- Feb 1-6:G.T., Chapt 4
Homework 2 (due 2/8): Chapt 4: 5(ii),8,10,13,14,15,16,17,18,19 plus #24 on p. 43 of Applied Combinatorics text
Week 3-- Feb 8-13: Chapt 5.1, 5.3
Homework 3 (due 2/15): Chapt 4: 22,23,24,25; Chapt 5: #1, 4(i)(ii), 7,8, 19
AMS 303 Old Quiz Questions and Solutions
Week 4-- Feb 15-20: G.T., Chapt 5, Quiz on Feb 15
Homework 4 (due 2/22): Chapt 5: #9, 12, 25, 28, 31.
Week 5-- Feb 22-27: Review and Test 1 (Test 1 on Feb 27)
Spring 2018 First Test
Fall 2017 First Test
Spring 2017 First Test
Solutions for Old First Tests
Solutions to Homeworks
THE TEXTBOOK NOW SWITCHES TO APPLIED COMBINATORICS (the AMS 301 text)
Week 6/7--Mar 1-8: Applied Combinatorics Chapter 9, sect 1,2,3,4
HomeWork 5 (3/20):Applied Combinatorics 9.1: 5c,10bc; 9.2: 3,4,10; 9.3: 4ac,5de,7de; 9.4: 2bcd,3 (write the whole polynomial out term-by-term), 7de, 9ab
Week 8/9- Mar 20 - 29: A.C. Chapter 4, sect 3,4,5
Homework 6 (due 4/3):4.3: 2ab,3,6,8,9,12,21; 4.4: 2,4,5,8: 4.5: 4a, 6a
Week 10- Apr 3-5:Chapter 10
Homework 7 (due 4/10): 10.1: 1ab,3,8ab,12a,15; 10.2: 1abc,2abc,3ab,4ab, 6ab
Week 11- Apr 10-12: Review and Test (test on Apr 12)
NOTE: There are errors in problem #5 on the fall & 2016 test
In fall 2016, Tigers should have 9 games to play;
Fall 2017 Second Test
Spring 2017 Second Test 5
Fall 2016 Second Test
Solutions to Old Second Tests
Solutions to Homeworks 5 and 6
Week 12-14- Apr 17-May 3: Postlude- Cryptanalysis
For students with 5th edition, here is the Postlude
Homwork to finish for class (do before class)
Apr 17: XTEIA DSL ASQA FKSF FKY IVYOPYUJQ NI PAY NI LNVRA TU SMYVTJSU
UYLAESEYV YUCDTAK SUR FKYTV VSUG NVRYV SVY JDNAYDQ VYDSFYR
Homework to finish for class Apr 19: Postlude problem #2
Homework to finish for class Apr 24: Postlude problem #3
Apr 26 Receive takehome cryptogram
Polyalphabtic Encoding Sheet
Template for Keyword Tables
Template for Aligning Alphabets
Tips for Takehome Final
Take-Home Final due on Thurs May 17th by 4 pm.
Submit solved final cyptogram by email
Historical Curve in Prof. Tucker's AMS 303 classes:
- approximately 30% A's, 40% B's, 25% C's, 5% D's,F's&W's