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