[Solved] Algo Assignment1-Basic Algorithms

For this programming assignment, you are given “starter code” (available on the course home page) that provides you with data structures and algorithms for insertion into a 2-3 tree. To receive full credit:• you must make use of the given starter code, and in particular, you must use thegiven data layout of the given Node class, and you may not add any additional datamembers to this class;• you must follow the high-level outline provided here — there are a number of differentapproaches to solve this problem, but you must use the approach given here.Submissions that do not adhere to the above rules will receive very low grades.You should read the problem statement on HackerRank for details of the input/outputformat. The main thing you have to do is implement an operation printRange(x, y) thatprints out all leaves whose keys lie in the interval [x, y]. Here, we will assume that x ≤ y;however, note that the data in the input file may not be of this form.The goal is to implement this with an algorithm whose running time is O(m + log(n)),where m is the number of keys in the interval [x, y] and n is the total number of keys.A simple idea that does not workLet us first consider a simple strategy that does not work, in the sense that it does not yieldan algorithm that is fast enough. We use the same notation from class and from the “Noteson 2-3 trees” handout for the data layout:1class Node {KeyType guide;// guide is the max key in subtree rooted at node}class InternalNode extends Node {Node child0, child1, child2;// child0 and child1 are always non-null// child2 is null iff node has only 2 children}class LeafNode extends Node {// guide is the keyValueType value;}Consider the following recursive algorithm which is initially invoked as printRange0 (p, x, y, h),where p = root of tree and h = height of tree. It prints out the key/value value for all keysin the range [x, y].printRange0 (p, x, y, h):if h = 0 then// p points to a leaf nodeif p.guide ∈ [x, y] then print p.guide, p.valuereturn// p points to an internal nodeprintRange0 (p.child0, x, y, h − 1)printRange0 (p.child1, x, y, h − 1)if p.child2 6= null then printRange0 (p.child2, x, y, h − 1)The problem with this algorithm is that it visits every node in the tree, so its runningtime is O(n), instead of O(m + log(n)), as required. To see the problem and one way to fixit, consider the following example:a b c d e f g h i j k l m n o p q r sPrintRange(l, s)XXt uX2Here, we want to print all keys in the range [l, s], that is, the keys at the gray shadedleaves. The search paths to l and s are highlighted in blue. You can see there is no point incontinuing the recursion at the internal nodes marked with a red X — all of the time spentexploring the descendants of these nodes is wasted.A slightly less simple idea that does workAs the above example illustrates, we would like to “prune” the recursion so that we do notwaste time exploring nodes that are to the left of to the right of the search paths to thekeys x and y.This is easy to do. Consider the following recursive algorithm which is initially invokedas printRange1 (p, x, y, h, lo), where p = root of tree, h = height of tree, and lo = −∞. Itprints out the key/value value for all keys in the range [x, y], and it is assumed that all keysbelow p are strictly greater than lo.printRange1 (p, x, y, h, lo):if h = 0 then// p points to a leaf nodeif p.guide ∈ [x, y] then print p.guide, p.valuereturnhi ← p.guide// p points to an internal node, and all keys below p lie in the interval (lo, hi]if y ≤ lo then return // All leaves below p lie strictly to the right of [x, y]if hi < x then return // All leaves below p lie strictly to the left of [x, y]printRange1 (p.child0, x, y, h − 1, lo)printRange1 (p.child1, x, y, h − 1, p.child0.guide)if p.child2 6= null then printRange1 (p.child2, x, y, h − 1, p.child1.guide)This algorithm works by pruning the recursion as indicated when y ≤ lo or hi < x.Notice how the value of lo gets updated on the recursive calls.• When it recurses on p.child1, since the maximum key stored under p.child0 is p.child0.guide,we know that all keys under p.child1 are strictly greater than p.child0.guide.• Similarly, when it recurses on p.child2, since the maximum key stored under p.child1 isp.child1.guide, we know that all keys under p.child2 are strictly greater than p.child1.guide.You may want to run the algorithm on the above example. You will see that therecursion gets pruned exactly at the nodes marked with a red X.In general, this recursive algorithm will visit nodes on or between the search paths forx and y, which is a total of O(m + log(n)) nodes. The only additional nodes visited arewhere the pruning occurs, and these are siblings of nodes along the search paths for x andy — so there are only O(log(n)) such nodes.3A general statement. We can make a more general statement about the relationshipbetween the keys lo and hi associated with an internal node p, and the search paths for xand y. Consider the following diagram:x yABCThis represents a 2-3 tree showing search paths to x and y.• Region A represents all internal nodes strictly to the left of the search path to x.Node p is in this region ⇐⇒ hi < x.• Region B represents all internal nodes strictly between the two search paths.Node p is in this region ⇐⇒ x ≤ lo and hi < y.• Region C represents all internal nodes strictly to the right of the search path to y.Node p is in this region ⇐⇒ y ≤ lo.Suggested development strategy. You should develop and do initial testing of yourcode on your own machine. You should try to develop and test small components, ratherthan try to develop the entire solution all at once. For example, you could write thehigh-level driver program that reads and parses the input, and prints out the results ofyour parsing. After you have all that working you should attempt to write the completeprogram, implementing printRange1 .Java specific issues. For this programming assignment, your program will generate a lotof output. It turns out that the usual way of outputting data in Java is horribly inefficient.Therefore, for this assignment you must use the BufferedWriter class for output. To accessthis class, you should import from java.io:import java.io.*;Then you can create a BufferedWriter as follows:BufferedWriter output =new BufferedWriter(new OutputStreamWriter(System.out, “ASCII”), 4096);Now, you will have to pass this output object as a parameter to any method that willproduce output, or alternatively, you can access it via a “global variable”. To output aString s, you do this:4output.write(s);Finally, when your program is done producing output, you need to “flush” the outputobject:output.flush();NOTES:• If you use System.out directly, instead of BufferedWriter, your program will definitely time out on several test cases, and you will not receive a very high score.• You should construct only one BufferedWriter object during the execution of yourprogram.• BufferedWriter methods may throw some exceptions, and because of this, you willhave to “decorate” your methods that invoke these methods directly or indirectly asfollows:static void myMethodForDoingSomething() throws Exception{…}• You should not use any try/catch blocks in your code.Other programming languages. You may use Python, or even C or C++. However,“starter code” is only available for Java and Python. If you do use C or C++, you still haveto have a Node structure with the same data members as in the “starter code”.