where k≥1, and k<i, and k<j, and i ≠ j. Associate a positive integer weight with each pair. Call a subnetwork N' of N netblessed if every two nodes named in pairs of N are blessed in N'. We say the total weight of a subnetwork is the sum of the weights of the pairs in the subnetwork. Write pseudocode for finding a netblessed subnetwork of minimum total weight given a network N. Write the pseudocode using Mathematical structures such as Set and List. For sets, use Φ to denote an empty set, use the symbol \ to denote the operation of removing elements from a set and use the symbol U to denote the operation of adding elements to a set. For example:

Set S = Φ;	// Define and initialize set S to be empty
Set A = {a,b,c,d,e};	// Define and initialize set A to {a,b,c,d,e}
S = A \ {a,b};	// Assign set {c,d,e} to S
S = A U {f,g};	// Assign set {a,b,c,d,e,f,g} to S

For lists use += and + to denote adding one or more elements to a list and -- to denote removing an element from a list. For example:

Pair x = <N1,N2>, y = <N3,N4>;	// Define and initialize Pairs
List L;	// Define a list L, initially empty
L += x + y;	// List L is [<N1,N2>, <N3,N4>]
Pair a = L--;	// Pair a is <N1,N2>
	// and L is now [<N3,N4>]

Explain which data structures would best be used to implement various portions of your pseudocode. Then explain the complexity of the operations in your pseudocode if implemented as you suggest.

An Acceptable Solution:

Set S = Φ;	// S represents the solution (set of Pairs)
List pairs;	// All input pairs will be added to pairs
For each input pair p, pairs += p;	// Build the list of pairs
Sort the list pairs by increasing weight;
Do the following while pairs is not empty:
Pair p = pairs--;	// Unconsidered pair of lowest weight
Let N1 and N2 be nodes of p;
Let S1 be the set of nodes blessed to N1 in S ;
Let S2 be the set of nodes blessed to N2 in S ;
If S1 ≠ S2 then S = S U {p};
Output S;

Data Structures and Types

1. Construct a class called Pairs whose objects hold all information related to pairs. For example:

              class Pair {
                 friend int cmpfn(const void*, const void*);
                 friend ...
                 int node1, node2, weight;  // assume nodes are identified by number
               public:
                 Pair (int n1, int n2, int w) { node1=n1; node2=n2; weight=w; }
              };
   

2. Use an array of pointers to Pair objects for list variable "pairs". For example:

              Pair **pairs = new Pair*[npairs];
   

   An index variable may be used to add Pair objects to the list (the += operation) in O(1) time when inputting data. For example:

              int npairs=0;    // the index variable
              ...
              pairs[npairs++] = new Pair(node1, node2, weight);
   

   The list can then easily be sorted using qsort (built into C/C++) in O(n*log(n)) time. For example:

              int cmpfn (const void *obj1, const void *obj2) {
                 if ((*((Pair**)obj1))->weight < (*((Pair**)obj2))->weight) return -1;
                 if ((*((Pair**)obj1))->weight > (*((Pair**)obj2))->weight) return 1;
                 return 0;
              }
              ...
              qsort(pairs, npairs, sizeof(Pair*), cmpfn);
   

   Removing an element (the -- operation) can be achieved in O(1) time by using an index variable that is incremented each time a Pair object "p" is taken from the list. For example:

              for (int i=0 ; i < npairs ; i++) {   // i is the index variable
                 Pair *p = pairs[i];                  // the -- operation
                 ...
              } 
   

3. Use an array of pointers to Pair objects for variable S. For example:

              Pair **S = new Pair*[npairs];
   

   An index variable may be incremented by 1 to add Pair objects to S in O(1) time. For example:

              int solution_count=0;   // the index variable
              ...
              S[solution_count++] = p;
   

   Displaying the result entails displaying the contents of each Pair object pointed to by an element of S. This is accomplished in O(n) time by means of an index variable. For example:

              for (int i=0 ; i < solution_count ; i++) 
                 cout << S[i]->node1 << " " << S[i]->node2 << " " << S[i]->weight << "\n";
   

4. Create a set of sets of nodes H. Initially each node is in a singleton set of H. The meaning of H on any iteration of the while loop will be that two nodes in the same set of H are blessed in S and no two nodes in different sets of H are not blessed in S. Use inverted trees to represent each set of H. Then sets can be identified in O(log(n)) time and H can be updated in constant time (union of the two sets containing the two nodes). For example:

              class Cell {     // to be used to carry objects in inverted trees
                 friend class H;
                 Cell *parent;
                 void *object;
                 int depth;
   
               public:
                 Cell(void *obj) { object = obj; parent = NULL; depth = 0; }
                 Cell *identify() {
                    Cell *p = this;
                    while (p->parent != NULL) p=p->parent;
                    return p;
                 }
              };
   
              class H {   // for maintaining inverted trees
                 char *filename;
                 Cell **cells;      // to support the inverted tree structure 
   
               public:
                 H (char *filename) {  // assume node data is in a file
                    this->filename = new char[strlen(filename)+1];
                    strcpy(this->filename, filename);
                    cells = NULL;
                 }
   
                 // integers n1 and n2 are used to identify nodes N1 and N2
                 bool redundancy (int n1, int n2) {  // for "if S1 ≠ S2..."
                    return cells[n1]->identify() == cells[n2]->identify();
                 }
   
                 void setunion (int n1, int n2) {  // for "... then S = S U {p};"
                    Cell *root1 = cells[n1]->identify();
                    Cell *root2 = cells[n2]->identify();
      
                    if (root1->depth > root2->depth) {
                       root2->parent = root1;
                       if (root1->depth < root2->depth+1) 
                          root1->depth = root2->depth+1;
                    } else {
                       root1->parent = root2;
                       if (root2->depth < root1->depth+1) 
                          root2->depth = root1->depth+1;
                    }
                 }
   
                 void readData () {   // for "pairs += p;"
                    ...
                    cells = new Cell*[nnodes];
                    for (int i=0 ; i < nnodes ; i++) 
                       cells[i] = new Cell(new int(i));
                    ...
                 }
              };
   

  start:  110101   100111   001100   010101   101010   011011   100100

  bin 0:  001100   101010   100100
  bin 1:  110101   100111   010101   011011

collect:  001100   101010   100100   110101   100111   010101   011011

  bin 0:  001100   100100   110101   010101
  bin 1:  101010   100111   011011

collect:  001100   100100   110101   010101   101010   100111   011011

  bin 0:  101010   011011
  bin 1:  001100   100100   110101   010101   100111

collect:  101010   011011   001100   100100   110101   010101   100111

  bin 0:  100100   110101   010101   100111
  bin 1:  101010   011011   001100

collect:  100100   110101   010101   100111   101010   011011   001100

  bin 0:  100100   100111   101010   001100
  bin 1:  110101   010101   011011

collect:  100100   100111   101010   001100   110101   010101   011011

  bin 0:  001100   010101   011011
  bin 1:  100100   100111   101010   110101

collect:  001100   010101   011011   100100   100111   101010   110101

   void SortOfSorter(int *lst, int a, int b) {
      if (a >= b) return;

      SortOfSorter(lst, a, (a+b)/2);
      SortOfSorter(lst, (a+b)/2+1, b);
      mangle(lst, a, (a+b)/2, b);
   }

The function mangle takes as input an array lst of integers where lst[a]≤lst[a+1]≤ ... ≤lst[(a+b)/2] and lst[(a+b)/2+1]≤lst[(a+b)/2+2]≤ ... ≤lst[b], and rearranges elements of lst so that lst[a]≤lst[a+1]≤ ... ≤lst[b]. Show the contents of lst after each call to mangle by filling in the boxes below (fill in boxes as before).

     9 3 6 1 10 8
     3 9 6 1 10 8
     3 6 9 1 10 8
     3 6 9 1 10 8
     3 6 9 1 8 10
     1 3 6 8 9 10

(a) Stack
(b) Queue
(c) Bipolar List
(d) Binary Tree
(e) Tree
(f) Heap

(a) Stack
(b) Queue
(c) Bipolar List
(d) Array
(e) Heap

(a) Stack
(b) 2-d Array
(c) Array & Linked Lists
(d) Circular Queue
(e) Tree

(a) The maximum number of neighbors for each city is 39.
(b) Finding the shortest path between a pair of cities.
(c) Performing a binary search for a ``least cost'' neighbor.
(d) Neighbors must be considered in reverse order of how they were input.

   3*(543 + 6673 - (56*(72+45)))

We want to write code for finding the value of such expressions. For example, the code should return a value of 1992 for the expression above. Suppose someone provides a function which, when invoked, returns a single symbol or token from an input expression, and the order the items are returned is the order they appear in the input expression, from the left. Suppose a Node class is defined such that objects of this class contain either a -, +, (, ) symbol or a token. Node objects will be used to store tokens and symbols until they are ready to be used in an arithmetic operation. In the example above, the token 3 and the leftmost * must be stored until the parenthesized subexpression to the right of the * is evaluated. Here is the question: the best organization of Node objects is as a

(a) Stack
(b) Queue
(c) Tree
(d) Heap
(e) Array
(f) Circular List

class Cell {                   // Cell objects for a linked list
   friend class Queue;
   void *object;  Cell *next;
   Cell (void *obj);           // Constructor
};

class Queue {
   Cell *tail;           // Circular linked list
public:
   Queue ();             // Initialize tail to NULL
   bool isEmpty();       // true iff the queue contains no objects
   void *dequeue();      // remove an object from the queue and return it
   void enqueue(void*);  // insert an object into the queue
};