CSCI 6110.601
(Spring 2013)
Applied Combinatorics and
Graph Theory
Prof. N. Adlai A. DePano
Introductory Notes
Welcome to the Spring
'12 offering of CSCI 6110, "Applied Combinatorics and Graph Theory."
This course is a look into the important areas of combinatorics and graph
theory, sources of many indispensable tools in every computer scientist's
"bag of tricks." We will review (and in many cases, introduce)
theoretical results and then apply them to interesting problems in computer
science. We should have occasion to explore the following two platforms:
- GraphBase, a
platform developed by Stanford's Donald Knuth to address two goals:
- "demonstrate the
art of literate programming"; and
- "provide a useful means for comparing combinatorial
algorithms and for evaluating methods of combinatorial computing."
- LINK, a software system
for discrete mathematics (graphs, for example), freely available via the
internet.
The
listed prerequisite for this course (CSCI 4101) implies a prior knowledge of
programming using an advanced high-level programming language (such as Java or
C++), familiarity with data structures and their use, a grasp of computational
models and algorithm analysis (big "O" notation and asymptotic
complexity), and that much-sought but hard-to-define commodity needed for an
advanced course like this -- mathematical maturity.
Catalog Entry
|
CSCI 6110 |
|
|
Applied Combinatorics and Graph Theory |
|
|
Prerequisites: CSCI 4101 or consent of department. A study of combinatorial and graph theoretic techniques for complexity analysis. Includes generating functions, recurrence relations, Polya's theory of counting, planar directed and undirected graphs, and NP-complete problems of combinatorial or graph-theoretic nature. Application of techniques to analysis of algorithms in graph theory, as well as more general problems, such as sorting and searching. |
|
|
3 units min / 3 units max, Lecture |
|
Required Text
|
The required text for this
course is Applied Combinatorics (2nd ed.) by Fred S. Roberts,
Prentice-Hall, 2004 (ISBN 0-13-079603-4). Most of the lecture material will
be based on this text. We will augment material from this book (it is
already quite substantial and rich in content) from more current
sources. In particular, we will experience the pedagogical
technique called "guided discovery" and will use material
developed for this approach by Prof. Kenneth Bogart of |
Course (Coarse?) Outline
We will
attempt to cover the following topics (adjustments may be made as we go along):
1.
Introduction
o
What is Combinatorics?
o
Three Problem Classes
o
History and
Application
2.
Basic Tools of
Combinatorics
o
Basic Counting Rules
o
Intro to Graph Theory
3.
The Counting Problem
o
Generating Functions
o
Recurrence Relations
o
Principle of Inclusoin
and Exclusion
o
Polya Theory of
Counting
4.
The Existence Problem
o
Pigeonhole Principle
o
Experimental Design
o
Coding Theory
o
Existence Problems in
Graph Theory
5.
Combinatorial
Optimization
o
Matching and Covering
o
Optimization with
Graphs and Networks
6.
The Stanford GraphBase
o
Features
o
Experiments
o
Enhancements
7.
LINK
o
Features
o
Experiments
o
Enhancements
Course Format
The
course will be done primarily in two formats -- lecture and groupwork. Student
participation is, obviously, a requirement. Regular problem sets will be
assigned and will be discussed in class in group setting. Students may also be
assigned projects based on the GraphBase and LINK platforms. Some
programming may be required in these projects.
Course Grades
Grades will
be based on a final exam, two in-class tests, and the assigned problem sets.
The weights assigned to these grade components are as follows:
Tests & Exams 60%Problem Sets 40%
Numerical
grades translate to their letter grade counterparts using the following table:
90 - 100 A 80 - 89 B 60 - 79 C 50 - 59 Dbelow 50 F
The last day to drop courses
or resign from the University is listed in the Spring 2013 bulletin as Apr. 1st (no kidding).
Assigned Work Policy
Assigned
work (whether individual or group) are a crucial part of the learning process
in this course. It is by "getting one's hands dirty" that one absorbs
or arrives at the subtle points of theoretical issues. Policies that apply to
assigned work are as follows:
- Individual work will
(typically) be assigned at least a week prior to its due date.
- "Late"
work will be penalized. Every full day that assigned work is late doubles
the penalty of the previous day, starting with one percentage point
deducted on the first day. So in practice, an assignment that is turned in
a week late automatically gets an F, having already incurred a penalty of
-64! However, it is understood that during the course of the semester,
life doesn't always follow a smooth path; therefore, everyone is entitled
to a "free pass," that is, the lowest homework score will
be dropped from the final computation of grades.
- Unintelligible=wrong=no
credit. You are expected to communicate your thoughts clearly.
Submitted homework is expected to be neat, solutions (if required)
appearing in order, and, in general, clearly explained by
accompanying explanations in English. One suggestion is to work out
problems on scratch paper and to recopy them for the final submission.
- Individual
assignments are expected to be your own personal effort.
However, there is very little one can do to prevent you from
"consulting" with each other on homework assignments. In a
controlled setting, this can be beneficial to you. After all, teaching one
another and working together are important skills. However, it is
essential that your homework submissions reflect your own personal
analysis and solution. It is suggested that you try to work on the
problem on your own, and then only when you get stuck should you begin
discussion with your colleagues. The interaction should be two-way -- you
contributing to it as well as profiting from it. When writing the final
submission. try to recreate the arguments on your own. Only when you can
do this can you truly say that you have learned from the group effort.
Needless to say, this joint work policy applies only to homework,
and not to examinations!
Office Hours
The
instructor should normally be available for consultation at his office (MATH
308) during the following times:
Mon, Wed 12:00 noon - 2:00 p.m.; 5:00 - 6:00 p.m.other times by appointment only
You are
encouraged to make use of these periods for your personal profit and for me to
get to know students better. Questions and suggestions are especially welcome
at these times. The instructor may be contacted as well through the following
channels:
Office phone: (504)280-7370, (504)280-6594 (department office); Fax: (504)280-7228URL: http://www.cs.uno.edu/~adlai
e-mail: ndepano@uno.edu or adlaidep@yahoo.com.Cell phone: (504)722-0352
Attendance Policy
Attendance
will be taken regularly. Although not specifically included as one of the
criteria for the final grade, attendance can have an impact on borderline
cases. Good attendance is an indication of the dedication of the student to the
learning enterprise. This will be taken by the instructor into consideration in
such cases.
Academic Dishonesty
As a
matter of policy, we call your attention to the University's rules regarding
academic dishonesty (http://studentaffairs.uno.edu/pdfs/AcademicDishonestyPolicy.pdf)
Academic dishonesty includes cheating, plagiarism, and collusion. In
particular, it includes "the unauthorized collaboration with another
person in preparing an academic exercise" and "submitting as one's
own any academic exercise prepared totally or in part for/by
another." In the event of academic dishonesty, the student will
be assigned a grade of 0 on the exam or exercise, the student will be
informed in writing of the action taken, and a copy of this letter will be sent
to the Assistant Dean for Special Student Service.
Students With Special Needs
Finally, we provide here a link to
the home page of the University's Office of Disability Services (ODS) that
contains valuable information for students with special needs (http://www.ods.uno.edu/).
As expressed therein, The University is committed to providing for the needs of
enrolled or admitted students who have disabilities under Section 504 of the
Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1990
(ADA). In general, University policy calls for reasonable accommodations to be
made for students with documented disabilities on an individualized and
flexible basis. It is the responsibility of students, however, to seek
available assistance at the University and to make their needs known.
Again welcome to the course and I hope you will find it worth your time and
effort.