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

This is a list of exam questions I've asked on past exams for my data structures class at the University of Pittsburgh. Why is inheritance potentially a problem for a SortedList? Assuming a Set is built with a sorted array as its backing structure, what is the computational complexity of the remove(Object) method?  State any assumptions you make and explain your answer. Assuming a Set is built with a sorted array as its backing structure, what is the computational complexity of the contains(Object) method?  State any assumptions you make and explain your answer. Explain how the binary search algorithm works.  If no code is written, be sure to provide a detailed description.  Illustrate with an example. What is one distinct advantage of using an array-backed SortedList over a linked approach? What is one distinct advantage of using a linked approach to a SortedList over an array-backed approach? Show the steps involved in performing an insertion sort on the a...

This is a list of exam questions I've asked on past exams for my data structures class at the University of Pittsburgh. What is the computational complexity when iterating over a linked list *without* using an iterator?  Why? Explain how using an iterator improves computational complexity. What is a circular array? What are 2 advantages of using a circular array for building a queue, instead of linked nodes? Using words and a drawing, explain what happens when you insert an item into the middle of a linked list. Using words and a drawing, explain what happens when you insert an item into the middle of an array list. Explain the behavior of a queue, including the operations a queue should be able to perform. In a queue implemented using a circular array, why do we need to know more than just the start and end positions to know if the queue is full? Explain why removing the first item in an array list is more work than removing the first item from a linked list. What are ...

This has become a routine now: I don't give extra credit but on final exams I usually include a gimme question that involves something absurd.  I've done it a few times before ( pigs in hats  /  hippos thinking about tacos  /  happy rabbits ).  For my web development class's final exam, question 16 was: "Illustrate what a warthog would look like if it were piloting a spaceship.  Title your drawing Star Boars."  These are the finest submissions. I tried to time this one with the release of the new Star Wars movie but I'm not so good at getting this kind of thing done so you get it 5 months late. Disclaimer: the dark side would have won if they had more porcine TIE Fighter pilots. As usual, click the small images to see the bigger images. Even after sustaining significant damage, this pig perseveres.  Star Boars are dedicated. Not sure if this is a pig or a normal guy with a big mustache.  Also the Pig Box wa...

I've done this once or twice before: I don't like "bonus" questions on exams but I like to give a little freebie question to lighten the mood.  These are the results of the very artistically talented (as well as some of the less artistically talented) students in my web applications class.   Disclaimer: don't try to feed a taco to a hippo, they don't eat meat and they're more dangerous than sharks or lions or bears or bearsharks or lionbears .  Maybe try a vegetarian taco *** . Click the images to enlarge. * * * #10: I appreciate this answer because the author really followed the directions. #9: There's irony in this much contemplation from a hippo that doesn't understand the concept of words. #8: I'm surprised there weren't *more* maracas and sombreros. #7: I don't have any idea what's wrong with this hippo... but I know there's a lot right. #6: Pretty sure this student thought ...

Last spring I decided to have some fun on the final exam for my Computer Data Structures class.  I was happy with the way it turned out , so I figured I'd do it again in this past fall term's Web Development class.  These are the results.   Disclaimer: to the best of my knowledge, no actual rabbits were harmed during this exam.  However a few students took the exam outside of the normally scheduled time with a proctor and I really don't have any idea what kind of interactions they had with rabbits or any other rodents, for that matter. Click the images to enlarge. * * *  #10: While not the most artistically drawn rabbit in the bunch, this rabbit has evolved into a bipedal species so I think he should get some credit. #9: I don't have anything to say about this rabbit, but I hope that's a foot in the back there.  #8: This rabbit also scores points for having hands and opposable thumbs.  #7: Thi...