geekitarian

Let's say we want to find the path between an origin and a destination in a graph.  We'll want to return a LinkedList that lists vertices in order from the origin to the destination.  To do this we’ll find the shortest path. In order to implement a getShortestPath method, we can take the following steps: Create a queue.  This will tell you the next vertices to visit. Create a map.  This will allow you to identify visited vertices, as well as trace your path backward. Add the origin vertex to your queue. Add the origin vertex to your map (try origin as the key, and null as the value). Then, while your queue is not empty (i.e. while you still have nodes not traversed): Retrieve & remove the next value from your queue.  We’ll call it “currentVertex” for now. If currentVertex is your destination, you’ve finished.  Calculate the path from origin to destination (using your map) and return it. If currentVertex is not your destination, retrieve th...

If you want to access each node in a binary tree in sorted order, how would you go about doing this?  Describe the procedure. Draw the resulting binary tree if the following values are added (as ordered below).  Is this tree complete? 56, 43, 60, 67, 80, 31, 12, 54, 65, 25, 28, 57, 50, 59 What nodes could you add to make this tree complete? How many nodes are in a full tree if the tree’s height is 11?  How many nodes are leaf nodes? What is the computational complexity of retrieving a value from a full tree? Describe the worst case for retrieval from a binary tree that is NOT full. Identify each the steps involved in removing the value “88” from the tree below. Write the code for the method public void add(Comparable value) in a Tree object.  State any assumptions made. Assume you are building a map with a tree as its backing structure.  Implement the get(Comparable key) method below.  State any assumptions made (beyond the get and set methods a...

Think about this MaxHeap: 0 1 2 3 4 5 6 23 12 19 7 10 18 14 Remember, children are found with this formula: Left child: 2i + 1 Right child: 2i + 2 Parents are found with this formula: Parent: (i - 1) / 2 If we have a maxheap, the children are smaller than the parents.  If we have a minheap, the children are larger than the parents.  This is a maxheap, so all parents are larger than their children. To add to a maxheap, we put the new value at the next available position in the array then swap up.  In the file for your assignment, we call this process reheapUp. If we add the value 20 to the maxheap above, we get this: 0 1 2 3 4 5 6 7 23 12 19 7 10 18 14 20 We swap 20 (index 7) with its parent, if the parent is smaller.  The parent value is 7 (index 3) so we swap up. 0 1 2 3 4 5 6 7 23 12 19 20 10 18 14 7 We swap 20 (index 3) ...

Let’s say we already have a binary tree, and we want to build an Iterator to return the nodes in our tree in order.  If we were just listing the nodes, we could follow this recursive algorithm: Go to the left child (if it exists) Output the current node Go to the right child (if it exists) Consider this tree: We would start at the root (M); we’d immediately go to the left (F), then go to the left again (A).  There are no more values to go to the left, so we’d output the current node (A).  Then we’d go to the right - but there’s nothing to the right of A.  So we’d return.  This would return us to the previous level of recursion, where we’d output the current node (F).  We’d then go to the right (K); the next step would be to go to the left (J), then go to the left again (G).  We’d then output G as there’s no further left to go to; there’s nothing to the right, so we’d return to previous level of recursion (J).  We’d output J, an...