Loyola University Chicago



DG 2.16 infinite array increasing, eventually inifinity, O(log n) to find x or say not thereBinary search2.19 k way mergeGreedy DG 5DG 5.3 approx: linear time or lower? Kruskal without lengths min even lower with right seqOr just BFS until repeat a vertex5.7 max spanning treeDG 2.13 recursion order inequlities full tree countB1 = 1B3 = 1 B5 = 2B7 = B1*B5 + B3*B3 + B5*B1 = 5Show B(2n+1) in Omega(2^n)B9 = 2*(1*5 + 1*2) = 14B11 = 2*2 + 2(14 + 5) = 432*1(e(n-1)) + 2*1*e(n-2) + 2*5*e(n-3)) works with base 3- - - - - - - - - -We are given a checkerboard which has 4 rows and n columns, and has an integer written in each square. We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or vertically adjacent squares (diagonal adjacency is fine). (a) Determine the number of legal patterns that can occur in any column (in isolation, ignoring the pebbles in adjacent columns) and describe these patterns. Call two patterns compatible if they can be placed on adjacent columns to form a legal placement. Let us consider subproblems consisting of the first k columns 1 ≤ k ≤ n. Each subproblem can be assigned a type, which is the pattern occurring in the last column. (b) Using the notions of compatibility and type, give an O(n)-time algorithm for computing an optimal placement. - - - - - - - - -Let us define a multiplication operation on three symbols a, b, c according to the following table; thus ab = b, ba = c, and so on. Notice that the multiplication operation defined by the table is neither associative nor commutative. * abca bbab cbac accFind an efficient algorithm that examines a string of these symbols, say bbbbac, and decides whether or not it is possible to parenthesize the string in such a way that the value of the resulting expression is a. For example, on input bbbbac your algorithm should return yes because ((b(bb))(ba))c = a. - - - - - - - - - - -Consider the task of searching a sorted array A[1 . . . n] for a given element x: a task we usually perform by binary search in time O(log n). Show that any algorithm that accesses the array only via comparisons (that is, by asking questions of the form “is A[i] ≤ z?”), must take Ω(log n) steps. - - - - - - - - - - -Pouring water. We have three containers whose sizes are 10 pints, 7 pints, and 4 pints, respectively. The 7-pint and 4-pint containers start out full of water, but the 10-pint container is initially empty. We are allowed one type of operation: pouring the contents of one container into another, stopping only when the source container is empty or the destination container is full. We want to know if there is a sequence of pourings that leaves exactly 2 pints in the 7- or 4-pint container. (a) ?Model this as a graph problem: give a precise definition of the graph involved and state the specific question about this graph that needs to be answered. (b) ?What algorithm should be applied to solve the problem? (c) ?Find the answer by applying the algorithm. HW10 wrapupFrom HW9:8.1:7 chessmovesDynamic!Problem SSee MultMatParen.pngSee multMat2.pyCode!Hotels how write?Display my Python hotelspart.pyI did not finish problem U, but the duplicate substring problem is really close to the palindrome problem that I did completely. Maybe come back but not now.Amortize!Counter:Linked list of bits, going as far as needed. Can add 1 or reset to 0Show you can amortize the time for each step to O(1).Actual time depends on how many carries.Big hint? How many 1’s can you set in an increment operation? How many 1’s can you unset?- - - - - - - - - - -How would you modify Dijkstra's algorithm, so the asymptotic order does not change, and you still find the length of a shortest path to each reachable vertex from starting vertex s. Plus now in addition for each vertex v also find the minimum number of edges among all paths to v with the minimal length.For example, if v is one of the vertices, and the minimum path length from s to v is 17, and there are four paths of that length to v, two with 3 edges, and others with 5 and 6 edges, then the algorithm should calculate for v: minimum length 17, and minimum number of edges 3.- - - - - - - - - - -Show that any array of integers x[1 ... n] can be sorted in O(n+M) time, whereM = max{xi’s}?min{xi’s} For small M , this is linear time: why doesn’t the Ω(n log n) lower bound apply in this case?Proof or counterexample. Always assume that the graph G = (V, E) is undirected. Do not assume that edge weights are distinct unless this is specifically stated.(a) If graph G has more than |V | ? 1 edges, and there is a unique heaviest edge, then this edge cannot be part of a minimum spanning tree.(b) If the lightest edge in a graph is unique, then it must be part of every MST.(c) The shortest path between two nodes is necessarily part of some MST.(d) (For any r > 0, define an r-path to be a path whose edges all have weight < r.) If G contains an r-path from node s to t, then every MST of G must also contain an r-path from node s to node t.(e) Suppose you are given a distinguished vertex s and where all edge weights are positive and distinct. Is it possible for a tree of shortest paths from s and a minimum spanning tree in G to not share any edges? If so, give an example. If not, give a reason. - - - - - - - - - Consider the following game. A “dealer” produces a sequence s1 · · · sn of “cards,” face up, where each card si has a value vi. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume n is even.(a) Show a sequence of cards such that it is not optimal for the first player to start by picking up the available card of larger value. That is, the natural greedy strategy is suboptimal.(b) Give an O(n2) algorithm to compute an optimal strategy for the first player. Given the initial sequence, your algorithm should precompute in O(n^2) time some information, and then the first player should be able to make each move optimally in O(1) time by looking up the precomputed information. - - - - - - - - - - a. Suppose you are updating the in-tree structure shown below in our usual form. Though no arrows are shown, assume each edge points upward. The rank of each tree is shown by its root. Completely redraw or clearly modify the picture to show the results after find(D); find(M); union(A, E). As in class assume the versions of these operations where find does compression and union uses the ranks. If the end of any edge you draw is not clearly higher than its starting point, put an explicit arrowhead on it to show the direction.Clearly note removal of current edges if you modify the figure in place. b. Finally, what is the rank of the one tree after the union? - - - - - - - - -The task dependency graph belpw shows the time needed to complete each node. The arrow A → B, indicates that A depends on B (and B must be completed first). What is the minimum time to complete all tasks?? What is the critical path, in time order, starting from the first task that needs to be completed? Minimum time ____ Critical path __________- - - - - - - - - - - -Let G(V, E) be a connected undirected graph. A breadth-first search starting from a vertex v visits v, then all vertices 1 step from v, then all other vertices 2 steps from v, …. The BFS determines a breadthfirst search tree. The remaining edges of G are all cross edges. Suppose uw is a cross edge and vertex u is k steps from v. Explain clearly why the vertex w must be k-1, k, or k+1 steps from v. Examples are not a sufficient answer. - - - - - - - - - - - Use the B-tree algorithm from the class web notes to delete the number 5 and then delete the number 80 (in that order, though the order should not matter) from the 2-3-tree in the diagram below. Draw the cumulative changes clearly. If you modify the current tree, cross out the obsolete parts clearly, and clearly link in the new parts above and below. Alternately, if you prefer, you may also totally rewrite the B-tree diagram. Be sure to follow our standard convention that the link to a child node clearly emanates from the appropriate place: an end of the parent node or from in between two data values. Recall that a 2-3-tree may have either one or two data values in any node. Again, note that you both need to end up with a legal 2-3 tree and follow the delete algorithm order from class twice.- - - - - - - - - - - - Consider either of the equivalent implementations of recursive function f below, Python or Java/C#. Let E(n) be the exact number of evaluations of seq elements in the execution of f(seq, step, n), where step can be any legal value – the value of step does not affect the number of evaluations of elements in seq. Complete an exact recurrence relation for E(n). You just need to write the recurrence relation, not solve it or determine its order. One small detail: remember the floor function notation ? ?.E(0) = 0E(n) = _______________________ for n > 0# Pythondef f(seq, step, n): '''seq is a list of integers; step is the integer index increment n is the number of indices to consider (outside of the recursion). Assume step*(n-1) is always less than the length of the list seq.''' if n == 0: return 0 tot = 0 for i in range(n): tot += seq[i*step] return (tot + f(seq, step, n//3) + f(seq, step*2, n//3) + f(seq, step*3, n//3))// Java/C#: step is the index increment inside int array seq// n is the number of indices to consider (outside of the recursion).// Assume step*(n-1) is always less than the length of the array seq.static int f(int[] seq, int step, int n){ if (n == 0) return 0; int tot = 0; for(int i = 0; i < n; i++) tot += seq[i*step]; return (tot + f(seq, step, n//3) + f(seq, step*2, n//3) + f(seq, step*3, n//3));} ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download