Computing Science 671
Title: Algorithms and Hard Problems
Fall Term 2003
ALWAYS UNDER CONSTRUCTION Check this page frequently for Updated Info See the detailed Course Schedule for links to papers referenced in Class. That page is updated frequently. Updated Oct. 28, 2003
|
Nov. 4 --- project proposal.
|
Time: T R 1400 1520
CSC B 41
Professor: Joe Culberson
Purpose
This course will consider some of the foundations of a Science of Algorithms, both empirical and theoretical. As a background course for those requiring it, I will attempt to relate some of the theory of algorithm analysis and complexity issues to empirical and practical results. As a research course, I will try to develop topics and project ideas that could lead to research suitable for a thesis. Prerequisites
Students should have a strong background in algorithms. CMPUT 304 or permission of the instructor. Some familiarity with probability would be most helpful. Course Outline
The following are representative topics; the detailed material presented will vary depending upon class and instructor interests at the time the course is given, as well as available time. The course will be loosely based around a study of SAT, graph coloring, clique finding and other hard problems, leading into subjects such as complexity classes, approximation algorithms, probabilistic and heuristic algorithms, random graph theory, algorithm analysis and adversary arguments. I will likely spend time on a study of hard regions and phase transitions in problem spaces. Interestingly, there is strong tie-in to physics of disordered systems. Detailed Course Schedule and Topics click here
Assignments
Assignment one
Assignment Two
Grading and Work Load
Class participation, including suggestions of ideas and asking of questions may be reflected in your grade. A portion of the course is in the form of seminars and student presentations. In the first two months of lectures I will cover some relevant material on complexity, algorithms, some relevant random graph theory and perhaps a few papers in the area. I will be assuming some familiarity with some of these topics, and this will be more in the form of a review/survey since clearly any one of these is a full term course in itself.
Assignment 1
| 20%
|
| Assignment 2 | 20%
|
| Seminar 1 | 10%
|
| Class Participation (discretionary) | 10%
|
| Written Project | 40%
|
General information on projects and project grading can be found here (click). All assignments and projects are individual work. All assignments and projects must accurately reflect the work of the student submitting them. Use proper citations for any references or assistance you use, including assistance from the instructor and other students. Check out the following web site carefully, in particular the code of student behavior.
Avoiding Plagiarism (click )
Any evidence of cheating will be reported to the dean with consequences possibly as severe as expulsion from the program. If you are unsure whether a certain action is appropriate, ask me first.
Texts
None. On request to be reserved in Cameron library are
- Author: Michael R. Garey and David S. Johnson
Title: Computers and Intractability, A guide to NP-completeness
- Author: Christos H. Papadimitriou
Title: Computational Complexity
- Author: Michael Sipser
Title: Introduction to the Theory of Computation
- Author: Edgar M. palmer
Title: Graphical Evolution: an introduction to the theory of random graphs
Papers
Various papers from the areas of interest (click) A Background Reading List
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. McGraw-Hill. This is currently the CMPUT 204/304 textbook and contains a wealth of information on algorithms.
- Gilles Brassard and Paul Bratley. Algorithmics Theory and Practice . Prentice-Hall, Inc., 1988.
- Joseph~C. Culberson. Graph Coloring Pages
- Michael~R. Garey and David~S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
- Ellis Horowitz and Sartaj Sahni. Fundamentals of Computer Algorithms . Computer Science Press, Inc., 1978.
- Gregory j.~E.~Rawlins. Compared to What? An introduction to the analysis of algorithms Computer Science Press, Inc., 1992.
- Edgar~M. Palmer. Graphical Evolution An Introduction to the Theory of Random Graphs Wiley-Interscience Series. J
- ohn Wiley \& Sons, Inc., 1985.
- Paul~Walton Purdom and Cynthia~A. Brown. The Analysis of Algorithms Holt, Rinehart and Winston, 1985.
- P. R. Cohen Empirical Methods for Artificial Intelligence MIT Press.
Further Reading
The following may also be useful background if you are doing empirical work and for thinking about presentations. Notes
From time to time I may make additional notes available from this page.
Normally, I do NOT give power point or overhead lectures, but
Here is the introductory Lecture