The Department of Computer Science & Engineering
cse@buffalo
CSE 4/572: KNOWLEDGE-BASED ARTIFICIAL INTELLIGENCE - Spring 2002

CSE 472/572:
Knowledge-Based Artificial Intelligence
Spring 2001

SYLLABUS

(Available on the Web at: http://www.cse.buffalo.edu/~rapaport/572/S01/syl.html )

Last Modified: 23 January 2002


Index: Other Relevant Links:
  • Catalog Description
  • CSE 472/572 homepage
  • Prerequisites
  • Directory of Documents
  • Staff
  • Class Meetings
  • Texts
  • Important Dates & Tentative Schedule
  • Reading
  • Attendance, Homeworks, Projects, Exams, Newsgroup
  • Homeworks
  • Projects
  • How to Study
  • Grading
  • Incompletes
  • Academic Integrity
  • Classroom Disruptions

  • CATALOG DESCRIPTION:

    Survey of knowledge-based artificial intelligence - the study of how to program computers, using classical symbolic methods, to behave in ways normally attributed to "intelligence" when observed in humans. Topics chosen from: history, definition, and philosophical foundations of AI; search (representing states and operators, forward, backward, depth-first, breadth-first, uniform cost, A*); propositional logic (syntax, semantics, clause form, rules of inference, resolution); predicate logic (syntax, semantics, rules of inference, substitutions, unification); knowledge representation (semantic networks, inheritance, frames); planning (representing operators, the frame problem); natural-language processing (syntax, semantics, pragmatics, analysis, generation); agents.

    PREREQUISITES:

    STAFF:

    Professor:
    Dr. William J. Rapaport, 214 Bell Hall, 645-3180 x 112, rapaport@cse.buffalo.edu
    Office Hours: TO BE ARRANGED; and by appointment.

    Teaching Assistant:
    Mr.~Nathan Bidwell; OFFICE LOCATION?; 645-????; nbidwell@buffalo.edu
    Office Hours: TO BE ARRANGED and by appointment.

    CLASS MEETINGS:

    CLASS INSTRUCTOR REGIS. NO. DAYS HOURSLOCATION
    LectureRapaport472: 235525
    572: 075463
    MWF10:00 - 10:50 a.m. Natural Sciences 210
    Recitation R2 Bidwell 472: 211492
    572: 033645
    Fri 2:00 - 2:50 p.m.Clemens 113
    Recitation R1 Bidwell 472: 031745
    572: 323306
    Mon 1:00 - 1:50 p.m.Norton 213
    Recitation R3 Bidwell 472: 031632
    572: 225045
    Tue 8:30 - 9:20 a.m.Bell 139

    NOTE: Recitations begin Friday, January 25

    TEXTS:

    IMPORTANT DATES & TENTATIVE SCHEDULE:

    DAYS DATES TOPICS READINGS
      Jan 23 - Feb 6 Intro to course.
    What is AI?
    Agents; Cassie.
    R&N 1 (Intro), 2 (Agents);
    Luger:
    2 (Turing),
    3 (Minsky),
    4 (Newell \& Simon),
    5 (Newell)
    Wed Jan 23 CCS Colloquium
    David Pierce, UB CSE
    "Machine Learning Strategies for Corpus-Based Natural-Language Processing"
    2:00 - 4:00 p.m., 280 Park
    Wed Feb 6 CCS Colloquium
    Deborah K.W. Walters, UB CSE
    TITLE TBA
    2:00 - 4:00 p.m., 280 Park
    Fri, Mon, Tue Jan 25, 28, 29 First meetings of recitations
      Feb 8 - Feb 22 Search R&N:
    3 (search),
    4.1 (best-first),
    4.2 (heuristic search)
    Luger 16 (GPS)
    Mon Feb 18 *** PROJECT 1 (mini-Eliza) DUE ***
    Tue Feb 19 UB CSEGSA Grad Conference
    Wed Feb 20 CCS Colloquium
    Suzanne Stevenson, U/Toronto CS
    TITLE TBA
    2:00 - 4:00 p.m., 280 Park
    Wed Feb 6 CCS Colloquium
    Deborah K.W. Walters, UB CSE
    TITLE TBA
    2:00 - 4:00 p.m., 280 Park
      Feb 25 - Mar 11 Reasoning:
    logic & automated theorem proving
    R&N:
    6 (logical agents),
    7 (FOL),
    9 (inference),
    10.1, 10.2 (unification);
    Luger:
    10 (Hayes, "In defense of logic"),
    14 (Logic Theorist)
    Mon Mar 4 *** PROJECT 2 (search) DUE ***
    Wed Mar 6 CCS Colloquium
    Ernest Lepore, Rutgers/Phil & CogSci
    TITLE TBA
    2:00 - 4:00 p.m., 280 Park
    Wed Mar 13 Review for Mid-Term
    Wed Mar 13 CCS Colloquium
    Ray Jackendoff, Brandeis/Ling & CogSci
    "Reintegrating Generative Linguistics"
    2:00 - 4:00 p.m., 280 Park
    Thu Mar 14 CCS Colloquium
    Ray Jackendoff, Brandeis/Ling & CogSci
    "Possible Stages in the Evolution of the Language Capacity"
    3:00 - 5:00 p.m., 280 Park
    Fri Mar 15 *** MID-TERM EXAM ***
    Mon Mar 18 Review of Mid-Term
      Mar 20 - Apr 10 Knowledge representation;
    SNePS
    R&N:
    8 (KB),
    10.5 (production systems),
    10.6 (semantic networks);
    SNePS readings;
    Luger:
    6 (Minsky, frames),
    7 (Collins & Quillian, semantic networks),
    9 (Schank, conceptual dependency),
    19 (McCarthy, advice taker)
    Fri Mar 22 *** Last day to withdraw with a grade of `R' ***
    Sat-Sun Mar 23 - Mar 30 Spring Break (no classes)
    Wed Apr 10 *** PROJECT 3 (automated reasoning) DUE ***
      Apr 12 - Apr 26 Natural-language understanding R&N:
    22 (communicating agents),
    23 (NLP);
    SNePS readings;
    Luger 8 (Winograd)
    Wed Apr 17 CCS Colloquium
    Susan Lederman, Queens U/Psych & CIS
    TITLE TBA
    2:00 - 4:00 p.m., 280 Park
    Wed Apr 24 CCS Colloquium
    Jeffry Pelletier, U/Alberta Phil & CS
    TITLE TBA
    2:00 - 4:00 p.m., 280 Park
    Fri Apr 26 *** PROJECT 4 (SNePS) DUE ***
      Apr 29 - May 1 Philosophical issues in AI R&N:
    26 (philosophical foundations),
    27 (future of AI);
    Luger:
    2 (Turing),
    29 (Minsky, on various disputes in AI),
    30 (Simon);
    Searle's Chinese-Room Argument
    Fri May 3 Last Class: Review
    Mon, Tue, Fri Apr 29, 30; May 3 Last meetings of recitations
    Sat-Thu May 4 - May 9 Exam Week
    (Assume that our
    FINAL EXAM
    is the afternoon of the last day)
     

    READING:

    1. ReadingCSE 472CSE 572
      R&N sections listed above;
      other assigned readings
      requiredrequired
      Luger sections listed above strongly recommended even more strongly recommended!!
      non-assigned
      sections of R&N
      recommended;
      at least read the intro
      & summary sections
      strongly recommended;
      at least read the intro
      & summary sections

    2. Not all assigned readings will be covered in lecture (in lecture, we shall only cover interesting or hard material, plus occasionally material that is not in the texts), but you are responsible for all assigned material in the texts and lectures.

    3. See "How to Read (a Computer Science Text)".

    ATTENDANCE, HOMEWORKS, PROJECTS, EXAMS, NEWSGROUP:

    1. You will be expected to attend all lectures and recitations, and to complete all readings and assignments on time. There will be weekly homework assignments, 4 programming projects (preferably in Lisp), a mid-term exam, and a final exam (during exam week). Taking both the exams is a necessary condition for passing the course.

    2. All homeworks will be announced in lecture. Therefore, be sure to get a classmate's phone number (for instance, 1 or 2 people sitting next to you in class, whoever they are!) so that you will not miss assignments in the unlikely event that you miss a class. There may be occasional extra assignments and quizzes in labs.

    3. You should subscribe to, and regularly monitor, the newsgroups sunyab.cse.472 and sunyab.cse.572. You may post questions and comments there that are of general interest to the entire class. From time to time, information about homeworks, etc., will be posted to the newsgroups. These newsgroups will be archived in the CSE 472/572 Newsgroup Archive.

    4. Just as you cannot expect to learn how to drive a car by reading about it or by watching other people do it, the same holds true for doing computer science. Do your work on time--this is one course you simply cannot cram for at the last minute, so don't even try! I cannot stress this strongly enough. Homeworks and--especially--projects may be fairly time-consuming, so please consider your other commitments, and plan your time accordingly.

    5. Students should notify Prof. Rapaport within the first two weeks of class if they have a disability which would make it difficult to carry out course work as outlined (requiring note-takers, readers, extended test time).

    HOMEWORKS:

    1. HW assignments will be of the "paper-and-pencil" variety, to be done at home.

    2. The purposes of homeworks are:

      • to give you practice in applying the concepts covered in the course
      • to give you a chance to assess the level of your understanding

    3. There will be approximately 1 HW each week.

    4. Due dates will be announced in lecture when the homework is assigned. HWs will be collected at the start of lecture on the due date. This is so that the homework can be discussed in the class period when it is due.

      If they are turned in after the start of lecture, your grade will be discounted by one full letter grade (e.g., A becomes B, A- becomes B-, etc.).

      If they are turned in after the start of the next lecture, your grade will be discounted by two full letter grades (e.g., A becomes C, A- becomes C-, etc.).

      If you turn in a HW after the start of the class after that, your grade will be discounted by three full letter grades (e.g., A becomes D, etc.).

      No HWs will be accepted after that.

    5. Put your full name, date, and your recitation number (R1, R2, R3) at the top right-hand side of each page, and secure all pages with a staple in the top left-hand corner.

    6. Note: The lowest homework grade will be dropped. You should assume that you will fail to turn in one homework (oversleep, get stuck in traffic, etc.)--that's the one that will be dropped. If you know now that you will regularly be late, see me to make alternative arrangements for turning in your work. Your graded HW will be returned in recitation. Occasional extra assignments or quizzes from lab can be used to replace low HW grades, at your TA's discretion.

    PROJECTS:

    1. Programming Languages, Lisp, and Unix: The prerequisite for this course is knowledge of programming in Common Lisp. However, CSE 202 was not taught last semester, so it is quite possible that many of you do not know any Lisp. Therefore, I will allow all students to use their favorite programming language(s) for the projects.

      CSE 472 students will have accounts on the CSE undergraduate machines; CSE 572 students will have accounts on the Grad Lab machines. If you do not have access to these machines, please let me know as soon as possible! But you are strongly advised to (learn and) use Lisp if you intend to do any research in AI. Moreover, there are good reasons to learn Lisp even if you want to make it in the real world of e-commerce; see:

      1. Paul Graham's Lisp Resources

      2. St. Amant, Robert, & Young, R. Michael (2001), "Common Lisp Resources on the Web", intelligence 12(3): 21-23.

      3. ... and, especially,
        Graham, Paul (2001), "Beating the Averages".

        The implementation of Lisp for this course is Allegro Common Lisp (acl), which runs under the Unix operating system. You will be expected to learn how to use Unix and to learn the idiosyncrasies of Allegro Common Lisp on your own (the Shapiro text should be of help). For more information on Lisp, see Marty Hall's "An Introduction and Tutorial for Common Lisp" website. CIT offers short courses on Unix, etc. To contact CIT:

        in person:216 Computing Center
        by phone:645-3542
        by fax:645-3617
        by email:cit-helpdesk@buffalo.edu
        on the Web:http://wings.buffalo.edu/computing/Help-Desk/
        http://www.cit.buffalo.edu/students.html

      4. Project Policies:

        • For each project, you will be expected to hand in a conference-style paper, typed or printed from a computer file, on 8.5 by 11 inch paper (stapled in the upper left-hand corner, without sprocket holes, and with your own title page), plus a well-documented listing of your program. (Please do not use folders or covers, unless your report is too thick to be stapled.) I strongly suggest that you learn to use Latex and ispell.

          The main product of your work is the paper, not the program! In the paper, you should say what you have done, and say (in English summary, not in programming detail) how you have done it. It should also include annotated examples of your program in action. These should be well chosen to illustrate the range of performance of your program. The examples should not be redundant, nor included merely because they look complicated. Each example should illustrate a particular ability of your program. Nevertheless, the reader will assume that your program does nothing interesting that isn't illustrated!

          The program listing should either be presented as figures throughout the paper, or as an appendix. In either case, the listing is included as documentation for what you say in the paper.

          Thus, each report must consist of the following components:

          • descriptive title (not: "Project 1")

          • your name, the course number (either CSE 472 or CSE 572), your recitation section (R1, R2, or R3), & date due

          • abstract of project (a 1-paragraph summary)

          • description of the project (the body of the paper)

          • list of references (if appropriate)

          • annotated sample runs (could be part of the description of the project)

          • commented code (could be as an appendix)

        • Late policy for projects:

          • Projects must be handed in at the start of lecture on the due date.

          • Projects handed in between the start of lecture on the due date and the start of the next class are 1 day late.

          • Projects handed in between the start of class on the nth day after the due date and the start of the next class are n+1 days late.

          • Each project that is n days late loses n full letter grades. (E.g., an `A' paper that is 1 day late gets a `B'.)

          • Rule of thumb: In general, you are better off handing in an incomplete project - with a report that indicates what programming problems you had and what you left unfinished - than handing in a late project that is complete.

        HOW TO STUDY:

        For general advice on how to study for any course, see my web page,
        "How to Study".

        GRADING:

        All graded work will receive a letter grade: 'A', 'A-', 'B+', 'B', 'B-', 'C+', 'C', 'C-' (472 only), 'D+' (472 only), 'D', or 'F'. Your course grade will be calculated as a weighted average of all letter grades according to the following weights:

        Recitation grade
        (including attendance, homeworks, quizzes, etc.)
        25%
        Projects25%
        Midterm Exam25%
        Final Exam25%
        Total100%

        For further information, see my web document on "Grading Principles"

        Incompletes:

        It is University policy that a grade of Incomplete is to be given only when a small amount of work or a single exam is missed due to circumstances beyond the student's control, and that student is otherwise doing passing work. I will follow this policy strictly! Thus, you should assume that I will not give incompletes :-) Any incompletes that I might give, in a lapse of judgment :-), will have to be made up by the end of the Fall 2001 semester. For more information on Incomplete policies, see the web page, "Incompletes".

        ACADEMIC INTEGRITY:

        While it is acceptable to discuss general approaches with your fellow students, the work you turn in must be your own. It is the policy of this department that any violation of academic integrity will result in an F for the course, that all departmental financial support including teaching assistanceship, research assistanceship, or scholarships be terminated, that notification of this action be placed in the student's confidential departmental record, and that the student be permanently ineligible for future departmental financial support. If you have any problems doing the homeworks or projects, consult the TA or Prof. Rapaport. Please be sure to read the webpage,
        "Academic Integrity: Policies and Procedures", which spells out all the details of this, and related, policies.

        CLASSROOM DISRUPTIONS:

        In large classes (such as this), students have been known to be disruptive, either to the instructor or to fellow students. The university's policies on this topic, both how the instructor should respond and how students should behave, may be found in the document
        "Obstruction or Disruption in the Classroom - Policies"


        William J. Rapaport (rapaport@cse.buffalo.edu)
        file: 572/S01/syl.21ja02.html