Tutorial

Find the questions along with the submission dates

Week - 1 (Submission Date: 7/8/2021)

1. List the following functions according to their order of growth from the lowest to the highest: $(n-2)!$, $2^{2n}$, $5log(n+100)^{10}$, $0.001n^{4}+3n^{3}$, $ln^{2}n$, $\sqrt[3]{n}$, $3^{n}$

2. Find whether the following assertions are correct:

   1. $2^{2n+1} \in \mathcal{O}(n)$

   2. $n(n+1)/2 \in \Theta(n^{3})$

3. Given two n*n matrices A and B, write down the algorithm for computing the matrix multiplication and compute its efficiency using a formal analysis framework.

4. What will be the time complexity of the following code segment:

5. Consider the following algorithm

1. What does this algorithm compute?

2. What is its basic operation?

3. How many times is the basic operation executed?

4. What is the efficiency class of this algorithm?

5. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

Week - 2 (Submission Date: 14/8/2021)

1. Find the time complexity of following recurrence relation using forward substitution: $T(n) = 3T(n-1), n>0$; $T(0)=1$

2. Solve recurrence $T(n) = T(n-1) + logn , n>0; T(1)=0$

3. Use Master theorem to solve the following recurrence relation. (Indicate the case and the solution) For all the cases, consider $T(1) = 1$ a) $T(n) = 4T(n/2) + n^{2} , n>1$ b)$T(n) = 2^{n} T(n/2) + n^{n}, n>1$ c) $T(n) = 2T(n/4) + n^{0.51}$ d) $T(n)= 3T(n/3) +(n/2), n>1$ e) $T(n) = 7 T(n/3) + n^{2}, n>1$

4. Draw the recursion tree and derive cost for recurrence $T(n) = a T(n/b) + f(n) , n> 1, T(1) = 1$

5. Can master theorem be used for recurrence relation which takes poly-logarithmic number of basic operations ? [ Extended version of masters theorem ]

Week - 3 (Submission Date: 25/8/2021)

1. Define the following terms and relate them to the interval scheduling problem feasible solution optimal solution objective criterion greedy strategy proposition used to verify the correctness

2. Differentiate global and local optimal solution

3. Job scheduling Consider the problem of scheduling n jobs of known durations $t_{1}, t_{2},...,t_{n}$ for execution by a single processor. The jobs can be executed in any order, one job at a time. You want to find a schedule that minimizes the total time spent by all the jobs in the system. (The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.) Design a greedy algorithm for this problem. Does the greedy algorithm always yield an optimal solution?

4. Identify the optimal substructure for the coin change problem. Write pseudocode of the greedy algorithm for the change-making problem, with an amount n and coin denominations d1 > d2 > ... > dm as its input. What is the time efficiency class of your algorithm?

5. You are planning to rob banks. All banks are arranged in a circular manner. Which means, the first and last banks are neighbor to each other. Each bank has a certain amount of money stashed. Adjacent banks have a security system connected which will automatically contact the police if two adjacent banks were broken into on the same day, which is the only constraint stopping you from robbing each of them. Given a list of non-negative integers representing the amount of money of each bank, determine the maximum amount of money you can rob tonight without alerting the police. Return -1 when no banks are there. If array: [1, 2, 3] then output is 3, You cannot rob the first bank (money = 1) and then rob the last bank (money = 3), because they are adjacent banks. So here, you can rob any one bank. So the maximum possible money you can rob is from the last bank.

Week - 4 (Submission Date: 5/9/2021)

1. You work as a freelancer and have a pool of 10 projects to work on. For each project you know how much money you will get for completing the project. You can complete any 3 projects this month. You want to select such projects that you will get the most money by completing them. What are the safe moves in this problem? [ Identify the strategy which helps in obtaining global optimal] (a) If there are more than 3 projects in the pool, remove the project with the lowest payment for completion, don't work on this project. In the other case, remove the first project from the pool and work on this project. (b) Take the project which you like the most. (c) Take the project for which you can apply the cool new technology that you've recently learned about. (d) Take the project with the highest payment for completion, complete it and remove it from the pool of projects.

2. You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel at most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances stop1 stop2 . . . ,stopN from your home city. What is the minimum number of refills needed?

   d = 950
   m = 400
   number of stops = 4
   stops distances = 200 375 550 750
   min refills = 2 [at 200 and at 550]

   Provide a greedy approach for finding the minimum number of refills.

3. Minimum number of platforms: Given the arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. This problem is known as Interval Partitioning (Scheduling all the intervals with minimum number of resources). Use a greedy approach to solve the problem.

Week - 5

1. Given an array of integers where each element represents the max number of steps that can be made forward from that element. Find the minimum number of jumps required to reach the end of the array? Example:

   Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
   Output: 3 (1-> 3 -> 8 -> 9)

   What is the optimal substructure for the problem? Like in Longest increasing subsequence(LIS), the input array must be processed in order from left to right. 2. Write a recursive procedure for LIS problem using Dynamic Programming. Also, Enhance the solution using the concept of memoization. 3. What will be the time complexity of the recursive version proposed for ques (2) with and without memoization?