2023年11月25日

算法代写 | Algorithms and Complexity (Extended)

本次英国代写是图灵机 – 算法与复杂性相关的限时测试

Algorithms and Complexity (Extended)

Exam paper

This exam is out of 70 marks. You can use any results (theorems, algorithms, etc.)
covered in the module (lectures and assignments).

Question 1

Recall that we write L for the class of languages decidable by a deterministic Turing
machine using O(log n) space. Show that the language R of words in f0; 1g
with twice as many 0s as 1s is in L.

For instance, 010; 001; 010010 2 R , but 011; 010110 = 2 R. You may assume that
basic arithmetic operations on binary integers, e.g. +1 and checking for equality, are
e ectable using only a constant amount of additional space.

Question 2

Consider a set of 5 hospitals and 5 students. Can the Gale-Shapley algorithm (where
hospitals make o ers to students) ever match a hospital h to a student s such that s is
last on the preference list of h? Either prove that this cannot ever happen, or design a
set of preference lists for hospitals and students for which this occurs.

Question 3

You want to spend n days in a new city. The two possible hotels are Hilton and Ritz. For
each 1  i  n, the cost of staying at the Hilton on day i is Hi and the cost of staying
at the Ritz on day i is Ri where Hi ;Ri are some positive constants. The cost of moving
from one hotel to the another is 100. You can start your stay at any of the two hotels.
Design an O(n) time algorithm which calculates the least possible expenditure of an n-day
stay. Explain both the correctness and running time of your algorithm.