Sunday, September 30, 2007

Extension on homework 2: Due now on Wednesday Oct 3rd

Folks
 
 Since I have been away on last Monday and didn't hold office hours,
I will extend the deadline for hw2 submission to Wednesday's class.

This will give time for people who had questions on homework 2 and couldn't
get me during office hours

(I realize  I am grasping at the straws here, considering how student-less and maytag-repairman-like my
office hours are even at the best of circumstances.. nevertheless..)

Rao

there is no typo/erro in the pattern database question..

Gavin's comments notwithstanding, there are no typos in the pattern database
question. You should do it the way it is given

(by the way, it is fine for h*(n) to be \infinity. You can still talk about admissiblity and
relative informedness of h1(n) and h2(n) ).

rao

Thursday, September 20, 2007

[cse 471] Instructions for your project report --plus-- Announcements on submission

Hello all,
 
I hope everybody is doing great with project-1!  I have opened a link for it under the "Assignments" section in blackboard for submitting your code part of this project. Please submit only your "CODE" (name the files as firstname_lastname.lisp) there.
 
You have to submit a hardcopy of your project report in the class next wednesday. The report should contain your code, sample runs for input cases, statistics collected (as required in the project tasks) and your analysis on the results etc. Please note that the purpose of the project (and a report) is not to test your LISP/programming skills, but to make you understand, analyze and explore the various methods you study in the course. So, your report is expected to contain good *analysis* and *observations*, and not just the code with outputs.
 
Here are some general suggestions for preparing your report:

1. Write the report clearly so that I can find out what you did for each task. A brief description of your implementation would be appreciated. 
2. Give the output of some sample test calls to show that you code has no bugs.
3. Given the output, do some thorough analysis. A comparison of various methods used, the effects of varying parameters (if any) on the experimental results etc would be necessary.
4. You can plot some figures to show the difference of different methods, to check whether it is consistent with the theoretical result (like the time complexity, space complexity, order of increase etc.) What are the conclusions? Does it make sense and why?
5. Did you encounter any problem during the project? Any unexpected results? Are there possible ways you tried or suggest to get better solutions?

Please let me know if you have any questions.
 
Thanks,
Aravind
 

Wednesday, September 19, 2007

The solutions to homework 1 are posted on the homepage (see the homeworks page)

Homework 2--CSP and Pattern database questions added and socket closed. Due date: October 1st.

[cse 471] grading scheme for homework-1

Hello all,
 
Grade distribution for homework-1:
 
Grad: 43.5  (mean) 50 (H) 36 (L)
UG: 43.8  (mean) 50 (H) 29 (L)
 
And, the grading scheme is as follows: (total is for 50 points + 5 e.c)
 
1.  8
2.  2+2+2
3.  4
4.  5
5. 
    5.i     1
    5.ii    1
    5.iii    2 + 2
 
     5.2   (1+1+2+2) = 6  
 
6.  5
7.
    7.1  2
    7.2 
          7.2.1  2
          7.2.2  3
          7.2.3  3
 
Extra credit:  5
 
I have written comments as to what is wrong with your solution in some cases. However, the complete solutions will be posted shortly. Please refer to them.
 
You can meet me during my office hours if you have any questions with the evaluation.
 
Thanks,
Aravind

Monday, September 17, 2007

[CSP Thinking cap]

Here are some things you can think of:
 
1. Have you played Sudoku--if so, can you illustate how what you do in sudoku wind up being equivalent to the various CSP heuristics?
 
 
2. Suppose we have three CSP problems:
 
 1.  20 variables and 5 (binary) constraints.
 2.  40 variables and 200 (binary) constraints
 3. 200 variables and 199,000 (binary) constraints
 
Which of the CSP problems above do you think will be easiest to solve? Which will be the hardest?
(assume that all constraints have about the same tightness).
 
3. For the CSP search algorithms we discussed in the class, does it matter whether the constraints are represented as (a) legal partial assignments (b) illegal partial assignments (c) pieces of code that take a partial assignment and return a boolean saying Yes/No.
 
 
4. A subclass S of a problem class P is considered canonical if every instance of P can be "compiled down" to a *finite* instance of S. For example, the class of "programs written in Intel m/c language" is a canonical class of all programs. (Instead of "finite" we might also consider compilations that are only *polynomially larger*--but ignore it for now).
 
 4.1 (easy) Argue that SAT (i.e., boolean stisfiability problems) are a canonical class of CSP problems.
 
 4.2 (harder) Argue that *Binary CSP* problems are a canonical class of CSP problems
 
 
5. (If you know Linear programming and Integer Programming). Argue that every 0-1 integer programming problem with constant objective function can be compiled down to CSP.
 
 
Rao
 
 
 

CSP Applet that you can play with..




Try
http://www.cs.ubc.ca/labs/lci/CIspace/Version4/Constraint/index.html

for a java applet that allows you to specify CSPs and solve them.

(The link http://www.cs.ubc.ca/labs/lci/CIspace/index.html  also has a variety of applets for search, logic etc etc that you may enjoy)

Rao

Homework 2 socket opened--qns on A* search added


Thursday, September 13, 2007

Re: Recitation session for project-I today (reminder) [cse 471/598]

(for students who have a time clash during proj-1 recitation session today.. )..
 
I would be in Open lab (214 BYENG) from 5 PM today evening. We can sit together and go through the recitation slides, plus discuss your questions/doubts on proj-1. 
 
Thanks,
Aravind
 
Dear Aravind Krishna :
 
I have a class between 3PM and 4PM today..
 
Is it possible to have that recitation for me or other people who are not available between 3 and 4 after 4:30PM again if you do not mind?
 
Thank you for your time.
 
 
 

 
On 9/13/07, Aravind Krishna <Aravind.Kalavagattu@asu.edu > wrote:
Hi everyone,
 
  I will be holding a recitation session for project-1 during my office hours today, i.e., 3 to 4 PM. The venue is room no. 455 BYENG bldg 4th floor. (.. the conference room right opposite to the elevators)
 
Cheers,
Aravind


Recitation session for project-I today (reminder) [cse 471/598]

Hi everyone,
 
  I will be holding a recitation session for project-1 during my office hours today, i.e., 3 to 4 PM. The venue is room no. 455 BYENG bldg 4th floor. (.. the conference room right opposite to the elevators)
 
Cheers,
Aravind

Wednesday, September 12, 2007

[Thinking cap topic for 9/12]: Pattern databases etc.

Hold forth on these... I am especially interested in seeing blog comments from 471 students..

First a diversion: Check out the following mail from earlier years on the history of n-puzzle problems and how these grabbed popular imagination at one time..
http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00023.html

Now the thinking-cap questions

0. Should h*(n) be zero for *all* goal nodes or only optimal goal nodes?


1. We argued that computing the optimal cost for getting each tile into its position and summing the distances will not give an admissible heuristic. However, Manhattan distance is doing the same thing--except in an abstract space. How come it is admissible?

1.1*****ADDED NEW (By EDITING BLOG POST)**********
[INTERACTIONS and Heuristics]

The reason we said we can't just add up true costs of putting individual tiles in the right position
is that the tiles have interactions. There are really *two* kinds of interactions

Positive interactions--getting one tile to its position makes it easier to get another tile to its position

Negative interactions--getting one tile to its position makes it *harder* to get another tile to its position.

How do positive and negative interactions affect the informedness and admissibility of the heuristics that *ignore* them?



2. The pattern we considered in the class was left and bottom edges. If instead we considerd the two diagonals of the goal position, will the resulting pattern database heuristic make sense?

3. Suppose there is a new 24-puzzle competition. You are all supposed to use the same hardware (computer memory etc) to solve
test instances optimally. Whoever solves the problem in the shortest time gets a prize (a "platinum-coated 24-puzzle, suitable for framing").
Before the competition starts however, everyone is given about 3 hours of time on the computer for any pre-computation. You want to use the pattern database heuristics, but you know that you don't quite have all the time needed to compute the pattern heuristic for all the possible states in the three hours. Is there any way you can use the precomputation time gainfully?


4. In the problem above, suppose for each team, they allowed two computers during pre-computation time. This obviously suggests the idea that you can compute two different pattern databases (say the left and bottom edges in one, and the right and top edges in the other). Can you imagine a way of using both the databases to improve search further?




--------------

Monday, September 10, 2007

[cse471/598] clarification on using blackboard (myasu) for the course

Hi all,
 
You might want to note that blackboard portal would be used *ONLY* for project submissions (and moreover, only your code part of the projects goes in there). This is why there would not be any separate links opened for other exercises like homeworks and exams, on the blackboard. (so avoid relying on the links in blackboard as pointers to see what are the current active exercises & their deadlines)
 
You must keep checking the course website regularly for announcements and *submission deadlines* for the exercises.
 
Thanks,
Aravind

[cse471/598] Announcements (LISP recitation for proj1 -- plus -- grade distribution of assgn-0 )

Hi all,
 
I hope you're all progressing well with LISP project-1 on search algorithms. I will hold a recitation session for project-1 during my office hours on thursday. (I will send you a reminder again with more details). You can also always email me your doubts / schedule an appointment separately in case you can't meet me during my office hours.
 
Please find the statistics of assignment-0 (LISP refresher) grading below:
 
Total:  Required (30 points)  + Extra Credit {e.c} (13 points) 
 
Grade distribution:  (most of you did great & scored full in the required portion)
 
UG:   
Highest was ( 30 + 13 e.c ) :  Least  was 22  :  Mean was 28.4
 
Grad:
Highest was (30 + 12 e.c ) :  Least was 24  : Mean was 29.2 
 
And the detailed evaluation scheme for each question is as follows:
 
1.  3
 2.
     2.1  2
     2.2  2
     2.3  2
          ( 1 point extra credit for implementing "middle" in linear time )
 3.  5
 4.  5
 5.
   5.a   2
   5.b   2
   5.c   2
   5.d   2 (e.c)
 6. 5
 7. 5  (e.c)
 8. 5  (e.c)
 
Let me know if you have any questions.
 
Thanks,
Aravind

[Thinking Cap]: Optimal Sub-structure;

 
 
 
1. We talked about the fact that all our search algorithms use "optimal-substructure" property.  Because of this we never have to maintain more than the "current best path" to a node. Give an example of a scenario where optimal substructure doesn't hold--and argue that in that case, (1) the markov property also doesn't hold ( i.e., where you can go from a state depends not just on the state, but how you got there) and (2) argue that you will need to maintain more than the best path to the intermediate nodes so as to be able to find the optimal path to the goal node.
 
1.1. In your example above, see if you can change the definition of "State" so that the optimal sub-structure property holds again (and so does markov property).
 
Rao
 

*Important*: Late homework/project acceptance policy..

I have already started getting late submission requests.

To be fair to everyone as well as allow for human fallibility, here is the procedure we will follow.

Each of you will be allowed

* one extension for the homeworks and
* one extension for the projects.

The  extension will allow you to submit the homework/project within two days from the deadline without penality
(if the due date is Monday, you will do the late submission by Wed class; if it is Wed, you come and deliver it
by Friday 10:40 to the CS office).

All you need to do is to send a mail to the TA or me *by the day of original due date* saying that
you plan to exercise that option (so we will wait  before posting solutions).

No substitutions or negotiations; and the extensions are non-transferable..

regards
Rao



Sunday, September 9, 2007

New thinking cap question(s)



1. Your friend was doing an iterative deepening uniform cost search on a graph representing the
distances between various landmarks in town (presumably to find optimal paths between any pair of
landmarks). Originally he had a graph where all the road distances were measured in multiples of integral
miles (i.e. each edge cost was an integer). After a while, your friend decided to represent the distances
more accurately and so went and found all distances correct to four decimal places. All of a sudden he found that
the efficiency of his search worsened quite dramatically. He was perplexed at this since the underlying graph
topology was the same and distances were just more accurate. Can you explain what happened?

2. What, if any,  are the differences between uniform cost search algorithm as we described in the class and "Dijkstra's algorithm" on
graphs that you have probably learned in CSE310?
 
 
Rao

 

Saturday, September 8, 2007

Question 7.2.1

"7.2.1. Argue that this search is likely to do better on the average than the best search you picked in 2.1"

Is it safe to assume that the "2.1" above is 7.1? Likewise, for 7.2.3, should it be 7.2, rather than 2.2?

Tuesday, September 4, 2007

Agenda and readings for tomorrow.

TOmorrow we will complete the discussion of IDDFS, revisit answers to the blog questions, and shift to
discussing uniform cost search and A* search. 

Assuming you already read 3.1 to 3.5, you should go ahead and read 4.1 and 4.2 (in the textbook)

rao