Purpose of This Assignment

This assignment exercises your knowledge of arrays and functions. It also gives you experience implementing a module that is not an application but is intended to be part of an application.

It is important for you to follow the design described here. Do not make up your own algorithm. Implement exactly the functions that are indicated. Keep the parameter order as shown here. If you change the parameter order, your module will not compile correctly with my tester.

Initially, this will look difficult. In reality, it is very short and simple. Keep it simple.

Background

An equivalence relation is a relation with the following properties for all x, y and z.

is reflexive: x x.

is symmetric: If x y then y x.

is transitive: If x y and y z then x z.

An equivalence relation on a set always partitions the set into equivalence classes, where members of a given equivalence class are equivalent to one another and members of different equivalence classes are not equivalent. For example, suppose that is a relation on set {1, 2, 3, 4, 5, 6} with equivalence classes {1, 3, 4}, {2, 6}, {5}. Then 1 4 and 2 6 but 2 is not equivalent to 3.

The Assignment

Your goal for this assignment is to create a tool that manages an equivalence relation that can be changed in a specific way by the program. For this assignment, the equivalence relation is always over a set of integers {1, 2, 3, , n} for some positive integer n.

This tool is not a complete program. It is intended to be part of a larger program. It must not have a main function.

Interface

The interface tells exactly what this module provides for other modules to use. Other modules must not use anything that is not described here.

For this assignment, an equivalence relation has type ER. A module that uses this tool can create an equivalence relation called e by saying

 ER R = newER(n); 

where n is a positive integer. Initially, each number is in its own equivalence class; the equivalence classes are {1}, {2}, , {n}. There are two operations that can be performed.

equivalent(R, x, y) returns a boolean value: true if x and y are currently in the same equivalence class in equivalence relation R, and false otherwise.

merge(R, x, y) modifies equivalence relation R by making x and y equivalent. It combines the equivalence class that contains x with the equivalence class that contains y. The merge function does not return an answer.

Example

For example, suppose that n = 7. The following shows a sequence of operations and shows the equivalence classes after each merge operation.

Step	Result
ER R = newER(7)	R = {1} {2} {3} {4} {5} {6} {7}
merge(R, 1, 5)	R = {1, 5} {2} {3} {4} {6} {7}
merge(R, 2, 7)	R = {1, 5} {2, 7} {3} {4} {6}
equivalent(R, 1, 5)	yields true
equivalent(R, 1, 7)	yields false
merge(R, 5, 7)	R = {1, 2, 5, 7} {3} {4} {6}
equivalent(R, 2, 5)	yields true
equivalent(R, 2, 3) yields false	yields false
merge(R, 2, 3)	R = {1, 2, 3, 5, 7} {4} {6}
equivalent(R, 3, 7)	yields true
equivalent(R, 4, 7)	yields false
merge(R, 4, 6)	R = {1, 2, 3, 5, 7} {4, 6}
merge(R, 2, 3)	R = {1, 2, 3, 5, 7} {4, 6}

As you can see from the last step, it is allowed to merge two values that are already equivalent. That should cause no change.

An Algorithm for Implementing an Equivalence Manager

You will not store the equivalence classes directly. Instead, you will store them implicitly, using the following ideas.You are required to implement an equivalence manager in this way. You will receive no credit for a module that does not follow this algorithm.

Each equivalence class has a leader, which is one of the members of that equivalence class. You will create a function leader(R, x) that returns the current leader of the equivalence class that contains x in equivalence relation R.

Two values are equivalent if they have the same leader.

There is another idea that is similar to a leader, but not exactly the same. Each value has a boss, which is a value in its equivalence class. Let's write boss[x] for x's boss.

If x is the leader of its equivalence class then boss[x] = x, indicating that x is its own boss.

If x is not the leader of its equivalence class then boss[x] x and boss[x] is closer to the leader, in the following sense. If you look at the values x, boss[x], boss[boss[x]], boss[boss[boss[x]]], then you will eventually encounter x's leader.

Details on the algorithm

Use an array to store the bosses. Declaration

 typedef int* ER; 

defines type ER to be the same as int*. Write the following functions.

newER(n) returns an array of n+1 integers. Allocate the array in the heap. This array will be used to store the bosses. If R has type ER then R[x] is x's boss. (If you prefer, you can call an equivalence relation boss. Then boss[x] is x's boss.)

In C++, arrays start at index 0. You will use indices 1, n, so you need to allocate n+1 slots. (Index 0 will not be used.)

Initialize the array so that each value is a leader of its own equivalence class. That is, boss[x] = x for x = 1, , n.

leader(R, x) returns the leader of x in equivalence relation R. To compute x's leader, just follow the bosses up to the leader. You are required to use this function any time you want to find the leader of a value.

equivalent(R, x, y) returns true if x and y are currently in the same equivalence class in equivalence relation R. (They are in the same equivalence class if they have the same leader.)

merge(R, x, y) merges the equivalence classes of x and y in R as follows. First, it finds the leaders x and y of xand y. If x and y are different (so x and y are not already in the same equivalence class) then y becomes the new boss of x and y becomes the leader of the combined equivalence class.

destroyER(R) deallocates R.

showER(R, n) prints the entire contents of array R (of size n) in a readable form for debugging. Be sure that showER shows both k and k's boss, for each k.

Important note.

It is crucial that your program never change the boss of a value that is not a leader. That is, if you are not sure that x is a leader, do not change R[x]. Pay attention to this!

In the past, many students have ignored this requirement. Needless to say, their modules did not work and their scores were low.

A Refinement Plan and Additional Requirements

Development plan

1. Create a directory (folder) to hold assignment 4. Put all of the files for this assignment in that directory.

2. Create a file called equiv.cpp. Copy and paste the template into it. Edit the file. Add your name and the assignment number. If you will use tabs, say how far apart the tab stops are.

3. Write a comment telling what this module will provide when it is finished.

4. Create a file called equiv.h. Copy the following into equiv.h, then edit it to add your name.

// CSCI 2530 // Assignment: 3 // Author: *** // File: equiv.h // Tab stops: none // These #ifndef and #define lines make it so that, if this file is // read more than once by the compiler, its body is skipped on all // but the first time it is read. #ifndef EQUIV_H #define EQUIV_H // An equivalence relation is an array of integers. // So ER abbreviates int*. typedef int* ER; // Public functions ER newER (const int n); void destroyER (ER R); bool equivalent (ER R, const int x, const int y); void merge (ER R, const int x, const int y); // The following is advertised here solely for debugging. These must // only be used for debugging. void showER(const ER R, const int n); int leader(ER R, const int x); #endif 

Note. In the types of equivalent and leader, parameter R is not marked const, even though it seems to make sense to do that. The reason is that improvements that can be done for extra credit need to make changes to R, even in equivalent and leader.

5. In equiv.cpp, write a contract, then an implementation, of the newER function. Notice that newER(n) returns an equivalence relation that can handle set {1, 2, , n}. Say that. Don't say that it returns an array.

6. In equiv.cpp, write a contract, then an implementation, of the showER function. Pay attention to what showER is supposed to do.

7. Create file testequiv.cpp. Add a main function to it, and make main create a new ER (using newER) and show that ER (using showER). Testequiv.cpp should contain

#include "equiv.h" 

to allow it to use what is described in equiv.h.

8. In equiv.cpp, write a contract, then an implementation, of the leader function. Modify testequiv.cpp so that it tests leader. Note that, at this point, each number will be its own leader. Run testequiv.cpp.

9. In equiv.cpp, write a contract, then an implementation, of the merge function. Modify testequiv.cpp so that it performs some merge operations and shows the equivalence relation after each merge. Run testequiv.cpp. Check the results.

10. In equiv.cpp, write a contract, then an implementation, of the equivalent function. Modify testequiv.cpp so that it shows equivalences after merge operations. Run testequiv.cpp. Check the results.

11. In equiv.cpp, write a contract, then an implementation, of the destroyER function. Modify testequiv.cpp so that it destroys an ER array. Run testequiv.cpp. Check the results.

12. Check your program. Proofread your contracts. Look for spelling and grammatical errors. Ensure that you have paid attention to the issues to be aware of.

13. Submit your work.