Basic Concepts in Graph Theory
Grading:
Lectures - I will be using a combination of powerpoint as well as chalkboard derivations to illustrate the concepts in the course. Before each class a pdf copy of the notes for the next day's lecture will be posted to the website. I will bring printed copies of the lecture slides for every member of the class. If you miss a lecture you can either get it from a friend or else pick one up from a box outside of my office. The format of the lectures will be a mix of traditional lecture and interactive solving of problems by members of the class. While solving these problems in class is optional, I encourage you to engage with the in class problems as it will make the homework problems much easier.
Discussion board: we will be using moodle as a way for students to help each other in the course. Here is a link to the moodle page for the course.
Academic Integrity - Don't cheat.
Section: Monday 3:30-4:20pm (Peterson 102) and Wednesday 1-1:50pm (CSB 005)
Office Hours:
Midterm. You will be allowed 1 8.5" by 11" sheet of paper (front and back, hand written) for notes. You will have to turn this in with your test. Here is the midterm and solutions from Spring 2011 Course for practice. You can also take this practice final (with solutions here). The material in Questions #3, 5, 8, 9, 10 you should be able to do for the midterm.
Here is a link to the notes from the review session that Susan and Ivan ran.
Final. You will be allowed 1 8.5" by 11" sheet of paper (front and back, hand written) for notes. You will have to turn this in with your test. Here is a study guide that I am in the process of preparing for the final (it is still a work in progress any suggestions are welcome). Here is the study guide with the solutions removed from the example problems.
This is a tentative class schedule for the course. Dates are subject to change a bit.
| Class # | Date | Notes | Reading |
| 1 | Monday August 1, 2011 | Lists with Repetition | CL Section 1 |
| 2 | Tuesday August 2, 2011 | Lists without Repetition | CL Section 1 |
| 3 | Wednesday August 3, 2011 | Sets Lecture 1 | CL Section 2 |
| 4 | Thursday August 4, 2011 | Sets Lecture 2 (inclusion exclusion) - Homework 1 Due Friday at 2pm (Solutions) | CL Section 2 and 3 |
| 5 | Monday August 8, 2011 | Inclusion Exclusion and Stirling Numbers, and Proofs by Double Counting | CL Section 3 and 4 |
| 6 | Tuesday August 9, 2011 | Stirling Numbers of the Second Kind, Proofs by Double Counting, Functions Lecture 1 | Fn Section 1 |
| 7 | Wednesday August 10, 2011 | Functions Lecture 2 | Fn Section 2 |
| 8 | Thursday August 11, 2011 | Orders of Permutations and Multichoose - Homework 2 (Solutions) | Fn Section 2 |
| 9 | Monday August 15, 2011 | Intro to Probability | CL Section 4 |
| 10 | Tuesday August 16, 2011 | Conditional Probability, Decision Trees, Bayes' Rule (this is the last lecture you need to study for the midterm) | |
| 11 | Wednesday August 17, 2011 | Bayes' Rule and Random Variables | Fn Section 4 |
| 12 | Thursday August 18, 2011 | Midterm (solutions)- Homework 3 (solutions) | |
| 13 | Monday August 22, 2011 | Expected Value and Linearity of Expectations | |
| 14 | Tuesday August 23, 2011 | Variance of a Random Variable, Intro to Induction | Fn Section 4, DT Section 4 |
| 15 | Wednesday August 24, 2011 | Review of Random Variables | Fn Section 4 |
| 16 | Thursday August 25, 2011 | Inductive Proofs - Homework 4 (new HW solutions). Old homework is here (old solutions solutions) | DT Section 4 |
| 17 | Monday August 29, 2011 | Constructing Recurrence Relations | DT Section 4 |
| 18 | Tuesday August 30, 2011 | Second-Order Linear Recurrence, intro to Recursion and Probability | DT Section 4 |
| 19 | Wednesday August 31, 2011 | Recursion and Probability | |
| 20 | Thursday September 1, 2011 | Review for Final | |
| 21 | Friday Septebember 2, 2011 | Final Exam Homework 5 solutions |
Miscellaneous: Matlab code to enumerate all permutations of a listt of elements with the specified number of repeats for each unique element. Also included is code to solve problem HW1 2.c