COMP3600/6466 — Algorithms

Notes:

• This assignment consists of two parts. In the second part, you need to write computer programs. You should write your programs in C/C++/Java. No other programming language is accepted. We will support only C++.
• Please submit both the report and the source codes, following the format below, with [studentID] replaced by your student ID. - Please write your report in a single .pdf file, named A1-[studentID].pdf. - Please name the source code that contains your main function for Part B Q2 to be A1-basic-[studentID].cpp (or the suitable extension) and for Part B Q3 to be A1-random-[studentID].cpp. - Please zip your report, source codes (please exclude the object files and executables), and test cases you use for analysing your program, into a single file, named A1-[studentID].zip. - Please submit the .zip file via Wattle. Please note that the maximum file size you can upload is 200MB.
• We provide 13 hours grace period. This means, there will be no penalty if you submit before Saturday, 24 August 2019 13:00 Canberra time. However, we will NOT accept assignment submission beyond this time.
• Assignment marking:
  • The total mark you can get in this assignment is 100 points plus 10 points bonus.
  • This assignment will contribute 20% to your overall mark.
  • This assignment is redeemable. However, we strongly suggest that you do this assignment. The results of this assignment will help you understand how much you have understood the materials. If you get< 55 in this assignment, it is an indication that you will likely have trouble in this class.
• Discussion with your colleagues are allowed and encouraged. However, you still need to work on the assign- ment on your own AND write the names you discussed this assignment with.

Revisions:

• 13 Aug: The time limit for Part B Q3 should be

(7 #suburbslog(#suburbs)
100 , 000 +^0.^07

)

ms CPU time (the constant addition
is 0. 07 and NOT 0. 7 ). The time limit in the test-cases are correct.

• 13 Aug: Add initial for Part A Q2a.
• 12 Aug: File name requirement in point 2 of Notes should be the same as the requirements in Part B.
• 6 Aug: Fig. 1, swapWandL.

[40 pts] Part A

1. [10 pts] Rank the following functions by increasing order of growth, and explain your ordering.
   • f 1 (n)=

√

2

√n

• f 2 (n)=(logn)π
• f 3 (n)=n(5 logn) 2
• f 4 (n)=πn
• f 5 (n)=

∑i=n
i= 1 c·i

(^2) , wherecis a positive constant.

2. [10 pts] Please find the asymptotic upper bound of the following recurrences and please make the bound as tight as possible. (a) [5 pts]T(n)=T(bn 3 c)+T(bn 6 c)+n

√

lognwith initialT(1),T(2),T(3),T(4),T(5)being a constant value.
Hint: Master method can help.

(b) [5 pts]T(n)=T(n−1)+nwith initialT(1)= 1.

3. [20 pts] LetAbe a sorted (ascending) sequence ofnunique integers, wheren= 2 bandbis a natural number. Given a numberkwhereA[1]≤k≤A[n]. Please: (a) [10 pts] Develop a pseudo code that in the worst case takesO(logn)to find the indexiwhereA[i]=kor output null ifkis not inA. (b) [10 pts] Show that the algorithm you developed in 3a indeed have the worst-case running time complexity ofO(logn).

[60 pts] Part B: Where should the Light Rail Network be Placed?

Figure 1:An illustration of Light Rail Network plan at AIT.

Congratulations!!! Your company has won a project to develop a light rail network in a town called AIT (AIT Is a Town), and you have been assigned to this massively profitable project!

Your first task (which is this assignment) is to decide where the light rail network should be located. To help make the decision, AIT’s town council has pro- vided you with an overview of the town, which is as follows:

• AIT occupies an axis-aligned rectangular area of sizeL×W. The lower left corner of the town’s area is at coordinate(0,0).
• AIT contains several suburbs. Each suburb has a center, and the center of each suburb can be thought of as a point, located at coordinate(x,y).
• The position of the suburbs’ centers are uniformly distributed inside theL×Warea of AIT.
• The centers of two or more different suburbs can be co-located.

Now, regarding the light rail network. For simplicity, one can assume that the light rail network is a line segment. Furthermore, the AIT’s town council requires that the light rail network should be a straight line segment parallel to theXaxis, from the left to the right border of AIT. For accessibility purposes, the center of each of AIT’s suburb will be linked to the light rail network via a highway. The highway will be a straight line segment parallel to theYaxis, starting at the suburb center and ending at the light rail network. Figure 1 provides an illustration. Due to budget constraints, the light rail network should be located so as to minimize the total length of the highways that connect each AIT’s suburb to the rail network.

When your boss found out about the above characteristics and requirements, she jumped in excitement because they are very similar to the many other light rail network development projects that your company is about to embark on. In fact, the differences are only in the size of the town, number of suburbs, and their locations. Therefore, to maximize the company’s profit, she requested that you develop a program that can provide the solution to the above problem in a relatively general manner, allowing it to decide the optimal position of the light rail networks in different towns.

Your tasks

To develop the program that reliably solve the above problem, please:

1. [10 pts] Formulate the problem, i..e., please provide the input and output specifications of the algorithm, along with explanation on your formulation. Hint: You can sum up the optimality criteria into a simple one.
2. [25 pts] Design a deterministic algorithm to solve the above problem in timeΘ(nlogn), wherenis the number of suburbs. Please provide: (a) [5 pts] The pseudo code of the algorithm. (b) [5 pts] Derivation of the time complexity of your algorithm. (c) [10 pts] Implementation of your algorithm. Please name the program A1-basic-[studentID].cpp Program Marking: If your program compiles and runs, you will get 1 point. We will then run your

program on 6 test cases: 2 cases would have up to 1,000 suburbs, 2 cases would have 1,001 – 1,000,
suburbs, and 2 cases would have 1,000,000 – 500,000,000 suburbs. For each test case, your program will
be given

(7 #suburbslog(#suburbs)
100 , 000 +^0.^7

)

ms CPU time to find a solution. The time limit will be rounded up to
2 decimal digit. You can assume your program will have access to at most 12GB RAM. It will be run as
a single thread process on a computer with Intel i7 3.4GHz processor. Tips: Be careful not to use arrays
allocated in the program stack (you might want to use std::vector than array). For each test case that your
program solves correctly within the given time and memory limit, you will get 1.5 points.
Examples of the test cases are available in
https://cs.anu.edu.au/courses/comp3600/a1-testCases.zip.
(d) [5 pts] Experimental analysis of the time complexity of your algorithm and analysis against the theoretical
analysis (2b). You will likely need to generate test cases for this. Please submit your test cases for
this analysis together with your source codes. Please note that the maximum file size you can upload is
200MB.

3. [25 pts] We discussed in class that randomized algorithm can often speed-up an algorithm. Similarly in this case, randomization can be used to develop a solution whose average time complexity is linear in the number of suburbs. Please provide: (a) [5 pts] The pseudo code of the algorithm. (b) [5 pts] Derivation of the average time complexity of your algorithm. (c) [10 pts] Implementation of your algorithm. Please name the program A1-random-[studentID].cpp Program Marking: Same as 2c. However, the time limit provided will be

(7 #suburbs
100 , 000 +^0.^07

)

ms CPU
time. The time limit will be rounded up to 2 decimal digit.
(d) [5 pts] Experimental analysis of the time complexity of your algorithm and analysis against the theoretical
analysis (3b). You will likely need to generate test cases for this. Please submit your test cases for this
analysis together with your source codes.

4. [Optional, Bonus: 10 pts] Can you develop a deterministic algorithm that solves the above problem inΘ(n), wherenis the number of suburbs? If you can, please provide the algorithm and derivation of its time complex- ity. Otherwise, please explain why it is impossible.

Input to the Program

The program will accept a single argument, which is the name of the input file. The input file containsn+ 1 lines, wherenis the number of suburbs in a town. The first line consists of three numbers, separated by a white space. The first number isL, the second number isW, and the last number is the number of suburbs in the town. Each line in the nextnlines consists of two numbers, separated by a white space. They represent thexandycoordinate of each suburb center in the town.

Example: 5 6 3 1 2 3 1 4 5 MeansL= 5 ,W= 6 , and there are 3 suburbs in AIT. The center of these suburbs are at(1,2),(3,1), and(4,5).

Output of the Program

A single line containing a single number, which is theYcoordinate of the light rail network.

Example the output of the example input is: 2