Programming Lab : Algorithm analysis


CSCI-UA 9102, Data Structures

  • Exercise 1.1.

    Given two functions \(f(x) = \Omega(\log(n)) \) and \(g = O(n)\), consider the following statements. For each statement, write whether it is true or false. For each false statement, write two functions \(f\) and \(g\) that show a counter example

    • \(g(n) = O(f(n))\)
    • \(f(n) = O(g(n))\)
    • \(f(n) = \Omega(\log g(n))\)
    • \(f(n) = \Theta(\log g(n))\)
    • \(f(n) + g(n) = \Omega(\log n)\)
  • Exercise 1.2. For each of the following statements, write two functions \(f\) and \(g\) that satisfy the given condition (Note that \(f(n) = \omega(g(n))\; \text{if}\;\forall k>0, \exists n_0\;|\; \forall n> n_0\; |f(n)|\geq k |g(n)|\)) and use java.lang.System.currentTimeMillis to compare the run times.

    • \(f(n) = O(g^2(n))\)
    • \(f(n) = \omega(g(n))\)
    • \(f(n) = \omega(\log g(n))\)
    • \(f(n) = \Omega(f(n) g(n))\)
    • \(f(n) = \Theta(g(n)) + \Omega(g^2(n))\)

  • Exercise 1.3. An array is “almost sorted” such that each element is at most k positions away from its correct sorted position. Task: Design an efficient algorithm to sort this array. Goal: Achieve better than O(n log n) complexity when k is small. Target Complexity: O(n log k)

  • Exercise 1.4. Given a string S, design an algorithm to find all the shortest substrings that occur only once in S. Goal: Optimize for both time and space (hint: use suffix trees or arrays).

  • Exercise 1.5. Given an array of integers, move all zeros to the end while maintaining the relative order of the non-zero elements. Task: Design an algorithm that does this in-place in O(n) time and O(1) space. Follow-up: Can it be done with only one pass?

  • Exercise 1.6. Design an algorithm to detect if a cycle exists in a singly linked list. Goal: Achieve O(n) time and O(1) space. Hint: Use Floyd’s Tortoise and Hare technique.

  • Exercise 1.7. Given an array, rotate it to the right by k steps. Task: Do this in-place using O(1) space and O(n) time. Design Challenge: Avoid naive repeated shifting.

  • Exercise 1.8. We say that two singly linked lists intersect at some node if they form a `Y” shape. We then say that the two lists are merging at node called “intersection node”. Design an O(n) time, O(1) space algorithm to find the intersection node (if such a node exists) (You are forbidden to modify the list).

  • Exercise 1.9. Given an array of (signed) integers, find the contiguous subarray with the largest sum. Task: Design an algorithm with O(n) time. Follow-up: Return the start and end indices of the subarray as well.

  • Exercise 1.10. Given an array of (signed) integers, find the contiguous subarray with the largest sum. Task: Design an algorithm with O(n) time. Follow-up: Return the start and end indices of the subarray as well.

  • Exercise 1.11. Given a singly linked list \(L_2 \rightarrow L_2 \rightarrow \ldots \rightarrow L_n\), reorder it into \(L_1 \rightarrow L_n \rightarrow L_2 \rightarrow L_{n-1} \rightarrow \ldots\) Task: Do it in-place in O(n) time and O(1) extra space. Challenge: Avoid using extra lists or recursion.