Sign in to follow this  
petemurray

data structure for intervals

Recommended Posts

Hi guys, I have a question on a mock exam and it is "Describe clearly your chosen data structure for representing intervals". Obviously they will probably ask a similar question on the real exam. So i'm trying to work out what it means. It's worth 5 marks! :O Now, i'm assuming I need 5 bullet points about it. However, I'm unsure what exactly the question means? All i can think of is that it is a list lol. It forms part of a larger question which is a data abstraction for 'intervals'. I will quickly brief you on it.. Now, I have created a constructor called make-interval which accepts a lower endpoint l and an upper endpoint u and a predicate c which defines the ordering of interval elements, and returns an interval. Here is my constructor: (define [make-interval c l u] (if (c l u) (if (string? l) (cons l (make-interval c (string (integer->char (+ 1 (char->integer (string-ref l 0))))) u)) (cons l (make-interval c (+ 1 l) u)) ) empty)) Examples: (make-interval string-leq? "a" "e") .. the result is '("a" "b" "c" "d" "e") (make-interval <= 1 5) .. the result is '(1 2 3 4 5) Surprisingly, it works. (assuming that string-leq is a predicate that determines whether the lower endpoint letter is less than the upper endpoints letter. Again, the question "Describe clearly your chosen data structure for representing intervals" arises... Please give me some pointers as to how to answer this question, as I have no idea what it is asking me. Thanks for everything, :)

Share this post


Link to post
Share on other sites
Quote:
Original post by petemurray
Surprisingly, it works.


EDIT: I'm unclear as to what's going on, sorry. Anyone else? As a response purely to your topic: std::pair<int, int> in C++'s STL.

Share this post


Link to post
Share on other sites
I suspect there's something you're misunderstanding about the question, but it's hard to say without more context. What operations should an interval support? Does it only have to work for integers and characters, like your make-interval does?

Share this post


Link to post
Share on other sites
yes only intervals and characters.

ALl i could think of was that it is a list of numbers that are ordered from the lowest point to the highest point. The make-interval constructor only works for string-leq? or <= predicates.

Not sure what else to say :S

Share this post


Link to post
Share on other sites
Does the larger question you mentioned require you to implement other functionality
on top of your interval representation?
Let's say you wanted to write a function "contains" that would check if a value is inside
an interval. With your make-interval, contains would have to search through the list, and
it wouldn't work for fractional values.
It helps to think about data types in terms of the things you want to do with them. So if the operations on intervals were e.g. min, max, and contains, think about the minimum amount of information you need to put into your interval implementation to make those operations work.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.4

I doubt you'll find a better explanation.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this