Time: MR 2-3:50pm
Location: LOW 3051
Textbook: "Introduction to Graph
Theory", Chartrand & Zhang Supplementary Texts: "Introduction
to Graph
Theory", Douglas B. West; "Introduction to Algorithms", Cormen,
Leisserson, Rivest and Stein
Prerequisites: Either (a
basic discrete math course such as MATH 2800) or ((working knowledge of
sets and logic, equivalence relations and functions, and methods of
proof) and (permission of the instructor)). You may want to go over
Appendices 1-3 in the textbook before the semester. Though not
required, knowledge of algorithm design and analysis techniques can be
helpful.
Grading: 4 homeworks (10% each) , a
midterm (25%) and a final (35%). In addition: Optional for undergrads, required for
graduate students.
Pick a research(ed) problem where graph models and algorithms are
utilized. Write a half-page description of the problem and submit it
before the midterm. At the end of the semester, we will have 15 min
presentations where you will present the problem (motivation and
background), the graph model and important ideas in the solution. You
are required to submit a report (of length more than 1 less than 3
pages) that summarizes these before May
1st. The weight of the
paper+presentation is 10%. When computing your final grade, we will
pick the best four grades out of the four homeworks and the paper. Project assignments are posted here.
Fundamental concepts and
methods of graph theory and its applications
of computing and the social and natural sciences. Topics include graphs
as models, representation of graphs, trees, distances, matchings,
connectivity, flows in networks, graph colorings, Hamiltonian cycles,
traveling salesman problem, planarity. All concepts, methods, and
applications are presented through a
sequence of exercises and problems, many of which are
done with the help of novel software systems for
combinatorial computing. (Cross listed as MATH-4150.
Students cannot obtain credit for both this course and
MATH-4150). Prerequisite: MATH-2800 and CSCI-
1100. Spring term. 4 credit hours.