Programming Resources
For Fun and Learning 		Charles Cusack
Computer Science
Hope College
main
Python
C++
JAVA
PHP
SQL
Assignments

AlgorithmRQs

Description

CSCI 255/385 Reading Questions from various sources

From Algorithms textbook

  • 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 P1+P5-P3-P7. 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 xi and yj
    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 x3.
      1. Which constraint will you hit first?
      2. What value will x3 be?
      3. What is the vertex? That is, give (x1,x2,x3).
      4. The initial vertex (the origin) is given by the final three equations, x1,x2,x3≥ 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(nk) considered efficient, but algorithms that are O(kn) 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?

From A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency (SIPC) textbook

  • Chapter 2-3.3:
    1. Define parallelism and concurrency
    2. If you have a Thread T, what is the difference between calling T.run() and T.start()?
    3. What does it mean that multi-threaded programs are nondeterministic?
    4. What does it mean for a call to a method (e.g. join) to block?
    5. Explain what fork and join mean in the context of parallel programs.
  • Chapter 3.4-3.6:
    1. What is the difference between RecursiveAction and RecursiveTask? When should each be used?
    2. How many ForkJoinPools should your program contain? How many calls to invoke should your program have?
    3. What is a reduction? Give an example of a computation that is a reduction.
    4. What is a map? Give an example of a computation that is a map.
    5. What is a downside of having the number of threads be about the same as the number of processors?
    6. What is the downside of having too many threads?
  • Chapter 4-5.2:
    1. Define each of the following, giving the appropriate notation and/or formula:
      • Work
      • Span
      • Speedup
      • Parallelism
    2. In a sentence or two, what does Amdahl's Law say?
    3. If half of an algorithm cannot be parallized, what is the best speedup you can attain no matter how many processors you have?
  • Chapter 5:
    1. What is the work and span of the parallel-prefix sum algorithm?
    2. What is the work and span of the parallel pack algorithm?
    3. What is the work and span of the parallel quicksort algorithm?
    4. What is the work and span of the parallel mergesort algorithm?
    5. What other parallel algorithm(s) is/are used to implement parallel quicksort?
  • Chapter 6:
    1. What does it mean for calls to interleave?
    2. Why can't you prevent bad interleavings by using a boolean variable that only allows one thread to access a segment of code at a time? (Hint: I should probably used the phrase "attempt to" in the preivous sentence.)
    3. Instead of using a boolean something called locks should be used. Why do they work when boolean variables do not?
    4. If a method is synchronized, what object is used as the lock?
    5. What is a reentrant lock and why are they important?
  • Chapter 7:
    1. Define race condition.
    2. Define bad interleaving.
    3. Define data race.
    4. What must be true of intermediate states for a concurrent program to be correct?
    5. What do compilers potentially have to do with data races?
  • Chapter 8-9:
    1. What are two things you can do (regarding data) to make concurrent programming easier?
    2. Give the 5 synchronization guidelines, including a sentence or two that explains each in a little more detail.
    3. Why didn't we need to worry about synchronization when we discussed algorithms like prefix sum and pack?
    4. Define deadlock.

Reading Questions from other places

  • IPP (Introduction to Parallel Programming) Questions
    Write a 1-2 page summary of the highlights from the reading. It can be in whatever format you find the most helpful. (e.g. a bunch of definitions, bullet points of the highlights, etc.)
  • Mergesort Questions
    1. What is the worts, average, and best case complexity of the Merge algorithm used by Mergesort?
    2. What is the worst, average, and best case complexity of Mergesort?
    3. How much extra memory is needed for Mergesort to sort an array of size n?
    4. Give two ways that Mergesort might be made more efficient.
  • Quicksort Questions
    1. What is the worts, average, and best case complexity of the Partition algorithm used by Quicksort?
    2. What is the worst, average, and best case complexity of Quicksort?
    3. How much extra memory is needed for Quicksort to sort an array of size n?
    4. Give two ways that Quicksort might be made more efficient.
  • Open MP Videos 1-7 question
    Note: After you download the code from the videos, edit make.def. Replace icl with gcc, /Qopenmp with -fopenmp and obj with o.
    1. Submit your Pi program as 385-SRQ
  • Open MP Videos 8-15 question
    1. Submit your Pi2.c program as 385-SRQ (from video 11)
  • Open MP Video 16-18 question
    1. In video 18, I think there is a very slight error in the code presented near the end of the video (just after 7:00). What is it?
  • Open MP Video 19-22 question
    1. Turn in your finished linked.c from video 19 as 385-SRQ.
    2. Turn in your finished linked2.c (rename it before submitting it) from video 21 as 385-SRQ. This one should attempt to use tasks.