Combinatorial and Graph Algorithms
School of Computing, National University of Singapore
(Fall Semester 2003)
CS5234 Course Web-Site
General Information
- Course: CS5234 : Combinatorial and Graph Algorithms
- Instructor: Prof. J. Nievergelt --- (Email: jn@comp.nus.edu.sg)
- Office:
S14 06-10
- Consultation Hours:
by appointment
- Assistant: Braendle Markus --- (Email: braendle@comp.nus.edu.sg)
- Office:
S15 03-10
- Consultation Hours:
by appointment
- Lectures -- Sat, 10:00am -- 12:00nn SR1, S16, Level 3
- Midterm Exam (Closed Book) -- Sat, 11 Oct 2003
- Final Exam (Open Book) -- Sat, 29 Nov 2003, 9-11 am, S16, Level 3, TR5
(notice the Final Exam starts at 9 am)
- Homework Information
- Homework Set 1
- Homework Set 2, due Sep 13
Use the GraphBench to implement an efficient MST algorithm based on an efficient
implementation of the Union-Find data structure.
Animate the algorithm as it operates on a graph and the Union-Find data structure.
(mail your program to Markus Braendle)
- Homework Set 3, due Sep 20
By searching the literature and the web, find out what software is available
(both commercial and freeware) to support the programming and understanding of graph
an other combinatorial problems and algorithms. Select a few of the packages you find and
describe them briefly.
- Homework Set 4, due Oct. 11
Write a project proposal: What problem you intend to investigate, what is the
state of knowledge about this problem, what additional questions and issues
you aim to investigate, what progress you have made so far.
- Homework Set 5 due Oct. 18
- Homework Set 6 due Nov. 1
- Final Exam
- Related Documents
Announcements
-
CS5234 introductory lecture during Week 0 is cancelled because Saturday 9-Aug is a public holiday.
Information on the course will be given out at the beginning of the first lecture on Sat 16-Aug.
Course content
- The broad spectrum of problem and algorithm complexity
- Models of computation
- Mathematics of algorithm analysis
- Typical problems and algorithms
- Problem reduction and coding
- The problem classes P and NP
- NP-complete problems: Satisfiability and others
- Exhaustive and heuristic search
Assessment
- 30% Homework (about one homework set every 2-3 weeks)
- 20% Project (due November 15, 2003)
- 10% Midterm exam
- 40% Final exam
Representative text books
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to algorithms, 2nd Ed., MIT Press 2001
- M.R. Garey and D.S Johnson.: Computers and intractability . A guide to the theory of NP-completeness
- W.H. Freeman & Co., San Francisco, 1979
- A. Nijenhuis, H.S. Wilf: Combinatorial algorithms, Academic Press 1978
- E. M. Reingold, J. Nievergelt, N. Deo: Combinatorial algorithms . Theory and practice, Prentice-Hall, 1977
- E. Horowitz, S. Sahni: Fundamentals of computer algorithms,
Computer Science Press, 1978
Links
CS5234 Announcement Page