CSC 422/522 Class Notes: Fall 2014

For a complete set of notes, please attend class or get notes from someone who attended. Only selected notes will be placed here.

1. Lecture 1: Intro. to CSC 422/522.
2. Lecture 2: Graphs.
   For a review of Big Oh notation: CSC 225 class notes. The introduction is in lectures 7 and 8 but algorithm space and time analysis continued throughout the class. CSC 225 or its equivalent is a prerequisite for CSC 422/522.
3. Lecture 3: Breadth First Search.
4. Lecture 4: Clockwise Breadth First Search.
5. Lecture 5: Clockwise BFS to find automorphisms of graphs.
6. Lecture 6: Automorphism groups of graphs.
7. Lecture 7: Isomorphic independent sets.
8. Lecture 8: Tree Isomorphism.
   Homework Hints.
9. Lecture 9: Walking faces.
10. Lecture 10: Preprocessing for planar embedding.
11. Lecture 11: Finding a planar embedding.
12. Lecture 12: Mathscinet.
13. Lecture 13: Program hints.
14. Lecture 14: Automorphisms of graphs and rotation systems.
    Note: I took some of the slides from Lecture 13 and moved them here so all the group theory information could stay together.
15. Lecture 15: An algorithm for finding a minimum dominating set.
16. Lecture 16: Better bounds for the dominating set algorithm.
17. Lecture 17: Compressed Adjacency matrix.
    Code for compressed adjacency matrices (click here).
    
18. Lecture 18: Maximum Flow in a Network.
19. Lecture 19: Vertex connectivity.
20. Lecture 20: The Queen graph Dominating set game
    The program for this, Queen.java, is available from connex in the resources section.
21. Lecture 21: Assignment #4 Bugs
22. Lecture 22: Crossing Cuts

    Crossing Cuts- solution to problem.

23. Lecture 23: Crossing Cuts- A bigger example.
24. Lecture 24: Algorithms for k-trees.
25. Lecture 25: Pfaffian orientations for counting perfect matchings.