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 exceptmath 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

or break it down with an intermediate assignment

Note that you are neverrequired 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:

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:

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 events i 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 sequence b if b is at least as long asa and the last len(a) elements of b are exactly the elements in a (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 sequence a 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:

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:

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:

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 log2 n + n2

Question 9

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

Question 10

T(n) = 10 + log3(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:

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 list lst, identify the tightest simple bound of the worst-case computational complexity in terms of the input size n = len(lst) and justify your    answer.

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.

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.

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.