COMP 15 – Data structures

DATA STRUCTURING USING C++ FOR ALGORITHMIC EFFICIENCY

Review 

Practice questions – II

Partha Biswas 0 Comments

Rooted trees

  • Given a binary tree, print the elements in a reversed level order.
  • Find the nearest match of a given value in a binary search tree.
  • Write a function to check whether two binary trees are structurally identical.
  • Write a function to find the size of a BST.
  • Write a function to compute the sum of all the elements in a BST.

Complexity analysis

  • Write down the lower bound, upper bound, and order functions for the following timing function: f(n) = 0.5 * n^3 + 2 * n^2 + log n
  • Solve the following recurrence equation: T(1) = 1; T(n) = T(n-1) + n(n-1), n > 1

recurrenceDownload

  • For the sorting algorithm below, compare the time complexity for partitioning in the middle vs the beginning.
L' = Sort (L, n)
begin
   if (n == 1) L' = L;
   else 
      Split L into two non-empty sets L1 and L2;
      L1' = Sort(L1);
      L2' = Sort(L2);
      L' = MERGE(L1', L2');
   end
end

Sorting

  • Discuss the sorting algorithms covered in the class. Analyze the time complexity for each sorting algorithm.
  • Given an array of n numbers, design an algorithm for checking whether there are repeated elements, without any additional space overhead.
  • Given an array consisting of 0’s, 1’s and 2’s, design an algorithm for efficiently sorting the array.

Heaps

  • What are the minimum and maximum number of elements in a heap of height h?
  • Given a min-heap, how would you find the max element? What is the complexity of such an algorithm?
  • Insert the following numbers into a heap for an inplace sort in descending order: 3, 5, 2, 9, 20.
  • Given a big file containing billions of numbers, design an algorithm to find the max 10 numbers.

Graphs

  • Write an algorithm for checking whether a given graph has a simple path from a given source node to a given destination node.
  • Assuming an adjacency matrix representation of a graph, count all the simple paths from a source to a destination.
  • Given a directed graph, write an algorithm to detect whether there is a cycle.
  • Given an undirected graph, write an algorithm to detect whether there is a cycle.
  • Assuming that there are only non-negative weights, suggest an algorithm for computing the single-source shortest path.

Hashing

  • Design an efficient algorithm to find the first non-repeated character in a string.
  • Design an efficient algorithm to find the first repeated character in a string.
  • Given an array of n numbers, present an algorithm which displays all pairs whose sum is S.
  • Given two sets A and B, and a number K, present an algorithm to find whether there exists a pair of elements, one from A and one from B that adds up to K.

Leave a Reply