Question

2. Let BT Node be the class we often use for binary-tree nodes. Write the following recursive methods: (a) numLeaves: a method that takes a BT Node T as parameter and returns the number of leaves in the tree rooted at T. (b) isEven: a boolean method that takes a BT Node T and checks whether its tree is strictly binary: every node in the tree has an even number of children.

3. Suppose you want to improve Merge Sort by first applying Heap Sort to a number of consecutive subarrays. Given an array A, your algorithm subdivides A into subarrays A1, A2 · · · Ak, where k is some power of 2, and applies Heap Sort on each subarray Ai alone. The algorithm proceeds into merging pairs of consecutive subarrays until the array is sorted. For example, if k = 4, you first apply Heap Sort to sort each Ai and then you merge A1 with A2 and A3 with A4, then you apply the merge function once to get the sorted array. (a) Does the proposed algorithm improve the asymptotic running time of Merge Sort when k = 2? How about the case k = log n (or a power of 2 that is closest to log n)? Justify. (b) Is the proposed algorithm stable? Is it in-place? Prove your answers.

4. Write a clear pseudocode for Breadth-First Search (BFS) in undirected graphs. How would you modify your code to compute the number of connected components in the input graph? Give details about the used data structures and the running time.

5. Write a clear pseudocode for Depth-First Search (DFS) in graphs. How would you modify your code to check whether the graph is acyclic?

6. The centrality of a vertex v in an undirected graph G is measured as follows: c(v) = n1(v) + n2(v) + · · · nd(v) where ni(v) is the number of vertices at distance i from v (e.g., n1(v) is the number of neighbors of v) and d is the maximum distance between v and a vertex of the same connected component as v in G (so d = 0 if v is isolated). Write the pseudocode of a most-efficient algorithm that computes the centrality of a vertex v in a given graph G. What is the running time of your algorithm? Prove your answer.

Answer 1

2. a)

static int getfullCount(Node root)  
{  
    if (root == null)  
    return 0;  
  
    int res = 0;  
    if (root.left != null && root.right != null)  
    res++;  
  
    res += (getfullCount(root.left) + getfullCount(root.right));  
    return res;  
}  

b) Since it is a "BINARY" tree it will always nodes that have even number of children.

4.

A standard BFS implementation puts each vertex of the graph into one of two categories:

• Visited
• Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The algorithm works as follows:

• Start by putting any one of the graph's vertices at the back of a queue.
• Take the front item of the queue and add it to the visited list.
• Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.
• Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node

5.

Pseudocode:

procedure DFS(G,v):
  label v as discovered
  for all edges from v to w in G.adjacentEdges(v) do
    if vertex w is not labeled as discovered then
      recursively call DFS(G,w)

For checking cycles in graph:

Algorithm:

• Create the graph using the given number of edges and vertices.
• Create a recursive function that initializes the current index or vertex, visited, and recursion stack.
• Mark the current node as visited and also mark the index in recursion stack.
• Find all the vertices which are not visited and are adjacent to the current node. Recursively call the function for those vertices, If the recursive function returns true, return true.
• If the adjacent vertices are already marked in the recursion stack then return true.
• Create a wrapper class, that calls the recursive function for all the vertices and if any function returns true return true. Else if for all vertices the function returns false return false.