geekitarian

I was paying bills today and it struck me how much easier things are since my wife and I paid off all of our student loans 2 years ago.  I’m simultaneously happy with a system that allows a broke kid like me to go to a decent college, and shocked by the crushing burden of debt that it can create.  The story of my own college debt is convoluted, uninformed, and fraught with my own mistakes and missteps. I grew up in Ohio always thinking I’d be going to OSU. I ended up doing in better on my SAT than anybody expected (myself included), and the University of Dayton offered me a big scholarship. Nevermind that OSU would still have been significantly cheaper. I decided to chase the dollars. It felt great to be offered so much money, though I didn't quite grasp the idea that it was more of a discount than a cash offer. It went fine; I sometimes felt unprepared, but I did OK overall and finished the year with a decent GPA. I had a girlfriend when I started college. The long distance ...

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) ...