CSE 7350 – Extra Problems

Name: ______

  1. Write an algorithm that finds the m smallest numbers in a list of n numbers. What is the running time of your algorithm?
  1. Write an improved selection sort by selecting both the min and max each time through the original list. What is the expected improvement in running time?
  1. Algorithm A performs 10n^2 basic operations, and algorithm B performs 300l*n basic operations. For what value of n does algorithm B begin to show its better performance.
  1. Suppose we are to search an array 700 million sorted items. What is the maximum number of comparisons that a binary search must perform to verify that a number is not in the set?
  1. A stable sorting algorithm maintains the previous order incase of a tie. Which of the sorting algorithms are stable? Justify your answer.
  1. Given a very large list to sort which is stored in external storage. Assume that accessing external storage is slow compared to main memory, and assume that main memory is too small to hold the complete list. What factor(s) should you consider in designing a sorting algorithm?
  1. A source generates the following message: ABCDABCABA What is the entropy of the source? How many bits of information does each symbol represent? What is the information content in the message? Provide a Huffman encoding of the message. How close to optimal is the Huffman encoding?
  1. Use Prim and Kruskal’s Algorithm to find a minimum spanning tree of a graph of your choice.
  1. Draw as many non-isomorphic bipartite graphs as you can on 6 vertices.
  1. Give 2 trees, Tree A and Tree B such that the post-order traversal of Tree A is the same as the port-order traversal of Tree B, and the pre-order traversal of Tree A is the same as the pre-order traversal of Tree B, but the in-order traversal of Tree A is different from the in-order traversal of Tree B.
  1. An array contains the following elements:

0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15 / 16 / 17 / 18
18 / 160 / 186 / 126 / 185 / 149 / 127 / 195 / 137 / 156 / 157 / 167 / 126 / 156 / 543 / 127 / 139 / 173 / 157

(i)Use a THETA(n) heapify to create a heap with the minimum element on top.

(ii)Use a THETA(n) heapify to create a heap with the maximum element on top.

  1. You have 6 topics to study for a final exam each worth the following points and requiring the following amount of time to study:

(i)Topic 1: 1hr 25 pts

(ii)Topic 2: 1hr 30 min 20 pts

(iii)Topic 3: 2 hrs 15 min 30 pts

(iv)Topic 4: 20 min 5 pts

(v)Topic 5: 45 min 10 pts

(vi)Topic 6: 30 min 10 pts

If you study a topic for a portion of the time (say half of the time), you get that percentage of the points (say, half of the points).

Which topics would you study if you had 3 hours, and how many points would you get?

Which topics would you study if you had 4 hours, and how many points would you get?

  1. Describe a version of the binary search which still runs in THETA(lg n) time, but does not require any “divide by 2” operation. Instead, this version should only use additions and/or subtractions to calculate the next index to compare against.

(i)How much information do you obtain on each comparison with the standard binary search?

(ii)In the limit, much information do you obtain on each comparison with your new search?

(iii)On average, how many more comparisons will be required with the new method?

(HINT: Consider the Fibonacci sequence such that if you have an array of 55 elements, you divide the array into two parts with one part containing 21 elements and the other containing 34 elements.)

  1. [8 pts] A tree has the following in-order and pre-order traversals. Draw the tree and give a post-order traversal.
  2. In-Order: K, P, L, E, N, F, A, M, C, G, B, H, I, O, J, D
  3. Pre-Order: C, E, K, L, P, M, A, N, F, I, B, G, H, J, O, D
  1. Give a Smallest-last vertex ordering of graph (a) on Page 571. Use this ordering to color the graph. Argue whether fewer colors might be possible.
  1. Fill in the table giving the appropriate values for the graphs shown:

|V|
|E|
Maximum Degree
Number of Components
Min Cut
Max Clique Size
Chromatic Number
(Number of colors needed)
Is the Graph Bi-Partite?
Does the graph have an Euler Tour?
  1. Describe a greedy algorithm for determining a vertex cover for an acyclic graph.
  1. A race is planned for 15 cars. The outcome of the race indicates which car is 1st, which is 2nd, and which is 3rd. The outcome of a race does not indicate which car is 4th – 15th. How many possible outcomes exist?
  1. Consider a random number generator capable of producing the values {1, 2, 3, 4} with uniform probability. This generator is called 7 times and the results are recorded. Order does not matter. How many different combinations of results are possible. How many ways can you get three 3’s, two 1’s, two 4’s and no 2’s on your seven calls?
  1. Find the GCD(36036, 64220). Find LCM(36036, 64220)