Reading Questions from Algorithms by Dasgupta, Papadimitriou, and Vazirani

• Chapter 0.0-0.4:
  Read through problem 0.4 (pages 9-10) attempting the first few parts and writing down questions about the parts you are having difficulty with. Bring this to class with you!
• Chapter 1.1-1.2:
  Give the complexity of each of the following algorithms.
  1. addition
  2. multiplication
  3. division
  4. modular addition
  5. modular multiplication
  6. modular exponentiation
  7. Euclid's Algorithm
  8. Extended Euclid's Algorithm (Hint: you'll have to do a little thinking/close reading for this one.
  9. Modular division
  Make sure to write down your answers and bring them to class!
• Chapter 1.3:
  
  1. Why is not practical/feasible/possible to use Fermat's Little Theorem to prove that a number N is prime, especially when N is large? Provide two different reasons if you are able.
  2. If I want to be 99% certain that a number is prime, how many times do I have to run the algorithm in Figure 1.7. (Alternatively, what value of k do I need to use in the algorithm in Figure 1.8?)
• Chapter 1.4:
  
  1. What is the difference between private-key and public-key cryptography?
  2. Given the RSA public key (91,7),
     1. Encrypt x=23.
     2. What are p and q?
  3. Given p, q, and e, describe what you need to do to compute d.
• Chapter 2.1-2.3:
  
  1. Explain clearly why multiplying by a power of two can be accomplished in linear time.
  2. Read the gray box on pages 52-53 (An n log n lower bound for sorting). Explain why they say that the tree described has to have at least n! leaves instead of exactly n! leaves?
  3. We rarely talk about lower bounds on algorithms. Why is it sometimes useful? For instance, you just read that the lower bound for sorting is n log n. What implications does this have?
  4. Does the iterative-mergesort algorithm on page 51 work if n is not a power of 2? If so, does the algorithm do exactly the same thing as the recursive one or is there a difference? If it is different, explain how.
• Chapter 2.4-2.5:
  
  1. The Median finding algorithm similar to one of the sorting algorithms we discussed in CSCI235. Which one? How is it different?
  2. Use the Master Method to solve the recurrence relation at the bottom of page 55.
  3. Verify that the lower right corner of XY is really P₁+P₅-P₃-P₇. That is, show that it is equal to CF+DH.
  4. Use the Master Method to verify that the solutions to the two recurrence relations on page 57 are what they say they are.
  5. What do you think about the reading questions so far?
• Chapter 3.1-3.2:
  
  1. Give the adjacency matrix representation for the graph in Figure 3.1b on page 81.
  2. Give the adjacency list representation for the graph in Figure 3.1b on page 81.
  3. How long does it take to determine if two vertices are adjacent if you are given an adjacency list? What if you are given an adjacency matrix?
  4. How long does it take to iterate over the neighbors of a vertex if you are given an adjacency list? What if you are given an adjacency matrix?
  5. Which is better, the adjacency matrix representation or the adjacency list representation. Justify your choice.
  6. Use the algorithm in Figure 3.3 on page 84 on the graph in Figure 3.1b on page 81, giving the result as a tree similar to the one shown in Figure 3.4 on page 85. Assume the adjacency lists are all in numerical order.
  7. What do you get when you add the number of tree edges and the number of back edges?
• Chapter 3.3-3.4:
  
  1. Identify the tree edges, forward edges, back edges, and cross edges in Figure 3.7. (In my version of the book there seems to be a missing dashed edge from A to F.)
  2. Briefly describe two algorithms to linearize (or topologically sort) a dag.
  3. The definition of connectivity/connected given near the bottom of page 91 actually defines an equivalence relation on the vertices of the graph. Explain why the three required properties hold.
  4. The book mentions that three very different sounding properties all turn out to be equivalent. Which properties are they and what does it mean that they are equivalent?
  5. When discussing finding connected components, the book makes a big deal about running explore from a sink component. Why is that important?
• Chapter 4.1-4.3:
  
  1. On pages 105-106 they outline an inductive proof for the correctness of BFS. Try to write down a complete proof. More importantly, make sure you are convinced of the correctness of the algorithm.
  2. Run BFS on the graph from Exercise 3.31 on page 102 starting at node D. Either label each node with its distance from D or draw the shortest-path tree.
  3. Come up with an example of a problem that can be modeled using a weighted graph that was not mentioned in the textbook. Clearly indicate what the weights mean and what a solution to the problem means.
• Chapter 4.4-4.5:
  First, a clarification from the reading: The "alarm clock algorithm" discussed on page 109 in run on the original graph G to simulate BFS being run on G'.
  1. Are BFS and Dijkstra's algorithms interchangeable? That is, do they both solve the same problem? Explain.
  2. Can Dijkstra's algorithm be used to compute the shortest path in an unweighted graph? If so, explain what changes, if any, would be necessary.
  3. Assuming you answered the previous question with "yes", is it a good idea to use Dijkstra's algorithm instead of BFS to determine shortest path in an unweighted graph? Explain your answer.
  4. If a binary heap has 25 elements, what is its height and how many nodes are on each level?
• Chapter 4.6-4.7:
  Textbook Error: In Figure 4.12, edge (B,A) is supposed to have weight -2, not 2.
  1. Explain why Dijkstra's algorithm does not work properly if a graph has negative weight edges.
  2. Explain why finding the shortest path in a graph doesn't make sense if the graph has negative wieght cycles.
  3. Run the algorithm in Figure 4.15 (page 119) on the graph from Exercise 4.1 (page 120), starting from A.
  4. Can the Bellman-Ford algorithm be run on the graph from Exercise 4.1 (page 120)? Explain.
  5. Can the algorithm in Figure 4.15 (page 119) be run on the graph from Exercise 4.2 (page 120)? Explain.
  6. Can Dijkstra's algorithm be run on the graph from Exercise 4.2 (page 120)? Explain.
• Chapter 5.1:
  
  1. Let's start out simple: How many edges does a tree with n vertices have?
  2. Explain what the cut property is and how it helps to construct an MST.
  3. If you understand the cut property, then you realize it allows the creation of greedy algorithms by selecting certain edges of the graph to add to an MST.
     1. How does Kruskal's algorithm select edges to include in an MST?
     2. How does Prim's algorithm select edges to include in an MST?
• Chapter 5.2:
  (Note: You can ignore the gray boxes in this section).
  1. Is Huffman encoding a good idea if the characters in a file all occur with approximately equal frequencies? If so, explain why. If not, what would be a better encoding?
  2. Is the tree in Figrue 5.10 optimal? Explain.
  3. Find an optimal encoding for a file with letters A, B, C, D, and E with frequencies 10, 50, 15, 45, and 35. What is the total number of bits required using your encoding?
  4. How many different optimal encoding can you think of for the previous problem. (Hint: Does "flipping" subtrees change the optimality of the solution? What other ways are there to modify it?)
• Chapter 5.3:
  
  1. Is the formula from the example on page 145 satisfiable? Clearly explain.
• Chapter 5.4:
  
  1. Explain the sentence at the bottom of page 146 to the top of page 147. In particular, what is the proper justification for the statement? (Hint: think back to 255.)
  2. Does the greedy algorithm for set cover guarantee an optimal solution? If so, explain. If not, what guarantee(s) does it give?
  3. Read the section again so you understand the proof the of the claim on pages 146-147. Hint: You will probably need to write down some math to justify a few of the steps. Also remember that you are allowed to work together and discuss reading questions.
• Chapter 6.1-6.3:
  
  1. Run the algorithm in the middle of page 158 on the graph at the top of the page. For each node, keep track of both L(j) and the previous node (as suggested on page 159).
     1. Give the values L(j) that result.
     2. How do you determine the length of the longest path from the L(j) values?
     3. What is the length of the longest path?
     4. Give the longest increasing subsequences using the previous node information. Is your solutiont the same as the one given on the bottom of page 157? Explain why or why not.
  2. True or false: A plain-jane algorithm that solves a problem by computing the optimal solution of subproblems using recursion usually leads to an efficient dynamic programming solution. Explain your answer. (Hint: Did you read the gray box on page 160?)
  3. Is it true that a solution to the shortest edit distance corresponds to a path in the "underlying DAG" (e.g. Figure 6.5) that has the maximal number of dotted lines? Explain.
• Chapter 6.4:
  
  1. What's your favorite color?
  2. What's your favorite number?
  3. What is the airspeed velocity of an unladen swallow?
  4. What do you get if you multiply 6 by 9?
• Chapter 6.5:
  
  1. If I have a 30x45 matrix and a 45x8 matrix, how long does it take to multiply them?
  2. Given the matrices in Figure 6.6, what is the cost to multiply them using parenthesization (((AxB)xC)xD)?
  3. If I have matrices A, B, and C with sizes 10x5, 5x15, and 15x12, is it cheaper to compute (AxB)xC) or (Ax(BxC)?
• Chapter 6.6:
  
  1. On page 172 they finish the discussion of shortest reliable path with the phrase "Need we say more?" In fact, they do need to say more. Describe how to compute the values of dist(v,i) efficiently, including what order to compute them and how to iterate over the edges. Also give the complexity of the resulting algorithm.
  2. Read the Warshall's algorithm notes linked on the course website. Then re-read the section on all-pairs shortest path (pages 172-173). Explain the similarities and differences between these two algorithms.
  3. Assume you have the set A={1,2,...,n}.
     1. How many subsets does A have?
     2. How many subsets of size k does A have?
     3. How many subsets that contain the number 1 does A have?
• Chapter 7.1:
  Note: Make sure you read the gray box on page 198 that discusses Matrix-vector notation.
  1. Given the following constraints, draw the feasible region: x ≤ 50, y ≤ 75, x+y ≤ 75, x≥ 0, y ≥ 0. Don't forget to shade the feasible region. (Note to self: Change x+y ≤ 75 to x+y ≤ 85 in the future.)
  2. There are 24 hours in a day. I can spend my time sleeping, working, or playing. I have to work between 4 and 10 hours a day and sleep at least 5 hours a day. I cannot play more than 12 hours a day. Playing is twice as fun as sleeping and sleeping is 3 times as much fun as working. I want to have as much fun as possible. Express this as a linear program.
  3. Try to find a solution to the linear program from the previous question. You may use online tools, etc. to assist you. Give the URL of the tool you used or specify what you used (e.g. Excel).
  4. The example in section 7.1.2 has 74 variables. How many constraints does it have?
  5. For the linear program one page 191 (above Figure 7.2), what are the matrices c, x, A, and b? (See the gray box on the top of page 198.)
  6. Bonus: If you can find a nice tool to draw the feasible region in 3 dimensions, send me a link.
• Chapter 7.2:
  
  1. Find the maximum flow for this network.
  2. Give the minimum cut that corresponds to the maximum flow from the previous question. (A cut should be given by specifying two sets of vertices corresponding to the two "sides" of the cut.)
  3. Explain what it means that flow is conserved at each vertex.
  4. If edge (a,b) in a network has capacity 7, is it possible to send 5 units from a to b, then send 3 units from b to a and finally send 4 units from a to b without violating the capacity of the edge? Explain. Also explain why this is an important question.
• Chapter 7.3:
  
  1. Give the perfect matching for the problem in Figure 7.7.
  2. Show the maximum flow in the network in Figure 7.8 corresponding to the matching from Figure 7.7. (Draw the network with the edges that have flow being darker).
• Chapter 7.4:
  
  1. In a few sentences, explain what the dual of a linear program (LP) is, how it relates to the original LP, how the optimal solutions of both relate to each other, and what the significance of this relationship is.
• Chapter 7.5:
  
  1. Explain why Column can always win rock-paper-scissors if Row announces that she intends to always pick rock.
  2. If Row plays rock 50% of the time, paper 25% of the time, and scissors 25% of the time, what strategy should Column use to win the most often? Should Column play randomly (and if so, give probabilities for each choice) or is it best for Column to pick one choice and stick with it (if so, specify what choice)?
  3. Calculate the expected payoff for Column's optimal strategy from the previous question. You will need to use the formula from page 210, filling in the appropriate values for the x_i and y_j
  4. In the second example, they declare that the value of the game is 1/7. Explain how we can be certain of this. In your answers, you should discuss the connection to linear programming and duals.
• Chapter 7.6:
  
  1. Describe how the simplex algorithm works at a high level. You should be able to describe it in a sentence or two.
  2. Imagine you apply the simplex algorithm to the LP on page 191 (Section 7.1) starting at the origin and you release the constraint on x₃.
     1. Which constraint will you hit first?
     2. What value will x₃ be?
     3. What is the vertex? That is, give (x₁,x₂,x₃).
     4. The initial vertex (the origin) is given by the final three equations, x₁,x₂,x₃≥ 0, (which looks like one equation but is just shorthand for 3 equations). What three equations yield the point after this first step?
  3. On page 220, they mention that there cannot be more than C(n+m,n) vertices (where C(m+n,n) is m+n choose n, the binomial coefficient which I can't seem to figure out how to draw in HTML). Explain why.
• Chapter 7.7:
  
  1. What is the output of the circuit on page 221?
• Chapter 8.1:
  
  1. Let k be a constant. Why are algorithms that are O(n^k) considered efficient, but algorithms that are O(kⁿ) are not?
  2. Find a solution to the problem from Figure 8.4 or explain why it does not exist.
  3. Find the largest independent set from Figure 8.5.
  4. Find the smallest vertex cover in Figure 8.5.
  5. Find the largest clique in Figure 8.5.
  6. Give a clear definition of search problem. (from the book, not your own!)
  7. Explain the relationship between search problems and optimization problems.
• Chapter 8.2:
  
  1. Give a complete and clear definition of P that someone not in this class could understand.
  2. Give a complete and clear definition of NP that someone not in this class could understand.
  3. Explain the idea of reductions. Specifically, if I have a reduction from A to B and an algorithm to solve B, how can I solve a instance of problem A?
  4. If A is NP-Complete and A → B (there is a reduction from A to B), does that imply that B is NP-Complete? Explain.
  5. If B is NP-Complete and A → B, does that imply that A is NP-Complete? Explain.
  6. If A → B and I have an efficient algorithm to solve A, does that imply an efficient algorithm to solve B? Explain.
  7. If A → B and I have an efficient algorithm to solve B, does that imply an efficient algorithm to solve A? Explain.
  8. Prove or disprove that P=NP, or give a good reason why you cannot.
• Chapter 8.3:
  NOTE: Re-read section Reductions, again on pages 244-245
  NOTE 2: Skip the section ZOE → Rudrata Cycle (middle of 256 to top of 260).
  1. On page 248 under numbered item 2: Clearly state what they are trying to show, what the contrapositive of this is, and why they can prove that instead.
  2. Find a solution to the 3SAT instance and Independent Set instance in Figure 8.8. Then explain how they are related to each other.
  3. Find a solution to the 3D Matching problem and ZOE problem on the top of page 255 and explain how they are related to each other.
• Chapter 9.1:
  
  1. On page 274 they mention that Figure 9.1 gives the conclusion of the earlier example. What is the conclusion and why?
  2. On page 276 they explain that the cost of the rest of the tour is at least the sum of 3 numbers. Explain why this is the case.
  3. Find an online resource that gives a more clear introduction to backtracking algorithms (one that helps you understand it better than the textbook does). E-mail me the URL.
  4. Find an online resource that gives a more clear introduction to branch-and-bound algorithms. E-mail me the URL.
• Chapter 9.2:
  
  1. Do we want α_A to be large or small? Explain.
  2. In section 9.2.1, does the algorithm they give guarantee a solution that is no worse than twice the optimal or no better than? In other words, is it possible that it can produce a solution that is closer to optimal?
  3. What is the value of α_A for the clustering algorithm in section 9.2.2?
  4. Explain why, unless P=NP, there cannot exist an efficient approximation algorithm for the travelling salesman problem. (Hint: see section 9.2.3)
• Chapter 9.3:
  
  1. Explain in a few sentences how local search heuristics work. In particular, what is the main idea behind them and how do you know when to stop?
  2. Do local search heuristics always lead to optimal solutions? Explain.
  3. In section 9.3.1, they describe one problem with a 2-change being that it will not always lead to an optimal solution. So what is the problem with using a k-change for a much larger value of k?