NAME: __ __

# CSE 331

Algorithms and Complexity

# Sample Final Exam: Spring 2020

A. Erdem Sariyuce May 4, 2020

DIRECTIONS:

Closed Book, Closed Notes except for two 8 __1__ ”* ×*11”

review sheet.

Time Limit: 2 hours 30 minutes.

• Answer the problems on the exam paper.

• Each problem starts on a new page.

• Make sure you write your NAME on the paper.

• If you need extra space use the back of a page.

• Problem 6 is a bonus problem.

• Keep your desk clear of everything else other than the exam paper, review sheets and writing imple- ments.

FEW GENTLE REMINDERS/SUGGESTIONS:

• You can quote any result that we covered in class or any problem that was there in a homework (but remember to explicitly state where you are quoting a result from).

• If the question does not specifically ask for a formal proof, just a correct proof idea should fetch you at least 80% of the points.

• If you get stuck on some problem for a long time, move on to the next one.

• The ordering of the problems is somewhat related to their relative difficulty. However, the order might be different for you!

• You should be better off by ** first reading all questions **and answering them in the order of what you think is the easiest to the hardest problem. Keep the points distribution in mind when deciding how much time to spend on each problem.

• Spend time on the bonus problem only if you are done with the rest of the exam.

• Finally, relax and enjoy the exam! (If not, think of a time when you’ll be done with 331!)

1.

(5 2 = 10 points) Answer True or False to the following questions. ** No justification **is required. (Recall that a statement is true only if it is logically true in all cases while it is false if it is not true in some case).

(a) BFS is a linear time algorithm.

** True False **(Please

**your answer)**

**CIRCLE**(b) Every undirected connected graph on * n *vertices has exactly

*1 edges.*

*n −*** True False **(Please

**your answer)**

**CIRCLE**(c) If all the edge weights of an undirected connected graph * G *are distinct, then

*G*has a unique minimum spanning tree.

** True False **(Please

**your answer)**

**CIRCLE**(d) Given * n *numbers

*1*

*a**, the median of the smallest ten numbers and the largest ten numbers among them can be computed in*

*, . . . , an**(*

*O**) time.*

*n*** True False **(Please

**your answer)**

**CIRCLE**(e) The * maximum *spanning tree problem (i.e. given a connected undirected weighted graph output a spanning tree with the maximum weight) is an NP-complete problem. (Recall that we have shown that the

*spanning tree problem is in P.)*

*minimum*** True False **(Please

**your answer)**

**CIRCLE**1.

(5 6 = 30 points) Each of the questions below has two parts. For the first part, you need to give a justification for the statement and is worth 2 points. For the second part, answer True or False and briefly JUSTIFY your answer. A correct answer with no or totally incorrect justification will get you 1 out of the total 4 points. ** An incorrect answer irrespective of the justification will get you **0

**4**

**out of****. You**

**points***assume part 1 when answering part 2 but to get credit for part 1, you*

*can**to answer part 1. (Recall that a statement is true only if it is logically true in all cases while it is is false if it is not true in some case).*

*have*(a) (** Part 1**) Argue why the following statement is

**.**

**TRUE**If * f *(

*) =*

*n**(*

*c · g**), then 2*

*n**(*

*f**) = (2*

*n**(*

*g**))*

*n**for every real number*

*c**.*

*c*(** Part 2**) Is the following statement true or false? Remember to briefly JUSTIFY your answer.

2* O*(

*) is*

*n**(2*

*O**). (Or more precisely, every function*

*n**(*

*f**) that is 2*

*n**(*

*O**) is also*

*n**(2*

*O**).)*

*n*** True False **(Please

**your answer)**

**CIRCLE**(b) (** Part 1**) Argue why the following statement is

**.**

**TRUE**Given * n *positive integers

*1*

*a**such that each*

*, . . . , an**(1); they can sorted in*

*ai nO** O*(

*log*

*n**) time.*

*n*(** Part 2**) Is the following statement true or false? Remember to briefly JUSTIFY your answer.

Given * n *numbers

*1*

*a**, where for every 1*

*, . . . , an**,*

*i n**5*

*ai**9*

*,**100 ; their sorted order can be output in*

*,**(*

*O**) time.*

*n*(See next page)

** True False **(Please

**your answer)**

**CIRCLE**(c) (** Part 1**) Argue why the following statement is

**.**

**TRUE**Given two numbers with * n bits*, they can be multiplied in

*(*

*O**3*

*n**2) time.*

*/*(** Part 2**) Is the following statement true or false? Remember to briefly JUSTIFY your answer.

Given two numbers with * n octal *digits (i.e. the numbers are in base 8), they cannot be multiplied in time asymptotically faster than

*(*

*O**2).*

*n*** True False **(Please

**your answer)**

**CIRCLE**(d) (** Part 1**) Argue why the following statement is

**.**

**TRUE**Given an undirected graph with * n *nodes and

*edges with positive integer weights (that are polynomially in*

*m**large) and two distinct vertices*

*n**=*

*s ̸**, the shortest*

*t**path can be computed in*

*s − t**((*

*O**+*

*m**) log*

*n**) time.*

*n*(** Part 2**) Is the following statement true or false? Remember to briefly JUSTIFY your answer.

Given an undirected unweighted graph * G *in

*vertices and*

*n**edges and two distinct vertices*

*m**=*

*s ̸**, the shortest*

*t**path can be computed in*

*s − t**(*

*O**+*

*m**) time.*

*n*** True False **(Please

**your answer)**

**CIRCLE**(a) (** Part 1**) Argue why the following statement is

**.**

**TRUE**Let * G *be a connected graph where each edge was weight 1. Then any BFS tree is an MST for

*.*

*G*(** Part 2**) Is the following statement true or false? Remember to briefly JUSTIFY your answer.

Let * G *be an undirected connected graph. If

*has a unique minimum spanning tree, then all the edge weights in*

*G**are distinct.*

*G*** True False **(Please

**your answer)**

**CIRCLE**1.

(25 points) You’re given the Internet as a graph * G *= (

*) such that*

*V, E**=*

*V**and*

*n**=*

*E**. (Assume*

*m**is connected.) Further for each edge*

*G**, you’re given it’s probability 0*

*e E**1 that it’ll transmit a packet (or equivalently, it is the probability it will not*

*pe**). Further, the probabilities are*

*fail**, i.e. given a path with edges*

*independent** e*1

*, the probability of that the entire path does not fail is given by ∏*

*, . . . , eℓ**.*

*ℓ pe*Design an * O*(

*log*

*m**) time algorithm, which given two distinct vertices*

*n**=*

*s**, outputs the*

*t V**path with the largest probability of not failing. (If you were deciding to route packets from*

*s t**to*

*s**, you should use this path.)*

*t*For simplicity, you can assume that each * pe *is a power of

__1__. For example, in the graph

below,

The path * s, u, t *has a probability of not failing of

__1__

*×*__1__=

__1__, while the path

*has*

*s, w, t*a probability of not failing of __1__ *× *__1__ =__ 1__ . Thus, your algorithm should output * s, w, t*.

Argue the correctness of your algorithm (formal proof is not required). Also briefly justify the run time of the algorithm.

(* Hint: *It

*be useful to transform the input and then apply a known algorithm on the transformed input. Further, these identities might be useful: log(*

*might**) = log*

*ab**+ log*

*a**and log(*

*b**) = log*

*a/b**log*

*a**. (These identities hold irrespective of the base in the logarithms and hence are not explicitly stated.))*

*b*1. (20 points) (This is an CS job interview question.) Given two arrays * A *and

*each with*

*B**numbers*

*n**1*

*a**and*

*, . . . , an**1*

*b**respectively, the algorithm needs to output the order*

*, . . . , bn**1*

*a**1*

*, b**2*

*, a**2*

*, b**. E.g. if*

*, . . . , an, bn**= 4 and*

*n**= (1*

*A**3*

*,**5*

*,**7) and*

*,**= (2*

*B**4*

*,**6*

*,**8), then the output is (1*

*,**2*

*,**3*

*,**4)(5*

*,**6*

*,**7*

*,**8). The output must be in the same array as the input. You can think of the input as an array of size 2*

*,**which contains*

*n**and*

*A**and your algorithm must rearrange these values as specified.*

*B*What makes the problem interesting that you are only allowed * O*(log

*) amount of*

*n**. By temporary space, I mean the total amount of space among all data structures and temporary variables*

*temporary space**the arrays*

*except**and*

*A**. In particular, the output has to be written in*

*B**and*

*A**.*

*B*Give an * O*(

*log*

*n**)-time algorithm that uses*

*n**(log*

*O**) temporary space. To receive full credit, you must fully specify your algorithm. Argue why your algorithm is correct and justify the running time and temporary space usage of your algorithm.*

*n*(* Note: *If you present an

*(*

*O**2) time algorithm with*

*n**(log*

*O**) temporary space or a*

*n**(*

*O**log*

*n**) time and*

*n**+*

*n**(1)-temporary space algorithm then you can get at most 5 points.)*

*O*(* Hint: *It

*be useful to think of a divide and conquer algorithm.)*

*might*2.

(15 points) Recall that the Bellman-Ford algorithm for input graph * G *= (

*) with costs*

*V, E**in each edge*

*ce**builds an*

*e ∈ E**matrix*

*n×n**such that*

*M**[*

*M**] for 0*

*i, u**1 and*

*≤ i ≤ n−**contains*

*u ∈ V**(*

*OP T**), i.e. the cost of a shortest*

*i, v**path using at most*

*u − t**edges (for a given target*

*i**). In particular, it computes*

*t ∈ V** M *[

*] = min*

*i, u**[*

*M**1*

*i**]*

*, u**min*

*,**[*

*M**1*

*i**] +*

*, w**(*

*c**)*

*u,w*

*.** u,w*)

*∈E*In class we discussed a way to compress the matrix above: if * M *[

*] =*

*i, u**[*

*M**1*

*i**], then we do not need to explicitly store*

*, u**[*

*M**]. In this problem, you will show that even with this compression idea a naive implementation of the Bellman-Ford algorithm still needs to store Ω(*

*i, u**2) entries. (Recall that in class we later saw that the algorithm only needs to store two columns at a time– what this problem is saying that the idea of*

*n**will not give you any benefit over the naive algorithm.)*

*compression alone*In particular, define an entry (* i, u*) to be

*, if*

*fresh**[*

*M**]*

*i, u**[*

*< M**1*

*i**]. For every large enough*

*, u**1 show that there exists a problem instance to the shortest path problem (with possibly negative weights but not negative cycle) on*

*n**vertices such that Ω(*

*n**2) entries in the matrix*

*n**as computed by the Bellman-Ford algorithm are fresh. (*

*M**: If you present an example for any fixed*

*Note**4 such that the matrix has*

*n ≥**has*

*M*at least * n*(

*1)*

*n −**2 fresh entries, then you can get up to 3 points.)*

*/*3. (** Bonus**) (2 points) Given an

*(*

*O**) time,*

*n**(log*

*O**) temporary space algorithm to solve the problem from Q4.*

*n*(* Hint: *You’ll need to formally prove the correctness of your algorithm. Also no partial credit on this one.)

(** Fun Question**) Write a limerick or a joke that is relevant to the course. Should you accept this task, also let me know if you are OK with me posting your entry on the course piazza (assuming of course I like it!) If I post your entry, I’ll put in your name too (if you prefer to remain anonymous on piazza, let me know).