CMSC 471 - Fall 2008

Course Info

• Course Description and Syllabus
• Lecture Schedule and Assignments
• Course Resources

News

• 11/4: A random TSP problem generator has been added above, as well as two 1000 node problems. My VERY naive hillclimbing method gets a path length of 16000 for the random one after 2 minutes. My VERY naive hillclimbing method gets a path length of 400 for the circular one after 2 minutes. You should be able to do much better.
• 11/3: I made a Tetris problem generator that can make random problems of arbitrary size. Enjoy.
• 10/30: The Light Cycle server has been updated with a bug fix. If two cycles crossed paths perpendicularly, they were not tying, and the game just continued.
• 10/30: Adam's slides are posted.
• 10/25: A sample C client for LC is available. I also added a link to the Java socket class documentation.
• 10/23: The Special Topic Writeup description is available.
• 10/23: Change to Extra Credit 3: The problem has been changed from TSP to weighted min-cut.
• 10/23: Some project updates:
  
  • The Project description document has been updated. There are a few major changes: the lightcycle game is now 30x30 (instead of 100x100), and you will start at (4,4) or (25,25). Your program should be able to handle other starting points and other sizes incase we decide to change this down the road. Also, I mention that it is your responsibility to conform your program to the checker programs provided.
  • The checker programs have been released and should be usable to start testing your work. Please report any bugs you find to Don via email, and they will get fixed immediately.
  • I plan on providing sample socket code for C/C++ and Java. If you have some sample socket code and would like to help me out, please send it to me. Otherwise, it is still your responsibility to figure out sockets (via internet, sample code online, or coming to see me in my office). Sockets really are pretty easy.
• 10/22: Description of Project Planning Assignment (From an email, so a bit out of context):
  This assignment is worth 5% of your grade (considered HW9). Over the course of the semester so far, we have cut out one homework assignment. Therefore, I decided to give you free points (basically) by answering the questions in this Final Project planning form. This assignment is due MONDAY 11/3/08, in class. This is 2 weeks from today.
  
  Attached is a questionnaire that will get you thinking about your final project implementations and make sure you understand everything before it's too late.
  
  Answer as detailed as possible. The more information you give me, the more feedback and advice I can give you. The more advice you get from me, the clearer it is what I am expecting. Also, I will be able to point out what would be extra credit.
  
  Anything you write in terms of the implementation or method is not a contract and you may change your mind later down the road. Please don't just write stuff down that you have no intention of following through with just to get this assignment out of the way.
  
  Only one form has to be filled out by each team. For the yes/no questions, please write out "yes" or "no" (do not circle). If you lie to me and tell me you will remember to cite your sources and you don't, you will get retroactively get a zero on this assignment. Your answers will be subjectively graded on the quality and the depth of your responses.
• 10/16: Email I sent to the class:
  HOMEWORK 5 - TIC TAC TOE:
  * This assignment has been extended to Wednesday before 5:30pm. I figured you guys have enough going on with Monday.
  * Oops. I accidentally deleted the homework 5 prompt when I was writing homework 6. If anyone has printed this homework out (and then scan it), or (even better) has it saved to their computer, please send it to me ASAP. Sorry about this. For those of you that haven't started, this should keep you held off for now: Implement the minimax algorithm for an AI player that plays tic-tac-toe perfectly. \A x [ question(x) -> email-question(x, Don)].
  
  
  HOMEWORK 6 - LOGIC:
  Sorry for not getting this homework out earlier. It is now available at: http://maple.cs.umbc.edu/~don/471/hw6.html. Understanding this homework assignment on your own will ensure you do well on the quiz on Monday. We will review the answers of the homework in class on Monday. Remember, this homework is worth 2.5% of your grade (therefore hw5 + hw6 = 10%). Any questions, email me. This homework is due monday in class (printed out or by hand).
  
  
  LOGIC QUIZ
  You should know the following stuff for the logic quiz on monday:
  * First order logic - R&N 8.1, 8.2, (8.3 helpful)
  * Be able to convert English to FOL
  * Inference -- R&N 9.1, 9.2, 9.5; especially check out the "CNF for FOL" on page 295 and the two examples on 298 and 299; you should be able to convert FOL sentences to CNF and perform resolution to prove by contradiction.
  
  
  
• 10/9: The game playing homework (homework 5) has been extended to be due October 20th (giving two weekends to work on this). The homework value has also been increased: from 5 percent of your grade to 7.5 percent.
• 10/7: The Loebner Prize is happening this weekend. Check out Tim Finin's blog post about the Loebner Prize. Extra Credit 4 is out, and it asks you to give a report on the 2008 competition.
• 10/4: Homework 5 is out and is due 10/15 at 5:29pm. To turn it in, email Niels your work with the following string in the title "471HW5".
• 10/3: To turn in Homework 4, email Niels your work. Make sure your email has the following string in the title: "471HW4". Homework 4 is due at 11:59pm Monday night.
• 10/1: HW4 benchmark: My somewhat naive approach to homework 4 takes anywhere from 200-400 generations to guess a 50-length string, 45-55 generations to guess a 25-length string, 10-12 generations to guess a 10-length string, and 5-6 generatons to guess a 5 length string.
• 10/1: HW4 Clarification: Do not "cheat" (as discussed in class). If you plan on doing anything clever, or wish to change the fundamental way the GA is organized, shoot me an email and I will tell you what to do.
• 10/1: homework 4
• 9/24: Regarding Homework 3: printing information in the expand function is suggested for debugging purposes. Please remove this for your final turn-in project and keep output to a minimum. We don't want to be printing out 200 pages when we grade your assignment.
• 9/22: To turn in Homework 3, email Niels your work. Make sure your email has the following string in the title: "471HW3". Homework 3 is due at 11:59pm Wednesday night.
• 9/22: Extra Credit 3 is out and is due 11/31.
• 9/19: Clarification:
  The expand function is completely domain specific and is basically a description of the state space in itself. For example, (expand-jugs '(3 4 1)) returns ((2 5 1) (1 4 3) (7 0 1) (3 2 3) (4 4 0) (3 5 0))
  You should have two expand functions, one for the jugs problem and one for the missionaries problem.
• 9/19: A major hint has been added to Homework 3.
• 9/18: Extra Credit 2 is out and is due 11/31.
• 9/18: Extra Credit 1 is out and is due 11/31.
• 9/16: Homework 3 is out and is due 9/24.
• 9/16: To turn in Homework 2b, email Niels your work. Make sure your email has the following string in the title: "471HW2". Niels has an email filter set up to match this string.
• 9/11: For Homework 2b, you do not need to do any error checking. For example, you can expect that (fib n) will never be passed anything other than an int.
• 9/11: Please note that on Homework 2b, the functions should take function parameters as input, not standard-in. standard-in should never be used for this homework.
• 9/9: Homework 2b is out and is due 9/17.
• 9/5: The Agents slides has been updated with more material that will be covered on Monday 9/10.
• 9/4: Number 3 in Homework 2a has been clarified.
• 9/2: Homework 2a is out and is due 9/10
• 8/22: Homework 1 is out and is due 9/3

Contact Info and Office Hours

• Don Miner (Instructor)
  • Offices: ITE223 or MAPLE Lab ITE 339
  • Office Hours: Tuesday 11:00am-11:30am (by appointment); Tuesday 1:00pm-4:00pm (by appointment); Wednesday 3:45-5:15 (walk-in)
  • E-mail:


• Niels Kasch (TA)
  • Office: ITE340
  • Office Hours:TuTh 1:00pm-2:30pm
  • E-mail:

Useful Resources

• Software
  • CLISP, a public-domain implementation of Common Lisp that is installed on the department's Unix machines (/usr/local/bin/clisp).
  • The Weka Machine Learning Toolkit, a widely-used open-source ML toolkit built in java. You should download your own copy for either Linux, Windows, or Mac. Since it's java, you can download it to your home directory on the UMBC systems and run it.


• Lisp References
  • Common Lisp manual (Steele 2nd edition)
  • Marty Hall's Common Lisp tutorial at JHU/APL