CSE 101 Practice Final Fall 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 101 Practice Final Fall 2021
1: True/False: For each of the following answer “True” or “False” and give a brief explanation (1 or 2 lines or sentences.)
1. DFS on a dense graph (lEl = Θ(lV l2 ) has runtime Θ(lV l2 )
2. Suppose f(n) and g(n) are positive-valued increasing integral functions. If 2f (n) e O(2g(n)) then f(n) e O(g(n))
3. If a connected undirected graph has two edges that both have the minimum weight then the graph has 2 distinct MSTs.
4. If a problem is in NP then there is no known polynomial time algorithm to solve it.
5. If you perform explore on a DAG starting at a source vertex, then all vertices will be marked as visited.
6. If an undirected connected graph has a cycle, and e is the unique lightest edge of that cycle, then e is part of all MSTs.
7. n + (n x 2) + (n x 4) + ...2 e O(n).
8. 2n + 2n − 1 + 2n −2 + ...1 e O(2n ).
9. It is always better to use a heap than an array as the data structure in Dijkstra’s algorithm.
2: Paths in Graphs 1 Give an O(lEl+lV l) algorithm, possibly using known algorithms from class as sub- routines, to tell, given a directed graph G and two vertices s and t, whether there is a not-necessarily simple path from s to t whose length is a multiple of 3. You can use without proof the correctness and time analysis of algorithms covered in class, but need to relate the above problem to the algorithms in question.
3: Paths in Graphs 2 Suppose you are on a road trip driving from point A to point B. There are several scenic routes you would like to drive through but they are time consuming so you actually only want to drive through exactly one. Design a reasonably efficient algorithm that, given a directed graph G = (V, E), a subset S C E, a starting vertex A and an ending vertex B, will determine if there exists a path from A to B that goes through exactly one edge in S .
4: shortest paths in graphs Given an undirected graph G with positive edge lengths and an edge e, design an algorithm that returns the length of the shortest cycle containing e that runs in O(lV l2 ) time.
5: Divide and Conquer 1: Consider the following problem: You are given a pointer to the root r of a binary tree, where each vertex v has pointers v.lc and v.rc to the left and right child, a positive weight w(v), and each edge points from parent to child. The value NIL represents a null pointer, showing that v has no child of that type. You wish to find the total weight of the heaviest path starting from the root that uses an even number of edges
Design a divide and conquer algorithm to do this (you may assume that the graph is complete and the bottom level is filled.
6: Divide and Conquer 2: Given a sorted array of n distinct integers (negative or positive) A[1, 2, 3, . . . , n], design an algorithm that determines if there exists an integer i such that A[i] = i in O(log n) time.
7: Greedy algorithm: In the pretty printing problem, you are given a list of lengths of words, positive real numbers w1 , w2 , ..wn , that must be printed in order, but can be broken up into lines in different ways with a maximum page width of M characters.
For Example: Suppose the words are “The lazy brown fox jumped over the fence”. If all characters have the same size, and we don’t count spaces, we’d have the list 3 , 4, 5, 3, 6, 4, 3, 5. Say M = 10. Then we could break them up as
T h e L a z y
B r o w n F o x
J u m p e d O v e r
T h e F e n c e
The slack of a line is the amount of empty spaces left over. In the above example, the slacks are 3, 2, 0, 2.
The penalty of a placement is the sum of all slacks. For the above example, the penalty would be 3 + 2 + 0 + 2 = 7.
1. Fill out the rest of this solution specification: (4 points)
● Instance: List of word lengths w1 ...wn with wi > 0 and M > max(wi ).
● Solution Format: Sequence of indices: (i1 , i2 , . . . , ik ) so that Line 1 consists of the words (w1 , . . . , wil ), Line 2 consists of the words (wil +1 , . . . , wi2 ), ..., Line k + 1 consists of the words (wik +1 , . . . , wn ).
● Constraints:
● Objective:
2. Candidate Greedy Strategy: Place words on the first line while the total is less than M . Then move on to the second line, and repeat until all words are assigned lines.
Show that this greedy strategy is optimal using the exchange argument (you do not need to provide the full strong induction proof here).
8: Dynamic Programming 1: You are Batman. You are located in the North-West corner of an n · m grid of city blocks (rows numbered from 1 to n and columns numbered from 1 to m.) Each city block has a building within it. The building located in the (i, j) city block has a height of H[i, j] meters. You are equipped with a bat-glide cape. With this bat-glide cape, you can jump and soar from a taller building to a shorter building. The wind is blowing from West to East so each jump must be any direction due east, north-east or south-east for any distance (the only constraint is that you must travel at least one column east). Each building has a citizen in danger. Your goal is to save the maximum number of citizens in danger. (your algorithm should run in O(n2 m2 ) time.)
9: Dynamic Programming 2 Suppose you have two sequences of positive integers A[1, . . . , n] and B[1, . . . , n]. A common subsequence of A and B is sequence that is a subsequence of both A and B. (Note: subsequences do not have to be consecutive.) You wish to find the weight of the heaviest common subsequence. The common subsequence between A and B that has the maximum sum of entries. For example: If the two sequences are:
(1, 2, 1, 2, 30, 1, 2) and (1, 30, 2, 1, 2, 1, 2)
Then the heaviest common subsequence is: (1, 30, 1, 2) with a weight of 34. (Note that this is different than the longest common subsequence.)
2021-12-07