# exam review

Posted by valkeye
Announcements Last Post
: Programming Students at UNISA School of Computing 06/19/2019 02:01PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 exam review October 18, 2008 07:33AM Registered: 13 years ago Posts: 232 Rating: 0
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
 Re: exam review October 18, 2008 08:16AM Registered: 11 years ago Posts: 423 Rating: 0
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 Registered: 11 years ago Posts: 79 Rating: 0
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.
 Re: exam review October 18, 2008 10:48AM Registered: 12 years ago Posts: 673 Rating: -1
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.
 Re: exam review October 18, 2008 01:25PM Registered: 13 years ago Posts: 232 Rating: 0
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
 Re: exam review October 20, 2008 08:03AM Registered: 12 years ago Posts: 673 Rating: -1
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)

while(queue.front()!=front){
Remove front
}
Return nth
 Re: exam review October 20, 2008 09:47AM Registered: 12 years ago Posts: 915 Rating: 0
I came up with the same solution althought I agree it gets horribly inefficient as n increases.
 Re: exam review October 20, 2008 10:59AM Registered: 13 years ago Posts: 232 Rating: 0
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 Registered: 14 years ago Posts: 88 Rating: 0
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.