Problem 1.
I will lead you through a couple of steps for solving the following problem:
Given a collection of integers (some of which may be negative),
find a subset that adds up to exactly 0. For example, the collection of integers {2, -3, 11, -4, 2, 1}
contains subsets {-3, 2, 1}, {2, -4, 2}, etc. that add up to exactly 0.
More precisely, you are given a collection of integers stored in an int[] and
have to design and code a boolean method called subsetSum that returns
true if there is a subset that adds up to 0 and returns false otherwise.
This problem, like TSP, is a notoriously hard problem to solve efficiently. So, like in the case of TSP, we will try a "brute force" solution that generates all possible subsets of the collection and checks each subset for the property of adding up to 0. We will use a boolean array to track the current subset being generated. The boolean array will have the same size as the array that stores the collection. For example, if subset is the name of our boolean array, then subset[i] indicates if the ith element from the collection is in the subset or not. In the above example, the subset {-3, 2, 1} will be represented by the subset array:
false true false false true trueOur first task is to recursively generate all subsets of the given collection. One way to do this is expressed in the following simple pseudocode:
Place the first element of the collection into the subset being generated; Generate the rest of the subset; Do not place the first element of the collection into the subset being generated; Generate the rest of the subset;
This pseudocode can be translated into the following incomplete Java function. This function aims to generate all subsets of the elements in the subarray collection[start..collection.length-1]. This means that start should be initially passed in as 0.
void generateSubsets(int start, int[] collection, boolean[] subset) { subset[start] = true; // Line 1 generateSubsets(start + 1, collection, subset); // Line 2 subset[start] = false; // Line 3 generateSubsets(start + 1, collection, subset); // Line 4 }
boolean subsetSum(int start, int[] collection, boolean[] subset)which returns true if the given collection has a subset that adds up to 0 and returns false otherwise. You may assume that there is boolean method called checkSum that checks if the elements in collection that are turned on in subset add up to 0.
Problem 2.
This problem is on the heap data structure.
50 21 10 18 12 15 13would correspond to the ternary heap
50 / | \ 21 10 18 / | \ 12 15 13For an element in slot i, write down the locations of its 3 children. For an element in slot i, write down the location of its parent.
Problem 3.
Here is an edge-weighted graph.
Problem 4.
This problem is on AVL trees.
Start with an empty AVL tree and insert the items
1, 2, 3, 4, 5, 6, 7, 8, 9, 10in that order, into the tree. For each insertion show the following information. Suppose that T is the current tree and x is the new item being inserted.