Homework 1
CSE 317: Design and Analysis of Algorithms
Due: 23:59 on November 8, 2024 on LMS
Submission Instructions:
Make a PDF file of your theory questions. Put all your code files and theory PDF file in a single
ZIP file as homework1-<your student ID>.zip. Submit it on the LMS.
Theory Questions
1. (5 + 5 points) Let A be an array of n distinct numbers. If i < j and A[i] > A[j], then the
pair (i, j) is called an inversion of A. Design an efficient algorithm to count the number of
inversions in A. Analyze the time complexity of your algorithm.
2. (5 + 5 points) Let A be a binary array of n elements i.e., each element A[i] ∈ {0, 1} for
1 ≤ i ≤ n. Furthermore, all zeroes appear before all ones in the array. Design an efficient
algorithm to find the index i of the first occurrence of 1 in A i.e., A[i − 1] = 0 and A[i] = 1.
Analyze the time complexity of your algorithm.
3. (5 + 5 points) Let L = ⟨x1 , x2 , . . . , xn ⟩ be a sequence of elements that contains exactly k
occurrences of the element x (1 ≤ k ≤ n). We want to find one j such that xj = x. Consider
the following procedure until x is found. Generate a random number i between 1 and n
and check whether xi = x. Which method is faster, on the average, this method or linear
search? Explain.
4. (5 + 5 points) For a sequence X = ⟨x1 , x2 , . . . , xn ⟩, we define the mirror of X as the se-
quence Y = ⟨xn , xn−1 , . . . , x1 ⟩. We say that a sequence X is beautiful if the mirror of X is
the same as X. Design an O(n2 ) dynamic programming algorithm that finds the minimum
number of elements to add to a given sequence X to turn it into a beautiful sequence. [We
can add new elements anywhere in the sequence.]
Programming Questions
Implement all of algorithms for above problems in a programming language of your choice
(C, C++, Python, Rust, or Java) and verify on the test cases.
Kindly consult the TA’s for test cases.