Applied Algorithms Anna Karlin, 426C Sieg
CSE 589, Autumn 1997

Homework # 1
Due in class, October 15

1. Big Oh: For each of the following questions, briefly explain your answer.
   1. If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on some inputs?
   2. If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on all inputs?
   3. If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on some inputs?
   4. If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on all inputs?
   5. Is the function where for even n and for odd n?

2. Dynamic Programming:
   • Consider the following data compression technique. We have a table of m text strings, each of length at most k. These are our code words. We want to encode a data string D of length n using as few code words as possible. For example, if our table contains the four code words (a,ba,abab,b) and the data string is bababbaababa, then the best way to encode it is (b,abab,ba,abab,a) - a total of five code words. Give the most efficient algorithm you can that, given an input data string D, produces an optimal encoding for D. You may assume that D has an encoding in terms of the table. What is the complexity of your algorithm in terms of n, k and m?
   • The following problem comes up in surface reconstruction. (I'll explain the application and this problem in more detail in class.) Let P and Q be polygons with m and n vertices and in 3 dimensions, where P and Q are planar and parallel. A tiling of P and Q is a set of triangles, called tiles, whose vertices are of the form or , that is, one side of each tile is a face of one polygon and the remaining tile vertex is on the other polygon (throughout i+1 is taken modulo m and j+1 is taken modulo n). The tile edges that have a vertex from each polygon are called cross edges. The set of tiles constructed must satisfy two properties: (1) Every face of each polygon is a side of exactly one tile. (2) Every cross edge is a side of exactly two tiles.

     Give a dynamic programming algorithm, which given polygons P and Q, constructs a tiling of P and Q of minimum surface area (the sum of the areas of all the triangles in the tiling).

3. Graph representation: Consider an unweighted graph with n vertices and m edges. The two common data structures used to represent such a graph are adjacency matrices and adjacency lists. An adjacency matrix is an matrix M, where M[i,j]=1 if there is an edge from vertex i to vertex j and M[i,j]=0 otherwise. An adjacency list consists of an n-element array of pointers, where the i-th element points to a linked list of the edges incident on vertex i.
   • For which of adjacency lists and adjacency matrices is it faster to test if a given edge (v,w) is in the graph?
   • For which of adjacency lists and adjacency matrices is it faster to find the degree of a vertex?
   • How much memory is used by each of the two data structures (in big Oh notation)?
   • What is the complexity of edge deletion/edge insertion for the two methods?
   • What is the complexity of traversing the graph for the two methods?
4. Depth-first search on a directed graph: Rewrite the pseudo-code for depth-first search given in the first lecture, so that it prints out, for each edge examined, whether the edge is a tree edge, a back edge, a forward edge or a cross edge.
5. We discussed (sometimes briefly) the following in the first lecture.
   • Traversing a graph using depth-first search
   • Traversing a graph using breadth-first search.
   • Finding the connected components of an undirected graph.
   • Finding the strongly connected components of a directed graph.
   • Determining if a directed or undirected graph has a cycle.
   • Topologically sorting a directed acylic graph.
   • Testing a graph for planarity.
   • Finding a minimum spanning tree for a weighted graph.

   For each of the following problems, describe how it could be modeled as a graph problem and solved with the aid of one or more of the above known algorithms, or ideas involved therein. I have purposely left these problems somewhat vague....

   1. Given a set of processes that need to be scheduled, and dependencies that tell you which processes need to be completed in order for a given process to execute, how would you schedule the processes so as not to violate any of the dependencies?
   2. How would you find your way out of a maze using a very large collection of pennies?
   3. DNA sequences - you are given experimental data consisting of small DNA fragments. For each fragment f, it has been determined experimentally that certain fragments lie to the left of f on the chromosome, certain fragments lie to the right of f, and the rest can be on either side. How would you go about finding a consistent ordering of the fragments from left to right that satisfies all the constraints?
   4. Broadcast - suppose a given processor on a network wishes to broadcast a message to all other processors. How would you go about routing the message to all the other processors as efficiently as possible? You can assume that you have information about the bandwidth and congestion on the various links in the network.
   5. Circuit simulation - Given a circuit layout and input/output information for each gate in the circuit (where its outputs go and where its inputs come from) how would you schedule the simulation of the gates in the circuit?
   6. Graphics- A triangle strip is a sequence of triangles, such that shares exactly one edge with and exactly one (other edge) with , for each 1<i <n. Rendering engines are often able to very efficiently render a ``triangle strip'', much more efficiently than they can render each of the n individual triangles. Given a large set of triangles (given by the 3D coordinates of the three vertices of each triangle), how would you go about constructing a set of maximal triangle strips to feed to the renderer.

 
• About this document ...