CMPE177: Applied Graph Theory and Algorithms

Martine Schlag, Fall 1998

Welcome to the evolving 177 Home Page

Send email to: your instructor, your TA, or to the entire class (including the instructor and TA).

Course Information

• Requesting academic accommodations
• Time and Place: MWF 12:30-1:40 NatSci Annex 102
• Section: Wed. 5-6pm Applied Sciences 169
• Lab hours: Applied Sciences 105: Tu 6-7pm, Th 12:30-1:30pm, F 10-11am
  The SUN workstations formerly in Applied Sciences 215 have been moved to 105. Students working on their CMPE177 projects will have priority on these workstations during these hours.
• Staff:
• Instructor: Martine Schlag
  Applied Sciences 317B
  (831)459-3243
  Office Hours: Tues. 11am-12pm and Mon. 2:30-3:30pm
• TA: Andrew S. Klingler
  Office Hours: Wed. 9-10am and Thur 1-3pm

Held in Trailer 12B behind Applied Sciences.
• Grading
• Text: A First Look at Graph Theory by John Clark and Derek Allan Holton.
  World Scientific 1991. Paperback. ISBN 981-02-0490-6
  Errata
• Syllabus
• Class Newsgroup: ucsc.class.cmpe177 - for announcements, general discussion, and help

Homework Assignments

• Homework 6: due Friday Dec. 11, beginning of class.
• Homework 5: due Friday Dec. 4, beginning of class.
• Homework 4: due Friday Nov. 20, beginning of class.
• Homework 3: due Friday Nov. 6, beginning of class.
• Homework 2: due Friday Oct. 23, beginning of class.
• Homework 1: due Friday Oct. 16, beginning of class.
• Homework 0: due Friday Oct. 9, beginning of class.

Project Description

Handouts

1. The Matrix-Tree Theorem (postscript)
2. Minimum Spanning Tree Algorithms (postscript)
3. Breadth First Search(postscript)
4. Dijkstra's Shortest Path Algorithm (postscript)
5. Depth First Search(postscript)
6. Cut Vertices and Biconnected Components (postscript)
7. Finding Strongly Connected Components with DFS(postscript)
8. Demoucron's Planarity Algorithm(postscript)

Other Information

• Academic Integrity
• Last Year(postscript)
• CS/CE home page
• Murphy's Law
• Unacceptable proof techniques
• Keiko

Portions of the CMPE177 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited.