Submit answers as PDF to Blackboard. Do not discuss this assignment with others until after the 17th. Late work is not accepted, so that we can discuss solutions in class on the 18th.
Question 1 (40 points)
A circle is defined as a 2D point in space (x,y) and a radius r. Design a data structure (write a class) that can store a collection of circles. Include psuedocode for a class method for your data structure that takes x,y coordinates as parameters and returns the circles that contain that point (that is, those circles where the requested point is within their radius). While this method can be pseudocode, make sure to write an explicit java method signature (like an interface) that illustrates what this method takes as input and what it returns.
What is the growth rate of this method, in big-O notation? What constitutes the input size for the big-O notation? Note: it doesn’t have to be a particularly good data structure or method – I’m just looking to see that you can describe it.
Question 2 (40 points)
A museum employs NUM_GUIDES tour guides. We want to design a system that when a group of visitors arrives, this new group is added to the tour guide with the fewest currently assigned visitors. How can I do this using a heap of lists?
Sketch/describe this heap of lists data structure. What is the time cost in big-O of adding 1 new visitor to the shortest list.
Question 3 (20 points)
Describe an algorithm, using data structures described this semester, to process an input stream containing characters and parentheses, such that the parentheses describe layers of output.
1
For example, your algorithm would take this input:
(Go ((cake) is) od)
and produce the following output:
cake
is
Good
What is the growth rate of this algorithm in big-O notation?
2
