DOC PREVIEW
Princeton COS 226 - Final

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

COS 226 Algorithms and Data Structures Spring 2003FinalThis test has 11 questions worth a total of 84 points. You have 150 minutes. The exam is closedbook, except that you are allowed to use a one page cheatsheet. No calculators or other electronicdevices are permitted. Give your answers and show your work in the space provided. Write outand sign the Honor Code pledge before turning in the test.“I pledge my honor that I have not violated the Honor Code during this examination.”Problem Score Problem Score1 72 83 94 105 116Sub 1 Sub 2TotalName:Login ID:Precept:1 12:30 Kevin2 1:30 Adriana4 3:30 Kevin12 PRINCETON UNIVERSITY1. Analysis of algorithms. (6 points)Precisely define what it means for an algorithm to have worst-case running time O(N2) whereN is the size of the input.2. String searching. (4 points)This question is about the problem of searching for any occurrence of an M-character patternin an N-character text string. Suppose that student X uses the brute-force method andstudent Y uses the right-left scan. The students are each given the option of picking fromamong one of the three string generators listed below for both programs to be tested on (bothpattern and text to be generated from the same generator, then both programs invoked onthe same input).A. random string of As and BsB. random ASCII charactersC. all As except last character is BFill in the blanks to give the best choice and expected results from each students’ point ofview. (If the asymptotic number of character compares is the same, answer ”1”.)(a) For X’s choice, brute-force is a factor of faster than right-left.(b) For Y’s choice, right-left is a factor of faster than brute-force.COS 226 FINAL, SPRING 2003 33. Geometric algorithms. (8 points)The computer graphics in Matrix Reloaded require fast geometric algorithms for various op-erations dealing with polygons. Let A and B be two simple polygons, represented by theircounter-clockwise ordering of their vertices. Let N be the total number of vertices For simplic-ity, you may assume that there are no degeneracies, e.g., A and B do not share any vertices,and there are no 3 vertices that are collinear.(a) Give a brief description of a fast algorithm for determining whether A lies completelywithin B, and circle the choice below that best describes its worst-case performance.(For full credit, you need to describe an optimal algorithm.)i. log N ii.√N iii. N iv. N log N v. N2You may use any of the subroutines from lecture and the book, including:Subroutine Primitive Running timeS1 do 2 line segments intersect? 1S2 do N line segments intersect? N log NS3 is point inside simple N -sided polygon? NS4 are 2 points on the same side of a line? 1S5 convex hull of N points N log NS6 Voronoi diagram of N points N log N(b) Repeat (a) when A and B are convex.4 PRINCETON UNIVERSITY4. Minimum spanning tree. (8 points)Consider the following undirected network with edge weights as shown.(a) List the edges in the MST in the order that Prim’s algorithm chooses them. Start Prim’salgorithm from vertex 1.(b) List the edges in the MST in the order that Kruskal’s algorithm selects them.COS 226 FINAL, SPRING 2003 55. Max flow, min cut. (10 points)Starting from the following flow (printed above or to the right of the capacities), perform oneiteration of the Ford-Fulkerson algorithm. Choose the fattest augmenting path, i.e., the pathwith the highest residual capacity.(a) Write down the fattest augmenting path.(b) What is the value of the resulting flow?(c) Is the resulting flow optimal? If so, give a min cut whose capacity is equal to the valueof the flow. If not, give a fattest augmenting path.6 PRINCETON UNIVERSITY6. Data compression. (6 points)Consider the following 21 character message that consists of 3 a’s, 7 c’s, 6 t’s, and 5 g’s.aaccccacttgggttttccggAre the following 43 bits a possible Huffman encoding of the message above?0000001111000101010010010010101010111001001Justify your answer as concisely and rigorously as possible.7. Algorithmic design. (8 points)Given an undirected network with V vertices, 10V edges, and integer edge weights between 1and V , describe how to find a MST asymptotically faster than V log V . What is the worst-caserunning time of your algorithm.COS 226 FINAL, SPRING 2003 78. Theory vs. practice. (12 points)For each of the following pairs, indicate which algorithm has the better worst-case runningtime and which one will likely perform better in practice on real-world inputs.(a) Sorting: I. Insertion sortII. Mergesort−−−−Worst-case−−−−Practice(b) Sorting: I. QuicksortII. Mergesort−−−−Worst-case−−−−Practice(c) Min spanning tree: I. Prim with binary heapII. Prim with Fibonacci heap−−−−Worst-case−−−−Practice(d) Priority queue: I. Binary search treeII. Binary heap−−−−Worst-case−−−−Practice(e) Linear programming: I. Ellipsoid algorithmII. Simplex algorithm−−−−Worst-case−−−−Practice(f) Convex hull: I. Package wrapII. Graham scan−−−−Worst-case−−−−Practice8 PRINCETON UNIVERSITY9. Choosing the right algorithms and data structures. (8 points)Circle the best answer to each of the following questions.(a) What is the primary reason to use Floyd’s algorithm to solve the all-pairs shortest pathproblem instead of Dijkstra’s algorithm?i. Faster for dense graphsii. Faster for sparse graphsiii. Implementing Fibonacci heaps is difficultiv. Can reconstruct the path itself in addition to the length of the shortest path(b) What is the primary reason to use the Burrows-Wheeler data compression algorithmover LZW?i. Uses less memoryii. Better compression ratioiii. Faster encodingiv. Faster decoding(c) Describe a situation when you would need to use breadth-first search instead of depth-first search.i. Find a Euler tourii. Find a directed cycleiii. Find a path between two vertices in an undirected graphiv. Find a path between two vertices with the fewest number of edges(d) Describe a situation when you would need to use the Bellman-Ford shortest path algo-rithm instead of Dijkstra’s algorithm.i. Compute routing directions in a GPS-based car navigation systemii. Detect arbitrage opportunity in currency exchangeiii. Compute the shortest path between two vertices in an undirected graphiv. Create a table that gives the lengths of the shortest routes that connect all pairs ofcitiesCOS 226 FINAL, SPRING 2003 910. Linear programming. (6 points)You are operating an


View Full Document

Princeton COS 226 - Final

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Load more
Download Final
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?