You are given a map of Santorini, a hot destination for summer vacations in Greece. Looking at the map, you soon realize that all streets in the island are one-way. Before booking your tickets, you would like to know if you can still reach any point in the island from any other point.
1. Model this as a graph problem. What are the nodes and edges in the graph? How does the original question translate in graph language?
2. Design an algorithm to solve this problem in O(n + m) time. Prove the correctness and the running time of your algorithm.
3. Due to an unexpected surge of tourists, the local authorities decided to block some streets entirely in an effort to reduce traffic. This had the effect that it is not possible anymore to start at some point u and end back in u. Despite this authorities claim that it is possible to find a point S, so that starting in S you can visit all other points in Santorini exactly once. Design an algorithm to test this claim in time O(n + m). Prove the correctness and the running time of your algorithm.
Fig: 1
4. Consider the following recursive algorithm. ALGORITHM Q(n) //Input: A positive integer if n = 1 return 1 else return Q(n-1) + 2 *n-1/nb. Set up a recurrence relation for the number of multiplications made by this algorithm and solve it. c. Set up a recurrence relation for the number of additions/subtractions made by this algorithm and solve it./n9. Consider the following recursive algorithm. ALGORITHM Riddle(A[0..n-1]) //Input: An array A[0..n-1] of real numbers if n = 1 return A[0] else temp← Riddle(A[0..n -2]) if temp ≤ A[n 1] return temp else return A[n - 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm's basic operation count and solve it.
3. Consider the following recursive algorithm, where array is an array of integers. You can assume that the length of array is a power of two, so len(array) is n = 2m for some m ≥ 0. (a) (1 marks) How many array accesses are made in total by calling squoogle (array)? An array access means that you evaulate array[i] for some i. Write your answer as a recursive formula in terms of m. You can treat the arguments to the recursive calls as if they do not require array accesses to compute. (b) (2 marks) Give a closed-form expression for your formula from part a) in terms of m. Prove your answer is correct using induction. (c) (0.5 marks) What is your closed-form expression from part b) in terms of n, the number of elements in the array?
1. Compute the following sums. a. 1+3+5+7+ +999 b. 2+4+8+16+...+1024 c Σ+1 d. Σ"}; 1. Σ–13+1g. Σ Σ - e Σ"di( + 1) Ξ 2. Find the order of growth of the following sums. Use the Θ(g(n)) notation with the simplest function g(n) possible. a. Σ"=(2+1)2 € Σ=1 + 1)2-1 b. Σ={1gi2 d. Σ. Σ( + 3)/n4. Consider the following algorithm. ALGORITHM Mystery (n) //Input: A nonnegative integer n S←0 for i ← 1 to n do S+S+i*i return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.
5. Consider the following algorithm. ALGORITHM Secret(A[0..n-1]) //Input: An array A[0..n-1] of n real numbers minval A[0]; maxval ← A[0] for i 1 to n - 1 do if A[i] < minval minval ← A[i] if A[i]> maxval maxval ← A[i] return maxval - minval Answer questions (a)-(e) of Problem 4 about this algorithm./n4. Consider the following algorithm. ALGORITHM Mystery (n) //Input: A nonnegative integer n S 0 for i ← 1 to n do S+S+i*i return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.
# Project 3: Griefer list ## Introduction Your job working at the MMORPG is going great. After a recent promotion, you've been assigned a more challenging task. The game has become popular enough to attract large numbers of griefers, which use trial accounts to troll and harass your paying customers. Given that the rules are different on different servers, each server maintains its own ban list. To help server admins out, you want to build a tool that lets them quickly lookup whether a player has been banned and when the most recent ban was. You already have a tool that concatenates all the banlists together and consists of lines with the following format: [USERNAME] [SERVERID] [UNIX_TIME_OF_BAN] Example line: bmrlpmyzybrb 819 1636184756 (the trolls seem to like to use randomly generated names) Your tool will read a single input file consisting of a number of lines like the one above, and will insert the players into a self-balancing tree data structure, organized by user name. Along with the above data (which is stored in a file), your tool will also read a list of names from standard input. For each name, it will print a prepared statement (see sample) that contains the name, the number of servers they've been banned on, and the most recent ban they received. You know that a tree is appropriate for this task as there might be duplicate data, and you want to be able to find spans of names in sorted order later. However, you aren't sure which tree to use. You know that given the large number of inserts into the data structure that a scapegoat tree would be appropriate. However, you want to compare it with at least one of these trees: * AVL tree * Red black tree * B-tree
Exercise 4: 10 Consider the partition problem: given n positive integers, partition them into two disjoint subsets with the same sum of their elements. (Of course, the problem does not always have a/nsolution.) Design an exhaustive-search algorithm for this problem. Try to minil number of subsets the algorithm needs to generate.
2. Suppose you have a row of n + 1 lilypads, and Fred wants to jump on every one of them exactly once. At each jump, he is able to jump one lilypad forward, one lilypad backwards, or two lilypads forward (skipping one). Let f(n) denote the number of ways Fred can jump on each of the n + 1 lilypads, starting at the first lilypad and ending at the n+1th lilypad. (a) (0.5 marks) What are the first six terms in this sequence, starting with f(0)? (b) (2 marks) Give a recursive formula for f(n). Briefly justify why your formula is correct. What is another name for this sequence?
Let A[1 .. n] be an array of n distinct numbers. If i<j and A[i]>A[j], then the pair (i, j) is called an inversion of A. 6a) List the five inversions of the array <2, 3, 8, 6, 1>. 6b) What array with elements from the set {1, 2,..., n} has the most inversions? How many does it have? 6c) What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. 6d) Give an algorithm that determines the number of inversions in any permutation on n elements in O(n lg n) worst-case time. (Hint: Modify merge sort.)
3. Recall that as we discussed in class, there is no known fast algorithm for graph isomorphism, and it is believed that no such algorithm exists. However, it is often possible to solve graph isomorphism quickly if there are restrictions on the types of graphs allowed as input. Your best friend Fred has a proposal for an alternative graph isomorphism algorithm when the input graphs are restricted to be trees. He suggests the following: 1) For each vertex v in G₁, compute deg(v) and append this value to a list L₁. 2) For each vertex v in G₂, compute deg(v) and append this value to a list L2. 3) Sort the lists L₁ and L2 in increasing order. 4) If L₁ and L₂ are the same, reutrn "yes", otherwise return "no”. Does Fred's algorithm work on all possible inputs? You can assume the input graphs are both trees. Prove your answer is correct.
1. The knapsack problem we discussed in class is the following. Given a knapsack of size M and n items of sizes {a₁, a2,..., an}, determine whether there is a subset S of the items such that the sum of the sizes of all items in S is exactly equal to M. We assume M and all item sizes are positive integers. Here we consider the following unlimited version of the problem. The input is the same as before, except that there is an unlimited supply of each item. Specifically, we are given n item sizes a₁, a2,..., an, which are positive integers. The knapsack size is a positive integer M. The goal is to find a subset S of items (to put in the knapsack) such that the sum of the sizes of the items in S is exactly M and each item is allowed to appear in S multiple times. For example, consider the following sizes of four items: {2, 7, 9, 3} and M = 14. Here is a solution for the problem, i.e., use the first item once and use the fourth item four times, so the total sum of the sizes is 2+3 × 4 = 14 (alternatively, you may also use the first item 2 times, the second item one time, and the fourth item one time, i.e., 2 ×2+7+3= 14). Design an O(nM) time dynamic programming algorithm for solving this unlimited knapsack problem. For simplicity, you only need to determine whether there exists a solution (namely, you answer is just "yes" or "no"; if there exists a solution, you do not need to report an actual solution subset).