Exam 1 Review

 

Review Topics for Exam 1 -- Big-O notation, Stable Matching, Elementary Graph Algorithms, Greedy Algorithmss

 

These exercises may be more challenging than the actual exam questions, but these problems cover the range of topics that you are responsible for on the exam, and if you are able to do most of these problems you should be well prepared to take the exam.

 

1.      Given the functions in column A and column B below, determine whether each function in column A is big-O, big-Q, or big-W of each function in column B.  Justify your answers by showing that the definitions are satisfied.

 

                        Column A                                                                    Column B

 

                        n2 + 4n  +4                                                                   n lg(n)

 

                        Ön                                                                                n2

 

                        n!                                                                                 2n

 

                        lg(n!)

 

                        n3/2

 

                        en

 

                        2lg(n)

 

2.      Can you determine the big-O or (better yet) the big-Q asymptotic bound on T(n) for the following function?  Show       your work.

                                     n

                        T(n) = å i2 

                                    i=1

 

3.      When Colonel Mustard told his friend Professor Plum that he had just written a matrix multiplication algorithm that has

     O(n3) asymptotic behavior, where n is the larger of the two dimensions (#rows, #cols.) in either of the two matrices to

     be multiplied, Plum replied that he had a Q(nlg 7) algorithm to perform the same task.  Assume both claims are true.

            a) Which of the two algorithms gives you the better guarantee of performance? Explain.

            b) Is it possible that Mustard's algorithm will always outperform Plum's for every value of n? Explain.

            c) Is it possible that Mustard's algorithm will never outperform Plum's? Explain.

            d) If you had to multiply a 4 by 5 matrix times a 5 by 3 matrix, do you have any basis for choosing Plum's                           algorithm over Mustard's?  Explain.

            e) Miss Scarlet claims that she has had good success using a Q(n2 lg2n) algorithm.  Should she be persuaded by

                Plum to use his algorithm instead?  Explain.

            f) Does Mr. Green have any justification for killing Plum in the Library with a lead pipe?  Explain.

 

4.      Given a graph G, write an algorithm to perform a breadth-first search (depth-first search) of the graph.

 

5.      A file contains only colons, spaces, newline, commas, and digits in the following frequency:

                        colon                100

space               700

                        newline             500

                        comma             600

                        0                      400

                        1                      250

                        2                      175

                        3                        50

                        4                      180

                        5                      250

                        6                      175

                        7                      200

                        8                      200

                        9                      220

 

            Construct the Huffman code.

 

6.      Given a graph consisting of 20 vertices.  Assume that initially all of the equivalence classes consist of a single element.  Construct your table for forming new equivalence classes using the union-find algorithm.  Show the result of the following sequence of instructions:

                        union(1,2), union(3,4), union(3,7), union(8,9),

                        union(1,8), union(3,10), union(3,11), union(3,12), union(3,13),

                        union(14,15), union(16,17), union(14,16), union(1,14), union (1, 3)

            when the unions are performed by rank.

 

7.      Suppose, in the example above, the next statement to be executed is:     find(17) == find (9)    What values are returned by these two calls to find?  Show how the table at the end of the previous sequence is changed by this test.

 

8.      Suppose you are given a connected graph g, with edge costs that you may assume are all distinct.  G has n vertices and m edges.  A particular edge e of G is specified.  Give an algorithm with running time O(n + m) to decide whether e is contained in a MST of G.

 

9.      Given a set of n men and n women.  Assume each member of these sets has a preference list of partners that may include indifferences.  Each man and woman will have a distinct first choice, but in any of their remaining choices they may be indifferent between two or more of the selections.  For instance if n = 4, man m1 may prefer woman w1 as his first choice, but may consider his second choice to be tied between w3 and w4 with w2 his distinct least favorite option.  A strong instability in a perfect matching S consists of a man m and a woman w, such that each of m and w prefers the other to their partner in S.  Does there always exist a perfect matching with no strong instability in every instance of the stable matching problem with indifferences?  A weak instability in a perfect matching S consists of a man m and woman w with partners w' and m' in S respectively such that 1) m prefers w to w' and w either prefers m to m' or is indifferent between these two, or 2) w prefers m to m', and m either prefers w to w' or is indifferent between the two choices.  Does there always exist a perfect matching with no weak instabilities?

 

10.  For any 2 nodes in a directed graph G, their strong components are either identical or disjoint.  Prove or give a counterexample.

 

11.  Be able to show that a directed graph is a DAG.  Be able to find a topological ordering of a DAG.

 

12.  There will be short answer/multiple choice/true false questions on the exam.

 

13.  Review the homework problems from the first 4 chapters.