MC 306 THEORY OF COMPUTATION
SPRING 2009 HOME PAGE
  • Class Meetings:
    • Classes: Tues-Thurs 12:40-2
    • Final Exam: Thurs, Dec. 17, 9-12
  • Instructor:
    • Alice Dean, Professor,
      Mathematics & Computer Science
    • Phone: 580-5286
    • Email
    • Home Page
  • Course Info Sheet
DATE TOPICS CLASS SLIDES, HOMEWORK,
& OTHER FILES		 READING & EXERCISES
  • Thursday, 11/19/09
    (Class #21)
  • Return, discuss Exam #2
  • Planar graphs
  • Reading:
    • 5.1-5.2
  • Exercises:
    • 5.1.1, 5.1.2, 5.2.1, 5.2.3
  • Tuesday, 11/17/09
    (Class #20)
  • Discuss final project
  • Matchings
  • Tonight: Numb3rs, with pizza and short talks by Dan Hurwitz and me – 7:30 in Harder 203
  • Reading:
    • 4.1
  • Exercises:
    • 4.1, #’s 1, 2, 6
  • Thursday, 11/12/09
    (Class #19)
  • EXAM #2
 
  • Tuesday, 11/10/09
    (Class #18)
  • Return, go over HW #4
  • Questions for Exam #2
  • Two more TSP algorithms: Closest Insertion and Two Optimal
  • Review Session Wednesday, 11/11/09, 7-8:30, Harder 201
  • Exam #2 on Thursday, 11/12/09
  • Reading:
    • Still 3.4
  • Exercises:
    • 3.4.2 – do closest insertion.
  • Thursday, 11/5/09
    (Class #17)
  • From last time:
    • Hamiltonian Cycles
  • Information about Exam #2
  • Closure of G and Hamiltonicity of G
  • Traveling Salesperson Problem
  • Reading:
    • 3.4
  • Exercises:
    • For the graph of 3.4.2: Do nearest neighbor (from any vertex you like) and cheapest link, and find a lower and upper bounds on the length of a TSP tour.
  • Tuesday, 11/3/09
    (Class #16)
  • From last time:
    • Characterizations and Algorithms for Euler Circuits
    • Chinese Postman Problem
  • Hamiltonian Cycles
  • Reading:
    • 3.1-3.3
  • Exercises:
    • 3.3.1-3.3.3
  • Thursday, 10/29/09
    (Class #15)
  • Go over HW #3
  • From last time: Euler and Hamiltonian Circuits
  • Characterizations and Algorithms for Euler Circuits
  • Chinese Postman Problem
  • Reading:
    • 3.1-3.2
  • Exercises:
    • 3.1.1 and 3.1.2 (you need not use Fleury's Algorithm as specified in 3.1.1)
  • Tuesday, 10/27/09
    (Class #14)
  • From last time: Whitney’s Theorem
  • Time Complexity of Graph Theory Questions
  • Euler and Hamiltonian Circuits
  • No new HW Problems
  • Help Session on Proofs: Wednesday, 11/28/09, 7-8:30 in Harder 201
  • Reading:
    • 3.1
  • Exercises:
    • No new exercises
  • Thursday, 10/22/09
    (Class #13)
  • Connectivity and cut vertices
  • Help Session on Proofs: Wednesday, 11/28/09, 7-8:30, in Harder 201
  • Reading:
    • 2.6
  • Exercises:
    • 2.6.1, 2.6.3
  • Tuesday, 10/20/09
    (Class #12)
  • Decide on date/time for extra session
  • Questions on HW #3
  • Breadth-First and Depth-First Search
  • Dijkstra’s Algorithm
  • Reading:
    • 2.5 (Doesn’t cover DFS)
  • Exercises:
    • 2.5.1 (also find DFS tree from vertex a),
    • 2.5.2
  • Thursday, 10/15/09
    (Class #11)
  • Return, go over Exam #1
  • Discussion of proofs by induction
  • No new reading
  • No new exercises
  • Tuesday, 10/13/09
    (Class #10)
  • From class before exam: Bridges
  • Spanning trees
  • Kruskal’s and Prim’s Algorithms
  • Reading:
    • 2.3-2.4
  • New exercises:
    • 2.3.3, 2.4.1—only 2nd graph of Fig. 2.23
  • Thursday, 10/8/09
    (Class #9)
  • Tuesday, 10/6/09
    (Class #8)
  • EXTRA OFFICE HOUR
    WEDNESDAY, 2-3:30
  • Return, go over HW #2
  • Questions for Exam #1 on Thursday
  • From last time: Prove tree characterization theorem
  • Reading:
    • Still [CH] 2.2
  • Exercises:
    • pp. 56-57, 2.2.1 & 2.2.2
  • Thursday, 10/1/09
    (Class #7)
  • Information about Exam #1, Thursday, October 8, 2009
  • Properties of trees (from slides of Tuesday, 9/29/09)
  • Characterizations of trees
  • Reading:
    • [CH] 2.2
  • No new exercises
  • Tuesday, 9/29/09
    (Class #6)
  • Proof of Havel-Hakimi Theorem
  • Trees
  • Reading:
    • [CH] 2.1
  • Exercises:
    • [BM] p. 13, 1.6.8 (recall that omega(G) = # of components of G); p. 26, 2.1.7
    • [CH] pp. 51-52, 2.1.3, 2.1.4
  • Thursday, 9/24/09
    (Class #5)
  • Proof of ‘Walk Counting’ Theorem
  • Degree Sequences and the Havel-Hakimi Theorem
  • Reading:
    • No new reading (omit [CH] 1.8)
  • Exercises: See last slide.
  • Tuesday, 9/22/09
    (Class #4)
  • Matrix representations of graphs
  • Reading:
    • [CH] 1.7
  • Exercises: [CH] p. 40, 1.7.1a,b and 1.7.2b
  • Thursday, 9/17/09
    (Class #3)
  • Characterization of bipartite graphs
  • Connectedness and components
  • Reading:
    • [CH] Still 1.6;
    • [BM] 1.6-1.7
  • Exercises: [CH] 1.6.2, 1.6.14
  • Tuesday, 9/15/09
    (Class #2)
  • Graph degrees and edges
  • New graphs from old: Subgraphs, unions and intersections
  • Walks and Paths
  • Reading:
    • [CH] 1.4-1.6;
    • [BM] 1.5-1.6
  • Exercises: [CH] 1.4.2, 1.4.9, 1.5.1, 1.5.2, 1.6.1, 1.6.6
  • Thursday, 9/10/09
    (Class #1)
  • Go over course info sheet
  • Basic definitions and notation
  • Reading:
    • [CH] 1.1 - 1.3;
    • [BM] 1.1-1.2 (In general, readings from [BM] are optional supplements to [CH])
  • Exercise: [CH] p. 13, 1.3.2