Homework 1 (Summer 2023)

Answer the following prompt in a maximum of 5 pages (excluding references) in JDF format. Any content beyond 5 pages will not be considered for a grade. 5 pages is a maximum, not a target; our recommended per-section lengths intentionally add to less than 5 pages. This length is intentionally set expecting that your submission may include diagrams, drawings, pictures, etc. These should be incorporated into the body of the paper.

If you would like to include additional information beyond the word limit, you may include it in clearly-marked appendices. These materials will not be used in grading your assignment, but they may help you get better feedback from your classmates and grader.

Homework 1 Prompt

Ever since the One Ring was forged by the Dark Lord Sauron, few have been able to resist its seductive power. Gollum was famously corrupted by it, and during his journey to destroy it, even Frodo was tempted by it. One of the few to be able to resist the call of its power was Samwise (Sam) Gamgee.

At one point during their journey to destroy the ring, Frodo, Sam, and Gollum arrive at a river. The river is too wide and deep to swim across, but fortunately, there is a small raft docked on one side. Frodo is too tired from the burden of carrying the ring to drive the raft, however, and Gollum is weak to steer. So, only Sam can steer the raft.

The raft is only large enough for two people at a time; if all three try to ride it, they will sink. So, Sam will have to take Gollum and Frodo across one at a time. However, neither Gollum nor Frodo can be be trusted alone with the One Ring on either side of the river. In fact, neither of them can be trusted alone on the raft with Sam and the ring: its allure is too great, and if given the opportunity, they will simply shove Sam off the side and keep the ring. Therefore, if the either Frodo or Gollum is on the raft with Sam, the ring must be left on one of the riverbanks; if the ring is on the raft, then only Sam can be on the raft with it.

How can Frodo, Sam, Gollum, and the ring get across the river under these conditions? Specifically, neither Frodo nor Gollum can ever be alone with ring on either bank of the river, nor can Frodo or Gollum be on the raft with the ring. If the ring is on the raft, then only Sam can be on the raft with it. Obviously, Sam is also permitted to steer the raft alone. (It is okay, however, for the ring, Sam, and Frodo or Gollum to be on one bank of the river together, so long as on the next move, Sam departs with either the ring or Frodo/Gollum).

First, construct a semantic network representing this problem. This should take approximately half a page, including a figure of two states with a transition between them. Make sure to include all components of the state, and an operator indicating how we transition from one state to another.

Second, apply generate & test to this semantic network in order to solve the problem. In applying generate & test, your generator should be smart enough to only make valid moves (e.g. it will not try to move Gollum and the ring together at once, or make consecutive moves in the same direction across the river without Sam bringing the raft back), but it should not be smart enough to only make moves that result in valid states (e.g. it should still try to move Frodo first, even though that move results in an invalid state, specifically Gollum alone with the ring). Your tester, in turn, should check each generated state to see if (a) it follows the rules, and (b) if it has met the goal. You may decide whether identifying states that have already been visited is the responsibility of the generator or the tester.

Include the entire semantic network that solves this problem. Clearly indicate which states are failed, and why. The semantic network should explore the entire problem space: every state should be either ruled out or have its following states explored. We expect this will fit on one page: you may create a more space-efficient representation if need be. As long as it is legible, you may also hand-write the network and insert it as an image into your paper.

For the purposes of this question, please ignore how foolhardy it would be to leave a ring of such immense power alone on the side of a river, as well as the fact that Frodo would never willingly permit Sam to carry the burden of the ring.

Submission Instructions

Complete your assignment using JDF, then save your submission as a PDF. Assignments should be submitted to the corresponding assignment submission page in Canvas. You should submit a single PDF for this  assignment. This PDF will be ported over to Peer Feedback for peer review by your classmates. If your assignment involves things (like videos, working prototypes, etc.) that cannot be provided in PDF, you should provide them separately (through OneDrive, Google Drive, Dropbox, etc.) and submit a PDF that links to or otherwise describes how to access that material.

This is an individual assignment. All work you submit should be your own. Make sure to cite any sources you reference, and use quotes and in-line citations to mark any direct quotes.

Late work is not accepted without advanced agreement except in cases of medical or family emergencies. In the case of such an emergency, please contact the Dean of Students.

Grading Information

Your assignment will be graded on a 10-point scale coinciding with a rubric designed to mirror the question structure. Make sure to answer every question posted by the prompt. Pay special attention to bolded words and question marks in the question text. For further information on how the assignment is graded, see the rubric in Canvas.

Peer Review

After submission, your assignment will be ported to Peer Feedback for review by your classmates. Grading is not the primary function of this peer review process; the primary function is simply to give you the opportunity to read and comment on your classmates’ ideas, and receive additional feedback on your own. All grades will come from the graders alone. See the course participation policy for full details about how points are awarded for completing peer reviews.