Computer Systems
Sample Examination Paper
January 2022
Answer all questions
Question 1
a. The diagram below shows roads connecting towns near to Rochdale. The numbers
on each arc represent the time, in minutes, required to travel along each road. Peter
is delivering books from his base at Rochdale to Stockport. Use Dijkstra’s algorithm
to find the minimum time for Peter’s journey.
[8 Marks]
b. Consider an environment in which there is a one-to-one mapping between user-
level threads and kernel-level threads that allows one or more threads within a
process to issue blocking system calls while other threads continue to run. Explain
why this model can make multithreaded programs run faster than their single-
threaded counterparts on a uniprocessor computer.
[6 Marks]
c. An interactive system using round-robin scheduling and swapping tries to give
guaranteed response to trivial requests as follows:
After completing a round-robin cycle among all ready processes, the system
determines the time slice to allocate to each ready process for the next cycle by
dividing a maximum response time by the number of processes requiring service.
Is this a reasonable policy? Explain and justify your argument, using examples if
necessary.
[6 Marks]
Question 2
a. Consider that you live in a small town where only dial-up access is available, with a
maximum possible speed of 300-Kbps (using V.44 modems). You are interested in
uploading a large video file of 2 gigabytes to a server on the Internet.
A bus visits your town every day from the closest city, which is located at 210km
away, and stops in front of your house for 5 minutes max (but it can leave as soon
you indicate you are done). The bus has a 100- Fi connection and it can
collect data from users in rural areas and transfer them to the Internet through a 2-
Gbps link once it gets back to the city.
Suppose the average speed of the bus is 70 km/h. What is the fastest way the user
can transfer the data to the server?
[8 Marks]
b. Convert the decimal number -92.882812710 to the equivalent 16-bit fixed point
notation. Use 1 sign bit, 7 bits for the real part and 8 bits for the fractional part.
Show clearly how you have performed the conversion and clearly state any
assumptions that you have made.
[6 Marks]
c. Your friend Jane needs to run a simulation for her thesis and her adviser wants her
to run it for a fixed problem size. Jane can make 80% of the program parallel, with
20% of it being sequential.
i) What speedup can Jane expect on 5 processors?
ii) What would the maximum theoretical speedup be on an infinite number of
processors?
[6 Marks]
Question 3
a. You are designing a network for a multinational corporation with offices in 50
different countries. Each office is required to be on a different subnet and the
corporation has obtained a Class B network address of 150.32.0.0.
Design subnets for all of the site offices and indicate how many hosts (usable ones)
can be assigned to each site office. Also, indicate if there is any room for expansion
to 10 more countries, using the same network IP address and subnetting scheme.
You are not required to list all subnets, however, you can mention the subnet
addresses, subnet masks and host address ranges for the first three and last subnet.
[6 Marks]
b. Consider the block cypher shown in the figure below:
Suppose that each block cipher Ti simply reverses the order of the eight input bits
(so that, for example, 11110000 becomes 00001111).
Further suppose that the 64-bit scrambler does not modify any bits (so that the
output value of the mth bit is equal to the input value of the mth bit).
i) With n = 3 and the original 64-bit input equal to 10100000 repeated eight
times, what is the value of the output?
ii) Repeat part i) but now change the last bit of the original 64-bit input from a
0 to a 1.
iii) Repeat parts i) and ii), but now suppose that the 64-bit scrambler inverses
the order of the 64 bits.
[8 Marks]
c. In this example you should assume that the function binarySearch is O(log n)
numberFound = 0
for i = 0..(n-1)
for j = 0..(n-1)
if binarySearch(A[i,j])
numberFound = numberFound + 1
i) Use the Big-O notation to express the time complexity of this algorithm
ii) If this algorithm takes 10 seconds to execute when n=2000, estimate how long it
will take when n=8000.
[6 Marks]