PastExamPapersOct2006

Hi! anyone tried the oct 2006 paper. How do you find it. I need help on question 3-the sentinel search. I don't understand how it works. Any tips on how to implement it.

Thanks.

Yeah ... question 3 also has me kinda confused.
This is what I understand from the question:
-Assign the value of item to the last element in (length of) the list
-Initialize i
-Then iteratively search the list for item
-When the item is found, exit loop
-check if i = = the last element (the element you added)
-if it is, return -1
else return i;

This way there is only one comparison in the loop, and you do one extra comparison after the loop

I'm guessing you also have to remove the item from the back of the list before returning, but yeah ...
Hope this helps

Thanks Pal.

What baffle's me a little, is there not only 1 comparison in the Sequential search?
I've simplified my version to get rid of the extra comparison outside the loop as well. This makes it way simpler than the sentinel search.
I'm not sure what the advantage of the sentinel search would be?

Hi AndreB,

What is your Big Oh analysis of the Sentinel search algorithm?
I also don't think there is an advantage in the sentinel search algorithm, it only ensures that the element is in the list?

Sorry Count Zero - I haven't got to the Big Oh analysis yet.
I'm currently going through Sorting.
There is another issue with the sentinel - what happens if the item did already exist, you have now added a duplicate of it to the end of the array - to what advantage?
I'm probably missing the point here - so I'll continue with the sorting.

Agreed, I don't get it either.

O well, I must also start with sorting
At least I'm more than half way with revision

Good luck with your studies!

cheers - to you as well.
I quick look at the Big Oh analysis of the sentinal search - it should stay O(n).
I don't get question 4 a, at all. Swap the nodes, not just the values of info???

Any suggestions?

Haven't yet reached the sentinel search, but what's your answers for question 1 (b) (ii). How do you do it? I've got O(n power 2). Any tips would be most welcome.

Question 9 (b) I've got this:

vertex Shortest Distance
0 ------ 4
1 ------ 6
2 ------ 0
3 ------ 5
4 ------ 7
5 ------ 5
6 ------ 9

I got the same answer for 1(b)(i) and shortest distance is good.
Goodluck.

Yeah - I also got O(n^2) for q1.b.2

AndreB Wrote:
-------------------------------------------------------
> What baffle's me a little, is there not only 1
> comparison in the Sequential search?
> I've simplified my version to get rid of the extra
> comparison outside the loop as well. This makes it
> way simpler than the sentinel search.
> I'm not sure what the advantage of the sentinel
> search would be?

In a sequential/linear search, there are two comparisons every time the loop starts, it checks whether it has found the item, and it checks whether it has reached the last element in the list. In a sentinel search, it only needs to check if it has found the item. Half the work.


AndreB Wrote:
-------------------------------------------------------
> There is another issue with the sentinel - what happens if the item did
> already exist, you have now added a duplicate of it to the end of the array -
> to what advantage?
> I'm probably missing the point here - so I'll continue with the sorting.

When the search completes (whether the item was in the original list or not) you remove the "sentinel" from the back of the list again. See above comments for the advantage. I'm just giving my opinion. I might be wrong, so don't take my word for everything.

Thanks Maggot!

That makes it very clear why the sentinel search is better than the sequential search.
So the Big Oh analysis is O(n)?

@Lordamp your answers seem to be correct.

Yip

Thanks Maggot,
In the sequential search on array based list, there is no second check to see if the item has been found. i.e. making use of a for loop instead of a while loop.
I do see that with the sentinel search you could use a while loop with a single check.
Sequnetial search = O(n)
Sentinel search = O(n)
I do think that the question simply checks t osee if we actually understand the sequential search, and know how to modify it to a sentinel search.
The merrits of whether or not the sentinel search is a better search algorithm does not really matter, I suppose.
Cheers.

Hi there,

I'm really struggling with Cos211-x. Can anyone be kind enough to mail me some past questions paper and/or tuts. Please.

Thanks
Jiby

Email: jiby.mundackal@gmail.com