Details of this Paper

Data Structures and Algorithms




Computing & Information Systems;University level 2;Data Structures and Algorithms;Assignment 2;Due date: Tuesday, November 4, 2014 at 11:59pm;Part A: Perfectly Balanced Binary Search Trees;Definition: For each node x in a perfectly balanced binary search tree, the number of nodes in the left and right subtrees of x differs by at most 1.;1) Using the given BinarySearchTree class, implement additional methods to;a. Create a binary search tree by successively inserting all elements of A.;public BinarySearchTree (List A);{ ? };b. Return a sorted list of all elements in A using an inorder traversal.;public void Output (List A);{ ? };c. Return the average depth of all nodes (elements) in the current binary search tree.;public float AverageDepth ();{ ? };2) Implement a class called PerfectlyBalancedBST which inherits from BinarySearchTree and has additional methods to;a. Create a perfectly balanced BST given a sorted list A.;public PerfectlyBalancedBST (List A);Note: You may need to implement a helper method since constructors cannot be recursive.;b. Calculate the theoretical average depth of a perfectly balanced BST with n elements.;public float TheoreticalAverageDepth ();3) Output the theoretical and actual average depths of a perfectly balanced BST. They should be the same for n=10, 100, and 1000.;4) Calculate the ?average? average depth of a binary search tree for 100 random instances of A for each of n=10, 100, and 1000. Compare this ?average? with the average depth of a perfectly balanced search tree on n nodes by taking the ratios.;Part B: Discrete Event Simulation of an Intersection;Definition: A discrete event simulation monitors and outputs particular events in chronological order and calculates statistics based on the input parameters.;Consider an intersection of two streets. One streets runs north to south, the other street runs east to west. Both streets are one-way.;The inter-arrival time of cars at the intersection is randomly drawn from an exponential distribution with a mean of Me for those cars coming from the east, and Mn for those cars coming from the north. Both Me and Mn are input parameters of the simulation. The random variable for the inter-arrival times is given by the formula;-M x ln(u);where ln is the natural logarithm, M is the mean, and u is a uniformly distributed random variable between 0 and;1. As an exercise on the side, generate a uniformly distributed random variable between 0 and 1, and plug it into the formula for a given M. Sum the result of the formula for 1000 trials and calculate the average. It should be very close to M;The other input parameters correspond to the cycle of lights at the intersection. The green light stays on for Ge seconds for cars coming from the east and Gn seconds for cars coming from the north. When one light is green, the other light is red. There is no orange light. Run the simulation for 100 cycles of lights.;Cars may only pass through the intersection on a green light in three second intervals. If the light is red, cars wait in a queue. Therefore, if a car arrives at an intersection when the light is green and there is no queue, it must still wait (if necessary) three seconds from the last car that passed through.;Given these parameters, the simulation monitors and outputs in chronological order the following events;1) The changing of lights;2) Cars arriving at an intersection;3) Cars leaving an intersection;The simulation calculates the average waiting time of all cars at the intersection for a given set of parameters. Your task therefore is to find the optimal cycle of lights that minimizes the average waiting time for a given Me and Mn. Graphically display your results;To help support the simulation, three classes are needed.;1) An Event class that contains the type of event and its time.;2) A Priority Queue (binary heap) of Events that orders the events chronologically;3) A Queue in each direction for cars to wait when the light is red;Finally, the full simulation is run from another class called Simulation that inputs the parameters, runs the simulation by generating, inserting, and deleting events from the priority queue, and calculates the statistics;Additional marks for Parts A and B;10 marks for in-line documentation


Paper#64920 | Written in 18-Jul-2015

Price : $27