All Homework

Homework 1

(12) Consider the problem of finding the common elements from 2 ordered lists A and B which contain no repeated elements. For instance, if A has 2,3,4,6,7 and B has 3,4,5,6,8, then the output would be 3,4,6. Assume A has n elements and B has m elements.
1. Describe an algorithm to solve this problem with as few comparisons as possible.
2. What is the largest number of comparisons that your algorithm uses? Your answer should be a formula involving n and m.
3. How would you modify your algorithm if the lists are not ordered?
4. What is the largest number of comparisons that this second algorithm uses?
(12) Consider the scenario from the first problem, but instead of finding the common elements, we want to create a list that combines all of the elements that are on either list (removing duplicates). So in our example above the output would be 2,3,4,5,6,7,8. Answer questions (a) through (d) from the previous question for this problem.
Questions to ponder, but not to be submitted: What changes in the previous 2 problems and your algorithms for them if repeated values are allowed on the lists? Does it make each problem easier or harder to solve? What complications arise?

Homework 2

(4) Draw a truth table for ¬p⊕q.
(4) Draw a truth table for (¬p∨r)↔¬(q⋀r).
(16) Problem 2.12 from AIDMA (about NOR).
(12) Problem 2.18 f,g,h,i from AIDMA. (Hint: Start by defining L(x,y)="x loves y." Then be careful—what is "a is loved by b?")

Homework 3

(15) AIDMA Problem 4.5. Give a clear explanation of your answers using logic.
(5) AIDMA Problem 4.6
(6) AIDMA Problem 4.8 b, c, d.
(6) AIDMA Problem 4.9 d, e, f.
(4) AIDMA Problem 4.17
(4) If the function in Problem 4.17 was f(x)=x⁴+1, would you be able to find an inverse? Explain why or why not.

Homework 4

(5) AIDMA Problem 5.3. Make sure to clearly justify your answer!
(5) AIDMA Problem 5.4. Explain why your solution works.
(5) AIDMA Problem 5.6. Your algorithm should be written in pseudocode similar to the one used in the textbook.
(5) AIDMA Problem 5.19. You do not need to give a formal proof that your algorithm works, but you should give a brief justification for why it does.

Homework 5

(5) AIDMA Problem 6.4.
(15) AIDMA Problem 6.6 b, e, and h. Simplify your answers and show all of the steps of your computations.
(5) AIDMA Problem 6.16. Your proof should consist of a bunch of steps of algebra to show that the one side of the equation is equal to the other side.
(10) AIDMA Problem 6.21. Clearly explain/justify your answer.

Homework 6

(8) AIDMA Problem 7.3
(6) AIDMA Problem 7.11 m. Provide detailed work for this and be careful!
(12) AIDMA Problem 7.13.

Homework 7

(10) AIDMA Problem 8.1.
(10) AIDMA Problem 8.9. The hint is telling you that 1+(1±sqrt(5))/2=[(1±sqrt(5))/2]². It's up to you to figure out why this is helpful. If you start doing the algebra, you should get to a step where that formula helps.

Homework 8

(8) AIDMA Problem 8.11 c
(8) AIDMA Problem 8.11 e
(24) AIDMA Problem 8.17. Read the instructions for part (a) carefully and follow the rules!
(8) IDAA Problem 2.5 #9 (page 84). Hint: Use induction.

Homework 9

Recall that an nth degree polynomial is p(x)= a_nxⁿ+ a_n-1x^n-1+ a_n-2x^n-2+... a₂x²+ a₁x+ a₀ . Evaluating a polynomial at a point mean plugging in a particular value for x and computing the answer.
1. (6) Give a brute-force algorithm to evaluate an nth degree polynomial at a particular value c. Assume the coefficient are given in an array (e.g. float[] a), where a[0] is the constant term, a[1] is the coefficient of x,etc. Thus, the function prototype would be
  float evaluate(float[] a, int n, float c). (Note that the array has n+1 entries, not n.)
2. (4) What is the worst-case efficiency of your algorithm from part (a)? Justify your answer.
3. (6) If your algorithm from part (a) is Θ(n²) (It shouldn't be worse than this!) give a linear time algorithm and justify that it is linear time. (If your solution from (a) is linear, just say "see (a)".)
4. (4) Is it possible to give an algorithm that is better than linear time? Explain why or why not, being careful about what assumptions you are making.
(6) Determine the exact number of character comparisons made by the brute-force searching algorithm to determine if the text THESE is contained in the string "THIS_IS_NOT_THEIR_THREE_THINGS_THERE_OR_THE_THING_FOR_THEE". You may assume the length of the string (58) is known. Show your work!

Homework 10

(10) A magic square of order n is an n×n matrix with the numbers 1 through n² arranged such that each number occurs exactly once and each row, column, and diagonal sum is the same.
1. Prove that the row/column/diagonal sum has to be n(n²+1)/2.
2. Design an exhaustive-search algorithm to generate all magic squares of order n. As always, do not forget to give the worst-case complexity of your algorithm!
(8) Let G be a graph with edge (u,v). Give an algorithm that will determine whether or not the edge (u,v) is on a cycle of the graph. As always, do not forget to give the worst-case complexity of your algorithm! (Hint: Modify an existing algorithm instead of starting from scratch.)

Homework 11

Consider the following directed acyclic graph.
1. (8) Find a valid topological sorting of the DAG using the DFS algorithm from the lecture notes (not from the book). Show all of your work, including the timestamps!
2. (8) Find a valid topological sorting of the DAG using the source-removal algorithm from the book. Clearly indicate the order in which the states are removed!
(8) Design a decrease-by-half algorithm that computes ⌊log₂ n⌋. Do not forget to give the work case complexity!
(8) You are given an n×n matrix whose rows and columns are sorted in increasing order. Design a O(n) algorithm to find a given number in the matrix. Make sure you justify the complexity of the algorithm. Also, make sure you understand the properties the matrix has—do not assume too much or too little! This one is a bit tricky, so it may take you some time and experimentation to find a good algorithm.

Homework 12

(8) IDAA 5.1 #11 (page 175)
Give a very clear and concise description of your algorithm. You should definitely give a paragraph description of your algorithm for this one. You do not need to give the complexity of this algorithm.
(8) IDAA 5.2 #11 (page 182)
Read the problem description carefully to make sure you understand what you can and cannot do! You may modify an existing algorithm. If so, you may just explain (very clearly!) how to modify that algorithm. Make sure your algorithm is clear and complete. Don't forget to justify why your algorithm is O(n log n)
(9) Traverse the binary search tree below using
1. pre-order traversal
2. in-order traversal
3. post-order traversal

Homework 13

(8) Design an efficient algorithm to find all anagrams of a given word using a list of words from a dictionary (which you can assume is in alphabetical order). For instance, given tea, the algorithm would output eat, ate, tea, etc., but not aet since that is not a word in the dictionary. Give the worst-case complexity of your algorithm given that the dictionary has m words, the input word has n characters, and for simplicity assume the average word in the dictionary has k characters.
(25) Show all of the steps of inserting the letter of ALGORITHMS into each of the following data structures in order (e.g. A, then L, etc.)
1. A regular (unbalanced) BST
2. An AVL tree
3. A 2-3tree
4. A Min Heap
5. A Max Heap
(8) Compute
13¹³⁰³ mod 101
by hand using one of the binary exponentiation algorithms. That is, you are not allowed to use a calculator, computer, abacus, or any other computational device besides your brain. Show all of your work (which should be a table with 3-5 columns). You are permitted to verify that your answer is correct with the use of a computer or calculator. In case it is not clear, you may do all of your intermediate computations modulo 101 and you will still get the same answer. For instance, 13*13=169=68 mod 101, so you can use 68 instead of 169 in the next calculation.

Homework 14

(8) IDAA Problem 7.2 #2. Make sure you show all steps of your computation.
(6) This problem (based on 8.1): Solve this instance of the coin row problem: 6, 2, 3, 9, 11, 8, 5. Don't forget to give the coins in the optimal solution!
(4+2+2) Consider this instance of the knapsack problem.
Capacity W = 11 Item weight value 1 3 27 2 2 13 3 4 40 4 3 32 5 5 48 6 7 82 7 1 12
1. Solve this instance of the knapsack problem using the bottom-up dynamic programming algorithm. Give the optimal cost and a list of the items to take.
2. How many different optimal solutions does this instance have? Explain how you know.
3. In general, how can you determine whether or not there is a unique solution to the knapsack problem using the table constructed by the algorithm?
(4+2+2)
1. Solve the instance of the knapsack problem from #1 using the memory function method.
2. Indicate which entries in the table are never computed by placing a '-' instead of a number.
3. Clearly indicate (using a circle or square or highlighter) which cells of the table are looked up rather than being recomputed. (That is, the entries that WOULD be computed a second time if the standard recursive algorithm was used.)

Homework 15

(8) Use Floyd's algorithm to find the solution to the all-pairs shortest path problem for this graph whose adjacency matrix is given here:
```
0 3 8 ∞ 1
∞ 0 ∞ 1 7
∞ 4 0 ∞ ∞
2 ∞ 2 0 ∞
∞ ∞ ∞ 6 0
```
(8) Use Prim's algorithm to find a minimum spanning tree for the following graph. Assume the adjacency lists are stored in numerical order and start from vertex 0. Give the value in the priority queue at every step of the algorithm. Draw the graph and darken the edges of the minimum spanning tree. (you may scan/photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree.
(8) Use Kruskal's algorithm to find a minimum spanning tree for the graph in the previous problem. Show the sets of vertices for every step of the algorithm. Draw the graph and darken the edges of the minimum spanning tree (you may scan/photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree.
(8) Construct a Huffman Encoding for the following data:
```
Symbol     A   B   C    D   E   F
Frequency 30   7   15  21  10  17
```
Give the encoding of each character and the total cost of encoding a file containing these characters.