Solutions to Midterm 2

CSE 373, Rohan Fernandes

November 28th 2000

Maximum marks for each problem are 20. Total credit: 100

• 1

  1.

  T= 21, S = 15,16,5,7.

  2.

  T= 21, S = 15,16,5,7.

  3.

  T= 21, S = 15,16,5,7.

  Common Mistakes :

  1.

  Selecting S such that there is no solution for the value of T.

  Doubtful Ideas :

  1.

  For worst-fit algorithm selecting largest number larger than T.

  2.

  Selecting negative numbers as members of S.

• 2 The technique to be used for solving this problem is dynamic programming. We will use another array A to store the solutions of the sub-problems.
  A[i] = length of the longest monotonically increasing subsequence of S ending with S[i].

  1.

  A[1]=1;

  2.

  for i = 2 to n do

  3.

  maxseq=1;

  4.

  for j = 1 to i do

  5.

  if ${ \bf {S}}[i] > { \bf {S}}[j]$ and ${ \bf {A}}[j] + 1 > maxseq$

  6.

  maxseq = S[j] + 1

  7.

  A[i]=maxseq;

  Common Mistakes :

  1.

  Backtracking based ideas. This is not a search based problem. It is an optimisation problem and backtracking solutions are not O(n²) Also backtracking reduced the search space but the complexity remains O(2ⁿ).

  Doubtful Ideas :

  1.

  Solutions using two-dimensional arrays (matrices). All dynamic programming problems do not require matrices.

• 3

  1.

  Figure 1

  2.

  Figure 2

  3.

  Figure 3

  4.

  Figure 4

  
  
    

  Figure 1: BFS traversal order.

  
  
  
  
    

  Figure 2: DFS traversal order.

  
  
  
  
    

  Figure 3: Minimum Spanning Tree.

  
  
  
  
    

  Figure 4: Shortest paths Spanning Tree.

  
  
  

• 4 This problem uses the backtrace of DFS to count the vertices in subtrees. There are two solutions to this problem depending on whether you assume you know the number of vertices n or otherwise. The solution here will assume we do not know the value of n.

  1.

  Traverse the tree in DFS order from any vertex.

  2.

  At each node we have a counter field which contains the value of the total number of node in the sub-tree with the current vertex as the root. Remember that this count is variable depending upon what the starting node in the DFS is. This is because different DFS traversals of a tree will result in vertices being parents of different subtrees.

  3.

  The counter is updated in this manner. Whenever a vertex is marked ``completely discovered'' the count is set to the following value (Sum counts of all child vertices of this vertex + 1). Since leaf vertices have no children they will have a count of 1. Intuitively count represents the number of vertices in the subtree rooted at a vertex where this vertex is the root of all the vertices in the subtree for a given DFS traversal.

  4.

  At the end of the first DFS traversal the root (The vertex we began DFS with) will contain the count of all vertices n in the tree.

  5.

  Now traverse the tree in any manner BFS or DFS and check if any vertex has the following properties.

  a.

  All children should have counts of less than or equal to n/2.

  b.

  The number n - count_{currentvertex} should also be less than or equal to n/2.

  Common Mistakes:

  1.

  Using BFS to count nodes. BFS cannot be used to count vertices in a subtree because after a vertex is discovered it is immediately marked as ``completely discovered'' after enqueueing its unvisited adjacent vertices.

  2.

  The central vertex of a diameter of the tree is the vertex with the property required.

  3.

  Removing the vertices in leaves first order until one vertex remains which is the required vertex.

  4.

  The n/2^th vertex found in BFS/DFS is the vertex with the required property. Counterexamples to this and the preceding two ideas can be easily found.

• 5 This algorithm use the idea of topological sort followed by relaxation of distances as the central ideas.

  1.

  Perform a topological sort on the nodes of the DAG. This is a linear time operation which can be done with either BFS or DFS. To do it with BFS is intuitive while doing it with DFS requires you to be clever with the printing.

  2.

  set up an array d to store the shortest distances from vertex v to all nodes after it in the topological sort. The vertices preceding v cannot be reached from it. Initialise all distances to $\infty$. Assuming vertex v is the ith vertex set d_i to 0.

  3.

  Now you can proceed in two ways.

  a.

  For each vertex after v in topological sort i.e for each vertex k from i+1 to n d_l = min (d_l, d_k + W_kl) where l is a neighbour of k succeding k in topological sort and W_kl is the distance of vertex l from vertex k.

  b.

  For each vertex after v in topological sort i.e for each vertex k from i+1 to n d_k = min (d_k, d_l + W_lk) where l is a neighbour of k preceding k in topological sort and W_lk is the distance of vertex k from vertex l.

  4.

  The preceding step is linear since we will have to make comparisons and computations on the order of the number of edges in the DAG. Using an adjacency list to represent the graph is necessary to ensure this linearity.

  Common Mistakes:

  1.

  Using dynamic programming without topological sort. This algorithm is O(n²).

  2.

  Dijkstra's algorithm. This is not linear. Besides it does not work for negative weighted graphs even negatively weighted graphs without cycles like a DAG.