Learning Outcomes

This assignment achieves the Learning Outcomes of:

.  1) Analyse general problem solving strategies and algorithmic paradigms, and apply them to solving new problems;

.  2) Prove correctness of programs, analyse their space and time complexities;

.  3) Compare and contrast various abstract data types and use them appropriately;

. 4) Develop and implement algorithms to solve computational problems.

In addition, you will develop the following employability skills:

. Text comprehension.

.  Designing test cases.

. Ability to follow specifications precisely.

Assignment timeline

In order to be successful in this assessment, the following steps are provided as a suggestion. This is an approach which will be useful to you both in future units, and in industry.

Planning

1.  Read the assignment specification as soon as possible and write out a list of questions you have about it.

2. Try to resolve these questions by viewing the FAQ on Ed, or by thinking through the problems overtime.

3. As soon as possible, start thinking about the problems in the assignment.

. It is strongly recommended that you do not write code until you have a solid feeling for how the problem works and how you will solve it.

4. Writing down small examples and solving them by hand is an excellent tool for coming to a better understanding of the problem.

.  As you are doing this, you will also get a feel for the kinds of edge cases your code will have to deal with.

5. Write down a high-level description of the algorithm you will use.

6.  Determine the complexity of your algorithm idea, ensuring it meets the requirements.

Implementing

1.  Think of test cases that you can use to check if your algorithm works.

.  Use the edge cases you found during the previous phase to inspire your test cases. .  It is also a good idea to generate large random test cases.

.  Sharing test cases is allowed, as it is not helping solve the assignment.

2.  Code up your algorithm  (remember decomposition and comments), and test it on the tests you have thought of.

3. Try to break your code.  Think of what kinds of inputs you could be presented with which your code might not be able to handle.

. Large inputs

.  Small inputs

. Inputs with strange properties

. What if everything is the same?

. What if everything is different?

. etc...

Before submission

. Make sure that the input/output format of your code matches the specification.

.  Make sure your filenames match the specification.

.  Make sure your functions are named correctly and take the correct inputs.

.  Remove print statements and test code from the file you are going to submit.

Documentation

For this assignment (and all assignments in this unit) you are required to document and com- ment your code appropriately. Whilst part of the marks of each question are for documentation, there is a baseline level of documentation you must have in order for your code to receive marks. In other words:

Insufficient documentation might result in you getting 0 for the entire question for which it is insufficient.

This documentation/commenting must consist of (but is not limited to):

. For each function, high-level description of that function.  This should be a two or three sentence explanation of what this function does.

. Your main function in the assignment should contain a generalised description of the approach your solution uses to solve the assignment task.

. For each function, specify what the input to the function is, and what output the function produces or returns (if appropriate).

. For each function, the appropriate Big-O or Big-Θ time and space complexity of that function, in terms of the input size.  Make sure you specify what the variables involved in your complexity refer to.  Remember that the complexity of a function includes the complexity of any function calls it makes.

. Within functions, comments where appropriate.  Generally speaking, you would comment complicated lines of code (which you should try to minimise) or a large block of code which performs a clear and distinct task (often blocks like this are good candidates to be their own functions!).

A suggested function documentation layout would be as follows:

There is a documentation guide available on Moodle in the Assignment section, which contains a demonstration of how to document code to the level required in the unit.

1    Question  1: Fast Food Chain

(10 marks, including 2 marks for documentation)

Burger Queen, a popular chain of fast food restaurants, is planning to open its restaurants along a newly built freeway.  They have identified N potential sites along the freeway such that the distance between every two consecutive sites is exactly 1 km.  They have also estimated the expected annual revenue generated by each site if a restaurant is opened at the site.  Due to different demographics and locations, each site may generate a different annual revenue.  It is company policy that no two restaurants can be within d kms of each other.  They have hired you to help them choose the sites to open restaurants such that no two restaurants are within d kms of each other and the overall revenue is maximised.  The company has an unlimited budget and they are happy to open any number of restaurants as long as no two restaurants are within d kms of each other.

You need to write a Python function named restaurantFinder(d,site_list) which takes two arguments:  d  is the distance parameter d; and site_list is a list of size N containing annual revenue (in million dollars) for each site, i.e., ith  number in the list is ri  denoting the annual revenue of the site i if a restaurant is opened at the site.  site_list contains the sites in the order they appear along the freeway, e.g., for each i, the distance between ith  and (i + x)th site is x kms.  You can assume that d is always a non-negative integer and site_list always contains at least 1 site.

The function must return a tuple (total_revenue,  selected_sites) where selected_sites is a list containing the site numbers where the company should open their restaurants to max- imise the revenue.  The list selected_sites must contain the site numbers in ascending order. total_revenue is the total annual revenue if the company opens restaurants at the sites in selected_sites.

Your function must solve the problem using O(N) space and O(N) time in the worst-case.

1.1 Example

Below is a sample input.

The above input shows that the value of d is 1 and there are 10 sites in total. Annual revenue of the first site is 50, for the second site is 10 and soon.

Below are some sample outputs for different values of d but the same list of sites..

If there  are  more than one possible  answers  (e.g.,  multiple  ways  to  achieve  the  maximum revenue), you can return any of the answers.

2    Question 2:  Climb King

(10 marks, including 2 marks for documentation)

One day, a tower appeared out of nowhere with the message – “Reach the top of the tower and your wish will be granted”.  Thus, everyone flocked to the entrance of the tower hoping to have their wish granted. You are one such adventurer, hoping to see the night sky at the top of the tower.

To your surprise, there is a map that shows the layout of floors of the tower.  For example, the first floor map shows that:

. There are |V | locations in the map.

. The entrance is shown in the map. This is where you enter the floor, there is only one entrance to the floor.

. There can be 1 or more exits shown in the map.  This is where you will always exit to the next floor.

.  There are |E| edges that connect the locations of a floor together.

. You can go from location-u to location-v, if a path e = (u,v) exists.  However, you can not go from location-v to location-u unless the opposite path e′ = (v, u) exist as well in the map.

. It would take x-minutes to traverse that specific path e = (u,v, x).  The time to traverse each path could vary, and would be stated in the map itself.

Thus, you would want to use the map to reach an exit as fast as possible.  However, you noticed strange markers in the map:

. There are |K| keys positioned at certain locations in the map.

. A key is needed in order to move on to the next floor. Without a key, you are powerless at the any of the exits location. You can exit the floor using any key.

.  Each key is however defended by a monster. It would take y-minutes to defeat the monster a retrieve the key.  This vary depending on keys, but you would always need to defeat a monster!  Eventually...  The map automatically calculates this based on your current capabilities.  In other words, you would be given the time it would take you to defeat a monster defending a key.

.  If you are at the same location as that of a key, you can choose not to engage with the monster and continue moving along path.  In other words, if you choose to fight the monster, you will be able to collect the key but will spend y minutes defeating the monster and getting the key.  If you choose not to fight the monster, you do not need to spend any time but you will leave the location without getting the key.

The start and exits changes every time you enter the floor.   However,  the map remains unchanged.  Thus, this causes a challenge for the adventurers.  Unlike them, you are a SSS- ranked computer scientist, with the power of algorithms and data structures – to climb the tower as fast as possible, computing the fastest path to go from the start to one of the exits. You would model the floor map using the graph ADT as follow:

2.1 Graph Data Structure

You must write aclass FloorGraph that represents the map of a floor.

The __init__ method of the FloorGraph would take as an input a list of paths represented as alist of tuples (u,v, x) where:

. u is the starting location ID for the path. This is anon-negative integer. . v is the ending location ID for the path. This is anon-negative integer.

. x is the amount of time needed to travel down the path from location-u to location-v. This is anon-negative integer.

. You cannot assume that the list of tuples is in any specific order.

. You cannot assume that the paths are 2-way paths.

. You can assume that the location IDs are continuous from 0 to |V | − 1 where |V |  is total number of locations.

. You can assume that all locations are connected by at least 1 path.

. The total number of paths |E| can be significantly smaller than |V | 2  and therefore you should not assume that |E| = Θ(|V | 2 ).

The init method of the FloorGraph also takes as an input a list of keys represented as a list of tuples (k, y) where:

.  k is the location ID where a key can be found in the floor.  This is anon-negative integer. . y is the amount of time needed to defeat the monster and retrieve the key if you choose

to fight the monster. This is anon-negative integer.

. You cannot assume that the list of tuples is in any specific order.

. You can assume that all of the k values are from the same set as the location ID, that is from the set of {0, 1, 2, ..., |V | − 1}.

. You can assume that each of the k values in the list keys list is unique.

Consider the following example in which the paths and keys arestored as a list of tuples:

There area total of 5 paths, connecting a total of 4 locations from ID 0 to 3 in the floor.  The first tuple (0, 1, 4) can be read as – there is a path from location-0 to location-1 and traversing this path takes 4 minutes.

There area total of 3 keys in the floor.  The key in location-0 requires 5-minutes to collect, the key in location-3 requires 2 minutes to collect and the key in location- 1 requires 3 minutes to collect.

Running the following code would create a FloorGraph object. We visualised the graph below for your viewing with the keys location underlined; you do not need to visualize the graph in your solution.

2.2 Optimal Route Function

You would now proceed to implement climb(self,  start,  exits) as afunction within the FloorGraph class. The function accepts 2 arguments:

.  start is anon-negative integer that represents the starting point in the floor. You begin from here and there is only a single start only in the floor.

.  exits is a non-empty list of non-negative integers that represents the exit points in the floor, in order to move on to the next floor.

. Do note that it is possible for the keys to be in the same location as the start and/or exits. As stated earlier, you can choose to spend time to engage the monster and collect the key, or to not waste any time and travel along another path without collecting the key.

This function would return one shortest route from start to one of the exits points that leads to the next floor. This route would need to include defeating one monster and collecting the key in order to go up to the next floor.  Thus the function would return a tuple of  (total_time, route):

. total_time is the time taken to complete the route.

. route is the shortest route as a list of integers that represent the location IDs along the path.  If there are multiple routes that satisfy the constraints stated, return any one of those routes.

If no such route exist, then the function would return None.

Several examples are provided in Section 2.3.