Data-structures Review

Post-midterm review

Asymptotic complexity

Big-oh notation

Big-omega notation

Big-theta notation

Solving recurrence equations

Problems:

  • Solve the recursive equation: T(1) = 1; T(n) = T(n-1) + n(n-1), n>1.
  • What is the min number of comparisons needed to find both max and min of n integers?
  • What is the min number of comparisons to find the max and the second max of n integers?

 

Sorting

Insertion sort – algorithm, complexity and benefits

Selection sort – algorithm, complexity and benefits

Quicksort – algorithm, complexity and benefits

Mergesort – algorithm complexity and benefits

Problems:

  • Discuss the sorting algorithms covered in the class.
  • Discuss the comparison of computational complexities of these sorting algorithms.
  • Given an array of n numbers, give 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, given an algorithm for sorting the array.
  • Given an array of 1M pixel color values and each of which is an integer in the range [0,255], which sorting algorithm is preferable for such an array?

 

Splay trees

Splay operations

  • Zig-zag
  • Zig-zig
  • Zig

Complexity of operations in splay trees

Algorithms for find(key), min(), max(), remove(key)

Problems:

  • Algorithms for inserting, deleting and finding a key in a splay tree?
  • Compare splay tree with binary search tree.

 

Heaps

Relationships between priority queues, selection sort, and the heap data structure.

Operations: min(), insert(key), removeMin(), bottomupHeap(), heapsort()

In-place heap sort

Problems:

  • 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 in-place sort in descending order: 3, 5, 2, 9, 20
  • Algorithms for inserting and deleting an entry in a heap?
  • Given a big file containing billions of numbers, how do we find the max 10 numbers?

 

Graphs

Representations: Adjacency matrix, Adjacency list

Graph traversals (DFS, BFS)

Shortest path algorithm

Problems:

  • Give an algorithm for checking whether a given graph has a simple path from a source node (s) to a destination node (t).
  • Assuming an adjacency matrix representation of a graph, count all the simple paths from source (s) to destination (t).
  • Given a directed graph, give an algorithm to detect whether there is a cycle.
  • Given an undirected graph, give an algorithm to detect whether there is a cycle.
  • Given a directed acyclic graph, give an algorithm to topologically sort the nodes.
  • Find the shortest graph distances between every pair of vertices in a given graph. Assume there the graph only has non-negative weights on the edges.

 

Hashing

Hashcoding and compression function

Examples of bad and good hash-coding

Examples of bad and good compression function

Collision, load-factor

Problems:

  • Give an efficient algorithm to find the first non-repeated character in a string.
  • Give 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 for finding whether there exists a pair of elements, one from A and one from B, that add up to K.
  • How would you implement an ordered/unordered set/map?

 

Tries and Suffix Trees

Trie and suffix tree representations and applications

Nifty solutions based on suffix trees to various string matching problems

Problems:

  • Given two strings, find the longest common substring.
  • Given a text T, find the longest palindrome as a substring of T.