Practice: Week 0 : Assignment 0 (Non Graded)

How many ones does the following procedure print when run with input n?

Read the upper bound on the for loop as 2^n. Consider the options below: A. Θ(2^{n^2}) B. 2^{Θ^{(n^2)}} C. Θ(^{2^{n(n+1)/2}}) D. Θ(n·2^n) E. Θ(n^22^n)

How many connected components result after performing the following sequence of union operations on a set of 10 items? 1-2, 3-4, 5-6, 7-8, 7-9, 2-8, 0-5, 1-9

How many bit strings (i.e, sequences over{0,1}) of length 18 have no consecutive ones? (You may write a program to answer this question, although a calculator should also suffice.)

Mark the correct options.

We have an exponential time algorithm for problem A, and problem A reduces in polynomial time to problem B. From this we can conclude that:

Which of the following is a stable sorting algorithm that takes the least time when applied to an almost sorted array ? (Recall that a sorting algorithm is stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted).

Which of the following statements is true? Statement 1: For every graph G and every maximum flow on G, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that’s possible in the graph. Statement 2: Suppose the maximum (s,t) -flow of some graph has value f. Now we increase the capacity of every edge by 1. Then the maximum (s,t)-flow in this modified graph will have value at most f + 1.

Suppose you have a set of N people who all do not know each other, and you have to process a sequence of queries of the following kinds: Type 1: MakeFriends (x,y) - x and y become friends with each other Type 2: AreFriends (x,y) - output 1 if x and y are friends, and output 0 otherwise In particular, for every pair of people, we need to maintain a state indicating whether they are friends or not, and update this state based on queries of type 1, and report the state for queries of type 2. Since you have learned about the disjoint sets data structures in your algorithms course, you decide to store the set of N people as N singleton sets to begin with. For each query of type 1, you perform a union operation, and for each query of type 2, you perform a find operation. What can you say about this algorithm?

If the rectangular lattice you are given is a 1×5 grid, as shown below, what is the smallest number of moves you need to turn off all the squares?

If the rectangular lattice you are given is a 2×3 grid, as shown below, with the top-left corner on to begin with, in how many moves can you turn off all the squares?

We have a a chessboard and 32 dominoes. Each domino is of such size that it exactly covers two adjacent squares on the board. The 32 dominoes therefore can cover all 64 of the chessboard squares. But now suppose we cut off two squares at diagonally opposite corners of the board and discard one of the dominoes. Is it possible to place the 31 dominoes on the board so that all the remaining 62 squares are covered?

Suppose we have a simple, undirected, connected graph G where all edges have non-negative weights, and in fact, the weight of each edge is either 1 or 20. Consider the following subgraph H of G — the vertex set of H is the same as the vertex set of G and the edge set of H consists of all the edges from G whose weight is one. Suppose H has three connected components with 10, 15, and 30 vertices. Then the weight of any minimum spanning tree of G is:

When an array is to be sorted, it may happen that some data values start out being in the same position where they should end up. For example, in the array which is originally: 45,−4,32,0 the 32 is right where it will be in the final sorted output: . −4,0,32,45 But as a particular sorting algorithm operates, it might (depending on the algorithm) move such an element out of the position where it belongs and move it back eventually. Let’s say that a sorting algorithm respects fixed points if it never moves an element that is in its proper position, on any input. Which of the following statements are true? In the options below, the implementation of selection sort is based on swapping the minimum element into it’s proper place in the current iteration, and does not involve the use heaps. You may also assume that the input array has no duplicate elements.

You are at a party where any two people have an odd number of mutual friends at the party. You see an even number of people other than you. What is the parity of the total number of attendees? Note that we follow the convention that nobody is friends with themselves.

In a party consisting of 5 couples, people who new each other shook hands (pre-covid era) while who did not know each other just greeted each other. One of them, X, observed: “If you don’t count me, then there are no two people present who shook hands the same number of times”. How many times did the wife of X shake hands ? (Nobody shook hands with himself or his spouse!)

Given an undirected graph G, we would like to color its vertices red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices. In other words, suppose the vertices of graph G are partitioned into the sets A and B, and the number of edges with both endpoints in A is denoted as a, and the the number of edges with both endpoints in B is denoted as b. Then, let us define the “quality” of the partition (A,B) as |a−b|and denote this by q(A,B). The goal is then to find a partition (A,B) that minimizes q(A,B). This is equivalent to: