Assignment 2
Due:11:30 pm May 20, 2022
• This assignment contains three parts, which all cost 30% for your final mark.
• Assignments should be converted to pdf format and submitted via Moodle as ass02.pdf
• Please write your name, student ID and your campus in your submission.
• Late submission will be deducted 25% for each late day.
Part A: Trapeziums (8 marks)
An equilateral triangle, with side of length 3n for some natural number n, is made of smaller equilateral triangles. See the figure below for the case n=2. A bucket-shaped trapezium shown in the right of the below figure is made from three equilateral triangles. Prove that it is possible to cover the remaining triangles with non-overlapping trapeziums. You should work for general case of n, the below figure is just an illustration for the case n=2.
Part B: Restricted Tower of Hanoi (8 marks)
There are n disks of different sizes and three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The object is to transfer all the disks to the third peg. Only one disk can be moved at a time, and it is forbidden to place a larger disk on top of a smaller one. In addition, any move should either place a disk on the middle peg or move a disk from that peg.
a) Design an algorithm (a strategy) that solves the problem. (2 marks)
b) Compute the total number of moves in your solution. (2 marks)
c) Is your solution optimal? (i.e. whether you achieve a solution in the minimum number of moves. Please clarify). (1 mark)
Part C: An assignment problem (7 marks)
Eve, an eavesdropper, wants to capture as much communication traffic as possible. She can eavesdrop on a specific channel for at most two hours,
contiguously or otherwise, or she will be detected. There are ten channels for her to choose from and she can eavesdrop for a total of 10 hours. Each channel cycles its transmission, but Eve will learn nothing by capturing the same traffic twice.
The following table shows overall how much traffic is sent across a channel in the specified transmission time.
Channel# 1 2 3 4 5 6 7 8 9 10
Overall traffic volume (Mb) 7 15 12 12 4 10 6 80 64 14
Transmission time (Hours) 1 3 3 2 1 4 6 4 16 2
a) Describe how you can determine the greatest volume of traffic Eve can capture, given the constraints of the system. (3 mark)
b) Use your method of part a) to determine which channels Eve should eavesdrop on to maximise the traffic captured. Show the details of your working. (3 mark)
c) Specify the overall volume of traffic captured by Eve. (1 mark)
Part D: Knight’s Tour (7 marks)
How many distinct squares can a chess knight reach after n moves on an infinite chessboard? (The knight’s moves are L-shaped: two squares either up, down, left, or right and then one square in a perpendicular direction.)
