Department of Computer Science
University of Arkansas
Syllabus
Fall 2002
CSCI 5283 Graph and Combinatoric
Algorithms A study of algorithms for graphs and combinatorics with
special attention to computer implementation and runtime efficiency.
Prerequisites: a programming language, MATH 2103
Textbook: Graph Theory and Its Applications, by Jonathan Gross
and Jay Yellen; CRC Press, 1999
Objectives: This is a course in algorithms for graph and combinatorial
structures and their implementations in a modern computer programming language,
such as C++ or Maple V. Attention to correctness and time and space complexity
for the algorithms will be an integral part of the course.
Grading: Homework problems will be assigned each day, and they will be
discussed in class. Students might
be asked to exhibit their solutions on the chalkboard. Grades will be determined from two
tests, a Midterm Test (50%) and a Final Test (50%).
The grading scale is usually: 90%-100% = A; 80%-89% = B; 70%-79% = C; 60%-60% =
D; below 60% = F.
Attendance and Inclement Weather Policy: There will be no classes on days on
which the University is officially closed. On days when the University is open,
yet traveling is hazardous, use your best judgment on coming to class. If you
miss some required work or assignment because of bona-fide traveling hazards,
then you will be given a reasonable opportunity to make up the missed
work. If you miss one of the
tests, then you must have a bona-fide excuse for having done so in order to
have a make up test administered.
Topics Covered
Appendix and Chapter 1. Introduction to Graph Models: graphs, digraphs
and other basic definitions and concepts
Chapter 2. Structures and Representation
Chapter 3.. Trees
Chapter 4. Spanning Trees
Chapter 5. Connectivity
Chapter 6. Graph Traversals
Chapter 7. Graph Operations
Chapter 9. Planarity of Graphs
Chapter 11. Special Digraphs
Chapter 13. Enumeration
Chapter 14. Algebraic Specification of Graphs and Digraphs