Faculty of Information Technology

EXAM CODES:                FIT1045

TITLE OF PAPER:            Alg & prog funda in python

EXAM DURATION:           2 hours 10 mins

Rules

During an exam, you must not have in your possession any item/material that has not been authorised for your exam. This includes books, notes, paper, electronic device/s, mobile phone, smart watch/device, calculator, pencil case, or writing on any part of your body. Any authorised items are listed below. Items/materials on your desk, chair, in your clothing or otherwise on your person will be deemed to be in your possession.

You must not retain, copy, memorise or note down any exam content for personal use or to share with any other person by any means following your exam.

You must comply with any instructions given to you by an exam supervisor.

As a student, and under Monash University’s Student Academic Integrity procedure, you must undertake your in semester tasks, and end-of-semester tasks, including exams, with honesty and integrity. In exams, you must not allow anyone else to do work for you and you must not do any work for others. You must not contact, or attempt to contact, another person in an attempt to gain unfair advantage during your exam session. Assessors may take reasonable steps to check that your work displays the expected standards of academic integrity.

Failure to comply with the above instructions, or attempting to cheat or cheating in an exam may constitute a breach of instructions under regulation 23 of the Monash University (Academic Board) Regulations or may constitute an act of academic misconduct under Part 7 of the Monash University (Council) Regulations.

Instructions

This exam tests theoretical concepts of the lecture as well as your capability to understand Python syntax and write programs to solve problems.

All Python code you write is understood to be Python 3 code. Note that, unless specified otherwise, your code responses are not allowed to import any modules except math and copy.

To answer a question that requires a code response, use 4 spaces to represent each indentation level. Do not use the Tab key to indent, as this will not indent and instead move you to the next field.

The exam is structured in three parts assessing learning outcomes of the three levels “application”, “analysis”, and “synthesis”, respectively. The weight between these three parts is as follows:

● Part 1: 20 marks (recommended writing time 35 minutes)

● Part 2: 27 marks (recommended writing time 45 minutes)

● Part 3: 23 marks (recommended writing time 40 minutes)

Instructions

Information

This exam tests theoretical concepts of the lecture as well as your capability to understand Python syntax and write programs to solve problems.

All Python code you write is understood to be Python 3 code. Note that, unless specified otherwise, your code responses are not allowed to import any modules exceptm ath and copy.

To answer a question that requires a code response, use 4 spaces to represent each indentation level. Do not use the Tab key to indent, as this will not indent and instead move you to the next field.

The exam is structured in three parts assessing learning outcomes of the three levels “application”, “analysis”, and “synthesis”, respectively. The weight between these three parts is as follows:

    Part 1: 20 marks (recommended writing time 35 minutes)

    Part 2: 27 marks (recommended writing time 45 minutes)

    Part 3: 23 marks (recommended writing time 40 minutes)

Part 1 - Application (20 marks)

Information

Part 1 - Application
In this part you are supposed to demonstrate your basic understanding of concepts taught in the unit by applying them directly to simple examples.

The recommended writing time for this part is 35 minutes.

Information

Python Fragment Formulation (Questions 1 to 4)

In this group of questions you are asked to produce short pieces of Python code. When you are asked to "write a Python expression" that evaluates to a specific concept you can either give the expression in one line or break it down into several lines where you assign intermediate concepts to variables. In any case, the last expression you write must represent the required concept.

For example, if the questions asks you to "write Python expression that corresponds to the arithmetic mean of two numbers a and b", you could give a one line expression

(a + b)/2

or break it down with an intermediate assignment

s = a + b   s/2

Note that you are never required to use the print function.

Question 1

Assume that a, b, and c are variables that refer to integer objects and consider the Python expression:

a-(b**(c-1))

Give an equivalent version of this expression by removing as many parentheses as possible.

Question 2

Assume the variables starts and ends refer to lists of start and end times of a set of events (given according to some fixed order of the events). Here, the times are given as integers referring to the number of days from a specific starting date. For example:

starts = [10, 15, 28, 23]   ends = [17, 16, 31, 30]

In this example, event 0 started at day 10 and ended at day 17 and so on.

We say that two events overlap if there is at least one day that both events have in common. For instance in the above example the events 0 and 1 as well as the events2 and 3 overlap.

Now assume that i and j are arbitrary indices corresponding to two events. Give a Python expression that evaluates to True of and only if eventsi and j are non-overlapping, i.e., there is no day during which both events were active.

Question 3

A king in chess can move exactly one square in an arbitrary direction (vertical, horizontal, or diagonal). This means that in the following situation the two kings do not attack each other.

Assume we have four variables c1, r1, c2, r2 that refer to positive integers representing the position of two kings on a chess board. Give a Python expression that evaluates to True if and only if the two kings attack each other (we can assume that the two positions are not equal).

Question 4

A sequence a is called a suffix of sequenceb if b is at least as long asa and the last len(a) elements of b are exactly the elements ina (in the right order). For instance:

● 'old' is a suffix of 'uphold'

● [1, 2, 3] is not a suffix of [2, 3]

Give a Python expression that evaluates to True if and only if a sequencea is a suffix of the sequence b.

Information

Apply Algorithm (Questions 5 - 7)

The following questions ask you to manually apply an algorithm introduced in the lecture and demonstrate your understanding by describing intermediate states of the computation.

Question 5

Write down the list content at the end of each iteration of the main loop of Selection Sort for the following list:

[6, 3, 10, 4, 2, 7]

Use one line for each intermediate list content.

Question 6

Apply Depth First Search (DFS) to traverse the following graph. Start your traversal from vertex 0, and write down the order in which vertices will be visited during the traversal.

Question 7

Consider the binary search algorithm given in the lecture slides using the following parameters:

seq = [2, 3, 5, 7, 7, 12, 15, 18, 26, 27, 50]   v = 7

Show the search region of the binary search algorithm at the start of each iteration. Use curly brackets to indicate the start and end of the region. For the example given above, the initial iteration has the following search region:

[{2, 3, 5, 7, 7, 12, 15, 18, 26, 27, 50}]

Moreover, write the value that will be returned from the algorithm.

Information

Big-oh Notation (Questions 8-11)

For each of the time complexities in this segment give the tightest bound in terms of a simple poly-logarithmic function using big-oh notation.

Note: use the ‘^’ symbol to indicate exponents, i.e., write O(n^2) for O(n2).

Question 8

T(n) = 3n log n + n

Question 9

T(n) = n/2 + log(10n)

Question 10

T(n) = 10 + log (2n) + 10(n % 2)

Question 11

T(n) = log(n)(n - 1)/2

Part 2 - Analysis (27 marks)

Information

Part 2 - Analysis

In this part you are required to utilise concepts from the unit to analyse algorithms, computational problems, and more broadly algorithmic design questions.

The recommended writing time for this part is 45 minutes.

Information

Discussion of Theoretical Concepts (Questions 12-14)

For each of the questions in this section, we are looking for a short answer of around 3-5 sentences. Try to be precise and coherent and use the technical terms covered in the unit where relevant.

Question 12

Consider the following greedy algorithm for the Traveling Salesperson Problem that accepts as input a cost/distance matrix costs and greedily computes a tour starting from vertex0 and selecting in each iteration an unvisited vertex of minimum cost (distance) from the current end-point of the tour:

def greedy_tsp(costs):       res = [0]       while len(res) < len(costs):           best = None           for i in range(len(costs)):               if i not in res and \               (not best or costs[res[-1]][best] > cost[-1][i]):                   best = i           res += [best]       return res += [0]

Demonstrate that this algorithm is not guaranteed to find an optimal tour by providing an example input and pointing out the difference between the optimal tour and the one found by the greedy algorithm.

Hint: It is enough to consider problem inputs consisting of 4 points (i.e., the cost matrix has 4 rows and 4 columns).

Question 13

When eliminating a specific matrix column with the Forward Elimination algorithm (as part of Gaussian Elimination) we can run into the situation that the diagonal element of this column is 0. Why is this a problem? How does Forward Elimination solve this situation? And why is this solution correct?

Question 14

Assume we already know that the following variant of the Hamiltonian Cycle is NP-complete.

A: Hamiltonian Cycle (Adjacency List)

Input: Adjacency list of graph G

Output: True if G contains a Hamiltonian Cycle;False otherwise

How can we demonstrate that this also implies the NP-completeness of the closely related problem where we provide the given input graph as adjacency matrix, i.e., the problem:

B: Hamiltonian Cycle (Adjacency Matrix)

Input: Adjacency matrix of graph G

Output: True if G contains a Hamiltonian Cycle;False otherwise

Recall that the adjacency list of a graph is a list of lists adj_list such that adj_list[i] contains the neighbours of vertex i. As size of the input for problem A we consider the number of vertices plus the sum of the lengths of the individual adjacency lists (i.e., the number of vertices plus two times the number of edges). As size of the inputs for problem B we consider the size of the adjacency matrix (i.e., the square of the number of vertices).

Note: We assume that we already know that Problem B is in NP.

Hint: How could you polynomially reduce one problem to the other? Which direction do you need? Why is the reduction polynomial?

Information

Computational Complexity (Questions 15-17)

For each of the following functions identify the tightest simple bound (using big-oh notation) of the worst-case computational complexity in terms of the input size and justify your answer. Depending on the specific function this justification could be based on one or more of:

● structural properties of the worst-case input for a given input size (e.g., "in the worst case the input list is inversely ordered")

● what line(s) is/are dominating the overall computational cost and

● additional arguments as necessary.

If helpful to make your argument, you can copy+paste the code of the function into your response to annotate individual lines with comments.

Question 15

For the following function that accepts as input a listlst, identify the tightest simple bound of the worst-case computational complexity in terms of the input size n = len(lst) and justify your answer.

def pick_selection(lst):     selection = []     n = len(lst)     k = n//2     i = 0     while i < k:       selection.append(lst[i])       i += 1     return selection

Question 16

For the following function that accepts as input a listlst, identify the tightest simple bound of the worst-case computational complexity in terms of the size of the input n = len(lst) and justify your answer.

def pick_selection2(lst):     selection = []     n = len(lst)     k = n//2     i = 0     while k >= 1:       i += k       k //=2       selection.append(lst[i])     return selection

Question 17

For the following function that accepts as input a listlst, identify the tightest simple bound of the worst-case computational complexity in terms of the size of the input n = len(lst) and justify your answer.

def is_every_second_unique(lst):     n = len(lst)     for i in range(1,n,2):       if lst[i] in lst[i+1:n]:         return False     return True

Information

Invariants (Questions 18 and 19)

For each of the following functions, identify the loop invariant, the loop exit condition, and the loop post-condition which shows the algorithm’s correctness.

You can simply list the assertions, or you can copy and paste the function into the answer field and add assertion annotations as comments, as shown in the lecture.

Question 18

For the following function, identify the loop invariant, the loop exit condition, and the loop post-condition which shows the algorithm’s correctness.

def sum_minutes(list_of_minutes):       """       Input: A list list_of_minutes of non-negative integers       Output: Two non-negative integers (total_hours, total_minutes),       such that the sum of all numbers in list_of_minutes is       total_hours*60 + total_minutes, and total_minutes < 60.       For example:       >>> sum_minutes([32,45,3,67])       (2, 27)       """       total_hours, total_minutes = 0, 0       while len(list_of_minutes) > 0:           total_minutes += list_of_minutes.pop()           if total_minutes >= 60:               total_hours += 1               total_minutes -= 60       return (total_hours, total_minutes)

Question 19

For the following function, identify the loop invariant, the loop exit condition, and the loop post- condition which shows the algorithm’s correctness.

def even_length(lst):       """       Input: A list lst of items       Output: True if len(lst) is even, False otherwise.       For example:       >>> even_length([1,2,3,4])       True       >>> even_length([1,2,3,4,5])       False       """       is_even = True       while len(lst) > 0:           lst.pop()           is_even = not is_even       return is_even

Part 3 - Synthesis (23 marks)

Information

Part 3 - Synthesis

In this part you are required to solve algorithmic problems. This may involve understanding new definitions as well as problem statements and inputs.

Note: Carefully check the instructions of the individual questions. In addition to writing Python programs, some questions may require you to also provide additional text explaining and analysing your solution.

The recommended writing time for this part is 40 minutes.

Information

Advanced Problem Solving: Bike Lanes (Questions 20-21)

City halls around the country want to introduce bike lanes to their local street network. They want to do that in a way that connects all major points of interest in their city but at the same time disrupts the car traffic as little as possible. For that the total distance covered by bike lanes should be minimised. Moreover, they want to offer a web page that allows bike riders to obtain a route between any two points of interest that only uses street segments with bike lanes.

Your company aims to design algorithms for both problems: a) the selection of street segments that should be equipped with bike lanes and b) finding bike routes in the corresponding sub network.

Question 20

You realise that the first problem (choosing street segments to be equipped with bike lanes) is a minimum spanning tree problem that can be solved with Prim’s minimum spanning tree algorithm. You remember this algorithm from your FIT1045 unit at Monash:

def min_extension(con, g):       min_weight = inf       for i in con:           for j in range(len(g)):               if j not in con and 0 < g[i][j] < min_weight:                   v, w = i, j                   min_weight = g[i][j]       return v, w   def mst(graph):       “””I: edge-weighted graph (as weighted adjacency matrix)           O: adjacency matrix of minimum spanning tree of graph“””       tree = empty_graph(len(graph))       con = [0]       while len(con) < len(graph):           i, j = min_extension(con, graph)           tree[i][j], tree[j][i] = graph[i][j], graph[j][i]           con += [j]   return tree

However, to produce a convenient input for the second part of your task, you want to modify the algorithm a bit.

Write a function mst(g) that accepts as input the adjacency matrix of a weighted graph and produces as output the parent list of a rooted MST of the represented graph (the root can be an arbitrary vertex). Explain the required modifications to the lecture algorithm in two sentences (either in the doc string or as separate text).

For the example graph shown below (assuming all edges having weight 1), if the spanning tree on the right is found, then the returned parent list is [None, 0, 1, 0, 1].

Question 21

In this question, we provide an algorithmic solution for the bike routing problem once a (rooted) tree of bike lanes is available.

Write a function route(a, b, tree) with

Input: two vertices (integers) a and b in a rooted tree T represented by a parent listtree.

Output: the unique path (as list of vertices) froma to b in T.

and give a short explanation for your approach.

For the trees shown in the image below, for example, the behaviour would be as follows:

>>>route(4, 3)   [4, 1, 0, 3]   >>>route(4, 2)   [4, 1, 2]

Hints:

● Start with explaining your approach; a correct approach is already worth up to 5 of the 10 marks for this question.

● Consider first the simplified situation where you assume that the path from a to b runs through the root of the rooted tree, as in example 1 below (a correct explanation plus implementation under this assumption is worth up to 5 marks).

● Then, consider what changes if the path does not run through the root? Can you find another vertex that takes the role of the root in the simplified case? See example 2 below.

Question 22

Paul is a teacher who just finished grading the final exam in a class. He has a list of the students’ scores on the final exam in a particular order (not necessarily sorted), and he wants to reward his students. He has planned to reward his students fairly based on these two rules:

1. All students must receive at least one reward.

2. Any given student must receive strictly more rewards than an adjacent student (a student immediately to the left or to the right) with a lower score and must receive strictly fewer rewards than an adjacent student with a higher score.

Write a function rewards(scores) that takes in a list of scores and returns a list of rewards that has a minimal sum while satisfying the two rules above. Assume that all the students have different scores.

For example:

>>> rewards([8, 4, 2, 1, 3, 6, 7, 9, 5])   [4, 3, 2, 1, 2, 3, 4, 5, 1]   >>> rewards([0, 4, 2, 1, 3])   [1, 3, 2, 1, 2]

Before writing your function, give at least one paragraph with an explanation of your implementation. You can write this paragraph before or after the function or also as a docstring.

Hint/suggestion: can you design a main loop with the invariant that, after iterationi , the temporary solution satisfies the two rules up to (inclusive) index i?