CSE 2353 - SMU
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?
2. 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?
3. 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.
4. 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?
5. A stable sorting algorithm maintains the previous order incase of a tie. Which of the sorting algorithms are stable? Justify your answer.
6. 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?
7. 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?
8. Use Prim and Kruskal’s Algorithm to find a minimum spanning tree of a graph of your choice.
9. Draw as many non-isomorphic bipartite graphs as you can on 6 vertices.
10. 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.
11. An array contains the following elements:
|0 |1 |2 |3 |
||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? | | | |
12. Describe a greedy algorithm for determining a vertex cover for an acyclic graph.
13. 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?
14. 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?
15. Find the GCD(36036, 64220). Find LCM(36036, 64220)
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.