CS 213:  Assignment #3

Due:  Before class on Tuesday, March 16, 1999

Submission Procedure:

1. Code is to be emailed to the grader bbh4@cornell.edu.
2. Please refer to the newsgroup for filenames specific to this assignment.
3. Please refer to the email you received from the grader for submission details.   Email the grader with questions.

Problem #1:  An IntSet Class  (2.5 hours)

Using the techniques of chapters 10 and 11 write a class to manipulate a set of integers.  The object of this class must be able to hold an arbitrarily large set of integers and must not use storage greater than twice the size of the set at any time.   Since this is a set (not a multiset) there cannot be duplicate entries in the set.   Also, the set should have a data element to store the cardinality of the set.   You must provide methods to do the following operations:

• Constructor with no parameters (empty set).
• Constructor that takes an int array and size and constructs a set with those elements.
• Equality operator (==).
• Overload <, <=, >, >= to set subset and proper subset relations.
• Union, Intersection, Difference and Symmetric Difference operations.  (The second operand of each is a set).
• Method to return the cardinality of the set.
• IsMember(int n) method.
• IsEmpty Method (returns a bool).
• GetCard method that returns the cardinality of the set.
• Assignment operator.
• A copy constructor
• Destructor that cleans up the memory allocated.

All of the data elements of this class should be private.  You must provide public methods to access the data.  You may use whatever algorithms you want to implement the set but you MAY NOT use any of the pre-built data structures from the standard libraries to store the data.

Here is the IntSet class header file I used in my solution.  intset.h

Problem #2:  Solving an 8-Puzzle  (4.0 hours)

An 8-Puzzle is defined as a 3x3 square grid of numbers from 0 to 8, where 0 is interpreted as a blank.  An operation on the puzzle is the process of sliding a numbered square (not 0) into the zero position.  In any given state of the board there can be many as 4 or as few as 2 possible operations.

Given an initial state and a goal state you will write a program that attempts to find the goal state from the initial state.

To do this you must do the following.

• Create a class "State" that stores the state of the board in a 3x3 array of ints and contains a pathcost (distance in moves from the initial state) and a pointer to the state from which this one was derived.
• Implement the following functions:
  • g()  returns the pathcost
  • h(state s) returns the "Manhattan distance" between the state and s.   This distance is defines as the sum over 1-9 of (delta x + delta y) where delta x (or y) is the absolute value of the difference in that dimension.
  • f(state s) = g() + h(s)
  • Implement up, down, left, right which return a pointer to a new state if successful and return this otherwise.
• Create a class List which stores all of the states on the "frontier" of the search space.

The idea here is to create an initial state and insert it into the frontier.  Then at each iteration, select the state "closest" to the goal.  (has the smallest f(goal) value) and delete it from the frontier.  In its place insert into the frontier each new state that is both a transition from the expanded state and is not a the state from which the expanded state was derived (i.e., not the state which undoes the state you are expanding).  The process terminates when you EXPAND the goal state.   Your program should then print the sequence of states from the goal to the initial state.

Hint:  The key idea here is that you must keep each state around even after you expand it so that it can be printed if it is needed in the solution.  Therefore, do not delete states that are removed from the data structure.

You may use whatever code from the libraries you want to solve this problem.

Note:  As assigned, this technique is not guaranteed to find a solution if one exists.  If you however strengthen the expansion criteria so that no state is repeated then it will find a solution if one exists.

Last Updated:  Tuesday, December 14, 2004 12:17:55 PM