AMS 303 GRAPH THEORY
Fall 2026
Instructor: Prof. Alan Tucker
Class Time and Place: TuTh 12:30 -1:50 pm in Heavy Engineering 201 .NOTE ROOM CHANGE
Zoom: The lectures are available live on Zoom (via Brightspace) and
afterwards as Zoom recordings.
Office Hours: PROF. TUCKER'S OFFICE HOURS on Zoom
https://stonybrook.zoom.us/j/6936387715 --Wed 11am-noon
Tu Th 3:30-5:00 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 72 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 the AMS Harriman help room
Tian Hao.Gao@stonybrook.edu, office hours: Wed 3-4, Fri 1-2pm, will grade homeworks for
students whose last names start with A-L
zimin.feng@stonybrook.edu, office hours:TuTh2-3pm , will grade homeworks for
students whose last names start with M-Z
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:Aug 25-Sept1: Applied Combinatorics Chapter 9, sect 1,2,3,4
Lecture Notes for Chap. 9 (Applied Combinatorics)
Homework 1 (due9/3):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 -- Sept 3- 15: A.C. Chapter 4
Lecture Notes for Chap. 4 (Applied Combinatorics)
Homework 2 (due 9/17):4.1: 4a; 4.2: 4b,9; 4.3: 2ab,3,6,8,9,12,21; 4.4: 2,4,5,8; 4.5: 4a,6a
Week 5 -- Sept 17-22: Chapter 10
Lecture Notes for Chap. 10(Applied Combinatorics)
Homework 3 (due9/24):10.1: 1ab,3,8ab,12a,15; 10.2: 1abc,2abc,3ab,4ab, 6ab
Week 6 -- Sept 24- 29: Review and 1st Test (test on Sept 29 in class live)
Past First Tests and Solutions
Past First Tests without Solutions
Solutions to Homeworks 1,2,3
The course now switches to Wilson's Introduction to Graph Theory (5th edition).
Week 7 - Oct 1-6: Chap 1 and 2 of Wilson
Lecture Notes for Chap. 1
Lecture Notes for Chap. 2
Homework 4 (due 10/8):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 8-- Oct 8-15: Chapt 4
Lecture Notes for Chap. 4
Homework 5 (due10/20):Chapt 4: 5(ii),8,10,13,14,15,16,17,18,19 plus #24 on p. 43 of Applied Combinatorics text
Week 9-- Oct 20-22: Chap 5.1,5.3
Lecture Notes for Chap. 5
Homework 6 (due10/27) 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
AMS 303 Old Quiz Questions without Solutions
Week 10- Oct 27-29: Chapt 5.2,5.5 and Quiz; 50-minute Quiz on Oct 29 on Respondus.
Homework 7 (due11/3):Chapt 5: #9, 12, 25, 28, 31.
Week 11- Nov 3-5: Review and Test 2 (Test 2 on iNov 5th)
(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
Past Second Tests without Solutions
Solutions to Homeworks 4,5,6
Week 12-14 Nov 10 - Dec 3 Cryptanalysis
Nov 11: Introduction to Cryptanalysis
Lecture Notes for Postlude - Cryptanalysis
Nov 13: For class, work postlude problem #2 (Error in text, the repeated sequence is JPLENFYV -the L was missing in the textbook)
Nov 18: For class, work postlude problem #3 and explanation of takehome project
Nov 20: Takehome project discussion (WATCH OUT: it is double keyword, not single keyword as in homeworks)
TAKEHOME PROJECT DUE Dec 5th by 11:59pm (for helpful links, see below)
Nov 26-Dec 5: No class -- work on takehome cryptogram project
Spring 2026 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 the second keyword (see Nov 18 or 20 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 90% of issues. PLEASE READ
Tips for Takehome Final
Take-Home Final due on Dec 5th at 11:59 pm
FOR 40-points FULL CREDIT: submit decoded cryptogram DIRECTLY TO PROF. TUCKER by email (do not submit on Blackboard) along
i) (15 pts) a picture of aligned alphabets;
ii) (5 pts) the trigraph table for collapsed cryptogram and table of frequent digraphs (like Fig P.2 in Postlude; and
iii) (20 pts) a careful analysis of how the keyword transpose table was filled in using exactly the reasoning Prof. Tucker used to solve the homework cryptograms.
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