AMS 303 GRAPH THEORY
Spring 2024
Class Time and Place: TuTh 10-11:20 am in Eng 145.
Instructor: Prof. Alan Tucker
Office Hours: PROF. TUCKER'S OFFICE HOURS ON ZOOM (see Zoom Meetings on Brightspace): Wed 11am - noon
Tu Th 1:30-3:00 pm, and Friday 3-4 pm and by apppointment
How to reach me: email: alan.tucker@stonybrook.edu
Course Texts: Applied Combinatorics, Sixth Edition, by A.Tucker, John Wiley & Sons.
and
Introduction to Graph Theory, Fifth Edition,
by R. Wilson, customized for Stony Brook. You can download a copy of the 4th editoion of
Wilson from the Univ of Edinburgh-google'Introduction to Graph theory by Wilson'
and see conversion of HW problems.
Tests: one quiz 20 pts, two mid-terms of 75 and 55 pts, and take-home
project of 40 pts. The total score (max 208 pts) is sum of quiz, tests and project plus HW score (described below). Total score is curved as described at bottom of this page.
Homework: Assigned weekly or bi-weekly and submitted through Brightspace.
The 7 HWs have a total score of 42 pts, most are worth 5 pts. The lowest score will be dropped
and the remaining total multiplied by 1/2, for a max of 18 pts, towards the total course score of 208 pts. HWs that are up to one week late will be accepted with a 1 pt penalty.
Solutions to all problems available before tests.
Weekly Assignments Listed Below.
Course Graders Office hours will be in AMS Harriman help room
Touhid Hussain,, office hours: MonWed 4-5pm, will grade homeworks for
students whose last names start with A-G
Thi-Thanh-Lam Vu, office hours: MonWed 10-11am, will grade homeworks for
students whose last names start with H-L
Alexander Etter, office hours: Tues 6-7pm plus by appointment in Zoom,
will grade homeworks for
students whose last names start with M-U
Yuejun Xu, office hours: TuTh 4-5 and by appointment (via Zoom), will grade homeworks
for students whose last names start with V-Z.
Americans with Disabilities Act: If you have a physical,
psychological, medical or learning disability that may impact your
course work, please contact Student Accessibility Support Center,
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
is confidential.
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
http://www.stonybrook.edu/uaa/academicjudiciary/
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 Polyas 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.
COURSE OUTLINE:
See Corrections of 6th edition of Applied Combinatorics for errors
Week 1-2:Jan 23-30: Applied Combinatorics Chapter 9, sect 1,2,3,4
Lecture Notes for Chap. 9 (Applied Combinatorics)
Homework 1 (due2/1):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 2-4 -- Feb 1-15: A.C. Chapter 4
Lecture Notes for Chap. 4 (Applied Combinatorics)
Homework 2 (due 2/20):4.1: 4,(delete 'total' in line 2),9; 4.2:2,5; 4.3: 2ab,3,6,8,9,12,21; 4.4: 2,4,5,8; 4.5:4a,6a
Week 5 -- Feb 20-22: Chapter 10
Lecture Notes for Chap. 10(Applied Combinatorics)
Homework 3 (due2/27):10.1: 1ab,3,8ab,12a,15; 10.2: 1abc,2abc,3ab,4ab, 6ab
Week 6 -- Feb 27-29: Review and 1st Test (test on Feb 29 on Respondus)
Past First Tests and Solutions
Solutions to Homeworks 1,2,3
The course now switches to Wilson's Introduction to Graph Theory (5th edition).
Week 7-- Mar 5-7: Intro to Graph Theory, Chapt 1&2 (skip sect 1.3)
Lecture Notes for Chap. 1
Lecture Notes for Chap. 2
Homework 4 (due3/19):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.
Spring Break Mar 11-15
Week 8-- Mar19-21: Chapt 4
Lecture Notes for Chap. 4
Homework 5 (due3/26):Chapt 4: 5(ii),8,10,13,14,15,16,17,18,19 plus #24 on p. 43 of Applied Combinatorics text
Week 9-- Mar 26-28: Chap 5.1,5.3 and Review for Quiz
Lecture Notes for Chap. 5
Homework 6 (due4/2) Chapt 4: 22,23,24,25};Chapt 5: #1, 4(i)(ii), 7,8, 19
,21,22,24
AMS 303 Old Quiz Questions and Solutions
Week 10- Apr 2-4: Chapt 5, Quiz on Apr 4 on Respondus.
Homework 7 (due4/9):Chapt 5: #9, 12, 25, 28, 31.
Week 11- Apr9-11: Review and Test 2 (Test 2 on Apr11th on Respondus)
(you are allowed a 2-sided page of definitions and statements of theorems--
no proofs, no solutions to HW problems)
Past Second Tests and Solutions
Solutions to Homeworks 4,5,6
Week 12-15 Apr 16-May2: Cryptanalysis
Read the Postlude in the text before Thursday's class.
Homework to finish before class (do first one sefore Apr 11 class)
Apr 16:: Decode XTEIA DSL ASQA FKSF FKY IVYOPYUJQ NI PAY NI LNVRA TU SMYVTJSU
UYLAESEYV YUCDTAK SUR FKYTV VSUG NVRYV SVY JDNAYDQ VYDSFYR
Apr 18: Postlude problem #2 (Error in text, the repeated sequence is JPLENFYV -the L was missing)
Apr 23: Postlude problem #3 and discussion about solving takehome cryptogram-
`due May 4 by 10pm (for helpdul links, see below)
Apr 25- May 2: No class -- work on takehome cryptogram project
Fall2023 Crypto File with Everyone's TakehomeProject
The following link explains the ways polyalphabetic encoding works
Polyalphabtic Encoding
The following link contains the frequency strips will be used in class to illustrate
how to find second keyword (see Apr 18 or 23 lecture) solving polyalphabetic codes
Sample Frequency Strips
The following links are helpful in the takehome project
Template for Keyword Tables
Template for Aligning Alphabets
If you are having a problem, this file covers 99% of issues. PLEASE READ
Tips for Takehome Final
Take-Home Final due on May 4th
FOR FULL CREDIT: submit decoded cryptogram DIRECTLY TO PROF. TUCKER by email (do not submit on Brightspace) along with pictures of aligned
alphabets and trigraph table for collapsed cryptogram.
Historical Curve in Prof. Tucker's AMS 303 classes:
- approximately 35% A's, 40% B's, 20% C's, 5% D's,F's&W's
- A 40% average (80 pts) is required to pass with a C