(a) Suppose you work for a major airline and are given the job of writing the algorithm for processing upgrades into first class on various flights. Any frequent flyer can request an upgrade for his or her up-coming flight using this online system. Frequent flyers have different priorities, which are determined first by frequent flyer status (which can be, in order, silver, gold, platinum, and super) and then, if there are ties, by length of time in the waiting list. In addition, at any time prior to the flight, a frequent flyer can cancel his or her upgrade request (for instance, if he or she wants to take a different flight), using a confirmation code they got when he or she made his or her upgrade request. When it is time to determine upgrades for a flight that is about to depart, the gate agents inform the system of the number, k, of seats available in first class, and it needs to match those seats with the k highest-priority passengers on the waiting list. Describe a system that can process upgrade requests and cancellations in O(log n) time and can determine the highest-priority flyers on the waiting list in O(k log n) time, where n is the number of frequent flyers on the waiting list.

1. Consider the digraph shown above. 1a. Give its strongly connected components. 1b. Draw its component graph.

2. Find the max-flow in the flow network shown above using the Ford-Fulkerson algorithm, starting from the flow indicated in the figure. The notation used is: An are with a label a/b has current flow a and a maximum capacity of b. (Thus, the existing flow has a flow value of 3 units.) Draw the residual network after every augmentation.

3. Consider the following 2-CNF formula: F = (-a V b)^(-bVc) ^ (cV b) ^ (bV-d) ^ (e Vb) ^ (Ve) • 3a. Draw the digraph corresponding to F. •3b. Use the digraph to prove that F is satisfiable, and find a satisfying assignment to F. • 3c. Further use the digraph to list all satisfying assignments to F.

4. Consider the following problem. The input is a target string T of length n and a set of words W = {₁,...,} of total length L (i.e., if | denotes the length of word w, then L = as a sequence of words from W. -1 ₁|w₂]). We want to know if T can be written For example, the target string T-abbababa with W = {abba, ab, aba, bab} can be written as ab+bab+aba. But the target string T-abbaba cannot be written in such a way. (These two examples have m=4, L=12, and n = 8 for the first one and n = 6 for the second one.) Show an algorithm that decides in polynomial time whether T can or cannot be written as a sequence of words from W. Hlint: Try a dynamic programming approach. Also state the worst-case running time of your algorithm as a function of n, m and/or L.

3. (a) Suppose G is a graph with n vertices and medges. Describe a way to represent Gusing O(n + m) space so as to support in O(log n) time an operation that can test, for any two vertices and w, whether and ware adjacent.

1. (a) Show that we can solve the telescope scheduling problem in O(n) time even if the list of n observation requests is not given to us in sorted order, provided that start and finish times are given as integer indices in the range from 1 to n².

Exercise 4. DYNAMIC PROGRAMMING. Suppose that we are given the coordinates of the n vertices of a convex n-sided polygon. We are to triangulate the polygon by drawing n - 3 nonintersecting diagonals, where a diagonal is a line segment that connects two non-adjacent vertices. The value of a triangulation is the sum of the lengths of the n-3 diagonals. A triangulation is optimal if it minimizes this value. The objective is to find an optimal triangulation as described by its n-3 diagonals. Show how dynamic programming leads to an O(n³) time solution, assuming a RAM model of computation.

Exercise 3. LINEAR VECTOR RECURRENCES. Let xn and yn be integer-valued sequences, with xo = yo = x1 = y₁ = 1. We have the general recurrence

Exercise 2. MATRIX MULTIPLICATION. Assume a RAM model of computation. The purpose is to derive efficient algorithms for multiplying an n × k matrix A with a k × n matrix B. The resulting matrix, C = AB is of dimension n xn. Grade school multiplication can be done in time (n²k), where now both n and k can be large. Suggest more efficient methods for all choices of k and n, paying, in particular, attention to the cases k = o(n), and n = o(k).