Assignment 1
COMP3121/9101 22T1 Released February 15, due March 3
In this assignment we review some basic algorithms and data structures. There are four problems, for a total of 80 points.
Your solutions must be typed, machine readable PDF files. All submissions will be checked for plagiarism!
Copyright By PowCoder代写 加微信 powcoder
For each question requiring you to design an algorithm, you must justify the correct- ness of your algorithm. If a time bound is specified in the question, you also must argue that your algorithm meets this time bound.
Partial credit will be awarded for progress towards a solution.
1. (20 points) You are playing a level of the latest smash-hit kung-fu video game. The level is composed of a sequence of n rooms filled with enemies. The hero must go through all n rooms in order, fighting all the enemies in each room. The level is completed when the hero exits the final room. For each room i, you know the number of times ai that the hero will die in that room.
Furthermore, this game has a very interesting death mechanic. The hero starts at age 20, and each time they die, their age is increased by the value of the death counter, which is the number of times that the hero has died. For example, after the first, second and third deaths, the hero¡¯s age becomes 21, 23 and 26 respectively. Moreover, before the hero enters any room, you can reset the death counter to 0, though this ability may only be used once in the entire level.
Design an algorithm which runs in O(n) time and calculates the minimum age at which the hero can finish the level.
2. You are given an array A consisting of n integers, each between 1 and M inclusive. You are guaranteed that no more than k distinct values appear in the array.
You are required to identify which of the values between 1 and M appear in the array, and for each such value, how many times it appears. Design algorithms which solve this problem and run in:
(a) (5 points) worst case ¦¨(n + M ) time; (b) (5 points) worst case ¦¨(n log n) time; (c) (5 points) worst case ¦¨(n log k) time;
(d) (5 points) expected ¦¨(n) time.
3. (20 points) You are given an n by n matrix of distinct integers. A summit is an element that is larger than all its neighbours in each of the (up to) 4 directions. Design an algorithm which runs in O(nlogn) time and finds the location of any summit.
Note that integers in the corners and boundaries can be summits, and there will al- ways be at least one summit, the maximum element. However, you do not necessarily have to find this specific summit.
4. (20 points) You have n poles of distinct heights spaced in a line, the ith of which is hi metres tall. You can wire together two poles i < j only if they are both taller than allpolesinbetweenthem,thatis,foreachi