%META:TOPICINFO{author="IlyaRatner" date="1055183702" format="1.0" version="1.44"}%
---+ Combinatorial Search
Portland State University CS 453/553<br>
Spring 2003
*Instructor*: Bart Massey<br>
*Time*: 18:00-21:40 Tuesdays<br>
*Place*: Cinema 90 (room?)<br>
*CRN*: 64086 (443) / 64091 (543)
This is a _tentative_ syllabus, and will change frequently
and without notice throughout the course.
* <a href="#schedule">Course Schedule</a>
---++ News
* The BlocksWorld course project description is up. Still needs some graphics, though. -- Main.BartMassey - 14 May 2003
* Main.BurkeEllett has put up a really cool page about his LocalSearchSolution to DriveYaNuts. Recommended reading. -- Main.BartMassey - 25 Apr 2003
* The [[CourseBibliography#lecture4][Lecture 4 reading]] is up. [[CompleteTents][Homework 2]] is up. -- Main.BartMassey - 16 Apr 2003
* The [[CourseBibliography#lecture3][Lecture 3 reading]] is up. The [[DriveYaNuts][homework]] schedule has been altered a bit: programs should be ready for PairInspection by this Friday, 11 April. The post-review programs are due before class Tuesday, 15 April. -- Main.BartMassey
* [[DriveYaNuts][Homework 1]] is up. -- Main.BartMassey - 01 Apr 2003
---++ Links
Please add to this list of links to useful information:
* State spaces
* Past offerings:
* [[http://www.cs.pdx.edu/~bart/cs510cs/][Winter 2001]]
* [[http://www.cs.pdx.edu/~bart/cs510ss/][Search and Scheduling: Winter 2000]]
* [[http://www.cs.pdx.edu/~bart/archive/cs510sps][Scheduling, Planning, and Search: Spring 1999]]
* AI Groups
* [[http://www.cirl.uoregon.edu][U. Oregon CIRL]]
* [[http://www.cs.ualberta.edu/~games][U. Alberta Games Group]]
* Papers and Books:
* [[http://cswww.essex.ac.uk/CSP/papers/Tsang-Fcs1993.pdf/][Foundations of Constraint Satisfaction]] -- The complete book by Edward Tsang
* [[http://citeseer.nj.nec.com/harvey95limited.html][Limited Discrepancy Search]] -- Harvey and Ginsberg's paper
---++ Course Communication
This webpage is http://cs543.wiki.cs.pdx.edu. The course
discussion e-mail list is mailto:%EMAILLIST%@%SITEHOST%,
which is also a general discussion list on PSU CS AI issues.
This website is a collaboratively-edited TWiki.TWikiSite.
* You are currently in the %WIKITOOLNAME%.%WEB% web. The color code for this web is a light green background, so you know where you are.
* If you are not familiar with the %WIKITOOLNAME% collaboration tool, please visit %TWIKIWEB%.WelcomeGuest in the %WIKITOOLNAME%.%TWIKIWEB% web first.
* There is also an e-mail discussion [[%EMAILLISTURL%][list]] associated with this website that you may be interested in.
* Advanced functionality is available via the WebMaintenance area.
Students are required to
[[TWiki.TWikiRegistration][register]] for the web, and are
encouraged to modify and add to these pages as appropriate.
---++ About the Course
The catalog says: "Explores methods for the solution of
constraint satisfaction and related problems using search
techniques, in the context of real-world problems such as
resource-bounded scheduling, enterprise planning, classical
planning, and one- and two-player games. Emphasis is on
coding projects, and on reading and reporting on selected literature."
Instruction is through a series of lectures, readings, and
web-based materials. Homework will consists of a set of
programming projects as well as some writing.
Prerequisites for the course are: algorithms and data
structures courses; a discrete math course; and the ability
to program fluently in some reasonably efficient and clear
programming language such as C, C++, Curry, Java, ML,
Nickle, Prolog, Scheme, Smalltalk, etc. (If you are in
doubt about the appropriateness of some language for this
course, please consult the instructor.)
---++ Course Goals
The successful student will be able to:
* Articulate the notion of state space and
the role of state spaces in computer science.
* Use the vocabulary of _class_, _problem_, _instance_, and
_solution_ in discussing computational theory.
* Determine whether a given decision problem is in
P, in NP, and/or NP hard.
* Use understanding of combinatorial state spaces to
design or select search techniques for solving
instances of combinatorial problems.
* Determine whether a problem is
amenable to local search, complete search, or hybrid
techniques.
* Select knowledgably from a wide variety of
combinatorial search
techniques.
* Use boolean constraint satisfaction (SAT) instances as
a theoretical tool for analysis and as an intermediate
form for applying existing SAT solvers to NP-hard
problems.
* Implement combinatorial search algorithms efficiently and cleanly
in a reasonable programming language.
* Cite relevant combinatorial search literature.
---++ Coursework
Coursework is of several kinds. A gradated series of
homework projects applying combinatorial search to
interesting problems will be 40% of course grade. A group
writing assignment constructing course web pages will be 20%
of course grade. A final larger course project will be 30%
of course grade. 10% of course grade will be at the
discretion of the instructor, covering attendance,
participation, and attitude.
---+++ Writing Assignment
Each week, a different group of students will be required to
take detailed course notes, and to use these notes in
collaboration with the instructor to design an entry for
http://wikipedia.com documenting the week's materials. The
instructor is unaware of any reasonable and available course
text on the subject of combinatorial search: in addition to
encouraging students to deeper exploration, this assignment
should effectively create such a text.
---+++ Course Project
The course project will involve designing, deploying, and
evaluating a large combinatorial search application. Wide
latitude is given in selection of projects: a [[BlocksWorld]["standard" project]] has been provided for those who choose not to select
their own.
---++ <a name="hwsub">Homework</a>
The homework consists mainly of programming assignments. The programming can be done in any reasonably clear and efficient programming language: many students choose C, C++, or Java, but [[http://nickle.org][Nickle]], ML, Scheme, Prolog, Smalltalk, or the like may be a better choice in many ways. For unusual languages (i.e. those not installed by default in the Linux Laboratory) please contact me in advance for approval and so that I can get set up to run programs.
In general, I will ask that programs read from standard input and write to standard output, and that the programs require no options or other configuration. Please take these requirements, and all of the requirements in each assignment, seriously. Further requirements and recommendations may be found in the CodeStyleGuide. When doing search experiments on departmental computers, please follow the departmental SafetyGuidelines.
The submission should include
* all source code for the program,
* any instructions needed to successfully build and run the program (including a Makefile if at all appropriate) on a box in the Linux Laboratory,
* and the writeup.
(All re-submissions should include all of these materials as well, even if they have not changed.)
The writeup is as important as the program. It should contain a description of the algorithms and design of the program, a discussion of the program's performance and notes on any issues of interest that arose during the homework. In general, the writeup should look like a scientific document. (There is a nice guide to technical writing at [[http://www.cs.columbia.edu/~hgs/etc/writing-style.html][Columbia University]]: you may find it useful.) Plain ASCII text is the preferred format for writeups: if you must use some fancier format, HTML or PDF are acceptable. Proprietary formats (e.g. Word or Framemaker documents) are *not* acceptable and will be discarded unread.
The submission should be bundled into a tar or zip archive, including a README describing its components. The archive should be e-mailed to mailto:cs543-homework@ai.cs.pdx.edu as an attachment. The subject of the e-mail should be "CS 443/543 HW #", where "#" is the homework number.
Homeworks:
1. DriveYaNuts, due 11 April 2003
1. CompleteTents, due 6 May 2003
1. LocalTents, due 13 May 2003
---++ Academic Honesty
Normal Student Conduct Code, Departmental, and University
guidelines apply. Every student is encouraged to work with
other students and seek outside assistance in completing the
course. However, it is absolutely mandatory that any
assistance received (coding help, algorithmic help, ideas,
writeup, references, etc.) be acknowledged explicitly and
fully by the student. Failure to do so is plagiarism, the
lowest form of academic conduct, and will result in a zero
on the assignment: the instructor will do everything in his
power to end the academic career of a plagiarist.
If you have doubts about the propriety of some course of
academic conduct, please consult the instructor: he will be
happy to advise.
---++ <a name="schedule">Schedule</a>
This is a _tentative_ schedule, and will change frequently
and without notice throughout the course.
|#| Date | Topics | Readings | Notes | Homework |
|1| 2003/4/1|[[SearchPhilosophy][Philosophy]] | |[[http://www.wikipedia.org/wiki/Combinatorial_search][n1]] | [[DriveYaNuts][1]](out) |
|2| 2003/4/8|[[SearchCSPs][CSPs]] | [[CourseBibliography#lecture2][*]] |[[http://ai.cs.pdx.edu/cgi-bin/twiki/view/CS543/SecondClassNotes][n2]]| |
|3| 2003/4/15|[[CompleteSearch][Complete Search]] | [[CourseBibliography#lecture3][*]] |[[ThirdClassNotes][n3]]| [[DriveYaNuts][1]](due 4/11), [[CompleteTents][2]](out) |
|4| 2003/4/22|[[LocalSearch][Local Search]] | [[CourseBibliography#lecture4][*]] |[[FourthClassNotes][n4]] | |
|5| 2003/4/29|[[SchedulingSearch][Scheduling]] | [[CourseBibliography#lecture5][*]] |[[FifthClassNotes][n5]] | [[LocalTents][3]](out) |
|6| 2003/5/6|[[PathfindingSearch][Pathfinding Search]] | [[CourseBibliography#lecture6][*]] | [[SixthClassNotes][n6]]| [[CompleteTents][2]](due 5/6) |
|7| 2003/5/13|[[PlanningSearch][Planning]] | [[CourseBibliography#lecture7][*]] |[[SeventhClassNotes][n7]] | [[LocalTents][3]](due 5/13), [[BlocksWorld][prj*]] |
|8| 2003/5/20|[[AdversarySearch][Adversary Search]] | [[CourseBibliography#lecture8][*]] |[[EigthClassNotes][n8]] | |
|9| 2003/5/27|[[SearchProof][Pruning Without Search]] | [[CourseBibliography#lecture9][*]] |[[NinthClassNotes][n9]] | |
|10| 2003/6/3|[[SearchWrapup][Conclusions and Frontiers]] | |[[TenthClassNotes][n10]] | |
%META:FILEATTACHMENT{name="EigthClassNotes" attr="" comment="Class 8" date="1054046617" path="C:\Documents and Settings\djensen\My Documents\CS443\EigthClassNotes" size="5397" user="DeronJensen" version="1.1"}%