# Homeworks and Solutions

There will be three homeworks and one mini-project, all of which will count towards 50% of the total grade. Since we would like to be able to make solutions available as soon as possible, we will be strict about lateness. The late policy is as follows:

 Days late (not including weekends) Penalty 1 day 10% off 2 days 30% off > 2 days Not accepted

The hand in time will be the beginning of class ie. 1:30 pm. The days described above are 24 hour periods starting from 1:30 pm of the due date. Note that since most homeworks are due on Thursday, the late penalty is 10% for hand in before 1:30 pm Friday and 30% for hand in before 1:30 pm on the following Monday.

## Homework 1

Puzzle files that you can compare your output against to see if it is doing the right thing
The handin directory is:
/afs/andrew/scs/cs/15-381/handin/assn1/your_userid

1. One student asked the following:
About Extra Credit, if we implement shortest path method. Does it mean that in DepthFS and BreadthFS, we must search all the possible routes and keep the shortest one. As result, the answer will be different from the one in puzzle test file. How should I specify in my program?

The homework states: "A more efficient search method also checks for equivalences. In other words, a state may be reached via different paths from the initial state. For extra 5 points credit, ensure that only the shortest path remains alive in the search when two paths from the initial state merge."

I read that to mean checking for shortest path to a given state *as you go* ("remains alive in the search..."), instead of exhaustively searching and then printing out the shortest path.

2. For island driven search, islands go at the end of the command line:
mysearch Island-BFS Sx Sy Gx Gy I1x I1y I2x I2y ... Inx Iny where I1 ... In are the islands.
3. You may not use STL for data structures that you will employ in the assignment. You should implement them yourself.
4. x and y are defined traditionally ie. x is columns and y is rows. This was a mistake in the addendum.
5. The solutions on cyprus.res.cmu.edu are just to show the steps each search will take. You might see that BFS has more steps than DFS - the reason is that what is on there is not the final path but the states DFS considers.
The solutions on there however, were done by hand. There might be a bug somewhere in there so feel free to email cyprus@cmu.edu and let me know.
6. The top left corner of the grid should be (0,0) as stated on the addendum and not (1,1) as stated in the original homework.
7. There is no need to specify the number of rows and columns in the grid file. Remember that the maximum size of a grid is 10 by 10. You will know the actual size of the grid when you read it in.
8. The search should not be exhaustive but it should stop when it finds the path to the goal state.

## Homework 2

There is now an addendum to Homework 2 that clarifies some ambiguities.

There have still been many questions concerning questions 1B and 3, and an error in the assignment.

1A - For number 12, the english language version does not actually match the 1st order logic provided. Ignore it. For your edification, a correct 1st order logic interpretation of the English would be: All(x)[Treefrog(x) => Exists(y)[Car(y) ^ Drives(x,y)]]

1B - When trying to prove that a statement does not have a resolution, any complete proof will do. In addition, I think that some may have misinterpreted my statement that you should "try all possible resolutions" to mean that you should disregard whether resolving your current resolvant with a given clause will actually help in any way. It is sufficient to try only those resolutions which help you; i.e. those which cause the elimination of one of the predicates in the previous resolvant. However, you must show all of _these_ possible resolutions in order for it to be a correct proof. I apologize if this led any to do lots of busy work which wasn't necessary.

3A2 - In this question, think of what you're supposed to do whenever a statement is assigned the value you assigned it in 3A1.

3B - I have stated previously that ? means we do not know which of the other possible values a statement is taking. Note that in this case, there are 3 other possible values, T, F, and @, and ? can mean any of the three.

3B - Also, note that if a variable's value is @, it means that the variable cannot be true all of the time (otherwise, we would say that it has value T), and it cannot be false all of the time. That is, there must be _some_ fluctuation in its value.

## Homework 3

Handed out March 14 due April 4
Optional early hand in March 24, at 4:30, NSH 4517 for 10% extra credit

### Code Updates to Homework 3

(Last updated March 20.)

There was another small problem with one of the code files. If you've already downloaded the tar file, you can get a copy of just the updated file here:

/afs/andrew.cmu.edu/scs/cs/15-381/381/public/util-bayes.c

## Mini Project

Handed out March 23, proposal due April 6, final write up due April 27

## Midterm

Solutions to the midterm are available here

## Final

Solutions to the final are available here

Back