
Jamie,

This is a list of the changes to the lectures since Fall 2020.
I've put a * on significant changes from Spring 2021.

Lecture 1.  Fundamental Combinatorial Objects.
 
*           The lecture is too long -- 55mins -- and we want to spend
            the time on the graphs + trees which is new material 
            so I deleted the slide with the C/Python permutation code.

Lecture 2.  Basic Counting Principles.  No change.

*           Note: rather than using binary strings to do the proof
            for nCk = nC(n-k), to save time, here is a simple one-line proof:
            Choosing k from n == removing n-k from n == choosing n-k from n to remove

Lecture 3.  The Binomial Theorem.  No change.

Lecture 4.  Combinations with Repetition
            We've already done the last example "two proofs that G can have at most
            n(n-1)/2 edges"
            For Spring 2021 we replaced it with "How many paths of length 2 edges are in K6?"
            But we have several examples like in lectures 5 and 6 and none for boxes and balls.
*           Have added a boxes and balls exercise to help students do assignment 1.

Lecture 5   Counting in graphs.  No change.

Lecture 6.  Graph Isomorphism.  No change.

Lecture 7.  Basics of Discrete Probability.  No change.

Lecture 8.  Conditional Probability and Independence.  No change.

Lecture 9.  Discrete Random Variables.

            Moved linearity of expection to new Lecture 10.
            Moved the bins and balls problem to new Lecture 10.
            Replaced with the geometric distribution.
            Followed by the binomial distribution.

Lecture 10  Applications of Discrete Random Variables.  New lecture.

            Review of Pr(X=x) and E(X).
            Linearity of Expection moved here.
            The bins and balls problem.
            The coupon collectors problem.

Lecture 11  Recurrence Relations

*           Inserted "constant coefficients" into definition.

Lecture 12  Solving First order Recurrences  No change

Lecture 13  Solving Second order Recurrences  No change

Lecture 14  First order Non-Homogeneous Recurrences  No change

Lecture 15  Solving Non-Homogeneous Recurrence Relations  No change

Lecture 16  Divide and Conquer Algorithms and Recurrences

            The lecture was too long so for Spring 2021 I deleted the
            general divide and conquer recurrence theorem.
            Now we have time to do the Add example.

            Also added a slide at end to "inform the students" that
            Maple can solve all the recurrences in the course.

Lecture 17  Generating Functions  No change.

Lecture 18  Calculating with Generating Functions
            For Spring 2021 I added Example 2:  Find the inverse of (1-x)^k 
            per our discussion and because we use it.
            This replaces 3 smaller not so useful examples.

Lecture 19  New Title "Rational Generating Functions"  No change.
            (i.e. back to the title you had commented out in your booket)

Lecture 20  Rational Generating Functions continued.

            Replaced 9.3 Partitions with Series Division.

Lecture 21  Solving Recurrences using Generating Functions.  No change.

Lecture 22  Summation Operator and Induction.
            For Spring 2021 I deleted the calculation of sum of odd numbers
            because lecture was too long.  Added exercises on induction.

Graph Theory

Lecture 23  Multigraphs and
Lecture 24  Eulerian Trails and  Cicuits

*           The lecture on Euler circuits is > 5 mins too long and the lecture on 
            multigraphs is > 5 mins too short.  I have a good solution; move the
            Bridges of Konigsberg problem to immediately follow the definition of degree
            as an good appliction of multigraphs and degree.

            No other change.

Lecture 25  Planarity

            For Spring 2021 I moved the material on face degrees to Lecture 26
            as the lecture was too long.

Lecture 26  Planarity continued.
            Moved face degrees here.
*           Just before the bounds on the maximum number of edges I had
            "It's easy to show that a graph is planar: find a planar embedding.
             How can we show that a graph is NOT planar?"
            with the (better) question
            "What is the maximum number of edges a planar simple graph can have?"

Lecture 27  We ran over time on Fall 2020 so for Spring 2021 I removed slide 6
            titled Necessary conditions which included two examples.
            I also changed necessary condition (3) on slide 5 to be the simpler
            (3) n is odd is a necessary and sufficient condition for Kn to have an E.C.
            No other change to the lecture.

            Note, I created an exercise as an application of the Theorem 11.8:
            "12 students are to be seated in a row of 12 seats in a classroom.  If each
            student knows at most 5 others, explain why it is possible to set them in such
            a way that each student does not know the student(s) sitting beside them."
            
            Jamie, I changed your notes.  On slide 9 we say the corollary is tight.
            I commented out your example of two copies of Kn since I gave two
            copies of K3 as an example (it's simpler) in the lecture.
            
            I still went 5 minutes over time in Spring 2021.  For Fall 2022 if you want to
            keep the lecture intact then I would remove Algorithm exhaustive search slide.

            For Fall 2022, if you decide to split this lecture into two, one solely
            on HPs and HCs and the other on covering necessary+sufficient conditions
            and converses and counterexamples, you'd be able to back the nice
            necessary condition example
            "Let G=(V,E) e a bipartite graph with bipartition V = V1 union V2.
             If G has a Hamiltonian cycle then |V1| = |V2|."

            Theorem 11.8 is on Hamiltonian paths.  The analagous theorem for Hamiltonian
            cyles is Theorem 11.9.  For the HC/HP lecture, I think it makes sense simply
            state Theorem 11.9 without proof:
            "Theorem 11.9  Let G=(V,E) be a simple graph with |V|>2.  If deg(x)+deg(y)>=n
             for all non-adjacent x,y in V then G contains a H.C." 
            Then give Kn,n and Kn,n-1 as examples supporting the theorem.  Then there
            are more exercises you can assign on the Theorems 11.8 and 11.9.
            This would "fill a hole" in our HP/HC lecture.
 
            If you do this then you can assign 11.5 exercise 18 as an exercise:
            "Helen and Dominic invite 10 friends to dinner.  In this group of 12,
             each person knows at least 6 others.  Prove that the 12 can be seated
             around a circular table in such a way that each person knows the 
             persons sitting on either side."
            
            Anyway, you'll figure this out.


Lecture 28  Trees  No change

Lecture 29  Trees and Rooted Trees  No change

Lecture 30  Rooted Trees  

            We went way over time again in Spring 2021 -- I used 1:00 hour.
            We need 20 mins for the DFS algorithm for the given example.

*           To fix this for Fall 2022 I have commented out the slide 7
            on Graph Algorithms which saves 7 minutes.

Lecture 31  Articulation Points and Biconnected Components   No change

Lecture 32  Weighted Graphs and Minimum Spanning Trees  No change


Also when I originally created the slides, I didn't know the difference
between example and exercise.  I've updated the booklet and slides so that
what we do in class is labelled Example and problems left for students
to do are labelled Exercise.

