Algorithms II
Autumn Semester 1998
Coursework Exercise 1
This work must be handed in by 4:00pm on 13th. November 1998.
This work will contribute 10% towards your final mark for this module.
Remember to include the standard coursework cover page.
-
Write an algorithm, length(list), in SPARKS pseudocode to count
the number of nodes in a singly-linked list list, where list
points to the head node of the list. The head node itself should not
be counted.
Assume the last node has link field set to end_of_list.
-
-
Describe fully an example of a recursive algorithm not discussed
in the lecture notes.
-
Consider a coin set containing coins with the following values:
1, 5, 10, 20, 25. Does the greedy algorithm described in the lecture notes
always work optimally for this coin set? Justify your answer.
-
Draw a tree to represent a binary search of the following sorted list
of integers;
1, 3, 5, 8, 11, 14, 15, 19, 21, 22, 24, 28, 30, 32, 33
-
This question is concerned with using a doubly-linked, circular list for keeping
track of free memory on multiprocessing workstations, as discussed in the
lectures and in section 4.8 of Horowitz and Sahni.
-
What are the four possible cases that can arise when an allocated block
of memory is returned to the free list if a coalescing strategy is
used?
-
The following segment of SPARKS pseudocode describes how coalescing is
performed when the memory block to the right of the freed block is
also free, but the block to the left is not.
p points to the memory being freed and n is its size.
rlink(llink(p+n)) <- p
llink(rlink(p+n)) <- p
llink(p) <- llink(p+n)
rlink(p) <- rlink(p+n)
size(p) <- n + size(p+n)
uplink(p+size(p)-1) <- p
tag(p) <- 0
if av = p + n then av <- p
-
Describe clearly in words what lines 1 and 2 of the above pseudocode do.
-
Describe clearly in words what lines 3 and 4 of the above pseudocode do.
-
What is uplink?
-
Why is uplink needed in the node structure of a free node?
-
In line 7 of the above pseudocode, the tag value at the start of the
freed block is set to zero. Why does the pseudocode not also set the
tag value at the end of the free block to zero?
-
Why is line 8 of the above pseudocode necessary?
-
The following SPARKS pseudocode describes the case when the blocks to the
left and the right of the freed block are free, and must be coalesced with
the freed block.
rlink(llink(p+n)) <- rlink(p+n)
llink(rlink(p+n)) <- llink(p+n)
q <- uplink(p-1)
size(q) <- size(q) + n + size(p+n)
uplink(q+size(q)-1) <- q
if av = p + n then av <- llink(p+n)
Describe clearly in words what this fragment of pseudocode does.