Welcome! Log In Create A New Profile

Advanced

exam review

Posted by valkeye 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
avatar exam review
October 18, 2008 07:33AM
Hi guys. What did everyone think of the exam?

I thought it was pretty straight forward actually. I had a problem though with question 6. The recursive findNth for a queueType.

I dont know if i'm just being really dense at the moment, but i cant see a possible way of answering the question correctly while sticking to all their limitations.

We had a similar question in assignment 2, but using a stack, which makes it easy. But having to use a first in first out data structure like a queue, without using any other helper data structures, and using recursion. I couldn't see a way to do it while leaving the queue in the original form.

So in the end I returned the nth value, but my queue was not in the original form.

What are your comments on this question and the exam? If you managed to find a recursive function to do the above while sticking to all their limitations please post it. I'd really appreciate seeing it.

-Valkeye
avatar Re: exam review
October 18, 2008 08:16AM
Yes, same problem with Q6. Otherwise OK.
I left it half done when I saw the problem as you described.

The question on the recursive sequential search driver function did not show the recursive function returning anything. I think this was a mistake, so I made a comment in the answer book and wrote the function to returned a bool value.

B
Re: exam review
October 18, 2008 09:21AM
Got stuck with Q6 after recursively "peeling the onion" up to the nth element. Then couldn't figure how to return everything to order. Suspected perhaps I needed two recursive calls in the same function but ran out of time trying to figure it out.

Overally the exam looked ok.
avatar Re: exam review
October 18, 2008 10:48AM
I had problems with Q6 too, but then I started drawing examples and eventually found the answer.

Base case is when n==1 and returns the item
Else
Get the front item
N = call the function with n-1
Add the front item to the queue (goes to the back)
Then do a while loop that keeps on popping the items in front of the real front just added and adding them to the back until the real front is in front again.

Then return n

Its probably not a very efficient way to do this but it works.
avatar Re: exam review
October 18, 2008 01:25PM
ok. That sounds interesting. I'll try that just now, not at home. but a while loop within a recursive function will execute many times, but the first recursive call tho the loop must finish deleting and adding, whilst the rest must cycle the entire queue. Also, the queueType data structure has no way of determining the size, so there's no way to determine the number of iterations to go thru in the loop.

But i'll give it a try. Thanks.

-Valkeye
avatar Re: exam review
October 20, 2008 08:03AM
Yeah, in real life you would have used an extra data structure.

You dont have to check the size.

//base
If n==1
Return queue.front()

Else
front = queue.front()
queue.deleteQueue()
nth=Nth(queue,n-1)
queue.addQueue(front)

while(queue.front()!=front){
Remove front
Add to back
}
Return nth
avatar Re: exam review
October 20, 2008 09:47AM
I came up with the same solution althought I agree it gets horribly inefficient as n increases.
avatar Re: exam review
October 20, 2008 10:59AM
i see that that solution would work, unless their are duplicate items in the list.

I remember 1 question said we can assume that there are no duplicates, but i dont think it was question 6. Or was it?

Cause if their are for example 2 elements in the queue with value 18 then when it encounters the 2nd value of 18 its gonna think its cycled the entire list.

But if their are no duplicates it should work. But in my opinion if that is the solution they were after i'd think its not a good question at all for 3 reasons.

1) queue's with duplicate values cant use the function.

2)the use of a while loop within a recursive function negates the need for a recursive function at all. In that case i would code a completely iterative solution and put it within an if statement and use a static bool value listCycled. Cause static variables dont have their values re initialized every time the function enters. Eg.

Static bool listDone = false;

If(!listDone){
//iterative code
listDone = true;
//recursive call here
return value;
}

Now technically it is a recursive function cause it calls itself, but the actual solution really is iterative. And it only gets called once, as on the second entry to the function, the value listDone retains its value true. Therefore its time complexity is the time complexity of the iterative solution only.

3) we've been focussing on time complexity for a lot of the course and we've been told to be aware of the time complexity of what we code. To be expected to code a recursive function with a while in it they're basically telling us to code an O(n squared).

But dont get me wrong, i'm not mocking ur guys solutions, in exam situations i think that ur solutions are a pretty damn good way to solve the question that was asked.

I'm just hoping that that's not what they were expecting, for the above reasons.

-Valkeye
Re: exam review
October 21, 2008 09:07AM
This question is similar to question 6 of assignment 2, the solution is also very similar.

regards
Lazarus Aron
Sorry, only registered users may post in this forum.

Click here to login