This book was created programmatically by GATE Overflow on Dec 10, 2019. If you feel any doubt regarding the answer, click on the question link and give a comment on the site. Studying all these questions might get you 60 marks in GATE but that might not be enough for an IIT. So, read standard books, solve exercise questions and use these questions for cementing the concepts and aim 85+. At least if you are not getting the solution to a given problem first refer standard book. If any error is found on any question it shall be updated at https://gateoverflow.in/corrections.

PDFs for the remaining subjects will be made available at http://classroom.gateoverflow.in and you can enroll in this course to get notification for the same. Enrollment is free and account details are of GATE Overflow with a new password which have been sent to all registered emails on GATE Overflow. New users will receive this email within a few minutes of confirming their email address.

You can now join our Facebook group for GATE CSE discussions.

You can visit http://playlists.gatecse.in for high quality videos for GATE CSE and how to use GO site/ebook.

CMI and ISI previous year questions

Since GATE Overflow started in August 2014, a lot of people have dedicated their time and effort in bringing this book now. Initiated by Omesh Pandita and Arjun Suresh as a Q/A platform for CSE students, Kathleen Bankson was instrumental in getting all previous year GATE questions here. Then experts like Praven Saini, Happy Mittal, Sankaranarayanan P.N., Suraj Kumar etc. have contributed a lot to the answers here. Pragy Agarwal even after topping GATE has continuously contributed here with his knowledge as well as in making the contents beautiful with fine latex skills. We also have to thank the work by Jothee, Misbah, Ishrat and Nataliyah who are continuously adding and keeping the contents here neat and clean. There are also many toppers of GATE 2015, 2016, 2017 and probably 2018 who are contributing a lot here. The list of all the contributors can be found here but even that does not include the contributions of some like Arif Ali Anapparakkal in helping design this book, Arvind Devaraj and others who have provided guidance and help etc. Last but not the least, we thank all the users of GATE Overflow.

We thank the contributions of Silpa V.S., Rahul Kumar Yadav and others for getting the GATECSE Lastrank page maintained. Bikram Ballav is behind most of the exams on GO (http://mockgate.com) and Arindam Sarkar made the interface for it. Pragy Agarwal is also behind the rank and score predictor tool, (http://mymarks.gatecse.in) used by GO which has 99-100% accuracy over the last 2 years.

Special thanks to Sachin Mittal for making the How to Use GO vidoes, Silpa V.S. for classifying the questions topicwise for the book, Pooja Palod for making the GATE 2018 schedule and Debashish Deka for GO classroom contributions.

Also thanks to all toppers who took time to write a review for GO.

Contributors

Table of Contents

An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu and have fixed the locations of 100 towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least 100 km apart, so that there is no interference of signals.

  1. Describe an algorithm which will answer the question “Is it feasible to set up towers at the given locations and provide service on 7 different frequencies?”. Your algorithm should say “feasible” if it is feasible, otherwise output the minimum number of frequencies needed to utilise all 100 towers.

Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week.
Suppose there are $n$ such matches scheduled during the coming week and you know the starting and finishing time for each match.

  1. Describe an efficient algorithm to compute the following: for each match, what is the next match whose starting time is strictly later than the finishing time of the current match? Analyze the worse-case complexity of your algorithm.

$\text{Air CMI }$operates direct flights between different cities. For any pair of cities $A$ and $B$, there is at most one flight in a day from $A$ to $B$. The online site $FakeTrip$ is tryingto compile a list of all routes available through $\text{Air CMI}$.

  1. $FakeTrip$ has a table of all direct flights operated by $\text{Air CMI}$. From this, it wants to prepare a list of all pairs of cities connected by a sequence of flights. Describe an algorithm for this and analyze the complexity of your algorithm.
  2. $CheapTricks$ is trying to enter the market by improving on $FakeTrip$. $CheapTricks$ has realized that not all connections listed by $FakeTrip$ are feasible because of arrival and departure constraints. $A$ connection from $A$ to $B$ to $C$ is possible if the scheduled arrival of the flight from $A$ to $B$ is at least one hour before the scheduled departure of the flight from $B$ to $C$.

Given a table of direct flights with scheduled arrival and departure times, describe an algorithm for $CheapTricks$ to list all pairs of cities connected by a route on which all connections are feasible within the same day. Analyze the complexity of your algorithm.

The frequency of a number in an array is the number of times it appears in the array. Describe an algorithm that finds the most frequent number in an array of $n$ numbers. If there are multiple numbers with highest frequency then list them all. Analyze the complexity of your algorithm.
Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots \leq A[n]$. You are given a number $x$x. The aim is to find out if there are indices $k$ and $l$ such that $A[k] + A[l] = x$. Design an algorithm for this problem that works in time $O(n)$.
Let $A$ be array of $n$ integers that is not assumed to be sorted. You are given a number $x$. The aim  is to find out if there are indices $k,\: l$ and $m$ such that $A[k] + A[l] + A[m] = x$. Design an algorithm for this problem that works in time $O(n^2)$.
An airline runs flights between several cities of the world. Every flight connects two cities. A millionaire wants to travel from Chennai to Timbuktu by changing at most $k_1$ flights. Being a millionaire with plenty of time and money, he does not mind revisiting the same city multiple times, or even taking the same flight multiple times in his quest. Can you help the millionaire by describing how to compute the number of ways he can make his journey? How many steps does your procedure take if there are $n$ cities and he can change flights at most $k_1$ times. You can assume that the procedure can add or multiply two numbers in a single operation.

A group of war prisoners are trying to escape from a prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as $B$, see picture below) and the prison (marked as $A$) are separated by a canyon which is also guarded by soldiers (marked as $S$). These soldiers sit in their pickets and rarely walk; the range of view of each soldier is limited to exactly $100$ meters. Thus, depending on the locations of soldiers, it may be possible to pass the canyon safely, keeping the distance to the closest soldier strictly larger than $100$ meters from any moment. The situation is depicted in the following picture, where the circles around $S$ indicate the range of view.

Provide an algorithm to determine if the prisoners  can pass the canyon unnoticed, given the width and the length of a canyon and the coordinated of every soldier in the canyon, and assuming that soldiers do not change their locations ($Hint$: Model this as a graph, with soldiers represented by the vertices.)

Given an array $A = \{a_1, a_2, \dots, a_n\}$ of unsorted distinct integers, write a program in pseudo-code for the following problem: given an integer $u$, arrange the elements of the array $A$ such that all the elements in A which are less than or equal to $u$ are at the beginning of the array, and the elements which are greater than $u$ are at the end of the array. You may use at most 5 extra variables apart from the array $A$.

Consider the $fast \: square$ and $multiply \: algorithm$ to calculate $x^y \: mod \: N$ as given below, where $x, \: y,\: N$ are positive integers and $1 \leq x, y < N$.

Input: $x, \:y, \:N$
Output: $x^y \: mod \:N$
1. z = y, u = 1, v = x;
2. while z > 0 do
3. if z $\equiv$ 1 mod 2 then
4. u = uv mod N;
end
5. $v = v^2 \: mod \: N; \: z = \lfloor \frac{z}{2} \rfloor$
end
6. return u
  1. Write a C function to implement the algorithm. Your function should take three arguments $x, y$ and $N$, and return the value $x^y \: mod \: N$, all of which are of type $unsigned long long$ (i.e., 64-bit unsigned integers). 
  2. Discuss whether your program works perfectly for all possible input combinations.
 

Let $M$ be an $(n \times n)$ matrix where each element is a distinct positive integer. Construct another matrix $M'$ by permuting the rows and/or permuting the columns, such that the elements of one row appear in increasing order (while looking from left to right) and those of one column appear in decreasing order (while looking from top to bottom).

  1. Describe an $O(n^2)$ time algorithm for constructing $M'$. Justify your analysis.
  2. Propose a data structure that supports your algorithm. Clearly explain how much additional storage, other than the matrix itself, is required in your algorithm.

A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source vertex $s$ and a designated destination vertex $t$. Let $P(v)$ denote the shortest path (may contain repetition of nodes/edges) from $s$ to $t$ that passes through $v$, and let $l(v)$ denote the path length (i.e., the number of edges) of $P(v)$.

  1. Describe an $O(|V|)$ time algorithm that determines the value of $\mathcal{T}$ where $\mathcal{T} = max_{\forall \: v \in V} l(v)$. Justify your analysis.
  2. Propose a data structure that supports your algorithm.

 

For example, in the graph shown in the above figure, $\mathcal{T}$ = 10, which corresponds to $P(6) : s \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 7 \rightarrow 6 \rightarrow 7 \rightarrow 4 \rightarrow 14 \rightarrow 13 \rightarrow t$.]

Let $A$ be a 30 × 40 matrix having 500 non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column.

Suppose that it is desired to create a stack of size 30 containing the values $r_1,\dots, r_{30}$, not necessarily in order such that the top of the stack contains the value $max_{1\leq i \leq 30} r_i$. Write pseudo-code for creating such a stack using a single scan of the matrix $A$.
  1. Assume you have a chocolate bar containing a number of small identical squares arranged in a rectangular pattern. Our job is to split the bar into small squares by breaking along the lines between the squares. We obviously want to do it with the minimum number of breakings. How many breakings will it take?
  2. Consider that the chocolate bar has n breaking lines along the length and m breaking lines along the breadth. Write a C function that will take n, m as inputs and print the line numbers along the length and the breadth according to your strategy of breaking the chocolate.
Given an array $A$ of n positive integers, write a program segment / pseudo-code to print the histogram of $A$ using the hash character ($\#$). Your histogram should consist of $n$ vertical columns of $\#$ with the $i$-th vertical bar containing $A[i]$ number of $\#$’s. For example, if you consider $A$ as the array $\{4, 1, 2, 1\}$, your output should look like

$\begin{array}{llll} \# \\ \# \\ \# & & \# & \\ \# & \# & \# & \# \end{array}$

You are given a list of positive integers along with a sequence of operations from the set $\left \{ *,+\right \}$ .You construct expressions from these two lists so that:

  • The numbers in the expression are drawn from the first list, without repetition and without altering their order.
  • All the operators in the second list are used in the expression, in the same order.

For example, if the two lists are $[1,3,2,1,4]$ and  $[′∗′,′+′]$  the set of possible expressions you can form are 
$1∗3+2,1∗3+1,1∗3+4,1∗2+1,1∗2+4,\ldots,2∗1+4,1∗3+2,1∗3+1,1∗3+4,1∗2+1,1∗2+4,\ldots,2∗1+4$
For each expression, the value is computed by bracketing operators from the right. That is, the expressions above are evaluated as

$1∗(3+2),  1∗(3+1),  1∗(3+4),  1∗(2+1),  1∗(2+4),…,2∗(1+4),  1∗(3+2),  1∗(3+1),  1∗(3+4),  1∗(2+1),  1∗(2+4),…,2∗(1+4)$
The aim is to determine maximum value among these expressions. In this example, the maximum value is $18$, from the expression $3*2+4,$ which is evaluated as $3∗(2+4) = 3*6 =18$. 
You may assume that the length of the first list is more than the length of the second list. 
Describe an algorithm to solve this problem.

Let $A$ be an array of $n$ integers, sorted, so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there are indices $k$ and $l$ such that $A[k]+A[l] = x$.

  1. Design an $O(n \log n)$ time algorithm for this problem.

Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ and $l$ such that $A[k]+A[l] = x$.

  1. Design an $O(n)$ algorithm for this problem.
There are a number of tourist spots in a city and a company GoMad runs shuttle services between them. Each shuttle plies between a designated origin and destination, and has a name. Due to lack of coordination, the same name may be allotted to multiple routes.

To make matters worse, another company GoCrazy introduces its shuttle services using the same set of shuttle names. A GoMad shuttle and a GoCrazy shuttle with the same name may start at different origins and$/$or end at different destinations.

A pass from a company allows unlimited travel in all the company’s shuttles. For each company, we have a list that specifies all routes allotted to each shuttle name.

Design an algorithm to find out if there is a source $s$, a target $t$, and a sequence of shuttle names $σ$ such that, irrespective of whether you are carrying a GoMad pass or a GoCrazy pass, you can start at $s$ and arrive at $t$ using the sequence $σ$.
Let $A = \{a_1,a_2, \dots ,a_n\}$ be an array of $n$ distinct numbers. The array may not be sorted. The first element $a_1$ is said to be a blip if $a_1 > a_2$. Similar, the last element an is said to be a blip if $a_n > a_{n-1}$. Among the remaining elements, an element $a_i$ is said to be blip if $a_i > a_{i-1}$ and $a_i > a_{i+1}$ where $i \in (2,3, \dots ,n-1)$.  Design an $O(\log n)$ time algorithm for finding a blip in $A$. Justify the complexity of your algorithm.
You are given two strings $S$ and $T$, each of length $\alpha$, consisting only of lower case English letters $(a,b, \dots ,z)$. Propose an $O(\alpha)$-time algorithm to decide whether $S$ can be obtained by permuting the symbols of $T$. For example, if $S \: = \: \text{ algorithm}$, $T \: = \text{ logarithm}$, your algorithm should return $\text{YES}$; but if $S \: = \text{ trainee}$, $T\: = \text{ retinaa}$, your algorithm should return $\text{NO}$.
Consider an array of length n consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers, using $O(n)$ time and only a constant amount of extra space.
Consider a max-heap of $n$ distinct integers, $n ≥ 4$, stored in an array $\mathcal{A}[1 . . . n]$. The second minimum of $\mathcal{A}$ is the integer that is less than all integers in $\mathcal{A}$ except the minimum of $\mathcal{A}$. Find all possible array indices of $\mathcal{A}$ in which the second minimum can occur. Justify your answer.

An automatic spelling checker works as follows. Given a word $w$, first check if $w$ is found in the dictionary. If $w$ is not in the dictionary, compute a dictionary entry that is close to $w$. For instance if the user types $\mathsf{ocurrance}$, the spelling checker should suggest $\mathsf{occurence}$, which belongs to the dictionary. Similarity between words such as $\mathsf{occurrence}$ and $\mathsf{occurrance}$ is quantified in terms of $alignment$.

An alignment between two strings $w1$ and $w2$ (over the alphabet $\{ \mathsf{a, b, c, ...., z} \}$) is obtained by inserting hyphens in the two strings such that the modified strings $align$ (i.e.,the modified strings are of equal length, and at each position, either both strings have the same letter or one of the strings has a hyphen).

here are three examples of alignments. The first is between $\mathsf{ocurrance}$ and $\mathsf{occurrence}$ and the second and third are between $\mathsf{ctatg}$ and $\mathsf{ttaagc}$.

(1)

oc-urr-ance

occurre-nce

(2)

ct-at-g-

-tta-agc

(3)

ctat---g-

---ttaagc

A $mismatch$ in an alignment is a position where one of modified strings has a hyphen and the other does not. There are three mismatches in the first alignment given above, five mismatches in the second, and seven mismatches in the third.

Use dynamic programming to give an efficient algorithm that takes two strings $x$ and $y$ (over the alphabet $\{ \mathsf{a, b, c, ... , z} \}$ as its input, and computes the minimum number of mismatches among all alignments of $x$ and $y$. What is the running time of your algorithm (in terms of the lengths of $x$ and $y)?$

Let $A$ be a sorted array of $n$ positive integers, such that $A[1] \leq A[2] \leq \dots \leq A[n]$. Given an integer $x$ as input, the goal is to find two array indices $k$ and $l$ such that $A[k]+A[l] =x$, if such indices exist; otherwise, the goal is to report 'Failure". Design an algorithm for this problem, that works in $O(n)$ time.
Draw a complete binary tree $T$ with $(N − 1)$ nodes where $N = 2^n$. Suppose each node in $T$ is a processor and each edge of $T$ is a physical link between two processors through which they can communicate. Given $M$ arrays $A_i = \{e_{1i}, e_{2i}, \dots, e_{Ni} \}$ for $1 \leq i \leq M$, develop an algorithm for the given architecture to compute the sum of each array $SUM_i = \Sigma^N_{j=1} e_{ji}$ for all $i$ in $O(\log  N + M)$ time.
Consider the following intervals on the real line: $A_1 = (13.3, 18.3) \: A_3 = (8.3, 23.3) − A_1 \cup A_2$ $A_2 = (10.8, 20.8) − A_1 \: A_4 = (5.8, 25.8) − A_1 \cup A_2 \cup A_3$ where $(a, b) = \{x : a < x < b\}$. Write pseudo-code that calculates (without using any comparison operation) which interval a given input $x \in (5.8, 25.8)$ belongs to, i.e., your pseudo-code should calculate $i \in \{1, 2, 3, 4\}$ such that $x \in A_i$.
You have an array $A$ with $n$ objects, some of which are identical. You can check if two objects are equal but you cannot compare them in any other way — i.e., you can check $A[i] == A[j]$ and $A[i] != A[j]$, but comparisons such as $A[i] < A[j]$ are not meaningful. (Imagine that the objects are JPEG images.) The array A is said to have a majority element if strictly more than half of its elements are equal to each other. Use divide and conquer to come up with an $O(n \log n)$ algorithm to determine if $A$ has a majority element.
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two lists in time $O(\log m + \log n)$.
A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes $n$ units of time for a string of length $n$, regardless of the location of the cut.
Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a $20$-character string at positions $3$ and $10$, then making the first cut at position $3$ incurs a total cost of $20 + 17 = 37$, while doing position $10$ first has a better cost of $20 + 10 = 30$.
Give a dynamic programming algorithm that, given the locations of $m$ cuts in a string of length $n$, finds the minimum cost of breaking the string into $m + 1$ pieces. You may assume that all m locations are in the interior of the string so each split is non-trivial.

Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week.
Suppose there are $n$ such matches scheduled during the coming week and you know the starting and finishing time for each match.

Develop an algorithm based on dynamic programming to compute the maximum number of complete matches you can watch next week. Analyze the worse-case complexity of your algorithm.

At the end of its fifth successful season, the Siruseri Premier League is planning to give an award to the Most Improved Batsman over the five years. For this, an Improvement Index will be computed for each batsman. This is defined as the longest sequence of increasing scores by the batsman among all his scores over the five seasons. For example, if the scores for a batsman over the five seasons are $(20, 23, 6, 34, 22, 52, 42, 67, 89, 5, 100)$, his Improvement Index is $7$ based on the sequence $(20, 23, 34, 52, 67, 89, 100)$. Describe an efficient algorithm based on dynamic programming to compute the Improvement Index for a batsman with an overall sequence of $n$ scores. Analyze the complexity of your algorithm.

There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products along the fibre towards its ends. The possible actions of the virus are as follows

  1. Produce an acid molecule to its left and a base molecule to its right.
  2. Produce a base molecule to its left and an acid molecule to its right.
  3. Divide into two viruses, each of which continues to behave like its ancestor.
  4. Die.

You are given a sequence of acid and base molecules from one end of the fibre to the other end. Design an algorithm to check if a single virus could possibly have produced the given sequence. Use dynamic programming, checking smaller subsequences before checking bigger subsequences.

A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award marks for internal assessment. Instead, each student will be evaluated based on the sum of the best contiguous segment (i.e., no gaps) of marks in the overall sequence of quizzes. However, the student is allowed to drop upto $K$ quizzes before calculating this sum.

Suppose a student has scored the following marks in $10$ quizzes during the semester.

$$\begin{array}{|c|c|c|c|c|}\hline \text{Quiz} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10  \\\hline \text{Marks } & 6 & -5 & 3 & -7 & 6 & -1 & 10 & -8 & -8 & 8 \\ \hline \end{array}$$

Without dropping any quizzes, the best segment is quiz $5-7$, which yields a total of $15$ marks. If the student is allowed to drop upto $2$ quizzes in a segment, the best segment is quiz $1-7$, which yields a total of $24$ marks after dropping quizzes $2$ and $4$. If the student is allowed to drop upto $6$ quizzes in a segment, the best total is obtained by taking the entire list and dropping all $5$ negative entries, yielding $33$ marks.

For $1\leq i<N, 0\leq j\leq K,$ let $B[i][j]$ denote the maximum sum segment ending at position $i$ with at most $j$ marks dropped.

  1. Write a recursive formula for $B[i][j].$
  2. Explain how to calculate, using dynamic programming, the score the professor needs to award each student.
  3. Describe the space and time complexity of your dynamic programming algorithm.
Let $G=(V,E)$ be a undirected graph. We say $S \subseteq V$ is a clique if and only if for all $u,\: v \: \in S$, the edge $(u, v)$ is in $E$.

Now let $G=(V,E)$ be a graph in which each vertex has degree at most 5. Give an algorithm to find the largest clique in $G$. What is the complexity of your algorithm?

You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your friends, so you can complete as many tasks as possible in parallel, on the same day.
Some tasks depend on others: for instance, you cannot purchase foreign exchange till you have bought your ticket. If task $B$ depends on task $A$, you can start $B$ only after you complete $A$. A set of tasks with no pending dependencies can be completed in parallel.
You are given a list of $n$ such tasks to be completed, where each task comes with a set of other tasks that it depends on. The set of tasks is feasible: there are no circular dependencies. You want to compute the minimum number of days needed to complete all the tasks, given the constraints.

  1. Model this problem formally using graphs.
  2. Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
You are given $n$ positive integers, $d_1, d_2 \dots d_n$, each greater than $0$. Design a greedy algorithm to test whether these integers correspond to the degrees of some $n$-vertex simple undirected graph $G = (V, E)$. [A simple graph has no self-loops and at most one edge between any pair of vertices].

A finite sequence of bits is represented as a list with values from the set $\{0,1\}$. For example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. The function $\text{length}(l)$ returns the length (number of bits) in the list $l$. For a nonempty list $l$, $\text{head}(l)$ returns the first element of $l$, and $\text{tail}(l)$ returns the list obtained by removing the first element from $l$. The operator $++$ denotes list concatenation.
For example:

  • $\text{head}([0,1,0]) = 0, \text{tail}([0,1,0]) = [1,0]$,
  • $\text{head}([1]) = 1, \text{tail}([1]) =  [ \: ]$, and
  • $[0,1,0]++[1] = [0,1,0,1]$.

Consider the following functions:
$\text{op}$ takes as input two bits and returns a bit.

op(a,b)
if (a = b) return(0)
else return(1)
endif

$\text{mystery}1$ takes as input two lists and returns a list.

mystery1(s,t)
if (length(s) != length(t)) then return(t)
else if (length(s) = 0) then return(s)
else return([op(head(s),head(t))] ++ mystery1(tail(s),tail(t)))
endif
endif

$\text{mystery}2$ takes as input two lists and outputs a list.

mystery2(s,t)
if (length(t) = 0) then return(s)
else return( mystery1(mystery2(s,tail(t)),mystery2(s,tail(t))))
endif

Suppose $s=t=110100100$. What are the first two bits of $\text{mystery2(s,t)}$?

A finite sequence of bits is represented as a list with values from the set $\{0,1\}$—for example, $[0,1,0], [1,0,1,1], \dots
[ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \text{ head}(l)$ returns the first element of $l$, and $\text{tail}(l)$ returns the list obtained by removing the first element from $l. \: \: a:l$ denotes a new list formed by adding a at the head of list $l$.
For example:
$\text{head}([0,1,0]) \: =\: 0, \text{tail}([0,1,0]) = [1,0]$,
$\text{head}([1]) \: = \: 1, \text{tail}([1]) = [ \: ],$ and
$1:[0,1,0] \: = \: [1,0,1,0]$.

Consider the following functions:
$xor$ takes takes as input two bits and returns a bit.

xor(a,b)
if (a == b) return(0)
else return(1)
endif

$f1$ takes as input a list and returns another list.

f1(s)
if (s == []) then return([1])
else if (head(s) == 0) then return(1:tail(s))
else if (head(s) == 1) then return(0:f1(tail(s)))
endif

$f2$ takes as input a bit and a list and returns a bit.

f2(b,s)
if (s == [ ]) then return(b)
else if (head(s) == 0) then return(f2(xor(b,1),tail(s)))
else if (head(s) == 1) then return(xor(b,1))
endif

$g1$ takes as input a nonnegative number and returns a list.

g1(n)
if (n == 0) then return([0])
else return f1(g1(n-1))
endif

$g2$ takes as input a nonnegative number and returns a bit.

g2(n)
if (n == 0) then return(0)
else return f2(g2(n-1),g1(n))
endif

What is the value of $g2(256)$ and $g2(257)$?

The below question is based on the following program. In the program, we assume that integer division returns only the quotient. For example $7/3$ returns $2$ since $2$ is the quotient and $1$ is the remainder.

mystery(a,b){
        if (b == 0) return a;
        if (a < b) return mystery(b,a);
        if (eo(a,b) == 0){
             return(2*mystery(a/2,b/2));
    }
    if (eo(a,b) == 1){
        return(mystery(a,b/2));
    }
    if (eo(a,b) == 2){
        return(mystery(a/2,b));
    }
    if (eo(a,b) == 3){
        return (mystery((a-b)/2,b));
    }
}
eo(a,b){
if ((a/2)*2 == a and (b/2)*2 == b) return 0; end;
if ((a/2)*2 < a and (b/2)*2 == b) return 1; end;
if ((a/2)*2 == a and (b/2)*2 < b) return 2; end;
return 3;
}

$\text{mystery}(75,210)$ returns

  1. $2$
  2. $6$
  3. $10$
  4. $15$

The below question is based on the following program. In the program, we assume that integer division returns only the quotient. For example $7/3$ returns $2$ since $2$ is the quotient and $1$ is the remainder.

mystery(a,b){
        if (b == 0) return a;
        if (a < b) return mystery(b,a);
        if (eo(a,b) == 0){
             return(2*mystery(a/2,b/2));
    }
    if (eo(a,b) == 1){
        return(mystery(a,b/2));
    }
    if (eo(a,b) == 2){
        return(mystery(a/2,b));
    }
    if (eo(a,b) == 3){
        return (mystery((a-b)/2,b));
    }
}
eo(a,b){
if ((a/2)*2 == a and (b/2)*2 == b) return 0; end;
if ((a/2)*2 < a and (b/2)*2 == b) return 1; end;
if ((a/2)*2 == a and (b/2)*2 < b) return 2; end;
return 3;
}

When $a$ and $b$ are $n$ bit positive numbers the number of recursive calls to $\text{mystery}$ on input $a,\: b$ is

  1. $O(n)$
  2. $O(\log \log n)$
  3. $O(\log n)$
  4. $O(n^{\frac{1}{2}})$

The below question is based on the following program.

procedure mystery (A : array [1..100] of int)
    int i,j,position,tmp;
    begin
        for j := 1 to 100 do
            position := j;
            for i := j to 100 do
                if (A[i] > A[position]) then
                    position := i;
                endfor
            tmp := A[j];
            A[j] := A[position];
            A[position] := tmp;
        endfor
end

When the procedure terminates, the array A has been:

  1. Reversed
  2. Sorted in descending order
  3. Left unaltered
  4. Sorted in ascending order

In the code fragment on the right, start and end are integer values and $\text{prime}(x)$ is a function that returns true if $x$ is a prime number and $\text{false}$ otherwise. At the end of the loop:

i := 0; j := 0; k := 0;
for (m := start; m <= end; m := m+1){
k := k + m;
if (prime(m)){
i := i + m;
}else{
j := j + m;
}
}
  1. $k < i+j$
  2. $k = i+j$
  3. $k > i+j$
  4. Depends on $\text{start}$ and $\text{end}$

Consider the code below, defining the function $A$:

A(m, n, p) {
    if (p == 0) return m+n;
    else if (n == 0 && p == 1) return 0;
    else if (n == 0 && p == 2) return 1;
    else if (n == 0) return m;
    else return A(m, A(m,n-1,p), p-1);
}

Express $A(m, n, 1)$ as a function of $m$ and $n$.

Consider the code below, defining the function $A$:

A(m, n, p) {
    if (p == 0) return m+n;
    else if (n == 0 && p == 1) return 0;
    else if (n == 0 && p == 2) return 1;
    else if (n == 0) return m;
    else return A(m, A(m,n-1,p), p-1);
}

Express $A(m, n, 2)$ as a function of $m$ and $n$.

Consider the code below, defining the function $A$:

A(m, n, p) {
    if (p == 0) return m+n;
    else if (n == 0 && p == 1) return 0;
    else if (n == 0 && p == 2) return 1;
    else if (n == 0) return m;
    else return A(m, A(m,n-1,p), p-1);
}

Compute $A(2, 2, 3)$ and $A(2, 3, 3)$.

Consider the code below, defining the functions $f$ and $g$:

f(m, n) {
    if (m == 0) return n;
    else {
        q = m div 10;
        r = m mod 10;
        return f(q, 10*n + r);
    }
}
g(m, n) {
    if (n == 0) return m;
    else {
        q = m div 10;
        r = m mod 10;
        return g(f(f(q, 0), r), n-1);
    }
}

Compute $g(3, 7), \: g(345, 1), \: g(345, 4) \text{ and } \: g(345, 0)$.

Consider the code below, defining the functions $f$ and $g$:

f(m, n) {
    if (m == 0) return n;
    else {
        q = m div 10;
        r = m mod 10;
        return f(q, 10*n + r);
    }   
}
g(m, n) {
    if (n == 0) return m;
    else {
        q = m div 10;
        r = m mod 10;
        return g(f(f(q, 0), r), n-1);
    }
}

What does $g(m, n)$ compute, for nonnegative numbers $m$ and $n$?

Let $x, y$ be two non-negative integers $< 2^{32}$. By $x \wedge y$ we mean the integer represented by the bitwise logical $AND$ of the 32- bit binary representations of $x$ and $y$. For example, if $x = 13$ and $y = 6$, then $x \wedge y$ is the bitwise $AND$ of 0$^{28}$1101 and 0$^{28}$0110, resulting in 0$^{28}$0100, which is 4 in decimal. (Here 0$^{28}$1101 means twenty-eight 0’s followed by the 4-bit string 1101.) Now consider the following pseudo-code:
integer x, n = 0;
while (x $\neq$ 0){
x $\leftarrow$ x $\wedge$ (x − 1);
n $\leftarrow$ n + 1;
}
print n;

  1. What will be the output of the pseudo-code for the input $x = 13$?
  2. What will be the output of the pseudo-code for an arbitrary non-negative integer $x < 2^{32}$?

A finite sequence of bits is represented as a list with values from the set $\{0,1\}$—for example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \text{ head}(l)$ returns the first element of $l$, and $\text{tail}(l)$ returns the list obtained by removing the first element from $l. a:l$ denotes a new list formed by adding a at the head of list $l$.
For example:
$\text{head}([0,1,0]) \: =\: 0, \text{tail}([0,1,0]) = [1,0]$,
$\text{head}([1]) \: = \: 1, \text{tail}([1]) = [ \: ],$ and
$1:[0,1,0] \: = \: [1,0,1,0]$.

Consider the following functions:
$xor$ takes takes as input two bits and returns a bit.

xor(a,b)
if (a == b) return(0)
else return(1)
endif

$f1$ takes as input a list and returns another list.

f1(s)
if (s == []) then return([1])
else if (head(s) == 0) then return(1:tail(s))
else if (head(s) == 1) then return(0:f1(tail(s)))
endif

$f2$ takes as input a bit and a list and returns a bit.

f2(b,s)
if (s == [ ]) then return(b)
else if (head(s) == 0) then return(f2(xor(b,1),tail(s)))
else if (head(s) == 1) then return(xor(b,1))
endif

$g1$ takes as input a nonnegative number and returns a list.

g1(n)
if (n == 0) then return([0])
else return f1(g1(n-1))
endif

$g2$ takes as input a nonnegative number and returns a bit.

g2(n)
if (n == 0) then return(0)
else return f2(g2(n-1),g1(n))
endif

What is the value of $g2(7)$ and $g2(8)$?

Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other vertex in $V$. We now increase the weight of every edge in the graph by 1. Are the following true or false, regardless of the structure of $G$? Give a mathematically sound argument if you claim the statement is true or a counterexample if the statement is false.

$T$ is still a minimum cost spanning tree of $G$.
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other vertex in $V$. We now increase the weight of every edge in the graph by $1$. Are the following true or false, regardless of the structure of $G$? Give a mathematically sound argument if you claim the statement is true or a counterexample if the statement is false.

All the shortest paths from $s$ to the other vertices are unchanged.

Let $P_1(x, y_1),\: P_2(x, y_2), \dots, P_n(x, y_n)$ be a collection of $n$ distinct points lying on a vertical line $L$. The value of $x$ is stored in a variable, and $y_1, y_2, \dots, y_n$ are stored in an array in decreasing order. Additionally, you are given two points $S(x′, y′)$ and $D(x′′, y′′)$, one on either side of $L$. A route $R$ from $S$ to $D$ is a two-hop path $S \rightarrow P_k \rightarrow D$, where $P_k$ is one of the points from $\{P1, P2, \dots, P_n\}$. The cost of $R$ is defined as the sum of the lengths of $SP_k$ and $P_kD$. Design an $O(\log  n)$-time algorithm to find the minimum-cost route from $S$ to $D$, i.e., your task is to select an appropriate point $P_k$ on $L$ such that the cost of the route $R$ from $S$ to $D$ through $P_k$ is minimized.

Consider the following statements.

  1. NP-complete problems are those that we know we can never solve efficiently.
  2. If we find an efficient algorithm for one NP-complete problem, then we can solve all NP-complete problems efficiently.
  3. Checking whether a number is a prime is an NP-complete problem.

Then:

  1. $1$ and $2$ are true but $3$ is false.
  2. $1$ and $3$ are false but $2$ is true.
  3. $2$ and $3$ are true but $1$ is false.
  4. All three statements are false.

Suppose we have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following can we infer from this fact?

  1. If the best algorithm for $B$ takes exponential time, there is no polynomial time algorithm for $A$.
  2. If the best algorithm for $A$ takes exponential time, there is no polynomial time algorithm for $B$.
  3. If we have a polynomial time algorithm for $A$, we must also have a polynomial time algorithm for $B$.
  4. If we don’t know whether there is a polynomial time algorithm for $B$, there cannot be a polynomial time algorithm for $A$.

Let $A$ be an $n\times n $ matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number $k$ appears in $A.$ If $k$ is present, we should report its position - that is, the row $i$ and column $j$ such that $A(i,j)=k.$ Otherwise, we  should declare that $k$ is not present in $A.$

  1. Describe an algorithm that solves this problem in time $O(n\log n).$ Justify the complexity of your algorithm.
  2. Describe an algorithm that solves this problem by examining at most $2n$ values in $A.$ Justify the complexity of your algorithm.
  3. For both algorithms, describe a worst-case input where $k$ is present in $A.$
Solve the following recurrence ($n$ is a natural number):

$T(n) = \begin{cases} 7T(n/3)+n^2 & n>2 \\ 1 & n \leq 2. \end{cases}$

You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time.

  1. Formulate a recurrence relation for counting $a_n$, the number of distinct ways in which you can climb up the staircase.
  2. Mention the boundary conditions for your recurrence relation.
  3. Find a closed form expression for $a_n$ by solving your recurrence.

Consider the code below, defining the function $\text{mystery}:$

mystery(a,b){
    if (a < 0 or b < 0) return 0;
    else if (a == 0) return b+1;
    else if (b == 0) return mystery(a-1,1);
    else return mystery(a-1, mystery(a,b-1));
}
  1. Express $\text{mystery}(1, \:n)$ as a function of $n$.
  2. Express $\text{mystery}(2,\: n)$ as a function of $n$.
  3. Compute $\text{mystery}(3, \:2)$ and $\text{mystery}(3, 3)$.

Alan’s task is to design an algorithm for a decision problem $P$. He knows that there is an algorithm $A$ that transforms instances of P to instances of the Halting Problem such that $\text{yes}$ instances of $P$ map to $\text{yes}$ instances of the Halting Problem, and $no$ instances of $P$ map to $\text{no}$ instances of the Halting problem. Which of the following is true.

  1. The existence of $A$ implies the existence of an algorithm for $P$.
  2. The existence of $A$ implies that there is no algorithm for $P$.
  3. The existence of $A$ says nothing about whether there is an algorithm for $P$.
  4. The Halting Problem can be solved using $A$.

We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference?

  1. If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$
  2. If the best algorithm for $A$ takes exponential time, then there is no polynomial time algorithm for $B$.
  3. If we have a polynomial time algorithm for $A$, then we must also have a polynomial time algorithm for $B$
  4. If we don’t know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.
The Income-Tax Department had prepared a list D of names of defaulters on March $31$. However, the government extended the deadline to pay taxes till April $15$.
The IT department has now received two additional lists of names: a list B of names of people who have paid their taxes between April $1$ and April $15$ at a bank, and a list O of names of people have paid their taxes during this period online. Some people have paid part of their taxes at a bank and part online, so there may be names that appear in both B and O.
From the lists D, B and O, the IT department wants to prepare a revised list of defaulters. The names in the original list D are sorted in alphabetical order while the names in B and O are listed according to the date on which they paid their taxes. Fortunately, no two people have the same name.
Describe an efficient algorithm to compute the revised list of defaulters. Assume that the size of D, B and O is n, m and k respectively and that $n > m > k$. Describe the running time of your algorithm in terms of these parameters.
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk is at the bottom of the pile. The only operation available for manipulating the disks is to pick up a stack of them from the top of the pile and invert that stack. (This corresponds to lifting up a stack $\text{dosas}$ or $\text{chapatis}$ between two big spoons and flipping the stack.)

Give an algorithm for sorting the disks using this operation.
Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk is at the bottom of the pile. The only operation available for manipulating the disks is to pick up a stack of them from the top of the pile and invert that stack. (This corresponds to lifting up a stack $\text{dosas}$ or $\text{chapatis}$ between two big spoons and flipping the stack.)

How many steps will your algorithm take in the worst case?

You are given two sorting algorithms A and B that work in time $O(n \log n)$ and $O(n^2)$, respectively. Consider the following statements:

  1. Algorithm $A$ will sort any array faster than algorithm $B$.
  2. On an average, algorithm $A$ will sort a given array faster than algorithm $B$.
  3. If we need to implement one of the two as the default sorting algorithm in a system, algorithm $A$ will always be preferable to algorithm $B$.


Which of the statements above are true?

  1. I, II and III
  2. I and III
  3. II and III
  4. None of them

You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time:

  1. $O(nm \log  m)$
  2. $O(mn \log  n)$
  3. $O(m + n)$
  4. $O(mn)$

A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of three-dimensional points

$[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)].$

We sort these in ascending order by the second coordinate. Which of the following corresponds to a stable sort of this input?

  1. $[(9, 0, 9),(7, 1, 8),(6, 1, 4),(0, 2, 5),(6, 5, 9),(3, 5, 7)]$
  2. $[(0, 2, 5),(3, 5, 7),(6, 1, 4),(6, 5, 9),(7, 1, 8),(9, 0, 9)]$
  3. $[(9, 0, 9),(7, 1, 8),(6, 1, 4),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
  4. $[(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
Give a strategy to sort four given distinct integers $a, b, c, d$ in increasing order that minimizes the number of pairwise comparisons needed to sort any permutation of $a, b, c, d$.

There are $n$ students of a class standing in a line. The students have to arrange themselves in ascending order on the basis of their roll numbers. This rearrangement of the line must be accomplished only by successively swapping pairs of adjacent students.

  1. Design an algorithm for this purpose that minimizes the number of swaps required.
  2. Derive an expression for the number of swaps needed by your algorithm in the worst case.

You are given $k$ sorted lists, each containing $m$ integers in ascending order. Assume that (i) the lists are stored as singly-linked lists with one integer in each node, and (ii) the head pointers of these lists are stored in an array.

  1. Write an efficient algorithm that merges these k sorted lists into a single sorted list using $\theta (k)$ additional storage.
  2. How would you modify your algorithm if you were permitted to use only constant additional storage?

Analyse the time complexity of your algorithm for each of the above two cases.

Suppose you have the following three subroutines:

  • $\text{max}(A, i, j)$: returns the index of the maximum among the set of consecutive elements $A[i, \dots, j]$ of the array $A$.
  • $\text{min}(A, i, j)$: returns the index of the minimum among the set of consecutive elements $A[i, \dots, j]$ of the array $A$.
  • $\text{swap}(A, i, j)$: swaps the two elements $A[i]$ and $A[j]$ in the array $A$.

Design an $O(n \log \: n)$ time algorithm which can use only these three subroutines to sort a given array $A = \{A[i]|i = 1, 2, \dots, n\}$ of distinct integers. Assume that the time complexity of the first two subroutines is $O(k)$, where $k = j − i$, and that for the third subroutine is $O(1)$.

Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.
Let $A$ and $B$ be two arrays, each containing $n$ distinct integers. Each of them is sorted in increasing order. Let $C = A  \cup B$. Design an algorithm for computing the median of $C$ as efficiently as you can.
Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of M players, numbered $1, 2, \dots , M$. You have $N$ players, numbered $1, 2, \dots  , N$ from which to choose your team, where $N \geq M$. Each of the $M$ players from the visiting team must be paired up with one of your $N$ players. The tournament rules insist that the pairings must respect the order that has been fixed for both teams. That is, when you pick players $i_1, i_2, \dots i_M$, to play against opponents numbered $1, 2, \dots , M$, it must be the case that $i_1 < i_2 < \dots < i_M$, in terms of the order $1, 2, \dots , N$ in which your players are listed.
You want to ensure a good fight, so you plan to pick your team so that the teams are as
evenly balanced as possible. Each player $j$ on your team has a numerical score $Y S(j)$ that represents his or her playing ability. Likewise, each player $i$ in the opponent team has a playing ability indicated by a numerical score $OS(i)$. The difference in strength between a player $i_j$ from your team and his or her opponent $j$ on the visiting team is the absolute value $\mid Y S(i_j ) − OS(j) \mid$. The imbalance of a pairing is the sum of these differences across all M match-ups in the pairing. Your aim is to minimize this imbalance.
For instance suppose you have six players, whose strengths are as follows.

$\begin{array}{|c|c|c|c|c|c|c|} \hline i & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline YS(i) & 2 & 3 & 4 & 1 & 5 & 7 \\ \hline \end{array}$

Also, suppose that the visiting team has three players, whose strengths are as follows.

$\begin{array}{|c|c|c|c|} \hline i & 1 & 2 & 3 \\ \hline OS(i) & 2 & 9 & 2 \\ \hline \end{array}$

In this situation, the most balanced pairing is $(1,1)$, $(3,2)$ and $(4,3)$, which yields an imbalance of
$\mid Y S(1) − OS(1)\mid+\mid Y S(3) − OS(2) \mid+\mid Y S(4) − OS(3) \mid = \mid 2 − 2 \mid + \mid 4 − 9 \mid + \mid 1 − 2 \mid = 6$
Propose an efficient algorithm to solve this problem and analyse its complexity.

The below question is based on following program:

procedure mystery (A : array [1..100] of int)
    int i,j,position,tmp;
    begin
        for j := 1 to 100 do
            position := j;
            for i := j to 100 do
                if (A[i] > A[position]) then
                    position := i;
                endfor
            tmp := A[j];
            A[j] := A[position];
            A[position] := tmp;
        endfor
end

The number of times the test $A[i] > A[\text{position}]$ is executed is:

  1. $100$
  2. $5050$
  3. $10000$
  4. Depends on contents of $A$

How many times is the comparison $i \geq n$ performed in the following program?

int i=85, n=5;
main() {
    while (i >= n) {
        i=i-1;
        n=n+1;
    }
}
  1. $40$
  2. $41$
  3. $42$
  4. $43$

Consider the code below, defining the functions $f$ and $g$:

f(m, n) {
    if (m == 0) return n;
    else {
        q = m div 10;
        r = m mod 10;
        return f(q, 10*n + r);
    }
}
g(m, n) {
    if (n == 0) return m;
    else {
        q = m div 10;
        r = m mod 10;
        return g(f(f(q, 0), r), n-1);
    }
}

How much time does it take to compute $f(m, n)$ and $g(m, n)$?

We are given a sequence of pairs of integers $(a_1, b_1),(a_2, b_2), \dots ,(a_n, b_n)$. We would like to compute the largest $k$ such that there is a sequence of numbers $c_{i_1} \leq c_{i_2} \leq \dots \leq c_{i_k}$ with $1 \leq i_1 < i_2 < \dots < i_k \leq n$ and for each $j \leq k$, $c_{i_j}=a_{i_j}$ or $c_{i_j} = b_{i_j}$ . Describe an algorithm to solve this problem and explain its complexity.

Consider the following function that takes as input a sequence $A$ of integers with n elements,$A[1],A[2], \dots ,A[n]$ and an integer $k$ and returns an integer value. The function length$(S)$ returns the length of the sequence $S$. Comments start with //.

function mystery(A, k){
n = length(A);
if (k > n) return A[n];
v = A[1];
AL = [ A[j] : 1 <= j <= n, A[j] < v ]; // AL has elements < v in A
Av = [ A[j] : 1 <= j <= n, A[j] == v ]; // Av has elements = v in A
AR = [ A[j] : 1 <= j <= n, A[j] > v ]; // AR has elements > v in A
if (length(AL) >= k) return mystery(AL,k);
if (length(AL) + length(Av) >= k) return v;
return mystery(AR, k - (length(AL) + length(Av)));
}
  1. Explain what the function computes.
  2. What is the worst-case complexity of this algorithm in terms of the length of the input sequence $A$?
  3. Give an example of a worst-case input for this algorithm.
Consider the $\text{fast  square}$ and $\text{multiply algorithm}$ to calculate $x^y \text{ mod } N$ as given below, where $x, \: y,\: N$ are positive integers and $1 \leq x, y < N$.

Input: $x, \:y, \:N$

Output: $x^y \: \text{ mod } N$

1. $z = y, u = 1, v = x;$

2. while $z > 0$ do

3. if $z \equiv \: 1$ mod $2$ then

4. $u = uv \text{ mod } N$;

end

5. $v = v^2 \text{ mod } N; \:  z = \lfloor \frac{z}{2} \rfloor$

end

6. return $u$.

What is the time complexity of the algorithm in terms of $N$? [Note that $N$ can be a very large integer, e.g., more than $512$ bits. Assume that the time complexity of modular multiplication is $O(log^2 \: N)$, when the positive integers involved are less than $N$.]
A file $F$ holds the non-zero elements of two large $n \times n$ matrices, $a$ and $B$. The matrix entries are sorted as triplets $(i, j, \text{value})$, where $\text{value}$ is the $(i,j)$th element of a matrix. The file first stores the element of $A$ and then those of $B$. The matrix elements are stored in $F$ in an arbitrary order. In each matrix, only the elements

$$\begin{array}{c}(i,i):=i=1, \dots ,n\}, \\ \{(j,j+1):j=1, \dots ,n-1\} \text{ and } \\ \{(j+1, j); j=1, \dots ,n-1\} \end{array}$$

are non-zero. You are to add $A$ and $B$ and store the sum in $C$ and then print $A$, $B$ and $C$. Due to limited memory, for storing all three matrices, you can use space to hold only up to $9n$ values (NOT triplets). Is it possible to have a $O(n)$ solution? If no, give reasons. If yes, provide a solution. Clearly explain the data structure and how you are going to store, retrieve, and add the elements.
Let $A=(a_1, a_2, \dots , a_n)$ be an array of $n$ distinct numbers. The array may not be sorted. The $\text{first}$ element $a_1$ is said to be a $\text{blip}$ if $a_1 > a_2$. Similarly, the $\text{last}$ element $a_n$ is said to be a $\text{blip}$ if $a_n>a_{n-1}$. Among the remaining elements, an element $a_i$ is said to be $\text{blip}$ if $a_i > a_{i-1}$ and $a_i>a_{i+1}$ where $ i \in \{2, 3, \dots , n-1\}$. Design an $O(\log n)$ time algorithm for finding a $\text{blip}$ in $A$. Justify the complexity of your algorithm.

The average memory access time for a microprocessor with first level cache is $3$ clock cycles.

  • If data is present in the cache, it is found in $1$ clock cycle.
  • If data is not found in the cache, $100$ clock cycles are needed to get it from off-chip memory.

It is desired to obtain a $50 \%$ improvement in average memory access time by adding a second level cache.

  • This second level cache can be accessed in $6$ clock cycles.
  • The addition of this second level cache does not affect the first level cache.
  • Off-chip memory accesses still require $100$ clock cycles.

To obtain the desired speedup, how often must data be found in the second level cache?

b. Two modules $M_1$ and $M_2$ of an old machine are being replaced by their improved versions $M_3$ and $M_4$, respectively in a new machine. With respect to the old machine, the speed-up of these modules ($M_3$ and $M_4$) are $30$ and $20$, respectively. Only one module is usable at any instant of time. A program $P$, when run on the old machine, uses $M_1$ and $M_2$ for $30 \%$ and $20 \%$ of the total execution time, respectively. Calculate the overall speed-up of $P$ when it is executed on the new machine.

Assume a machine has $4$ registers (one of which is the accumulator $A$) and the following instruction set.

  • $\text{LOAD}$ and $\text{STORE}$ are indirect memory operations that load and store, using the address stored in the given register operand. Thus, $\text{LOAD R}$ loads the contents of $\text{memory}[R]$ into $A$, and $\text{STORE R}$ stores the contents of $A$ in $\text{memory[R]}$.
  • $MOV$ copies any register into any other register.
  • $ADD$ and $SUB$ operate on the accumulator and one other register, such that $A = A \text{ op } R$.
  • $LDC$ stores a given $7$-bit constant in the accumulator.
  • $BRA$, $BZ$, and $BNE$ are branch instructions, each taking a $5$ – bit offset.

Design an instruction encoding scheme that allows each of the above instructions (along with operands) to be encoded in $8$ bits.

A machine $\mathcal{M}$ has the following five pipeline stages; their respective time requirements in nanoseconds (ns) are given within parentheses:

  • $F$-stage — instruction fetch ($9$ ns),
  • $D$-stage — instruction decode and register fetch ($3$ ns),
  • $X$-stage — execute/address calculation ($7$ ns),
  • $M$-stage — memory access ($9$ ns),
  • $W$-stage — write back to a register ($2$ ns).

Assume that for each stage, the pipeline overhead is $1$ ns. A program $P$ having $100$ machine instructions runs on $\mathcal{M}$, where every $3$rd instruction needs a $1$ – cycle stall before the $X$-stage. Calculate the CPU time in seconds for completing $P$.

Consider the following timings for a five-stage processor pipeline (these timings include the latching overhead):

$$\begin{array}{ll} \text{Fetch} & 305 \text{ ps} \\  \text{Decode} & 275 \text{ ps} \\   \text{Execute} & 280 \text{ ps} \\  \text{Memory} & 305 \text{ ps}  \\ \text{Write Back} & 250 \text{ ps}  \\ \end{array}$$

  1. Given the timings for the datapath stages listed above, what would be the clock period for the entire datapath?
  2. In a pipelined datapath, assuming no hazards or stalls, what will be the throughput (instructions per second) in steady state?
  3. Assuming that $N$ instructions are executed, and that all $N$ instructions are add instructions, what is the speedup of this pipelined implementation compared to a nonpipelined implementation? Assume that each add instruction consists of Fetch, Decode, Execute and Write Back.

Consider the following programming errors:

  1. Type mismatch in an expression.
  2. Array index out of bounds.
  3. Use of an uninitialized variable in an expression.

Which of these errors will typically be caught at compile-time by a modern compiler.

  1. I, II and III
  2. I and II
  3. I and III
  4. None of them

In programming language terminology, $\text{ call by value }$ refers to the fact that:

  1. A function call can return a value.
  2. When a function is called, arguments are copied into local storage.
  3. Functions can indirectly modify the value of external variables.
  4. Every argument passed to a function must have a value.

In programming languages like C, C++, Python $\dots$ the memory used by a program is typically separated into two parts, the stack and the heap. Consider the following statements:

  1. A stack is efficient for managing nested function calls.
  2. Stack space is limited while heap space is not.
  3. The stack cannot be used for persistent data structures.

Then:

  1. $1$ and $2$ are true but $3$ is false.
  2. $1$ and $3$ are true but $2$ is false.
  3. $2$ and $3$ are true but $1$ is false.
  4. All three statements are true.

Suppose we are working with a programming language that supports automatic garbage collection. This means that:

  1. Uninitialized variables are assigned null values.
  2. Unreferenced dynamically allocated memory is added back to free space.
  3. Unreachable $\text{if – then – else}$ branches are pruned.
  4. Expressions where array indices exceed array bounds are flagged.

Consider the use of Cyclic Redundancy Code (CRC) with generator polynomial $G(x)$ for error detection. Recall that error detection with a CRC works by appending the CRC value to the bit sequence to make it a multiple of $G(x)$.

  1. Calculate the CRC value of the bit sequence $1 \: 1 \: 0 \: 0 \: 1 \: 1$, if $G(x) = x^4 + x^3 + 1$.
  2. A $\text{burst error}$ of length $k$ means that there are $k$ bits from the first to the last error positions in the frame, including both positions. Note that the intermediate bits may or may not be in error. For example, if $1 \: 0 \: 1 \: 1 \: 0 \: 0$ is transmitted and $1 \: 1 \: 0 \: 1 \: 1 \: 0$ is received, then we can say that a burst error of length $4$ has occurred. Construct a burst error of length $5$ in such a way that the error cannot be detected by the CRC with the $G(x)$ given above.

The data link layer uses a fixed-size sliding window protocol, where the window size for the connection is equal to twice the bandwidth-delay product of the network path. Consider the following three scenarios, in each of which only the given parameter changes as specified (no other parameters change). For each scenario, explain whether the throughput (not utilization) of the connection increases, decreases, remains the same, or cannot be determined:

  1. the packet loss rate $L$ decreases to $L/3$;
  2. the minimum value of the round trip time $R$ increases to $1.8R$;
  3. the window size $W$ decreases to $W/3$
A block of bits with $n$ rows and $m$ columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expression for the probability that the error will be detected.
  1. Consider sending a large file of $360,000$ bits from Host $A$ to Host $B,$ connected through a router, as shown in the below figure $2.$ Assume that there is no queuing and propagation delay, and the router has sufficient buffer space. Host $A$ splits the file into segments of $S$ bits each and adds $36$ bits of header to each segment, forming packets of $(36+S)$ bits. Each link has a transmission rate of $R\: \text{bps}.$ Find the value of $S$ that minimizes the time needed to move the file from Host $A$ to Host $B.$
  2. The $CPU$ of a system having an execution rate of $1$ million instructions per second needs $4$ machine cycles on an average for executing an instruction. On an average, $50\%$ of the cycles use memory bus. For execution of the programs, the system utilizes $90\%$ of the $CPU$ time. For block data transfer, an $I/O$ device is attached to the system, while the $CPU$ executes background programs continuously. Determine the maximum $I/O$ transfer rate for each of the two cases: 
    1. programmed $I/O$
    2. cycle-stealing $DMA$ (in transparent mode)

You may assume that transferring one byte involves $4$ operations: in-status, check-status, branch and read/write in memory, each requiring one machine cycle.

In a LAN, $n^2$ routers are connected in an $n \times n$ mesh such that $R(i, j)$ represents a router in the $i$-th row and $j$-th column of the mesh.

  1. Find how many distinct shortest paths exist between two routers $R(i_1, j_1)$ and $R(i_2, j_2) \: (1 \leq i_1, j_1, i_2, j_2 \leq n)$. Two paths are distinct if they differ in at least one link.
  2. At most how many of these distinct shortest paths will be node disjoint, i.e., with no common node except the source and the destination? Justify your answer.
Stations $A$ and $B$ are connected through a line of bandwidth $64$ $\text{kbps}$. Station $A$ uses $16$ $\text{byte}$ packets to transmit messages to $B$ using a sliding window protocol. The round trip propagation delay between $A$ and $B$ is $50$ $\text{milliseconds}$. Determine the window size $A$ should use to maximize the line utilization. Assume that the ack frame is of negligible size and processing delay may be ignored. Justify your answer.

A network has $125$ stations attached by a dedicated pair of lines to a hub in a star topology. The distance from each station to the hub is $25$ meters, the speed of the transmission lines is $10$ Mbps, all frames are of length $12500$ bytes, and the signal propagates on the line at a speed of $2.5 \times 10^8$ meters/second. Assume that token-ring protocol is used for medium access control. Assume single-frame operation, eight-bit latency at each station, and a free token is of three bytes long.

  1. Find the effective frame transmission time.
  2. Assume that each station can transmit up to a maximum of $k = 2$ frames/token. Find the maximum throughput of the network.
A heavily loaded $1$ km long, $10$ Mbps token ring network has a propagation speed of $200$ meter per micro-second. Fifty stations are uniformly spaced around the ring. Each data packet is $256$ bits long, including $32$ bits of header. The token is of $8$ bits. What is the effective data rate of the network assuming the stations always have packets to transmit?

A school database maintains the following relations for its students, teachers and subjects:

  • Student(st_name, st_address, class, section, roll_no, regn_no)
  • Teacher(t_name, t_address, tel_no)
  • Subject(s_name, t_name, text_book, class)
    

Consider the following constraints on the existing data.

  • A student after admission to the school is assigned with a unique regn no. However, a student also gets a roll no that starts from $1$ for each class and section. A class can have many sections and a student is placed in only one class and section as expected in a school.
  • In the school a teacher’s name (t_name) has been found to be unique. However, more than one teacher may stay at the same address and the tel no is a land line connection where an address will have only one such telephone.
  • A subject name (s_name) is unique but the same subject may be taught in many classes (for example, History may be taught in many classes with different contents but s name remains the same). Every subject has a set of standard text books for a class and there may be more than one teacher who can teach the subject. Any teacher may use any of the standard text books to teach a subject.
  1. Considering the above constraints, identify the functional /multivalued dependencies present and normalize the relations.
  2. Using the normalized set of relations answer the following query using relational algebra or SQL: List all the teachers (t_name) who can teach History in Class V and reside in “Baranagar” (name of a locality). Consider that any address offers a locality name.
Suppose we have a relation $R(A, B, C, D, E)$ with the functional dependencies:
$A \rightarrow D, B \rightarrow C, D \rightarrow E, CE \rightarrow B$.

If we project $R$ and therefore its functional dependencies onto the schema $ABC$, what will the key(s) for $ABC$ be?

Two queries equivalent to each other are specified for a relation $R(A, B, C, D, E, F)$. The queries are:

  • $\pi_{A,B,C}(\sigma B>500(R))$
  • $\sigma B>500(\pi_{A,B,C}(R))$

The system maintains a $B+$ tree index for $(A, B, C)$ on $R$. However, the index is unclustered. The relation $R$ occupies $100$ pages and the index structure needs $5$ pages only. Compute the number of disk accesses required for each of the queries and thereby decide which one of the two queries will be preferred by the query optimizer for minimum cost of execution. The cost of query execution is primarily dependent on the number of disk accesses.

Let $R(A,B,C)$ be a relation with primary key $(A)$ and $S(A, D, E)$ a relation with primary key $(A, D)$. Each of the relations has $n$ tuples. If the number of tuples in $R \: \text{ natural join } S$ is $m$, then determine the number of tuples in $R$ $\text{ natural left outer join } S$.

Consider relations $R(A, B)$ and $S(B, C)$. Find a propositional formula $\phi$ such that the following two relational algebra expressions produce the same answer.

  • $\pi_{A,B}(\sigma_\phi(R \bowtie S))$
  • $R \cap ({\rho_T(A)}(\pi_C(S)) \times \pi_B(S))$

Consider a LIBRARY database consisting of the following entity sets:

  • Book (bookid, title, publishername)
  • Book authors (bookid, authorname)
  • Publisher (publishername, address, phonenumber)
  • Bookcopies (bookid, accessionnumber)
  • Book loans (bookid, cardnumber, issuedate, duedate)
  • Borrower (cardnumber, name, address, phonenumber)

Write a relational algebra expression for retrieving the names of the borrowers who do not have any book issued. Hence write an equivalent SQL statement for the above query.

Consider the following schema:

  • SUPPLIER (supId : integer, supName : string, supAddress : string)
    PARTS (partId : integer, partName : string, partColour : string)
    CATALOG (supId : integer, partId : integer, price : real)

The key fields are underlined, and the domain of each field is listed after the field name. The CATALOG relation lists the prices charged for parts by suppliers.

  1. Let the relations have the following properties: 

    $\begin{array}{|l|l|l|} \hline \text{Relation} & \text{Total Number of Tuples} & \text{No. of tuples per block} \\ \hline \text{SUPPLIER} & 2,000 & 25 \\ \hline \text{PARTS} & 4,500 & 30 \\ \hline  \text{CATALOG} & 9,000 & 45 \\ \hline \end{array}$

    Estimate the number of block accesses required to produce the result of the following query: Find the names of suppliers who supply every part.

  2. Write the above query (given in (a)) in relational algebra using some or all of the following operators: SELECT, PROJECT, JOIN, CARTESIAN PRODUCT, UNION, INTERSECTION, DIFFERENCE.

Consider two $n \times 1$ vectors $u$ and $v$ , stored as table $U(\text{ind,val})$ and $V(\text{ind,val})$ with the same schema A row $(i,u_i)$ of table $U$ specifies the $i^{th}$ element of vector $u$ has value $u_i$  (similarly for $v$, respectively). Only the non-zero entries of the vectors are stored in the corresponding tables. For example, if the vector $u$ equals $(0, 1, 3, 0, 2, 0)$, then it is represented in table $U$ as $$\begin{array}{|l|l|} \hline \textbf{ind}&\textbf{val} \\\hline 2&1 \\3&3 \\5&2\\ \hline \end{array}$$

Write a relational algebra expression or an SQL query to compute the sum $u + v$ of the two vectors $u$ and $v$. Explain your solution.
Consider the following relations:

$\text{STD_CHOICES } (\underline{\text{Student_ID}}, \underline{\text{Course_ID}}, \text{Semester})$ and

$\text{COURSE_ASSIGN} (\underline{\text{Teacher_ID}}, \underline{\text{Course_ID}}, \underline{\text{Semester}})$.

The former indicates the choice of courses for students and the latter indicates the course assigned to teachers for different semesters. Note that each student may take multiple courses, each teacher can teach multiple courses and each course can also be taught by multiple teachers. Write the relational calculus expression to output the ID for all the students who have not been taught by the same teacher in more than one course across all semesters.

Commodity items have some positive or negative changes in their prices each week. Each trading company picks a portfolio of commodity items, that is, they have one or more items and they own some non-zero quantity of each one. The database table for this problem consists of the following two relations:

Commodity(item-number int, price-change float, week int),
Owns(company-name text, item-number int, quantity float).

Write an SQL query which returns the item-numbers of commodities for which, in any given week, the price change is greater than or equal to that of all other items and there exists at least one company selling that item only. (i.e., not selling any other item) in that week.

You are given a logic block $L$ that takes two inputs $A$ and $B$, and produces $A+B$ as output. Realize a two-input $XOR$ gate using only the logic block $L$. You can use as many pieces of block $L$ as you need. You may use the constant function 0; but no other type of gate is allowed.
The CPU of a computer has a ripple-carry implementation of a $2$’s complement adder that takes two $8$ – bit integers $A = a_7a_6 \dots a_0$ and $B = b_7b_6 \dots b_0$ as inputs, and produces a sum $S = s_7s_6 \dots s_0$, where $a_i, b_i, c_i \in \{0, 1\} \text{ for } (0 \leq i \leq 7)$. Let $A = 1001 \: 1001 $ and $B = 1000 \: 0110$. What will be the output $S$ of the adder? How will the value of $S$ be interpreted by the machine?
Professor Hijibiji has defined the following Boolean algebra $\mathcal{B} = (B, +, *)$, where
$B = \{1, 2, 3, 5, 6, 10, 15, 30\}$, i.e., the set of all eight factors of $30$;
the two binary operators $’+’$ and $’*’$ respectively denote the LCM (least common multiple) and GCD (greatest common divisor) of two integer operands.

Define the complementation operation $\bar{a}$ for all $a \in B$ such that $\bar{\bar{a}}= a$.

Professor Hijibiji has defined the following Boolean algebra $\mathcal{B} = (B, +, *)$, where

  • $B = \{1, 2, 3, 5, 6, 10, 15, 30\}$, i.e., the set of all eight factors of $30$;
  • the two binary operators $’+’$ and $’*’$ respectively denote the LCM (least common multiple) and GCD (greatest common divisor) of two integer operands.

Show that the two operations of $\mathcal{B}$ satisfy

  1. associativity
  2. commutativity
  3. distributivity.

Professor Hijibiji has defined the following Boolean algebra $\mathcal{B} = (B, +, *)$, where

  • $B = \{1, 2, 3, 5, 6, 10, 15, 30\}$, i.e., the set of all eight factors of $30$;
  • the two binary operators $’+’$ and $’*’$ respectively denote the LCM (least common multiple) and GCD (greatest common divisor) of two integer operands.

Which are the identity elements for $\mathcal{B}$?

Let $C$ denote a logic block that is capable of comparing two $4$ – bit $2$’s complement numbers $A\:(a_3, a_2, a_1, a_0)$ and $B\: (b_3, b_2, b_1, b_0)$, where $a_i, b_i \in \{0, 1\}$ for $i = 0, 1, 2, 3$. The circuit $C$ has eight input lines $a_3, a_2, a_1, a_0, b_3, b_2, b_1, b_0$, and three output lines $E, L, G$ (Equal: $E$; Less than: $L$; Greater than: $G$). For example, if $A > B$, then the outputs should be $E = 0,\: L = 0$, and $G = 1$. Write the Boolean equations for the three outputs $E, \: L$, and $G$.

The value of the Boolean expression (with usual definitions) $(A’BC’)’ +(AB’C)’$ is

  1. $0$
  2. $1$
  3. $A$
  4. $BC$

Consider a simple code $\mathcal{C}$ for error detection and correction. Each codeword in $\mathcal{C}$ consists of $2$ data bits $[d_1, d_0]$ followed by check bits $[c_2, c_1, c_0]$. The check bits are computed as follows: $c_2 = d_1+d_0, \: c_1=d_1$ and  $c_0=d_0$, where $'+'$ is a modulo-$2$ addition.

  1. Write down all the codewords for $\mathcal{C}$
  2. Determine the minimum Hamming distance between any two distinct codewords of $\mathcal{C}$
Show that $\{1,A \bar{B}\}$ is functionality complete, i.e., any Boolean function with variables $A$ and $B$ can be expressed using these two primitives.
Add the following two floating point numbers $A$ and $B$ given in IEEE $754$ single precision format and show the sum $S$ in the same format.
$A: 0000011000100 \: 0000 \: 000000000000001$
$B: 1000011000100 \: 0000 \: 000000000000001$

For the function given by the Karnaugh map shown below, you can change at most one $1$ or one $0$ entry to a DON'T CARE. Determine what single change of this kind produces the simplest two-level AND-OR realization. Assume both uncomplemented and complemented inputs are available.

Define a Boolean function $F(X_1, X_2, X_3, X_4, X_5, X_6)$ of six variables such that

$\\ \begin{array}{llll} F & = & 1, &  \text{when three or more input variables are at logic 1} \\ { } & = & 0, & \text{otherwise} \end{array} $
How many essential prime implicants does $F$ have? Justify they are essential.

There are five buckets, each of which can be open or closed. An arrangement is a specification of which buckets are open and which bucket are closed. Every person likes some of the arrangements and dislikes the rest. You host a party, and amazingly, no two people on the guest list have the same likes and dislikes. What is the maximum number of guests possible?

  1. $5^{2}$
  2. $\binom{5}{2}$
  3. $2^{5}$
  4. $2^{2^{5}}$

If the letters of the word $\textbf{COMPUTER}$ be arranged in random order, the number of arrangements in which the three vowels $O, U$ and $E$ occur together is

  1. $8!$
  2. $6!$
  3. $3!6!$
  4. None of these

If the letters of the word $\text{COMPUTER}$ be arranged in random order, the number of arrangements in which the three vowels $O, U$ and $E$ occur together is

  1. $8!$
  2. $6!$
  3. $3!6!$
  4. None of these

Consider all possible words obtained by arranging all the letters of the word $\textbf{AGAIN}$. These words are now arranged in the alphabetical order,  as in a dictionary. The fiftieth word in this arrangement is

  1. $\text{IAANG}$
  2. $\text{NAAGI}$
  3. $\text{NAAIG}$
  4. $\text{IAAGN}$

Let $(1+x)^n = C_0+C_1x+C_2x^2+ \dots + C_nx^n$, $n$ being a positive integer. The value of

$$\bigg( 1+\dfrac{C_0}{C_1} \bigg) \bigg( 1+\dfrac{C_1}{C_2} \bigg) \cdots \bigg( 1+\dfrac{C_{n-1}}{C_n} \bigg)$$ is

  1. $\bigg( \frac{n+1}{n+2} \bigg) ^n$
  2. $ \frac{n^n}{n!} $
  3. $\bigg( \frac{n}{n+1} \bigg) ^n$
  4. $ \frac{(n+1)^n}{n!} $

$^nC_0+2^nC_1+3^nC_2+\cdots+(n+1)^nC_n$ equals

  1. $2^n+n2^{n-1}$
  2. $2^n-n2^{n-1}$
  3. $2^n$
  4. none of these

The following sum of $n+1$ terms $$2 + 3 \times \begin{pmatrix} n \\ 1 \end{pmatrix} + 5 \times \begin{pmatrix} n \\ 2 \end{pmatrix} + 9 \times \begin{pmatrix} n \\ 3 \end{pmatrix} + 17 \times \begin{pmatrix} n \\ 4 \end{pmatrix} + \cdots$$ up to $n+1$ terms is equal to

  1. $3^{n+1}+2^{n+1}$
  2. $3^n \times 2^n$
  3. $3^n + 2^n$
  4. $2 \times 3^n$

The value of the term independent of $x$ in the expansion of $(1-x)^2(x+\frac{1}{x})^7$ is

  1. $-70$
  2. $70$
  3. $35$
  4. None of these

Let $(1+x)^n  = C_0+C_1x+C_2x^2+ \cdots +C_nx^n, \: n$ being a positive integer. The value of 

$$\bigg( 1+\frac{C_0}{C_1} \bigg) \bigg( 1+\frac{C_1}{C_2} \bigg) \cdots \bigg( 1+\frac{C_{n-1}}{C_n} \bigg)$$

is

  1. $\bigg( \frac{n+1}{n+2} \bigg) ^n$
  2. $ \frac{n^n}{n!} $
  3. $\bigg( \frac{n}{n+1} \bigg) ^n$
  4. $\frac{(n+1)^n}{n!}$

The value of the term independent of $x$ in the expansion of $(1-x)^{2}(x+\frac{1}{x})^{7}$ is

  1. $-70$
  2. $70$
  3. $35$
  4. None of these

The number of terms independent of $x$ in the binomial expansion of $\bigg(3x^2 + \dfrac{1}{x}\bigg)^{10}$ is 

  1. $0$
  2. $1$
  3. $2$
  4. $5$

The coefficient of $x^6y^3$ in the expression $(x+2y)^9$ is

  1. $84$
  2. $672$
  3. $8$
  4. none of these

The value of  $^{13}C_{3} + ^{13}C_{5} + ^{13}C_{7} +\dots + ^{13}C_{13}$  is

  1. $4096$
  2. $4083$
  3. $2^{13}-1$
  4. $2^{12}-1$

Five letters $A, B, C, D$ and $E$ are arranged so that $A$ and $C$ are always adjacent to each other and $B$ and $E$ are never adjacent to each other. The total number of such arrangements is

  1. $24$
  2. $16$
  3. $12$
  4. $32$

The number of terms with integral coefficients in the expansion of $(17^\frac{1}{3}+19^\frac{1}{2}x)^{600}$ is

  1. $99$
  2. $100$
  3. $101$
  4. $102$

Let $A$ be a set of $n$ elements. The number of ways, we can choose an ordered pair $(B,C)$, where $B,C$ are disjoint subsets of $A$, equals

  1. $n^2$
  2. $n^3$
  3. $2^n$
  4. $3^n$

Let $m$ and $n$ be two integers such that $m \geq n \geq 1.$ Count the number of functions $f : \{1, 2, \ldots , n\} \to \{1, 2, \ldots , m\}$ of the following two types:

  1. strictly increasing; i.e., whenever $x < y, f(x) < f(y),$ and
  2. non-decreasing; i.e., whenever $x < y, f(x) ≤ f(y).$

Let $C_i(i=0,1,2...n)$ be the coefficient of $x^i$ in $(1+x)^n$.Then 

$\frac{C_0}{2} – \frac{C_1}{3}+\frac{C_2}{4}-\dots +(-1)^n \frac{C_n}{n+2}$ is equal to

  1. $\frac{1}{n+1}\\$
  2. $\frac{1}{n+2}\\$
  3. $\frac{1}{n(n+1)}\\$
  4. $\frac{1}{(n+1)(n+2)}$

Let $A=\{10,11,12,13, \dots ,99\}$. How many pairs of numbers $x$ and $y$ are possible so that $x+y\geq 100$ and $x$ and $y$ belong to $A$?

  1. $2405$
  2. $2455$
  3. $1200$
  4. $1230$ 

A integer is said to be a $\textbf{palindrome}$ if it reads the same forward or backward. For example, the integer $14541$ is a $5$-digit palindrome and $12345$ is not a palindrome. How many $8$-digit palindromes are prime?

  1. $0$
  2. $1$
  3. $11$
  4. $19$

How many paths are there in the plane from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N},$ if the possible steps from $(i,j)$ are either $(i+1,j)$ or $(i,j+1)?$

  1. $\binom{2m}{n}$
  2. $\binom{m}{n}$
  3. $\binom{m+n}{n}$
  4. $m^{n}$

We need to choose a team of $11$ from a pool of $15$ players and also select a captain. The number of different ways this can be done is

  1. $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$
  2. $11$ . $ \begin{pmatrix} 15 \\ 11 \end{pmatrix}$
  3. $15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5$
  4. $(15 . 14 . 13 . 12 . 11 .10 . 9 . 8 . 7 . 6 . 5) . 11$

Sales have slumped at the Siruseri noodle factory and the management may need to terminate the contracts of some employees. Every employee has one immediate boss. The seniormost person in the company is the president, who has no boss. For legal reasons, if an employee’s contract is not terminated, then his boss’s contract cannot be terminated either. For how many different sets of employees can the management legally terminate contracts? Note that one possibility that has to be counted explicitly is that no employees’ contracts are terminated (that is, the set of employees whose contract is terminated is the empty set).

For example, suppose there are four employees, organised as follows. Each arrow points from an employee to his or her boss.

Here, there are $7$ different ways to terminate contracts for a set of employees, as follows:

$[ \{1,2,3,4 \}, \{ \}, \{ 4 \}, \{ 2 \}, \{ 3, 4 \}, \{ 2, 4 \}, \{ 2, 3, 4 \}]$

For the inter-hostel six-a-side football tournament, a team of $6$ players is to be chosen from $11$ players consisting of $5$ forwards, $4$ defenders and $2$ goalkeepers. The team must include at least $2$ forwards, at least $2$ defenders and at least $1$ goalkeeper. Find the number of different ways in which the team can be chosen.

  1. $260$
  2. $340$
  3. $720$
  4. $440$

The school athletics coach has to choose $4$ students for the relay team. He calculates that there are $3876$ ways of choosing the team if the order in which the runners are placed is not considered. How many ways are there of choosing the team if the order of the runners is to be taken into account?

  1. Between $12,000$ and $25,000$
  2. Between $75,000$ and $99,999$
  3. Between $30,000$ and $60,000$
  4. More than $100,000$
Consider a social network with $n$ persons. Two persons $A$ and $B$ are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons $F_1, \dots, F_m$ such that $A$ and $F_1$ are friends, $F_1$ and $F_2$ are friends, $\dots, F_{m−1}$ and $F_m$ are friends, and finally $F_m$ and $B$ are friends.
It is known that there are $k$ persons such that no pair among them is connected. What is the maximum number of friendships possible?
In a party there are $2n$ participants, where $n$ is a positive integer. Some participants shake hands with other participants. It is known that there are no three participants who have shaken hands with each other. Prove that the total number of handshakes is not more than $n^2.$

A club with $x$ members is organized into four committees such that 

  1. each member is in exactly two committees,
  2. any two committees have exactly one member in common .

Then $x$ has 

  1. exactly two values both between $4$ and $8$.
  2. exactly one value and this lies between $4$ and $8$.
  3. exactly two values both between $8$ and $16$.
  4. exactly one value and this lies between $8$ and $16$.

A subset $S$ of set of numbers $\{2,3,4,5,6,7,8,9,10\}$ is said to be good if has exactly $4$ elements and their $gcd=1$, Then number of good subset is

  1. $126$
  2. $125$
  3. $123$
  4. $121$

The number of permutation of $\{1,2,3,4,5\}$ that keep at least one integer fixed is.

  1. $81$
  2. $76$
  3. $120$
  4. $60$

In how many ways can three person, each throwing a single die once, make a score of $11$

  1. $22$
  2. $27$
  3. $24$
  4. $38$
Consider $2n$ committees, each having at least $2n$ persons, formed from a group of $4n$ persons. Prove that there exists at least one person who belongs to at least $n$ committees.

Consider $30$ multiple-choice questions, each with four options of which exactly one is correct. Then the number of ways one can get only the alternate questions correctly answered is

  1. $3^{15}$
  2. $2^{31}$
  3. $2 \times \begin{pmatrix} 30 \\ 15 \end{pmatrix}$
  4. $2 \times 3^{15}$

The number of permutations of the letters $a, b, c$ and $d$ such that $b$ does not follow $a,c$ does not follow $b$, and $c$ does not follow $d$, is

  1. $11$
  2. $12$
  3. $13$
  4. $14$

If $^nC_{r-1}=36$, $^nC_r=84$ an $^nC_{r+1}=126$ then $r$ is equal to

  1. $1$
  2. $2$
  3. $3$
  4. none of these

Suppose in a competition $11$ matches are to be played, each having one of $3$ distinct outcomes as possibilities. The number of ways one can predict the outcomes of all $11$ matches such that exactly $6$ of the predictions turn out to be correct is

  1. $\begin{pmatrix}11 \\ 6 \end{pmatrix} \times 2^5$
  2. $\begin{pmatrix}11 \\ 6 \end{pmatrix} $
  3. $3^6$
  4. none of the above

A club with $x$ members is organized into four committees such that

  1. each member is in exactly two committees, 
  2. any two committees have exactly one member in common.

Then $x$ has

  1. exactly two values both between $4$ and $8$
  2. exactly one value and this lies between $4$ and $8$
  3. exactly two values both between $8$ and $16$
  4. exactly one value and this lies between $8$ and $16$

Let $\sigma$ be the permutation:

$$\begin{array} {}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 5 & 6 & 2 & 4 & 9 & 8 & 7 & 1, \end{array}$$ $I$ be the identity permutation and $m$ be the order of $\sigma$ i.e. $m=\text{min}\{\text{positive integers }n: \sigma ^n=I \}$. Then $m$ is

  1. $8$
  2. $12$
  3. $360$
  4. $2520$
Consider all possible permutations of eight distinct elements $a, b, c, d, e, f, g, h$. In how many of them, will $d$ appear before $b$? Note that $d$ and $b$ may not necessarily be consecutive.
A palindrome is a sequence of digits which reads the same backward or forward. For example, $7447$, $1001$ are palindromes, but $7455$, $1201$ are not palindromes. How many $8$ digit prime palindromes are there?

A club with $n$ members is organized into four committees so that each member belongs to exactly two committees and each pair of committees has exactly one member in common. Then

  1. $n=4$
  2. $n=6$
  3. $n=8$
  4. $n$ cannot be determined from the given information
  1. Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than 1 in a given tree. What is the maximum possible value of $k$? Justify your answer.
  2. Consider $2n$ committees, each having at least $2n$ persons, formed from a group of $4n$ persons. Prove that there exists at least one person who belongs to at least $n$ committees.

The five vowels—$A, E, I, O, U$—along with $15$ $X’s$ are to be arranged in a row such that no $X$ is at an extreme position. Also, between any two vowels, there must be at least $3$ $X’s$. The number of ways in which this can be done is

  1. $1200$
  2. $1800$
  3. $2400$
  4. $3000$

Let $n$ be the number of ways in which $5$ men and $7$ women can stand in a queue such that all the women stand consecutively. Let $m$ be the number of ways in which the same $12$ persons can stand in a queue such that exactly $6$ women stand consecutively. Then the value of $\frac{m}{n}$ is

  1. $5$
  2. $7$
  3. $\frac{5}{7}$
  4. $\frac{7}{5}$

In a class of $80$ students, $40$ are girls and $40$ are boys. Also, exactly $50$ students wear glasses. Then the set of all possible numbers of boys without glasses is

  1. $\{0, \dots , 30\}$
  2. $\{10, \dots , 30\}$
  3. $\{0, \dots , 40\}$
  4. none of these

In a room there are $8$ men, numbered $1,2,  \dots ,8$. These men have to be divided into $4$ teams in such a way that

  1. every team has exactly $2$ members, and
  2. there are no common members between any two teams. For example, $\{(1,2),(3,4),(5,6),(7,8)\} \{(1,5),(2,7),(3,8),(4,6)\}$ are two such $4$-team combinations. The total number of such $4$-team combinations is
  1. $\frac{8!}{2^4}$
  2. $\frac{8!}{2^4(4!)}$
  3. $\frac{8!}{4!}$
  4. $\frac{8!}{(4!)^2}$

A Pizza Shop offers $6$ different toppings, and they do not take an order without any topping. I can afford to have one pizza with a maximum of $3$ toppings. In how many ways can I order my pizza?

  1. $20$
  2. $35$
  3. $41$
  4. $21$

A new flag of ISI club is to be designed with $5$ vertical strips using some or all of the four colors: green, maroon, red and yellow. In how many ways this can be done so that no two adjacent strips have the same color?

  1. $120$
  2. $324$
  3. $424$
  4. $576$

Suppose that the number plate of a vehicle contains two vowels followed by four digits. However, to avoid confusion, the letter $‘O’$ and the digit $‘0’$ are not used in the same number plate. How many such number plates can be formed?

  1. $164025$
  2. $190951$
  3. $194976$
  4. $219049$

A general election is to be scheduled on $5$ days in May such that it is not scheduled on two consecutive days. In how many ways can the $5$ days be chosen to hold the election?

  1. $\begin{pmatrix} 26 \\ 5 \end{pmatrix}$
  2. $\begin{pmatrix} 27 \\ 5 \end{pmatrix}$
  3. $\begin{pmatrix} 30 \\ 5 \end{pmatrix}$
  4. $\begin{pmatrix} 31 \\ 5 \end{pmatrix}$

Suppose that $6$-digit numbers are formed using each of the digits $1, 2, 3, 7, 8, 9$ exactly once. The number of such $6$-digit numbers that are divisible by $6$ but not divisible by $9$ is equal to

  1. $120$
  2. $180$
  3. $240$
  4. $360$
There is a party of $n$ people. Each attendee has at most $r$ friends in the party. The friend circle of a person includes the person and all her friends. You are required to pick some people for a party game, with the restriction that at most one person is picked from each friend circle. Show that you can pick $\dfrac{n}{r^{2}+1}$ people for the game.
an is a n-digit number of 0's and 1's with no consecutive 0's i.e., without the occurrence of '00'. For example, a8 =10111011. Construct a recurrence relation for an(a0=1).

Let $\{f_n(x)\}$ be a sequence of polynomials defined inductively as

$$ f_1(x)=(x-2)^2$$

$$f_{n+1}(x) = (f_n(x)-2)^2, \: \: \: n \geq 1$$

Let $a_n$ and $b_n$ respectively denote the constant term and the coefficient of $x$ in $f_n(x)$. Then

  1. $a_n=4, \: b_n=-4^n$
  2. $a_n=4, \: b_n=-4n^2$
  3. $a_n=4^{(n-1)!}, \: b_n=-4^n$
  4. $a_n=4^{(n-1)!}, \: b_n=-4n^2$
A bit string is called legitimate if it contains no consecutive zeros $, e.g., 0101110$ is legitimate, where as $10100111$ is not. Let $a_n$ denote the number of legitimate bit strings of length $n$. Define $a_0=1$. Derive a recurrence relation for $a_n ( i.e.,$  express $a_n$ in terms of the preceding $a_i's).$

The sum $\sum_{k=1}^n (-1)^k \:\: {}^nC_k \sum_{j=0}^k (-1)^j  \: \: {}^kC_j$ is equal to 

  1. $-1$
  2. $0$
  3. $1$
  4. $2^n$

A simple graph is one with no self-loops or multiple edges. Among the simple graphs with $n$ vertices and at most $20n − 3$ edges:

  1. There is always a graph with all vertices connected to at least $42$ other vertices.
  2. For all such graphs the number of vertices connected to at least $42$ other vertices is at most cn for some constant $c < 1$.
  3. There are no graphs with each vertex connected to at most $38$ other vertices.
  4. None of the above

Let $T = (V, E)$ be a tree, and let $v \in V$ be any vertex of $T$.

  • The $\text{eccentricity}$ of $v$ is the maximum distance from $v$ to any other vertex in $T$.
  • The $\text{centre  } C$  of $T$ is the set of vertices which have minimum eccentricity among all vertices in $T$.
  • The $\text{weight of  }v$ is the number of vertices in the largest subtree of $v$.
  • The $\text{centroid }$ $C$ of $T$ is the set of vertices with minimum weight among all vertices in $T$.

Construct a tree $T$ that has disjoint centre and centroid, each having two vertices (i.e. $C \cap \mathcal{C} = \not{O}$ and $|C| = |\mathcal{C}| = 2)$.

Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given  to you by a $0-1$ matrix $A$ of size $n\times n$  as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ if and only if $(i,j)$ is an edge in $G.$
A connected component in $G$ is a subgraph in which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
A complete graph on $n$ vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let $G$ be a complete graph on $10$ vertices. Let $u$, $v$, $ w$ be three distinct vertices in $G$. How many simple paths are there from $u$ to $v$ going through $w$?

A simple graph is one in which there are no self-loops and each pair of distinct vertices is connected by at most one edge. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex of degree $4$, a vertex of degree $5$, a vertex of degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex?

  1. $3$
  2. $0$
  3. $5$
  4. $4$

An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What is the degree of vertex $10$ ?

  1. $5$
  2. $6$ 
  3. $7$ 
  4. $8$

Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements:

  1. There is a vertex of degree smaller than $8$ in $G$.
  2. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it.

Which of the following is true:

  1. I Only
  2. II Only
  3. Both I and II
  4. Neither I nor II
     

An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a connected, undirected graph that contains no cycle.

  1. A $\text{leaf}$ in a tree is a vertex that has degree $1$. Prove that if $G$ is a tree with at least two vertices then $G$ contains at least two leaves.
  2. A $\text{bipartite graph}$ is one in which the vertex set $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ so that for every edge $\{u, v\}$, $u$ and $v$ lie in different partitions—that is, $u \in V_1$ and v$ \in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.

A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that:

  • Each road connects exactly two buildings.
  • Any two buildings are connected via a sequence of roads.
  • Omitting any road leads to at least two buildings not being connected by any sequence of roads.

Is it always possible to colour each building with either red or blue so that every road connects a red and blue building?

Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not an endpoint of any green coloured edge. If a graph $G$ does not satisfy this property, which of the following statements about $G$ are valid?

  1. There is a red coloured edge.
  2. Any vertex that is the endpoint of a red coloured edge is also the endpoint of a green coloured edge.
  3. There is a vertex that is not an endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge.
  4. (A) and (C).

A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable.
The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:

Find a minimal colouring.

An international cellphone company provides service on $7$ different frequencies. They wish to set up business in TamilNadu and have fixed the locations of $100$ towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least $100$ km apart, so that there is no interference of signals.

Model this problems using graphs.
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots , v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.

Let $G=(V, E)$ be a graph. Define $\bar{G}$ to be $(V, \bar{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \bar{E}$ if and only if $(u, v) \notin E$. Then which of the following is true?

  1. $\bar{G}$ is always connected.
  2. $\bar{G}$ is connected if $G$ is not connected.
  3. At least one of $G$ and $\bar{G}$ connected.
  4. $G$ is not connected or $\bar{G}$ is not connected

A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that:

  • Each road connects exactly two buildings.
  • Any two buildings are connected via a sequence of roads.
  • Omitting any road leads to at least two buildings not being connected by any sequence of roads.

Two roads are said to be $\text{adjacent}$ to each other if they serve a common building. A set of roads is said to be $\text{preferred}$ if:

  • No two roads in the set are adjacent, and,
  • Each building is served by at least one road in the set.
  1. Is it always possible to find a preferred set of roads?
  2. Is it ever possible to find two sets of preferred roads differing in at least one road?

Substantiate your answers by either proving the assertion or providing a counterexample.

Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected.

Given a good graph, devise a linear time algorithm to find two such vertices.
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected.

Show that there exists a graph $H$ such that we cannot find three distinct vertices $u_1, u_2, u_3$ such that each of $G − u_1,\: G − u_2,$ and  $G − u_3$ is connected.
Let $G=(V, E)$ be a graph where $\mid V \mid  =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Consider a path of maximum length in $G$.)
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.

An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:

Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.

City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at intersections with traffic lights so that any segment of road can be reached by at least one ambulance that does not have to pass through a traffic light to reach the scene of the accident. If we model the road network as a graph, where intersections with traffic lights are vertices and edges represent road segments between traffic lights, the graph-theoretic question to be answered is:

  1. Find a spanning tree with minimum number of edges.
  2. Find a spanning tree with minimum cost.
  3. Find a minimal coloring.
  4. Find a minimum size vertex cover.

For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n$-bit binary strings and $E = \{(u,v) \mid u, v$ belongs to $V, u$ and $v$ differ in exactly one bit position$\}$.

  1. Determine size of $E$
  2. Show that $G$ is connected

A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable.

The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:

Find a maximum size independent set.

Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each individual has the skills to take part in a subset of the events. However, the same individual cannot be part of the team for two different events because of a possible clash in timings. Your aim is to create teams to take part in as many events as possible.

To do this, you decide to model the problem as a graph where the nodes are the events and edges represent pairs of events where the team that you plan to send shares a member. In this setting, the graph theoretic question to be answered is:

  1. Find a maximum length simple cycle
  2. Find a maximum size independent set
  3. Find a maximum matching
  4. Find a maximal connected component

ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected-there is a path from each city to every other city. The contract requires the network to remain connected if $any$ single link fails. What is the minimum number of links that ScamTel needs to set up?

  1. $34$
  2. $32$
  3. $17$
  4. $16$

A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices?

  1. $60$ edges and $20$ vertices
  2. $30$ edges and $20$ vertices
  3. $60$ edges and $50$ vertices
  4. $30$ edges and $50$ vertices

Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$  For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$

  1. $2$
  2. $-1$
  3. $0$
  4. $1$

Let $G$ be a simple graph on $n$ vertices.

  1. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.
  2. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle).
Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple path of length at least $k$.
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle).
Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple cycle of length at least $k+1$.
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable.
The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:

Find a spanning tree with minimum number of edges.

A fan of order $n$ is a graph on the vertices $\{0, 1, \dots, n\}$ with $2n − 1$ edges defined as follows: vertex $0$ is connected by an edge to each of the other $n$ vertices, and vertex $i$ is connected by an edge to vertex $i + 1$, for $1 \leq i \leq n − 1$.

Let $f_n$ denote the number of spanning trees of the fan of order $n$.

  1. Calculate $f_4$.
  2. Write a recurrence for $f_n$.
  3. Solve for fn using ordinary generating functions.

Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following is true?

  1. $s=99$
  2. $s=198$
  3. $99 \: < \: s \: < \: 198$
  4. None of the above
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following property: there exists a vertex that is a neighbour of all other vertices. Consider the following statements:

  1. If $P$ is false, then there is a pair of vertices such that the distance between them is at least $4.$
  2. If $P$ is true, then the distance between any pair of vertices is at most $2.$

What can you say about these statements?

  1. Only i is true
  2. Only ii is true
  3. Both i and ii are true
  4. Neither i nor ii is true
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a  vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).

A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable.

The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:

  1. Find a spanning tree with minimum number of edges.
  2. Find a minimal colouring.
  3. Find a minimum size vertex cover.
  4. Find a maximum size independent set
A vertex cover of a graph $G = (V, E)$ is a set of vertices $V' \subseteq V$ such that for any edge $(u, v) \in E$, either $u$ or $v$\ (or both) is in $V'$. Write a linear time algorithm to find the minimum vertex cover of a given tree $T$. Establish its correctness.

Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has weight $53$ and the shortest path from $s$ to $v$ has weight $65.$ Which of the statements is always true?

  1. Weight of $(u, v) \leq 12$
  2. Weight of $(u, v) = 12$
  3. Weight of $(u, v) \geq 12$
  4. Nothing can be said about the weight of $(u, v)$

Four siblings go shopping with their father. If Abhay gets shoes, then Asha does not get a necklace. If Arun gets a T-shirt, then Aditi gets bangles. If Abhay does not get shoes or Aditi gets bangles, the mother will be happy. Which of the following is TRUE?

  1. If the mother is happy, then Aditi got bangles.
  2. If Aditi got bangles, then Abhay got shoes.
  3. If the mother is not happy, then Asha did not get a necklace and Arun did not get a T-shirt.
  4. None of the above.

Let X be an nonempty set and let P(X) denote the collection of all subset of X. Define $\textit{f}:\textit{X*P(X)}\rightarrow \mathbb{R}$ by

$f(x,A) = \begin{cases}  1 \text{ if } x  \epsilon A & \\ 0 \text{ if } x \not\epsilon  A & \end{cases}$

Then $f\left ( x,A\cup B \right )$ equals

  1. $f(x,A)+f(x,B)$
  2. $f(x,A)+f(x,B)-1$
  3. $f(x,A)+f(x,B) - f(x,A) \cdot f(x,B)$
  4. $f(x,A)+ \mid f(x,A) – f(x,B) \mid$

Let $m$ and $n$ range over natural numbers and let $\text{Prime}(n)$ be true if $n$ is a prime number. Which of the following formulas expresses the fact that the set of prime numbers is infinite?

  1. $(\forall m) (\exists n) (n > m) \text{ implies Prime}(n)$
  2. $(\exists n) (\forall m) (n > m) \text{ implies Prime}(n)$
  3. $(\forall m) (\exists n) (n > m) \wedge \text{Prime}(n)$
  4. $(\exists n) (\forall m) (n > m) \wedge \text{Prime}(n)$

Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes—for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that there are infinitely many twin primes.
Let $\text{TwinPrime}(n)$ be a predicate that is true if $n$ and $n+2$ are twin primes. Which of the following formulas, interpreted over positive integers, expresses that there are only finitely many twin primes?

  1. $\forall m \cdot \exists n \cdot m \leq n \text{ and not(TwinPrime}(n))$
  2. $\exists m \cdot \forall n \cdot n \leq m \text{ implies TwinPrime}(n)$
  3. $\forall m \cdot \exists n \cdot n \leq m \text{ and TwinPrime}(n)$
  4. $\exists m \cdot \forall n \cdot  \text{TwinPrime}(n) \text{ implies }n \leq m$

In the land of Twitter, there are two kinds of people: knights (also called outragers), who always tell the truth, and knaves (also called trolls), who always lie. It so happened that a person with handle @anand tweeted something offensive. It was not known whether @anand was knight or a knave. A crack team, headed by Inspector Chitra, rounded up three suspects and interrogated them.

The first interrogation went as follows.

  • Chitra : What do you know about @anand?
  • Suspect $ 1$ : @anand once claimed that I was a knave.
  • Chitra : Are you by any chance @anand?
  • Suspect $1$ :  Yes.

Let 

$$f(x,y) =  \begin{cases}  \dfrac{x^2y}{x^4+y^2}, &  \text{      if } (x,y) \neq (0,0) \\ 0 & \text{    if } (x,y) = (0,0)\end{cases}$$

Then $\displaystyle{\lim_{(x,y)\rightarrow(0,0)}}f (x,y)$

  1. equals $0$
  2. equals $1$
  3. equals $2$
  4. does not exist

Consider the following two statements.

  1. There are infinitely many interesting whole numbers.
  2. There are finitely many uninteresting whole numbers.

Which of the following is true?

  1. Statements $1$ and $2$ are equivalent.
  2. Statement $1$ implies statement $2$.
  3. Statement $2$ implies statement $1$.
  4. None of the above.

Let $X_1,X_2,X_3,X_4$ be i.i.d. random variables each assuming the value $1$ and $-1$ with probability $\dfrac{1}{2}$ each. Then, the probability that the matrix $\begin{pmatrix}X_1 &X_2\\ X_3 &X_4\end{pmatrix}$ is nonsingular equals

  1. $1/2$
  2. $3/8$
  3. $5/8$
  4. $1/4$

Let $\mathbb{N}=\{1,2,3, \dots\}$ be the set of natural numbers. For each $n \in \mathbb{N}$, define $A_n=\{(n+1)k, \: k \in \mathbb{N} \}$. Then $A_1 \cap A_2$ equals

  1. $A_3$
  2. $A_4$
  3. $A_5$
  4. $A_6$

Let $X$ be the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$. Define the set $\mathcal{R}$ by $\mathcal{R} = \{(x,y) \in X \times X : x$ and $y$ have the same remainder when divided by $3\}$.

Then the number of elements in $\mathcal{R}$ is

  1. $40$
  2. $36$
  3. $34$
  4. $33$
Let $A$ and $B$ are two non-empty finite subsets of $\mathbb{Z}$, the set of all integers. Define  $A+B=\{a+b:a\in A,b\in B\}$.Prove that $\mid A+B \mid \geq \mid A \mid + \mid B \mid -1 $, where $\mid S \mid$ denotes the cardinality of finite set $S$.

Let $A$ and $B$ be disjoint sets containing $m$ and $n$ elements respectively, and let $C=A \cup B$. Then the number of subsets $S$ (of $C$) which contains $p$ elements and also has the property that $S \cap A$ contains $q$ elements, is

  1. $\begin{pmatrix} m \\ q \end{pmatrix}$
  2. $\begin{pmatrix} n \\ q \end{pmatrix}$
  3. $\begin{pmatrix} m \\ q \end{pmatrix} \times \begin{pmatrix} n \\ p-q \end{pmatrix}$
  4. $\begin{pmatrix} m \\ p-q \end{pmatrix} \times \begin{pmatrix} n \\ q \end{pmatrix}$

$x^{2}+x+1$ is a factor of $\left ( x+1 \right )^{n}-x^{n}-1$ whenever

  1.  $n$ is odd
  2. $n$ is odd and multiple of $3$
  3. $n$ is an even multiple of $3$
  4. $n$ is odd and not a multiple of $3$

A $\text{3-ary}$  boolean function is a function that takes three boolean arguments and produces a boolean output. Let $f$ and $g$ be  $\text{3-ary}$ boolean functions. We say that $f$ and $g$ are neighbours if $f$ and $g$ agree on at least one input and disagree on at least one input: that is, there exist $x,\: y,\: z$ such that $f(x, y, z) = g(x, y, z)$ and $x',y',z'$ such that $f(x',y',z') \neq g(x',y',z')$.
Suppose we fix a $\text{3-ary}$ boolean function $h$. How many neighbours does $h$ have?

  1. $128$
  2. $132$
  3. $254$
  4. $256$

An $n-$variable Boolean function $f:\{0,1\}^n \rightarrow \{0,1\} $ is called symmetric if its value depends only on the number of $1’s$ in the input. Let $\sigma_n $ denote the number of such functions.

  1. Calculate the value of $\sigma_4$.
  2. Derive an expression for $\sigma_n$ in terms of $n$.
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected.

Show that for any subgraph $H$ of $G$, $H$ is good if and only if $G$ is good.

Let $G$ be a group with identity element $e$. If $x$ and $y$ are elements in $G$ satisfying $x^5y^3=x^8y^5=e$, then which of the following conditions is true?

  1. $x=e, \: y=e$
  2. $x\neq e, \: y=e$
  3. $x=e, \: y \neq e$
  4. $x\neq e, \: y \neq e$

Let $H$ be a subgroup of group $G$ and let $N$ be a normal subgroup of $G$. Choose the correct statement :

  1. $H\cap N$ is a normal subgroup of both $H$ and $N$
  2. $H\cap N$ is a normal subgroup of $H$ but not necessarily of $N$
  3. $H\cap N$ is a normal subgroup of $N$ but not necessarily of $H$
  4. $H\cap N$ need not to be a normal subgroup of either  $H$ or $N$

Let $G$ be a finite group of even order. Then which of the following statements is correct?

  1. The number of elements of order $2$ in $G$ is even
  2. The number of elements of order $2$ in $G$ is odd
  3. $G$ has no subgroup of order $2$
  4.  None of the above.

Let $G =\{a_1,a_2, \dots ,a_{12}\}$ be an Abelian group of order $12$ . Then the order of the element $ ( \prod_{i=1}^{12} a_i)$ is

  1. $1$
  2. $2$
  3. $6$
  4. $12$

The inequality $\frac{2-gx+x^{2}}{1-x+x^{2}}\leq 3$ is true for all the value of $x$ if and only if

  1. $1\leq g\leq 7$
  2. $-1\leq g\leq 1$
  3. $-6\leq g\leq 7$
  4. $-1\leq g\leq 7$

If $\alpha 1,\alpha 2,\dots,\alpha n$ are the positive numbers then

$\frac{a1}{a2}+\frac{a2}{a3}+\dots+\frac{an-1}{an}+\frac{an}{a1}$ is always

  1. $\geq n$
  2. $\leq n$
  3. $\leq n^{\frac{1}{2}}$
  4. None of the above
Find the number of positive integers n for which $n^{2}+96$ is a perfect square.
Consider an $m \times n$ integer lattice. A path from $(0, 0)$ to $(m, n)$ can use steps of $(1, 0)$, $(0, 1)$ or diagonal steps $(1, 1)$. Let $D_{m,n}$ be the number of such distinct paths. Prove that $D_{m,n} = \Sigma_k \begin{pmatrix} m \\ k \end{pmatrix} \begin{pmatrix} n+k \\ m \end{pmatrix}$
The numbers $1, 2, \dots , 10$ are arranged in a circle in some order. Show that it is always possible to find three adjacent numbers whose sum is at least $17$, irrespective of the ordering.

$Q10$  The equation $p\left ( x \right ) = \alpha$ where $p\left ( x \right ) = x^{4}+4x^{3}-2x^{2}-12x$ has four distinct real root if and only if

  1. $p\left ( -3 \right )<\alpha$
  2. $p\left ( -1 \right )>\alpha$
  3. $p\left ( -1 \right )<\alpha$
  4. $p\left ( -3 \right )<\alpha <p\left ( -1 \right )$

If the equation $x^{4}+ax^{3}+bx^{2}+cx+1=0$ (where $a,b,c$ are real number) has no real roots and if at least one of the root is of modulus one, then

  1. $b=c$
  2. $a=c$
  3. $a=b$
  4. none of this

$Q8$ If $\alpha_{1},\alpha_{2},\alpha_{3}, \dots , \alpha_{n}$ be the roots of $x^{n}+1=0$, then $\left ( 1-\alpha_{1} \right )\left ( 1-\alpha_{2} \right ) \dots \left ( 1-\alpha_{n} \right )$ is equal to

  1. $1$
  2. $0$
  3. $n$
  4. $2$

The equation

    $\frac{1}{3}+\frac{1}{2}s^{2}+\frac{1}{6}s^{3}=s$

has

  1. exactly three solution in $[0.1]$
  2. exactly one solution in $[0,1]$
  3. exactly two solution in $[0,1]$
  4. no solution in $[0,1]$

The equation $x^{6}-5x^{4}+16x^{2}-72x+9=0$ has

  1. exactly two distinct real roots
  2. exactly three distinct real roots
  3. exactly four distinct real roots
  4. six different real roots

Let $A$ be the set of all prime numbers, $B$ be the set of all even prime numbers, and $C$ be the set of all odd prime numbers. Consider the following three statements in this regard:

  1. $A=B\cup C$.
  2. $B$ is a singleton set
  3. $A = C \cup \{2\}$

Then which one of the following holds?

  1. None of the above statements is true.
  2. Exactly one of the above statements is true.
  3. Exactly two of the above statements are true.
  4. All the above three statements are true.

Let $G$ be the group $\{\pm1, \pm i \}$ with multiplication of complex numbers as composition. Let $H$ be the quotient group $\mathbb{Z}/4 \mathbb{Z}$. Then the number of nontrivial group homomorphisms from $H$ to $G$ is

  1. $4$
  2. $1$
  3. $2$
  4. $3$

A binary relation $R ⊆ (S ×S)$ is said to be Euclidean if for every $a, b, c ∈ S, (a, b) ∈ R$ and $(a, c) ∈ R$ implies $(b, c) ∈ R$. Which of the following statements is valid?

  1. If $R$ is Euclidean, $(b, a) ∈ R$ and $(c, a) ∈ R$, then $(b, c) ∈ R$, for every $a, b, c ∈ S$
  2. If $R$ is reflexive and Euclidean, $(a, b) ∈ R$ implies $(b, a) ∈ R$, for every $a, b ∈ S$
  3. If $R$ is Euclidean, $(a, b) ∈ R$ and $(b, c) ∈ R$, then $(a, c) ∈ R$, for every $a, b, c ∈ S$
  4. None of the above.

Let $A$, $B$ and $C$ be three non empty sets. Consider the two relations given below:

$$\begin{array}{lll} A-(B-C)=(A-B) \cup C & & (1) \\ A – (B \cup C) = (A -B)-C & & (2) \end{array}$$

  1. Both $(1)$ and $(2)$ are correct
  2. $(1)$ is correct but $(2)$ is not
  3. $(2)$ is correct but $(1)$ is not
  4. Both $(1)$ and $(2)$ are incorrect

Suppose $X$ and $Y$ are finite sets, each with cardinality $n$. The number of bijective functions from $X$ to $Y$ is

  1. $n^n$
  2. $n \log_2 n$
  3. $n^2$
  4. $n!$ 

Suppose $f_{\alpha} : [0,1] \to [0,1],\:\: -1 < \alpha < \infty$ is given by

$$f_{\alpha} (x) = \frac{(\alpha +1)x}{\alpha x+1}$$

Then $f_{\alpha}$ is

  1. A bijective (one-one and onto) function
  2. A surjective (onto ) function
  3. An injective (one-one) function
  4. We cannot conclude about the type

Let $X$ be a nonempty set and let $\mathcal{P}(X)$ denote the collection of all subsets of $X$. Define $f: X \times \mathcal{P}(X) \to \mathbb{R}$ by

$$f(x,A)=\begin{cases} 1 & \text{ if } x \in A \\ 0 & \text{ if } x \notin A \end{cases}$$ Then $f(x, A \cup B)$ equals

  1. $f(x,A)+f(x,B)$
  2. $f(x,A)+f(x,B)\: – 1$
  3. $f(x,A)+f(x,B)\: – f(x,A) \cdot f(x,B)$
  4. $f(x,A)\:+ \mid f(x,A)\: – f(x,B) \mid $

Consider the sets defined by the real solutions of the inequalities

$$A = \{(x,y):x^2+y^4 \leq 1 \} \:\:\:\:\:\:\:\: B = \{ (x,y):x^4+y^6 \leq 1\}$$

Then

  1. $B \subseteq A$
  2. $A \subseteq B$
  3. Each of the sets $A – B, \: B – A$ and $A \cap B$ is non-empty
  4. none of the above

If $A$ be the set of triangles in a plane and $R^{+}$ be the set of all positive real numbers,  then the function $f\::\:A\rightarrow R^{+},$ defined by $f(x)=$ area of triangle  $x,$ is

  1. one-one and into
  2. one-one and onto
  3. many-one and onto
  4. many-one and into

Let $A,B$ and $C$ be three non empty sets. Consider the two relations given below:

  • $A-(B-C)=(A-B)\cup C$
  • $A-(B\cup C)=(A-B)-C$
  1. Both (1) and (2) are correct.
  2. (1) is correct but (2) is not.
  3. (2) is correct but (1) is not.
  4. Both (1) and (2) are incorrect.

Suppose $X$ and $Y$ are finite sets, each with cardinality $n$.. The number of bijective functions from $X$ to $Y$ is

  1. $n^{n}$
  2. $n\log_{2}n$
  3. $n^{2}$
  4. $n!$

Suppose $f_{\alpha}\::\:[0,1]\rightarrow[0,1],\:-1<\alpha<\infty$ is given by

$$f_{\alpha}(x)=\dfrac{(\alpha+1)x}{\alpha x+1}.$$

Then $f_{\alpha}$ is

  1. A bijective (one-one and onto) function.
  2. A surjective (onto) function.
  3. An injective (one-one) function.
  4. We can not conclude about the type.

Two sets have $m$ and $n$ elements. The number of subsets of the first set is $96$ more than that of the second set. Then the values of $m$ and $n$ are

  1. $8$ and $6$
  2. $7$ and $6$
  3. $7$ and $5$
  4. $6$ and $5$

You are given three sets $A,B,C$ in such a way that 

  1. the set $B \cap C$ consists of $8$ elements,
  2. the set $A\cap B$ consists of $7$ elements, and
  3. the set $C\cap A$ consists of $7$ elements.

The minimum number of elements in the set $A\cup B\cup C$ is

  1. $8$
  2. $14$
  3. $15$
  4. $22$
Let $S = \{x \in R : 1 \leq |x| \leq 100\}$. Find all subsets $M$ of $S$ such that for all $x, y$ in $M$, their product $xy$ is also in $M$.

Consider the group $$G=\begin{Bmatrix} \begin{pmatrix} a & b \\ 0 & a^{-1} \end{pmatrix} : a,b \in \mathbb{R}, \: a>0 \end{Bmatrix}$$ with usual matrix multiplication. Let $$ N = \bigg\{ \begin{pmatrix}1 & b \\ 0 & 1 \end{pmatrix} : b \in \mathbb{R} \bigg\}.$$ Then, 

  1. $N$ is not a subgroup of $G$
  2. $N$ is a subgroup of $G$ but not normal subgroup
  3. $N$ is a normal subgroup and the quotient group $G/N$ is of finite order
  4. $N$ is a normal subgroup and the quotient group is isomorphic to $\mathbb{R}^+$ (the group of positive reals with multiplication).

A set contains $2n+1$ elements. The number of subsets of the set which contain at most $n$ elements is

  1. $2^n$
  2. $2^{n+1}$
  3. $2^{n-1}$
  4. $2^{2n}$

Which one of the following statements is correct regarding the elements and subsets of the set $\{1, 2, \{1, 2, 3\}\}$?

  1. $\{1, 2\} \in \{1, 2, \{1, 2, 3\} \}$
  2. $\{1, 2\} \subseteq \{1, 2, \{1, 2, 3\} \}$
  3. $\{1, 2, 3\} \subseteq \{1, 2, \{1, 2, 3\} \}$
  4. $3 \in \{1, 2, \{1, 2, 3\} \}$
Let $B=\{1, 2, 3, 4\}$. A set $S \subseteq B \times B$ called a symmetric set of $B$ if for all $x, y \in B$, $$ (x, y) \in S \Rightarrow (y,x) \in S.$$

Find the number of symmetric sets of $B$.

If $A$ be the set of triangles in a plane and $R^{+}$ be the set of all positive real numbers,  then the function $f\::\:A\rightarrow R^{+},$ defined by $f(x)=$ area of triangle  $x,$ is

  1. one-one and into
  2. one-one and onto
  3. many-one and onto
  4. many-one and into

Let $(x_n)$ be a sequence of a real number such that the subsequence $(x_{2n})$ and $(x_{3n})$ converge to limit $K$ and $L$ respectively. Then

  1. $(x_n)$ always converge
  2. If $K=L$ then $(x_n)$ converge
  3. $(x_n)$ may not converge but $K=L$
  4. it is possible to have $K \neq L$
Let $D = \{d_1, d_2, \dots, d_k\}$ be the set of distinct divisors of a positive integer $n$ ($D$ includes 1 and $n$). Then show that
$\Sigma_{i=1}^k \sin^{-1} \sqrt{\log_nd_i}=\frac{\pi}{4} \times k$.
hint: $\sin^{−1} x + \sin^{−1} \sqrt{1-x^2} = \frac{\pi}{2}$

A function $f:\mathbb{R^2} \rightarrow \mathbb{R}$ is called degenerate on $x_i$, if $f(x_1,x_2)$ remains constant when $x_i$ varies $(i=1,2)$. Define

$$f(x_1,x_2) = \mid 2^{\pi _i/x_1} \mid ^{x_2} \text{ for } x_1 \neq 0$$,

where $i = \sqrt {-1}$. Then which of the following statements is true?

  1. $f$ is degenerate on both $x_1$ and $x_2$
  2. $f$ is degenerate on $x_1$ but not on $x_2$
  3. $f$ is degenerate on $x_2$ but not on $x_1$
  4. $f$ is neither degenerate on $x_1$ nor on $x_2$

Consider the functions $f,g:[0,1] \rightarrow [0,1]$ given by

$$f(x)=\frac{1}{2}x(x+1) \text{ and } g(x)=\frac{1}{2}x^2(x+1).$$

Then the area enclosed between the graphs of $f^{-1}$ and $g^{-1}$ is

  1. $1/4$
  2. $1/6$
  3. $1/8$
  4. $1/24$

The area bounded by $y=x^2-4$, $y=0$ and $x=4$ is

  1. $\frac{64}{3}$
  2. $6$
  3. $\frac{16}{3}$
  4. $\frac{32}{3}$

The area lying in the first quadrant and bounded by the circle $x^{2}+y^{2}=4$ and the lines $x= 0$ and $x=1$ is given by

  1. $\frac{\pi}{3}+\frac{\sqrt{3}}{2}$
  2. $\frac{\pi}{6}+\frac{\sqrt{3}}{4}$
  3. $\frac{\pi}{3}-\frac{\sqrt{3}}{2}$
  4. $\frac{\pi}{6}+\frac{\sqrt{3}}{2}$

The area enclosed by the curve $\mid\: x \mid + \mid y \mid =1$ is

  1. $1$
  2. $2$
  3. $\sqrt{2}$
  4. $4$

Let $f: \bigg( – \dfrac{\pi}{2}, \dfrac{\pi}{2} \bigg) \to \mathbb{R}$ be a continuous function, $f(x) \to +\infty$ as $x \to \dfrac{\pi^-}{2}$ and $f(x) \to – \infty$ as $x \to -\dfrac{\pi^+}{2}$. Which one of the following functions satisfies the above properties of $f(x)$?

  1. $\cos x$
  2. $\tan x$
  3. $\tan^{-1} x$
  4. $\sin x$
Let $n$ be a fixed positive integer. For any real number $x,$ if for some integer $q,$ $$x=qn+r, \: \: \:  0 \leq r < n,$$ then we define $x \text{ mod } n=r$.

Specify the points of discontinuity of the function $f(x)=x \text{ mod } 3$ with proper reasoning.

Let $S\subseteq \mathbb{R}$. Consider the statement 

“There exists a continuous function $f:S\rightarrow S$ such that $f(x) \neq x$ for all $x \in S.$ ”

This statement is false if $S$ equals

  1. $[2,3]$
  2. $(2,3]$
  3. $[-3,-2] \cup [2,3]$
  4. $(-\infty,\infty)$

Consider the following functions

$f(x)=\begin{cases} 1, & \text{if } \mid x \mid \leq 1 \\ 0, & \text{if } \mid x \mid >1 \end{cases}.$   and  $g(x)=\begin{cases} 1, & \text{if } \mid x \mid \leq 2 \\ 2, & \text{ if } \mid x \mid > 2 \end{cases}. $

Define $h_1(x) = f(g(x))$ and $h_2(x) = g(f(x))$. Which of the following statements is correct?

  1. $h_1$ and $h_2$ are continuous everywhere
  2. $h_1$ is continuous everywhere and $h_2$ has discontinuity at $\pm1$
  3. $h_2$ is continuous everywhere and $h_1$ has discontinuity at $\pm2$
  4. $h_1$ has discontinuity at $\pm 2$ and $h_2$ has discontinuity at $\pm1$.

If $f(x) = \sin \bigg( \dfrac{1}{x^2+1} \bigg),$ then

  1. $f(x)$ is continuous at $x=0$, but not differentiable at $x=0$
  2. $f(x)$ is differentiable at $x=0$, and $f’(0) \neq 0$
  3. $f(x)$ is differentiable at $x=0$, and $f’(0) = 0$
  4. None of the above

Suppose that the function $h(x)$ is defined as $h(x)=g(f(x))$ where $g(x)$ is monotone increasing, $f(x)$ is concave, and $g’’(x)$ and $f’’(x)$ exist for all $x$. Then $h(x)$ is

  1. always concave
  2. always convex
  3. not necessarily concave
  4. None of these

The piecewise linear function for the following graph is

  1. $f(x)=\begin{cases} = x,x\leq-2 \\ =4,-2<x<3 \\  = x+1,x\geq 3\end{cases}$
  2. $f(x)=\begin{cases} = x-2,x\leq-2 \\ =4,-2<x<3 \\  = x-1,x\geq 3\end{cases}$
  3. $f(x)=\begin{cases} = 2x,x\leq-2 \\ =x,-2<x<3 \\  = x+1,x\geq 3\end{cases}$
  4. $f(x)=\begin{cases} = 2-x,x\leq-2 \\ =4,-2<x<3 \\  = x+1,x\geq 3\end{cases}$

The integral $$\int _0^{\frac{\pi}{2}} \frac{\sin^{50} x}{\sin^{50}x +\cos^{50}x} dx$$ equals

  1. $\frac{3 \pi}{4}$
  2. $\frac{\pi}{3}$
  3. $\frac{\pi}{4}$
  4. none of these

For real $\alpha$, the value of $\int_{\alpha}^{\alpha+1} [x]dx$, where $[x]$ denotes the largest integer less than or equal to $x$, is

  1. $\alpha$
  2. $[\alpha]$
  3. $1$
  4. $\dfrac{[\alpha] + [\alpha +1]}{2}$

The value of the definite integral $\int_0^{\pi} \mid \frac{1}{2} + \cos x \mid dx$ is

  1. $\frac{\pi}{6} + \sqrt{3}$
  2. $\frac{\pi}{6} - \sqrt{3}$
  3. $0$
  4. $\frac{1}{2}$

The value of the integral $\displaystyle{}\int_{-1}^1 \dfrac{x^2}{1+x^2} \sin x \sin 3x \sin 5x dx$ is 

  1. $0$
  2. $\frac{1}{2}$
  3. $ – \frac{1}{2}$
  4. $1$

Consider the function $$f(x) = \begin{cases} \int_0^x \{5+ \mid 1-y \mid \} dy & \text{ if } x>2 \\ 5x+2 & \text{ if } x \leq 2 \end{cases}$$ Then

  1. $f$ is not continuous at $x=2$
  2. $f$ is continuous and differentiable everywhere
  3. $f$ is continuous everywhere but not differentiable at $x=1$
  4. $f$ is continuous everywhere but not differentiable at $x=2$

Given that $\int_{-\infty}^{\infty} e^{-x^2} dx = \sqrt{\pi}$, the value of $$ \int_{-\infty}^{\infty}  \int_{-\infty}^{\infty} e^{-(x^2+xy+y^2)} dxdy$$ is

  1. $\sqrt{\pi/3}$
  2. $\pi/\sqrt{3}$
  3. $\sqrt{2 \pi/3}$
  4. $2 \pi / \sqrt{3}$

The value of $$\underset{n \to \infty}{\lim} \bigg[ (n+1) \int_0^1 x^n \text{ln}(1+x) dx \bigg]$$ is

  1. $0$
  2. $\text{ln }2$
  3. $\text{ln }3$
  4. $\infty$

Let $0 < \alpha < \beta < 1$. Then $$ \Sigma_{k=1}^{\infty} \int_{1/(k+\beta)}^{1/(k+\alpha)} \frac{1}{1+x} dx$$ is equal to

  1. $\log_e \frac{\beta}{\alpha}$
  2. $\log_e \frac{1+ \beta}{1 + \alpha}$
  3. $\log_e \frac{1+\alpha }{1+ \beta}$
  4. $\infty$

If $f$ is continuous in $[0,1]$ then $$\underset{n \to \infty}{\lim} \Sigma_{j=0}^{[n/2]} \frac{1}{n} f \bigg(\frac{j}{n} \bigg)$$ (where $[y]$ is the largest integer less than or equal to $y$)

  1. does not exist
  2. exists and is equal to $\frac{1}{2} \int_0^1 f(x) dx$
  3. exists and is equal to $ \int_0^1 f(x) dx$
  4. exists and is equal to $\int_0^{1/2} f(x) dx$

Given that $\int_{-\infty}^{\infty} e^{-x^2/2} dx = \sqrt{2 \pi}$, what is the value of $\int_{- \infty}^{\infty} \mid x \mid ^{-1/2} e^{- \mid x \mid} dx$?

  1. $0$
  2. $\sqrt{\pi}$
  3. $2 \sqrt{\pi}$
  4. $\infty$

The map $f(x) = a_0 \cos \mid x \mid +a_1 \sin \mid x \mid +a_2 \mid x \mid ^3$ is differentiable at $x=0$ if and only if

  1. $a_1=0$ and $a_2=0$
  2. $a_0=0$ and $a_1=0$
  3. $a_1=0$
  4. $a_0, a_1, a_2$ can take any real value

$f(x)$ is a differentiable function on the real line such that $\underset{x \to \infty=}{\lim} f(x) =1$ and $\underset{x \to \infty=}{\lim} f’(x) =\alpha$. Then

  1. $\alpha$ must be $0$
  2. $\alpha$ need not be $0$, but $\mid \alpha \mid <1$
  3. $\alpha >1$
  4. $\alpha < -1$

Let $f$ and $g$ be two differentiable functions such that $f’(x)\leq g’(x)$for all $x<1$ and $f’(x) \geq g’(x)$ for all $x>1$. Then

  1. if $f(1) \geq g(1)$, then $f(x) \geq g(x)$ for all $x$
  2. if $f(1) \leq g(1)$, then $f(x) \leq g(x)$ for all $x$
  3. $f(1) \leq g(1)$
  4. $f(1) \geq g(1)$

Let $y=\left \lfloor x \right \rfloor$ where $\left \lfloor x \right \rfloor$ is greatest integer less than or equal to $x$. Then

  1. $y$ is continuous and many-one.
  2. $y$ is not differentiable and many-one.
  3. $y$ is not differentiable.
  4. $y$ is differentiable and many-one.

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a strictly increasing function. Then which one the following is always true?

  1. The limits $\lim_{x \rightarrow a+} f(x) $ and $\lim_{x \rightarrow a-} f(x)$ exist for all real numbers $a$
  2. If $f$ is differentiable at $a$ then $f'(a)>0$
  3. There cannot be any real number $B$ such that $f(x)<B$ for all real $x$
  4. There cannot be any real number $L$ such that $f(x)>L$ for all real $x$

Consider the function $f(x) = \dfrac{e^{- \mid x \mid}}{\text{max}\{e^x, e^{-x}\}}, \: \: x \in \mathbb{R}$. Then

  1. $f$ is not continuous at some points
  2. $f$ is continuous everywhere, but not differentiable anywhere
  3. $f$ is continuous everywhere, but not differentiable at exactly one point
  4. $f$ is differentiable everywhere

Let $g: \mathbb{R} \rightarrow \mathbb{R}$ be differentiable with $g'(x^2)=x^3$ for all $x>0$ and $g(1) =1$. Then $g(4)$ equals

  1. $64/5$
  2. $32/5$
  3. $37/5$
  4. $67/5$

An even function $f(x)$ has left derivative $5$ at $x=0$. Then

  1. the right derivative of $f(x)$ at $x=0$ need not exist
  2. the right derivative of $f(x)$ at $x=0$ exists and is equal to $5$
  3. the right derivative of $f(x)$ at $x=0$ exists and is equal to $-5$
  4. none of the above is necessarily true
Let $\lceil x \rfloor$ denote the integer nearest to $x$. For example, $\lceil 1.1 \rfloor =1, \lceil 1.5 \rfloor =1$ and $\lceil 1.6 \rfloor$ =2. Draw the graph of the function $y= \mid x - \lceil x \rfloor \mid$ for $0 \leq x \leq 4$. Find all the points $x, \: 0 \leq x \leq 4$, where the function is not differentiable. Justify your answer.

Let $[x]$ denote the largest integer less than or equal to $x.$ The number of points in the open interval $(1,3)$ in which the function $f(x)=a^{[x^2]},a\gt1$ is not differentiable, is

  1. $0$
  2. $3$
  3. $5$
  4. $7$

Let $f(x)=(x-1)(x-2)(x-3)g(x); \: x\in \mathbb{R}$ where $g$ is twice differentiable function. Then

  1. there exists $y\in(1,3)$ such that $f’’(y)=0.$
  2. there exists $y\in(1,2)$ such that $f’’(y)=0.$
  3. there exists $y\in(2,3)$ such that $f’’(y)=0.$
  4. none of the above is true.

The general solution of the differential equation $2y{y}'-x=0$ is (assuming $C$ as an arbitrary constant of integration)

  1. $x^{2}-y^{2}=C$
  2. $2x^{2}-y^{2}=C$
  3. $2y^{2}-x^{2}=C$
  4. $x^{2}+y^{2}=C$

The general solution of the differential equation $x+y-x{y}'=0$ is (assuming $C$ as an arbitrary constant of integration)

  1. $y=x(\log x+C)$
  2. $x=y(\log y+C)$
  3. $y=x(\log y+C)$
  4. $y=y(\log x+C)$

Consider the differential equation $(x^{2}-y^{2})\frac{\mathrm{d} y}{\mathrm{d} x}=2xy.$  Assuming  $y=10$ for $x=0,$ its solution is

  1. $x^{2}+(y-5)^{2}=25$
  2. $x^{2}+y^{2}=100$
  3. $(x-5)^{2}+y^{2}=125$
  4. $(x-5)^{2}+(y-5)^{2}=50$

The set of value(s) of $\alpha$ for which $y(t)=t^{\alpha}$ is a solution to the differential equation $$t^2 \frac{d^2y}{dx^2}-2t \frac{dy}{dx}+2y =0 \: \text{ for } t>0$$ is

  1. $\{1\}$
  2. $\{1, -1\}$
  3. $\{1, 2\}$
  4. $\{-1, 2\}$

A function $y(x)$ that satisfies $\dfrac{dy}{dx}+4xy=x$ with the boundary condition $y(0)=0$ is

  1. $y(x)=(1-e^x)$
  2. $y(x)=\frac{1}{4}(1-e^{-2x^2})$
  3. $y(x)=\frac{1}{4}(1-e^{2x^2})$
  4. $y(x)=\frac{1}{4}(1-\cos x)$

If $f(x)=e^{5x}$ and $h(x)=f’’(x)+2f’(x)+f(x)+2$  then $h(0)$ equals

  1. $38$
  2. $8$
  3. $4$
  4. $0$

Let $f’(x)=4x^3-3x^2+2x+k,$  $f(0)=1$ and $f(1)=4.$ Then $f(x)$ is equal to

  1. $4x^4-3x^3+2x^2+x+1$
  2. $x^4-x^3+x^2+2x+1$
  3. $x^4-x^3+x^2+2(x+1)$
  4. none of these

Let $f(x)=1+x+\dfrac{x^2}{2}+\dfrac{x^3}{3}...+\dfrac{x^{2018}}{2018}.$ Then $f’(1)$ is equal to 

  1. $0$
  2. $2017$
  3. $2018$
  4. $2019$

The domain of the function $\text{ln}(3x^2-4x+5)$ is

  1. set of positive real numbers
  2. set of real numbers
  3. set of negative real numbers
  4. set of real numbers larger than $5$

The domain of the function $\ln(3x^{2}-4x+5)$ is

  1. set of positive real numbers
  2. set of real numbers
  3. set of negative real numbers
  4. set of real numbers larger than $5$

Let $y=\lfloor x \rfloor$, where $\lfloor x \rfloor$ is greatest integer less than or equal to $x$. Then

  1. $y$ is continuous and many-one
  2. $y$ is not differentiable and many-one
  3. $y$ is not differentiable
  4. $y$ is differentiable and many-one
Consider the funciton $M$ defined as follows:

$M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$

Compute the following$: M(101)$
Consider the funciton $M$ defined as follows:

$M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$

Compute the following$: M(99)$
Consider the funciton $M$ defined as follows:

$M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$

Compute the following$: M(87)$
Consider the funciton $M$ defined as follows:

$M(n) = \begin{cases} n-10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$

Give a constant time algorithm that computes $M(n)$ on input $n$. (A constant-time algorithm is one whose running time is independent of the input $n$)

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a strictly increasing function. Then which one of the following is always true?

  1. The limits $\lim_{x\rightarrow a+} f(X)$ and $\lim_{x\rightarrow a-} f(X)$ exist for all real number a
  2. if $f$ is differentiable at a then $f'(a)>0$
  3. There cannot not be a real number $B$ such that $f(x) < B$ for all real $x$
  4. There cannot not be a real number $L$ such that $f(x) > L$ for all real $x$

If $\textit{f}(x)=\frac{\sqrt{3}\sin x}{2+\cos x}$ then the range of $\textit{f}(x)$ is

  1. the interval $\left[-1,\frac{\sqrt{3}}{2}\right]$
  2. the interval $\left[\frac{-\sqrt{3}}{2},1\right]$
  3. the interval $\left[-1,1\right]$
  4. none of the above

If $\textit{f}(x)=x^{2}$ and $g(x)=x \sin x +\cos x$ then

  1. $f$ and $g$ agree at no point
  2. $f$ and $g$ agree at exactly one point
  3. $f$ and $g$ agree at exactly two point
  4. $f$ and $g$ agree at more then two point

Let $f(x) = \dfrac{2x}{x-1}, \: x \neq 1$.  State which of the following statements is true.

  1. For all real $y$, there exists $x$ such that $f(x)=y$
  2. For all real $y \neq 1$, there exists $x$ such that $f(x)=y$
  3. For all real $y \neq 2$, there exists $x$ such that $f(x)=y$
  4. None of the above is true

If $f(x)$ is a real valued function such that $2f(x)+3f(-x)=15-4x$, for every $x \in \mathbb{R}$, then $f(2)$ is

  1. $-15$
  2. $22$
  3. $11$
  4. $0$

The piecewise linear function for the following graph is

 

  1. $f(x) = \begin{cases} = x, \: x \leq -2 \\ =4, \: -2<x<3 \\ =x+1, \: x \geq 3 \end{cases}$
  2. $f(x) = \begin{cases} = x-2, \: x \leq -2 \\ =4, \: -2<x<3 \\ =x-1, \: x \geq 3 \end{cases}$
  3. $f(x) = \begin{cases} = 2x, \: x \leq -2 \\ =x, \: -2<x<3 \\ =x+1, \: x \geq 3 \end{cases}$
  4. $f(x) = \begin{cases} = 2-x, \: x \leq -2 \\ =4, \: -2<x<3 \\ =x+1, \: x \geq 3 \end{cases}$

Suppose that a function $f$ defined on $\mathbb{R} ^2$ satisfies the following conditions:

$$\begin{array} &f(x+t,y) & = & f(x,y)+ty, \\ f(x,t+y) & = & f(x,y)+ tx \text{ and } \\ f(0,0) & = & K, \text{ a constant.} \end{array}$$

Then for all $x,y \in \mathbb{R}, \:f(x,y)$ is equal to

  1. $K(x+y)$
  2. $K-xy$
  3. $K+xy$
  4. none of the above

If $f(x)$ is a real valued function such that $$2f(x)+3f(-x)=15-4x,$$ for every $x \in \mathbb{R}$, then $f(2)$ is

  1. $-15$
  2. $22$
  3. $11$
  4. $0$

For non-negative integers $m$, $n$ define a function as follows

$$f(m,n) = \begin{cases} n+1 & \text{ if } m=0 \\ f(m-1, 1) & \text{ if } m \neq 0, n=0 \\ f(m-1, f(m,n-1))  & \text{ if }  m \neq 0, n \neq 0 \end{cases}$$ Then the value of $f(1,1)$ is

  1. $4$
  2. $3$
  3. $2$
  4. $1$

Let $f : (0, \infty) \rightarrow (0, \infty)$ be a strictly decreasing function. Consider $h(x) = \dfrac{f(\frac{x}{1+x})}{1+f(\frac{x}{1+x})}$. Which one of the following is always true?

  1. $h$ is strictly decreasing
  2. $h$ is strictly increasing
  3. $h$ is strictly decreasing at first and then strictly increasing
  4. $h$ is strictly increasing at first and then strictly decreasing

If  $2f(x)-3f(\frac{1}{x})=x^2 \: (x \neq0)$,  then $f(2)$ is

  1. $\frac{2}{3}$
  2. $ – \frac{3}{2}$
  3. $ – \frac{7}{4}$
  4. $\frac{5}{4}$

Let $f(x) = \dfrac{x-1}{x+1}, \: f^{k+1}(x)=f\left(f^k(x)\right)$ for all $k=1, 2, 3, \dots , 99$.  Then $f^{100}(10)$ is

  1. $1$
  2. $10$
  3. $100$
  4. $101$

Consider the function $h$ defined on $\{0,1,…….10\}$ with $h(0)=0, \:  h(10)=10 $ and

$$2[h(i)-h(i-1)] = h(i+1) – h(i)  \:   \text{ for } i = 1,2, \dots  ,9.$$

Then the value of $h(1)$ is

  1. $\frac{1}{2^9-1}\\$
  2. $\frac{10}{2^9+1}\\$
  3. $\frac{10}{2^{10}-1}\\$
  4. $\frac{1}{2^{10}+1}$

Let $A=\{1, 2, 3, 4, 5, 6, 7, 8 \}$. How many functions $f: A \rightarrow A$ can be defined such that $f(1)< f(2) < f(3)$?

  1. $\begin{pmatrix} 8 \\ 3 \end{pmatrix}$
  2. $\begin{pmatrix} 8 \\ 3 \end{pmatrix} 5^8$
  3. $\begin{pmatrix} 8 \\ 3 \end{pmatrix} 8^5$
  4. $\frac{8!}{3!}$

Let $X =\frac{1}{1001}+\frac{1}{1002}+\frac{1}{1003}+\ldots+\frac{1}{3001}$. Then

  1. $X< 1$
  2. $X>\frac{3}{2}$
  3. $1< X< \frac{3}{2}$
  4. none of the above

Let $I=\int (\sin x – \cos x)(\sin x + \cos x)^3 dx$ and $K$ be a constant of integration. Then the value of $I$ is

  1. $(\sin x + \cos x)^4+K$
  2. $(\sin x + \cos x)^2+K$
  3. $- \frac{1}{4} (\sin x + \cos x)^4+K$
  4. None of these

Let $R$ be the triangle in the $xy$ – plane bounded by the $x$-axis, the line $y=x$, and the line $x=1$. The value of the double integral $$ \int \int_R \frac{\sin x}{x}\: dxdy$$ is

  1. $1-\cos 1$
  2. $\cos 1$
  3. $\frac{\pi}{2}$
  4. $\pi$

For $a,b \in \mathbb{R}$ and $b > a$ , the maximum possible value of the integral $\int_{a}^{b}(7x-x^{2}-10)dx$ is

  1. $\frac{7}{2}\\$
  2. $\frac{9}{2}\\$
  3. $\frac{11}{2}\\$
  4. none of these

Let $f$ be a continuous function with $f(1) = 1$. Define $$F(t)=\int_{t}^{t^2}f(x)dx$$.

The value of $F’(1)$ is

  1. $-2$
  2. $-1$
  3. $1$
  4. $2$

Let $a,b,c$ be non-zero real numbers such that 

$\int_{0}^{1} (1 + \cos^8x)(ax^2 + bx +c)dx = \int_{0}^{2}(1+ \cos^8x)(ax^2 + bx + c) dx =0$

Then the quadratic equation $ax^2 + bx +c=0$ has 

  1. no roots in $(0,2)$
  2. one root in $(0,2)$ and one root outside this interval
  3. one repeated root in $(0,2)$
  4. two distinct real roots in $(0,2)$

Let $\psi : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous function with $\psi(y) =0$ for all $y \notin [0,1]$ and $\int_{0}^{1} \psi(y) dy=1$. Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a twice differentiable function. Then the value of $$\lim _{n\rightarrow \infty}n \int_{0}^{100} f(x)\psi(nx)dx$$ is

  1. $f(0)$
  2. $f’(0)$
  3. $f’’(0)$
  4. $f(100)$

Let the function $f(x)$ be defined as $f(x)=\mid x-1 \mid + \mid x-2 \:\mid$. Then which of the following statements is true?

  1. $f(x)$ is differentiable at $x=1$
  2. $f(x)$ is differentiable at $x=2$
  3. $f(x)$ is differentiable at $x=1$ but not at $x=2$
  4. none of the above

$\underset{x \to 2}{\lim} \dfrac{1}{1+e^{\frac{1}{x-2}}}$  is

  1. $0$
  2. $1/2$
  3. $1$
  4. non-existent

Let  $a_n=\bigg( 1 – \frac{1}{\sqrt{2}} \bigg) \cdots \bigg( 1 – \frac{1}{\sqrt{n+1}} \bigg), \: n \geq 1$. Then $\underset{n \to \infty}{\lim} a_n$

  1. equals $1$
  2. does not exist
  3. equals $\frac{1}{\sqrt{\pi}}$
  4. equals $0$

$\underset{x \to \infty}{\lim} \bigg( \frac{3x-1}{3x+1} \bigg) ^{4x}$ equals

  1. $1$
  2. $0$
  3. $e^{-8/3}$
  4. $e^{4/9}$

Let $f(x)$ be a continuous function from $[0,1]$ to $[0,1]$ satisfying the following properties.

  1. $f(0)=0$,
  2. $f(1)=1$, and
  3. $f(x_1)<f(x_2)$ for $x_1 < x_2$ with $0 < x_1, \: x_2<1$.

Then the number of such functions is

  1. $0$
  2. $1$
  3. $2$
  4. $\infty$

Let $$f(x) = \begin{cases}\mid \:x \mid +1, & \text{ if } x<0 \\ 0, & \text{ if } x=0 \\ \mid \:x \mid -1, & \text{ if } x>0. \end{cases}$$ Then $\underset{x \to a}{\lim} f(x)$ exists

  1. if $a=0$
  2. for all $a \in R$
  3. for all $a \neq 0$
  4. only if $a=1$

$\underset{x \to 0}{\lim} \dfrac{x \tan x}{1- \cos tx}$ is  equal to

  1. $0$
  2. $1$
  3. $\infty$
  4. $2$

The value of $\underset{x \to 0}{\lim} \dfrac{\tan ^2 x – x \tan x }{\sin x}$ is

  1. $\frac{\sqrt{3}}{2}$
  2. $\frac{1}{2}$
  3. $0$
  4. None of these

$\underset{x \to 1}{\lim} \dfrac{x^{\frac{1}{3}}-1}{x^{\frac{1}{4}}-1}$ equals

  1. $\frac{4}{3}$
  2. $\frac{3}{4}$
  3. $1$
  4. None of these

$\underset{x \to -1}{\lim} \dfrac{1+\sqrt[3]{x}}{1+\sqrt[5]{x}}$ equals

  1. $\frac{3}{5}$
  2. $\frac{5}{3}$
  3. $1$
  4. $\infty$

$\underset{x \to 0}{\lim} x \sin \big( \frac{1}{x} \big)$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

$\underset{x \to 0}{\lim} \sin \bigg( \dfrac{1}{x} \bigg)$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

$\underset{x \to \infty}{\lim} \bigg( 1 + \dfrac{1}{x^2} \bigg) ^x$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

$\underset{x \to 1}{\lim} \dfrac{x^{16}-1}{\mid x-1 \mid}$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

The limit $\:\:\:\underset{n \to \infty}{\lim}  \Sigma_{k=1}^n \begin{vmatrix} e^{\frac{2 \pi i k }{n}} – e^{\frac{2 \pi i (k-1) }{n}} \end{vmatrix}\:\:\:$ is

  1. $2$
  2. $2e$
  3. $2 \pi$
  4. $2i$

The limit $\underset{n \to \infty}{\lim} \bigg( 1- \frac{1}{n^2} \bigg) ^n$ equals

  1. $e^{-1}$
  2. $e^{-1/2}$
  3. $e^{-2}$
  4. $1$

Let $a_n= \bigg( 1 – \frac{1}{\sqrt{2}} \bigg) \cdots \bigg( 1- \frac{1}{\sqrt{n+1}} \bigg), \: \: n \geq1$. Then $\underset{n \to \infty}{\lim} a_n$

  1. equals $1$
  2. does not exist
  3. equals $\frac{1}{\sqrt{\pi}}$
  4. equals $0$

The limit $\displaystyle{}\underset{x \to \infty}{\lim} \bigg( \frac{3x-1}{3x+1} \bigg) ^{4x}$ equals

  1. $1$
  2. $0$
  3. $e^{-8/3}$
  4. $e^{4/9}$

$\displaystyle{}\underset{n \to \infty}{\lim} \frac{1}{n} \bigg( \frac{n}{n+1} + \frac{n}{n+2} + \cdots + \frac{n}{2n} \bigg)$ is equal to

  1. $\infty$
  2. $0$
  3. $\log_e 2$
  4. $1$

Let $\{a_n\}$ be a sequence of real numbers. Then $\underset{n \to \infty}{\lim} a_n$ exists if and only if

  1. $\underset{n \to \infty}{\lim} a_{2n}$ and $\underset{n \to \infty}{\lim} a_{2n+2}$ exists
  2. $\underset{n \to \infty}{\lim} a_{2n}$ and $\underset{n \to \infty}{\lim} a_{2n+1}$ exist
  3. $\underset{n \to \infty}{\lim} a_{2n}, \underset{n \to \infty}{\lim} a_{2n+1}$ and $\underset{n \to \infty}{\lim} a_{3n}$ exist
  4. none of the above

Suppose $a>0$. Consider the sequence $a_n = n \{ \sqrt[n]{ea} – \sqrt[n]{a}, \:\:\:\:\: n \geq 1$. Then

  1. $\underset{n \to \infty}{\lim} a_n$ does not exist
  2. $\underset{n \to \infty}{\lim} a_n=e$
  3. $\underset{n \to \infty}{\lim} a_n=0$
  4. none of the above

Let $\{a_n\}, n \geq 1$, be a sequence of real numbers satisfying $\mid a_n \mid \leq 1$ for all $n$. Define $A_n = \frac{1}{n}(a_1+a_2+\cdots+a_n)$, for $n \geq 1$. Then $\underset{n \to \infty}{\lim} \sqrt{n}(A_{n+1}-A_n)$ is equal to

  1. $0$
  2. $-1$
  3. $1$
  4. none of these

The value of $\underset{x \to 0}{\lim} \dfrac{\tan^{2}\:x-x\:\tan\:x}{\sin\:x}$ is

  1. $\frac{\sqrt{3}}{2}$
  2. $\frac{1}{2}$
  3. $0$
  4. None of these

$\underset{x\rightarrow 1}{\lim}\dfrac{x^{\frac{1}{3}}-1}{x^{\frac{1}{4}}-1}$ equals

  1. $\frac{4}{3}$
  2. $\frac{3}{4}$
  3. $1$
  4. None of these

$\underset{x\rightarrow-1}{\lim}\dfrac{1+\sqrt[3]{x}}{1+\sqrt[5]{x}}$ equals

  1. $\frac{3}{5}$
  2. $\frac{5}{3}$
  3. $1$
  4. $\infty$

$\underset{x\rightarrow 0}{\lim}x\sin\left(\dfrac{1}{x}\right)$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

$\underset{x\rightarrow 0}{\lim}\sin\left(\dfrac{1}{x}\right)$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

$\underset{x\rightarrow \infty}{\lim} \left(1+\dfrac{1}{x^{2}}\right)^{x}$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

$\underset{x\rightarrow 1}{\lim} \dfrac{x^{16}-1}{\mid x-1\mid}$ equals

  1. $-1$
  2. $0$
  3. $1$
  4. Does not exist

Let $ f(x, y) = \begin{cases} \dfrac{x^2y}{x^4+y^2}, & \text{ if } (x, y) \neq (0, 0) \\ 0 & \text{ if } (x, y) = (0, 0) \end{cases}$

Then $\lim_{(x, y) \rightarrow (0,0)}$$f(x,y)$

  1. equals $0$
  2. equals $1$
  3. equals $2$
  4. does not exist

The limit of the sequence $\sqrt{2}, \sqrt{2\sqrt{2}}, \sqrt{2\sqrt{2\sqrt{2}}}, \dots$ is

  1. $1$
  2. $2$
  3. $2\sqrt{2}$
  4. $\infty$

Let $(v_n)$ be a sequence defined by $v_1 = 1$ and $v_{n+1} = \sqrt{v_n^2 +\left(\dfrac{1}{5}\right)^n}$ for $n\geq1$. Then $\displaystyle{\lim_{n \rightarrow \infty}v_n}$ is

  1. $\sqrt{5/3}$
  2. $\sqrt{5/4}$
  3. $1$
  4. $\text{non existent}$

Let $(x_n)$ be a sequence of real numbers such that the subsequences $(x_{2n})$ and $(x_{3n})$ converge to limits $K$ and $L$ respectively. Then

  1. $(x_n)$ always converges
  2. if $K=L$, then $(x_n)$ converges
  3. $(x_n)$ may not converge, but $K=L$
  4. it is possible to have $K \neq L$

Let $f(x)=e^{-\big( \frac{1}{x^2-3x+2} \big) };x\in \mathbb{R} \: \: \& x \notin \{1,2\}$. Let $a=\underset{n \to 1^+}{\lim}f(x)$ and $b=\underset{x \to 1^-}{\lim} f(x)$. Then

  1. $a=\infty, \: b=0$
  2. $a=0, \: b=\infty$
  3. $a=0, \: b=0$
  4. $a=\infty, \: b=\infty$

Let $X_1,X_2, . . . ,X_n$ be independent and identically distributed with $P(X_i = 1) = P(X_i = −1) = p\ $and$ P(X_i = 0) = 1 − 2p$ for all $i = 1, 2, . . . , n.$ Define

$a_n=P\bigg(  \prod_{i=1}^{\infty} X_i=1 \bigg )$, $b_n=P\bigg(  \prod_{i=1}^{\infty} X_i=-1 \bigg )$, $c_n=P\bigg(  \prod_{i=1}^{\infty} X_i=0 \bigg )$

Which of the following is true as $n$ tends to infinity?

  1. $a_n \rightarrow1/3, b_n \rightarrow1/3,c_n \rightarrow1/3$
  2. $a_n \rightarrow p, b_n \rightarrow p,c_n \rightarrow 1-2p$
  3. $a_n \rightarrow1/2, b_n \rightarrow1/2,c_n \rightarrow0$
  4. $a_n \rightarrow0, b_n \rightarrow0,c_n \rightarrow1$

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be a continuous function such that $\lim _{n\rightarrow \infty} f’’(x)$ exists for every $x \in \mathbb{R}$, where $f’’(x) = f  \circ f^{n-1}(x)$ for $n \geq 2$. Define 

$$S=\big\{\lim _{n \rightarrow \infty} f’’(x): x \in \mathbb{R}\big\}  \text{ and } T=\big\{x  \in \mathbb{R}:f(x)=x\big\}$$

Then which of the following is necessarily true?

  1. $S \subset T$
  2. $T \subset S$
  3. $S = T$
  4. None of the above

 If $f(a)=2, \: f’(a) = 1, \: g(a) =-1$ and $g’(a) =2$, then the value of   

                                  $$\lim _{x\rightarrow a}\frac{g(x) f(a) – f(x) g(a)}{x-a}$$ is

  1. $-5$
  2. $-3$
  3. $3$
  4. $5$

Which of the following is true?

  1. $\log(1+x) < x- \frac{x^2}{2} + \frac{x^3}{3} \text{ for all } x>0$
  2. $\log(1+x) > x- \frac{x^2}{2} + \frac{x^3}{3} \text{ for all } x>0$
  3. $\log(1+x) > x- \frac{x^2}{2} + \frac{x^3}{3} \text{ for some } x>0$
  4. $\log(1+x) < x- \frac{x^2}{2} + \frac{x^3}{3} \text{ for some } x>0$

The maximum possible value of $xy^2z^3$ subjected to condition $x,y,z \geq 0$ and $x+y+z=3$ is

  1. $1$
  2. $\frac{9}{8}$
  3. $\frac{9}{4}$
  4. $\frac{27}{16}$

The function $f(x) = x^{1/x}, \: x \neq 0$ has

  1. a minimum at $x=e$;
  2. a maximum at $x=e$;
  3. neither a maximum nor a minimum at $x=e$;
  4. None of the above

Let $f(x)=\sin x^2, \: x \in \mathbb{R}$. Then

  1. $f$ has no local minima
  2. $f$ has no local maxima
  3. $f$ has local minima at $x=0$ and $x=\pm\sqrt{(k+\frac{1}{2} ) \pi}$ for odd integers $k$ and local maxima at $x=\pm\sqrt{(k+\frac{1}{2} ) \pi}$ for even integers $k$
  4. None of the above

The function $f(x)=\sin x(1+ \cos x)$ which is defined for all real values of $x$

  1. has a maximum at $x= \pi /3$
  2. has a maximum at $x= \pi$
  3. has a minimum at $x= \pi /3$
  4. has neither a maximum nor a minimum at $x=\pi/3$

The function $f(x)$ defined as $f(x)=x^3-6x^2+24x$, where $x$ is real, is

  1. strictly increasing
  2. strictly decreasing
  3. increasing in $(- \infty, 0)$ and decreasing in $(0, \infty)$
  4. decreasing in $(- \infty, 0)$ and increasing in $(0, \infty)$ 

Consider the function

$f(x)=\bigg(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots+\frac{x^n}{n!}\bigg)e^{-x}$,

where $n\geq4$ is a positive integer. Which of the following statements is correct?

  1. $f$ has no local maximum
  2. For every $n$, $f$ has a local maximum at $x = 0$
  3. $f$ has no local extremum if $n$ is odd and has a local maximum at $x = 0$ when $n$ is even
  4. $f$ has no local extremum if $n$ is even and has a local maximum at $x = 0$ when $n$ is odd.

The maximum value of the real valued function $f(x)=\cos x + \sin x$ is

  1. $2$
  2. $1$
  3. $0$
  4. $\sqrt{2}$

It is given that $e^a+e^b=10$ where $a$ and $b$ are real. Then the maximum value of $(e^a+e^b+e^{a+b}+1)$ is

  1. $36$
  2. $\infty$
  3. $25$
  4. $21$

If $x$ is real, the set of real values of $a$ for which the function $$y=x^2-ax+1-2a^2$$ is always greater than zero is

  1. $- \frac{2}{3} < a \leq \frac{2}{3}$
  2. $- \frac{2}{3} \leq  a < \frac{2}{3}$
  3. $- \frac{2}{3} < a < \frac{2}{3}$
  4. None of these

If $f(x) = \dfrac{\sqrt{3} \sin x}{2+\cos x}$, then the range of $f(x)$ is

  1. the interval $[-1 , \sqrt{3}{/2}]$
  2. the interval $[-\sqrt{3}{/2}, 1]$
  3. the interval $[-1, 1]$
  4. none of these

If $f(x) = \dfrac{\sqrt{3}\sin x}{2+\cos x}$, then the range of $f(x)$ is

  1. the interval $[-1, \sqrt{3}/2]$
  2. the interval $[- \sqrt{3}/2, 1]$
  3. the interval $[-1, 1]$
  4. none of the above

$\underset{n \to \infty}{\lim} \dfrac{1}{n} \bigg( \dfrac{n}{n+1} + \dfrac{n}{n+2} + \cdots + \dfrac{n}{2n} \bigg)$ is equal to

  1. $\infty$
  2. $0$
  3. $\log_e 2$
  4. $1$

The value of the infinite product

$$P=\frac{7}{9} \times \frac{26}{28} \times \frac{63}{65} \times \cdots \times \frac{n^3-1}{n^3+1} \times \cdots \text{ is }$$

  1. $1$
  2. $2/3$
  3. $7/3$
  4. none of the above

The value of $\underset{n \to \infty}{\lim} \bigg( \dfrac{1}{1-n^2} + \dfrac{2}{1-n^2} + \dots + \dfrac{n}{1-n^2} \bigg)$  is

  1. $0$
  2. $ – \frac{1}{2}$
  3. $\frac{1}{2}$
  4. none of these

The Taylor series expansion of $f(x)= \text{ln}(1+x^2)$ about $x=0$ is

  1. $\sum _{n=1}^{\infty} (-1)^n \frac{x^n}{n}$
  2. $\sum _{n=1}^{\infty} (-1)^{n+1} \frac{x^{2n}}{n}$
  3. $\sum _{n=1}^{\infty} (-1)^{n+1} \frac{x^{2n+1}}{n+1}$
  4. $\sum _{n=0}^{\infty} (-1)^{n+1} \frac{x^{n+1}}{n+1}$

Consider the sets defined by the real solutions of the inequalities

$A = \{(x,y):x^2+y^4 \leq 1\} \:\:\:\:\:\:\: B=\{(x,y):x^4+y^6 \leq 1\}$ Then

  1. $B \subseteq A$
  2. $A \subseteq B$
  3. Each of the sets $A – B, \: B – A$ and $A \cap B$ is non-empty
  4. none of the above

In the Taylor expansion of the function $f(x)=e^{x/2}$ about $x=3$, the coefficient of $(x-3)^5$ is

  1. $e^{3/2} \frac{1}{5!}$
  2. $e^{3/2} \frac{1}{2^5 5!}$
  3. $e^{-3/2} \frac{1}{2^5 5!}$
  4. none of the above

The Taylor series expansion of $f(x)=\ln(1+x^{2})$ about $x=0$ is

  1. $\sum_{n=1}^{\infty}(-1)^{n}\frac{x^{n}}{n}$
  2. $\sum_{n=1}^{\infty}(-1)^{n+1}\frac{x^{2n}}{n}$
  3. $\sum_{n=1}^{\infty}(-1)^{n+1}\frac{x^{2n+1}}{n+1}$
  4. $\sum_{n=1}^{\infty}(-1)^{n+1}\frac{x^{n+1}}{n+1}$

Let $I=\int(\sin\:x-\cos\:x)(\sin\:x+\cos\:x)^{3}dx$ and $K$ be a constant of integration. Then the value of $I$ is

  1. $(\sin\:x+\cos\:x)^{4}+K$
  2. $(\sin\:x+\cos\:x)^{2}+K$
  3. $-\frac{1}{4}(\sin\:x+\cos\:x)^{4}+K$
  4. None of these

Let $V$ be the vector space of all $4 \times 4$ matrices such that the sum of the elements in any row or any column is the same. Then the dimension of $V$ is

  1. $8$
  2. $10$
  3. $12$
  4. $14$

The rank of the matrix $\begin{bmatrix} 0 &1 &t \\ 2& t & -1\\ 2& 2 & 0 \end{bmatrix}$ equals 

  1. $3$ for any real number $t$
  2. $2$ for any real number $t$
  3. $2$ or $3$ depending on the value of $t$
  4. $1,2$ or $3$ depending on the value of $t$

Let $A$ be $2 \times 2$ matrix with real entries. Now consider the function $f_A(x)$ = $Ax$ . If the image of every circle under $f_A$ is a circle of the same radius, then 

  1. A must be an orthogonal matrix
  2. A must be a symmetric matrix
  3. A must be a skew-symmetric matrix
  4. None of the above must necessarily hold 

The determinant  $\begin{vmatrix} b+c & c+a & a+b \\ q+r & r+p & p+q \\ y+z & z+x & x+y \end{vmatrix}$  equals

  1. $\begin{vmatrix} a & b & c \\ p & q & r \\ x & y & z \end{vmatrix}$
  2. $2\begin{vmatrix} a & b & c \\ p & q & r \\ x & y & z \end{vmatrix}$
  3. $3\begin{vmatrix} a & b & c \\ p & q & r \\ x & y & z \end{vmatrix}$
  4. None of these

The value of $$\begin{vmatrix} 1 & \log _x y & \log_x z \\ \log _y x & 1 & \log_y z \\ \log _z x & \log _z y & 1 \end{vmatrix}$$ is

  1. $0$
  2. $1$
  3. $-1$
  4. None of these

The value of $\begin{vmatrix} 1+a & 1 & 1 & 1 \\ 1 & 1+b & 1 & 1 \\ 1 & 1 & 1+c & 1 \\ 1 & 1 & 1 & 1+d \end{vmatrix}$   is

  1. $abcd(1+\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d})$
  2. $abcd(\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d})$
  3. $1+\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d}$
  4. None of these

Let $A$ be an $n \times n$ matrix such that $\mid A^{2} \mid\: =1$. Here $\mid A \mid $ stands for determinant of matrix $A$. Then

  1. $\mid A \mid =1$
  2. $\mid A \mid =0 \text{ or } 1$
  3. $\mid A \mid =-1, 0 \text{ or } 1$
  4. $\mid A \mid =-1  \text{ or }  1$

Let $A_{ij}$ denote the minors of an $n \times n$ matrix $A$. What is the relationship between $\mid  A_{ij} \mid $ and $\mid A_{ji} \mid $?

  1. They are always equal
  2. $\mid A_{ij} \mid = – \mid A _{ji} \mid \text{ if } i \neq j$
  3. They are equal if $A$ is a symmetric matrix
  4. If $\mid A_{ij} \mid =0$ then $\mid A_{ji} \mid =0$

Let $a$ be a non-zero real number. Define

$$f(x) = \begin{vmatrix} x & a & a & a \\ a & x & a & a \\ a & a & x & a \\ a & a & a & x \end{vmatrix}$$ for $x \in \mathbb{R}$. Then, the number of distinct real roots of $f(x) =0$ is

  1. $1$
  2. $2$
  3. $3$
  4. $4$

The value of $\:\:\begin{vmatrix} 1&\log_{x}y &\log_{x}z \\ \log_{y}x &1 &\log_{y}z \\\log_{z}x & \log_{z}y&1 \end{vmatrix}\:\:$ is

  1. $0$
  2. $1$
  3. $-1$
  4. None of these

The value of  $\begin{vmatrix} 1+a& 1& 1& 1\\ 1&1+b &1 &1 \\ 1&1 &1+c &1 \\ 1&1 &1 &1+d \end{vmatrix}$ is

  1. $abcd(1+\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d})$
  2. $abcd(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d})$
  3. $1+\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d}$
  4. None of these

Let $A$ be an $n\times n$ matrix such that $\mid\: A^{2}\mid=1.\:\: \mid A\:\mid$  stands for determinant of matrix $A.$ Then

  1. $\mid\:(A)\mid=1$
  2. $\mid\:(A)\mid=0\:\text{or}\:1$
  3. $\mid\:(A)\mid=-1,0\:\text{or}\:1$
  4. $\mid\:(A)\mid=-1\:\text{or}\:1$

If  $\begin{vmatrix} 10! & 11! & 12! \\ 11! & 12! & 13! \\ 12! & 13! & 14! \end{vmatrix} = k(10!)(11!)(12!)$, then the value of $k$ is

  1. $1$
  2. $2$
  3. $3$
  4. $4$

If $\alpha, \beta$ and $\gamma$ are the roots of $x^3 - px +q = 0$, then the value of the determinant

$$\begin{vmatrix}\alpha & \beta & \gamma\\\beta & \gamma & \alpha\\\gamma & \alpha & \beta\end{vmatrix}$$

is

  1. $p$
  2. $p^2$
  3. $0$
  4. $p^2+6q$

If $A =\begin{bmatrix} 2 &i \\ i & 0 \end{bmatrix}$ , the trace of $A^{10}$ is

  1. $2$
  2. $2(1+i)$
  3. $0$
  4. $2^{10}$

Let $A$ be a $3× 3$ real matrix with all diagonal entries equal to $0$. If $1 + i$ is an eigenvalue of $A$, the determinant of $A$ equals

  1. $-4$
  2. $-2$
  3. $2$
  4. $4$

If $f(x) = \begin{vmatrix} 2 \cos ^2 x & \sin 2x & – \sin x \\ \sin 2x & 2 \sin ^2 x & \cos x \\ \sin x & – \cos x & 0 \end{vmatrix},$  then $\int_0^{\frac{\pi}{2}} [ f(x) + f’(x)] dx$  is

  1. $\pi$
  2. $\frac{\pi}{2}$
  3. $0$
  4. $1$

The eigenvalues of the matrix $X = \begin{pmatrix} 2 & 1 & 1  \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}$ are

  1. $1,1,4$
  2. $1,4,4$
  3. $0,1,4$
  4. $0,4,4$

Let $\lambda_1, \lambda_2, \lambda_3$ denote the eigenvalues of the matrix

$$A \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos t & \sin t \\ 0 & – \sin t & \cos t \end{pmatrix}.$$ If $\lambda_1+\lambda_2+\lambda_3 = \sqrt{2}+1$, then the set of possible values of $t, \: – \pi \leq t < \pi$, is

  1. Empty set
  2. $\{ \frac{\pi}{4} \}$
  3. $\{ – \frac{\pi}{4}, \frac{\pi}{4} \}$
  4. $\{ – \frac{\pi}{3}, \frac{\pi}{3} \}$

If the matrix $A = \begin{bmatrix} a & 1 \\ 2 & 3 \end{bmatrix}$ has $1$ as an eigenvalue, then $\textit{trace}(A)$ is

  1. $4$
  2. $5$
  3. $6$
  4. $7$

Let $A$ be a real $2 \times 2$ matrix. If $5+3i$ is an eigenvalue of $A$, then $det(A)$

  1. equals 4
  2. equals 8
  3. equals 16
  4. cannot be determined from the given information

The set of vectors constituting an orthogonal basis in $\mathbb{R} ^3$ is

  1. $\begin{Bmatrix} \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}, & \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, & \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \end{Bmatrix}$
  2. $\begin{Bmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{pmatrix}, & \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, & \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \end{Bmatrix}$
  3. $\begin{Bmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{pmatrix}, & \begin{pmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \\ 0 \end{pmatrix} \end{Bmatrix}$
  4. None of these

For the matrices $A = \begin{pmatrix} a & a \\ 0 & a \end{pmatrix}$ and $B = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$, $(B^{-1}AB)^3$ is equal to

  1. $\begin{pmatrix} a^3 & a^3 \\ 0 & a^3 \end{pmatrix}$
  2. $\begin{pmatrix} a^3 & 3a^3 \\ 0 & a^3 \end{pmatrix}$
  3. $\begin{pmatrix} a^3 & 0 \\ 3a^3 & a^3 \end{pmatrix}$
  4. $\begin{pmatrix} a^3 & 0 \\ -3a^3 & a^3 \end{pmatrix}$

Let $A=\begin{pmatrix} 1 & 1 & 0\\ 0 & a & b\\1 & 0 & 1 \end{pmatrix}$. Then $A^{-1}$ does not exist if $(a,b)$ is equal to

  1. $(1,-1)$
  2. $(1,0)$
  3. $(-1,-1)$
  4. $(0,1)$

An $n \times n$ matrix is said to be tridiagonal if its entries $a_{ij}$ are zero except when $|i−j| \leq 1$ for $1 \leq i, \: j \leq n$. Note that only $3n − 2$ entries of a tridiagonal matrix are non-zero. Thus, an array $L$ of size $3n − 2$ is sufficient to store a tridiagonal matrix. Given $i, j$, write pseudo-code to

  1. store $a_{ij}$ in $L$, and
  2. get the value of $a_{ij}$ stored earlier in $L$.

If $$f(x) = \begin{bmatrix} \cos x & -\sin x & 0 \\ \sin x & \cos x & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ then the value of $\big(f(x)\big)^2$ is

  1. $f(x)$
  2. $f(2x)$
  3. $2f(x)$
  4. None of these

A real $2 \times 2$ matrix $M$ such that $$M^2 = \begin{pmatrix} -1 & 0 \\ 0 & -1- \varepsilon \end{pmatrix}$$

  1. exists for all $\varepsilon > 0$
  2. does not exist for any $\varepsilon > 0$
  3. exists for some $\varepsilon > 0$
  4. none of the above is true

Let $$ A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 2  \\ 1 & 2 & 3 \end{pmatrix} \text{ and } B=\begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix}.$$ Then

  1. there exists a matrix $C$ such that $A=BC=CB$
  2. there is no matrix $C$ such that $A=BC$
  3. there exists a matrix $C$ such that $A=BC$, but $A \neq CB$
  4. there is no matrix $C$ such that $A=CB$

Let $A$ be a matrix such that:

$A=\begin{pmatrix} -1 & 2\\ 0 & -1 \end{pmatrix}$

and $B=A+A^2+A^3+\ldots +A^{50}$. Then which of the following is true?

  1. $B^{2}=I$
  2. $B^{2}=0$
  3. $B^{2}=B$
  4. None of the above

The diagonal elements of a square matrix $M$ are odd integers while the off-diagonals are even integers. Then

  1. $M$ must be singular
  2. $M$ must be nonsingular
  3. There is not enough information to decide the singularity of $M$
  4. $M$ must have a positive eigenvalue.

The number of ordered pairs $(X, Y)$, where $X$ and $Y$ are $n \times n$ real, matrices such that $XY-YX=I$ is

  1. $0$
  2. $1$
  3. $n$
  4. infinite
Consider a $n \times n$ matrix $A=I_n-\alpha\alpha^T$, where $I_n$ is the $n\times n$ identity matrix and $\alpha$ is an $n\times 1$ column vector such that $\alpha^T\alpha=1$.Show that $A^2=A$.

If $M$ is a $3 \times 3$ matrix such that $\begin{bmatrix} 0 & 1 & 2 \end{bmatrix}M=\begin{bmatrix}1 & 0 & 0 \end{bmatrix}$ and $\begin{bmatrix}3 & 4 & 5 \end{bmatrix} M = \begin{bmatrix}0 & 1 & 0 \end{bmatrix}$ then $\begin{bmatrix}6 & 7 & 8 \end{bmatrix}M$ is equal to

  1. $\begin{bmatrix}2 & 1 & -2 \end{bmatrix}$
  2. $\begin{bmatrix}0 & 0 & 1 \end{bmatrix}$
  3. $\begin{bmatrix} -1 & 2 & 0 \end{bmatrix}$
  4. $\begin{bmatrix} 9 & 10 & 8 \end{bmatrix}$

Let $A_{ij}$ denote the minors of an $n\times n$ matrix $A.$ What is the relationship  between $\mid A_{ij}\mid$ and $\mid A_{ji}\mid$?

  1. They are always equal.
  2. $\mid A_{ij}\mid=-\mid A_{ji}\mid$ if $i\neq j.$
  3. They are equal if $A$ is a symmetric matrix.
  4. If $\mid A_{ij}\mid=0$ then $\mid A_{ji}\mid=0.$

If $A$ is a $3 \times 3$ matrix satisfying $A^3 – A^2 +A-I= O$ (where $O$ is the zero matrix and $I$ is the identity matrix) then the value of $A^4$ is

  1. $A$
  2. $O$
  3. $I$
  4. none of these

Suppose $A$ and $B$ are orthogonal $n \times n$ matrices. Which of the following is also an orthogonal matrix? Assume that $O$ is the null matrix of order $n \times n$ and $I$ is the identity matrix of order $n$.

  1. $AB-BA$
  2. $\begin{pmatrix} A & O \\ O & B \end{pmatrix}$
  3. $\begin{pmatrix} A & I \\ I & B \end{pmatrix}$
  4. $A^2 – B^2$

The set of vectors constituting an orthogonal basis in $\mathbb{R}^{3}$ is

  1. $\begin{Bmatrix} \begin{pmatrix} 1\\ -1 \\0 \end{pmatrix}&,\begin{pmatrix} 1\\ 1 \\0 \end{pmatrix}&,\begin{pmatrix} 0\\ 0 \\ 1 \end{pmatrix} \end{Bmatrix}$
  2. $\begin{Bmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} \\0 \end{pmatrix}&,\begin{pmatrix} 0\\ 1 \\0 \end{pmatrix}&,\begin{pmatrix} 0\\ 0 \\ 1 \end{pmatrix} \end{Bmatrix}$
  3. $\begin{Bmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} \\0 \end{pmatrix}&,\begin{pmatrix} \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}} \\0 \end{pmatrix} \end{Bmatrix}$
  4. None of these

Suppose $A$ and $B$ are orthogonal $n\times n$ matrices. Which of the following is also an orthogonal matrix? Assume that $O$ is the null matrix of order $n\times n$ and $I$ is the identity matrix of order $n.$

  1. $AB-BA$
  2. $\begin{pmatrix} A & O \\ O & B \end{pmatrix}$
  3. $\begin{pmatrix} A & I \\ I & B \end{pmatrix}$
  4. $A^{2}-B^{2}$

Let $x_1, x_2, x_3, x_4, y_1, y_2, y_3$ and $y_4$ be fixed real numbers, not all of them equal to zero. Define a $4 \times 4$ matrix $\textbf{A}$ by

$$\textbf{A} = \begin{pmatrix} x_1^2+y_1^2 & x_1x_2 + y_1 y_2 & x_1x_3+y_1y_3 & x_1x_4+y_1y_4 \\ x_2x_1 + y_2 y_1 & x_2^2+y_2^2 & x_2x_3+y_2y_3 & x_2x_4+y_2y_4 \\ x_3x_1 + y_3 y_1 & x_3x_2+y_3y_2 & x_3^2+y_3^2 & x_3x_4+y_3y_4 \\ x_4x_1 + y_4 y_1 & x_4x_2+y_4y_2 & x_4x_3+y_4y_3 & x_4^2+y_4^2  \end{pmatrix}$$

Then rank$(\textbf{A})$ equals

  1. $1$ or $2$
  2. $0$
  3. $4$
  4. $2$ or $3$

Let $A$ be a square matrix such that $A^3 =0$, but $A^2 \neq 0$. Then which of the following statements is not necessarily true?

  1. $A \neq A^2$
  2. Eigenvalues of $A^2$ are all zero
  3. rank($A$) > rank($A^2$)
  4. rank($A$) > trace($A$)

Suppose the rank of the matrix

$$\begin{pmatrix}1&1&2&2\\1&1&1&3\\a&b&b&1\end{pmatrix}$$

is $2$ for some real numbers $a$ and $b$. Then $b$ equals

  1. $1$
  2. $3$
  3. $1/2$
  4. $1/3$

If $A$ is a $2 \times 2$ matrix such that trace $A = det \ A = 3,$ then what is the trace of $A^{-1}$?

  1. $1$
  2. $\left(\dfrac{1}{3}\right)$
  3. $\left(\dfrac{1}{6}\right)$
  4. $\left(\dfrac{1}{2}\right)$

The rank of the matrix

$\begin{bmatrix} 1 &2 &3 &4 \\ 5& 6 & 7 & 8 \\ 6 & 8 & 10 & 12 \\ 151 & 262 & 373 & 484 \end{bmatrix}$

  1. $1$
  2. $2$
  3. $3$
  4. $4$

Suppose that $A$ is a $3 \times 3$ real matrix such that for each $u=(u_1, u_2, u_3)’ \in \mathbb{R}^3, \: u’Au=0$ where $u’$ stands for the transpose of $u$. Then which one of the following is true?

  1. $A’=-A$
  2. $A’=A$
  3. $AA’=I$
  4. None of these

Let $A=\begin{pmatrix} -1 & 2 \\ 0 & -1 \end{pmatrix}$, and $B=A+A^2+A^3+ \dots +A^{50}$. Then

  1. $B^2 =1$
  2. $B^2 =0$
  3. $B^2 =A$
  4. $B^2 =B$

If $a,b,c$ and $d$ satisfy the equations

$$a+7b+3c+5d =16\\8a+4b+6c+2d = -16\\ 2a+6b+4c+8d = 16 \\ 5a+3b+7c+d= -16$$

Then $(a+d)(b+c)$ equals

  1. $-4$
  2. $0$
  3. $16$
  4. $-16$

The value of $\lambda$ such that the system of equation

$$\begin{array}{} 2x & – & y & + & 2z & = & 2 \\ x & – & 2y & + & z & = & -4 \\ x & + & y & + & \lambda z & = & 4 \end{array}$$ has no solution is

  1. $3$
  2. $1$
  3. $0$
  4. $-3$

The values of $\eta$ for which the following system of equations

$$\begin{array}  {} x & + & y & + & z & = & 1 \\ x & + & 2y & + & 4z & = & \eta \\ x & + & 4y & + & 10z & = & \eta ^2 \end{array}$$

has a solution are

  1. $\eta=1, -2$
  2. $\eta=-1, -2$
  3. $\eta=3, -3$
  4. $\eta=1, 2$

Let two systems of linear equations be defined as follows:

$\begin{array} {} & x+y & =1 \\ P: & 3x+3y & =3 \\ & 5x+5y & =5 \end{array}$ and $\begin{array} {} & x+y & =3 \\ Q: & 2x+2y & =4 \\ & 5x+5y & =12 \end{array}$. Then,

  1. $P$ and $Q$ are inconsistent
  2. $P$ and $Q$ are consistent
  3. $P$ is consistent but $Q$ is inconsistent
  4. None of the above

The values of $\eta$ for which the following system of equations

$$\begin{array} {} x & + & y & + & z & = & 1 \\ x & + & 2y & + & 4z & = & \eta \\ x & + & 4y & + & 10z & = & \eta ^2 \end{array}$$ has a solution are

  1. $\eta = 1, -2$
  2. $\eta = -1, -2$
  3. $\eta = 3, -3$
  4. $\eta = 1, 2$

Let $P_1$, $P_2$ and $P_3$ denote, respectively, the planes defined by

$$\begin{array} {} a_1x +b_1y+c_1z=\alpha _1 \\ a_2x +b_2y+c_2z=\alpha _2 \\ a_3x +b_3y+c_3z=\alpha _3 \end{array}$$

It is given that $P_1$, $P_2$ and $P_3$ intersect exactly at one point when $\alpha _1 = \alpha _2 =\alpha _3=1$. If now $\alpha _1 =2, \: \alpha _2=3, \: \alpha _3 = 4$ then the planes

  1. do not have any common point of intersection
  2. intersect at a unique point
  3. intersect along a straight line
  4. intersect along a plane

Let two systems of linear equations be defined as follows:

$\begin{array}{lll} &  x+y  & =1 \\  P: & 3x+3y & =3 \\ &  5x+5y & =5 \end{array}$ and $\begin{array}{lll} & x+y & =3 \\ Q: & 2x+2y & =4 \\  & 5x+5y & =12 \end{array}$. Then,

  1. $P$ and $Q$ are inconsistent
  2. $P$ and $Q$ are consistent
  3. $P$ is consistent but $Q$ is inconsistent
  4. None of the above

The $a, b, c$ and $d$ satisfy the equations

$$\begin{matrix} a & + & 7b & + & 3c & + & 5d & = &16 \\ 8a & + & 4b & + & 6c & + & 2d & = &-16 \\ 2a & + & 6b & + & 4c & + & 8d & = &16 \\  5a & + & 7b & + & 3c & + & 5d & = &-16  \end{matrix}$$

Then $(a+d)(b+c)$ equals

  1. $-4$
  2. $0$
  3. $16$
  4. $-16$

Consider following system of equations:

$\begin{bmatrix} 1 &2 &3 &4 \\ 5&6 &7 &8 \\ a&9 &b &10 \\ 6&8 &10 & 13 \end{bmatrix}$$\begin{bmatrix} x1\\ x2\\ x3\\ x4 \end{bmatrix}$=$\begin{bmatrix} 0\\ 0\\ 0\\ 0 \end{bmatrix}$

The locus of all $(a,b)\in\mathbb{R}^{2}$ such that this system has at least two distinct solution for ($x_{1},x_{2},x_{3},x_{4}$) is

  1. a parabola
  2. a straight line
  3. entire $\mathbb{R}^{2}$
  4. a point

If the system of equations

$\begin{array} \\ax +y+z= 0 \\ x+by +z = 0 \\ x+y + cz = 0 \end{array}$

with $a,b,c \neq 1$ has a non trivial solutions, the value of $$\frac{1}{1-a} + \frac{1}{1-b} + \frac{1}{1-c}$$ is

  1. $1$
  2. $-1$
  3. $3$
  4. $-3$

Let $\theta=2\pi/67$. Now consider the matrix $A = \begin{pmatrix} \cos \theta & \sin \theta \\ – \sin \theta & \cos \theta \end{pmatrix}$. Then the matrix $A^{2010}$ is

  1. $\begin{pmatrix} \cos \theta & \sin \theta \\ – \sin \theta & \cos \theta \end{pmatrix}$
  2. $\begin{pmatrix} 1& 0 \\ 0 & 1 \end{pmatrix}$
  3. $\begin{pmatrix} \cos^{30} \theta & \sin^{30} \theta \\ – \sin^{30} \theta & \cos^{30} \theta \end{pmatrix}$
  4. $\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$

If $f(x)=\begin{bmatrix}\cos\:x & -\sin\:x & 0 \\  \sin\:x & \cos\:x & 0 \\  0 & 0 & 1 \end{bmatrix}$ then the value of $\big(f(x)\big)^2$ is

  1. $f(x)$
  2. $f(2x)$
  3. $2f(x)$
  4. None of these

Let $C_{n}$ be the number of strings $w$ consisting of $n$ $X's$ and $n$ $Y's$ such that no initial segment of $w$ has more $Y's$ than $X's.$ Now consider the following problem. A person stands on the edge of a swimming pool holding a bag of $n$ red and $n$ blue balls. He draws a ball out one at a time and discards it. If he draws a blue ball, he takes one step back, if he draws a red ball, he moves one step forward. What is the probability that the person remains dry?

  1. $\frac{C_{n}}{2^{2n}}$
  2. $\frac{C_{n}}{\binom{2n}{n}}$
  3. $\frac{n\cdot C_{n}}{(2n)!}$
  4. $\frac{n\cdot C_{n}}{\binom{2n}{n}}$

A basket contains some white and blue marbles. Two marbles are drawn randomly from the basket without replacement. The probability of selecting first a white and then a blue marble is $0.2$. The probability of selecting a white marble in the first draw is $0.5$. What is the probability of selecting a blue marble in the second draw, given that the first marble drawn was white?

  1. $0.1$
  2. $0.4$
  3. $0.5$
  4. $0.2$

You are given two coins $A$ and $B$ that look identical. The probability that coin $A$ turns up heads is $\frac{1}{4}$, while the probability that coin $B$ turns up heads is $\frac{3}{4}.$ You choose one of the coins at random and toss it twice. If both the outcomes are heads, what is the probability that you chose coin $B?$

  1. $\frac{1}{16}$
  2. $\frac{1}{2}$
  3. $\frac{9}{16}$
  4. $\frac{9}{10}$

$10\%$ of all email you receive is spam. Your spam filter is $90\%$ reliable: that is, $90\%$ of the mails it marks as spam are indeed spam and $90\%$ of spam mails are correctly labeled as spam. If you see a mail marked spam by your filter, what is the probability that it really is spam?

  1. $10\%$
  2. $50\%$
  3. $70\%$
  4. $90\%$

Varsha lives alone and dislikes cooking, so she goes out for dinner every evening. She has two favourite restaurants, $\textit{Dosa Paradise}$ and $\textit{Kababs Unlimited}$, to which she travels by local train. The train to $\textit{Dosa Paradise}$ runs every $10$ minutes, at $0, 10, 20, 30, 40$ and $50$ minutes past the hour. The train to $\textit{Kababs Unlimited}$ runs every $20$ minutes, at $8, 28$ and $48$ minutes past the hour. She reaches the station at a random time between $7:15$ pm and $8.15$ pm and chooses between the two restaurants based on the next available train/ What is the probability that she ends up eating in $\textit{Kababs Unlimited}$?

  1. $\frac{1}{5}$
  2. $\frac{1}{3}$
  3. $\frac{2}{5}$
  4. $\frac{1}{2}$

There are $7$ switches on a switchboard, some of which are on and some of which are off. In one move, you pick any $2$ switches and toggle each of them-if the switch you pick is currently off, you turn it on, if it is on, you turn it off. Your aim is to execute a  sequence of moves and turn all $7$ switches on. For which of the following initial configurations is this not possible? Each configuration lists the initial positions of  the $7$ switches in sequence, from switch $1$ to switch $7.$

  1. (off,on,off,on,off,off,on)
  2. (off,on,on,on,on,on,off)
  3. (on,off,on,on,on,on,on)
  4. (off,off,off,off,off,on,off)

A determinant is chosen at random from the set of all determinants of order $2$ with elements $0$ or $1$ only. The probability of choosing a non-zero determinant is

  1. $\frac{3}{16}$
  2. $\frac{3}{8}$
  3. $\frac{1}{4}$
  4. none of these

A die is thrown thrice. If the first throw is a $4$ then the probability of getting $15$ as the sum of three throws is

  1. $\frac{1}{108}$
  2. $\frac{1}{6}$
  3. $\frac{1}{18}$
  4. none of these

Suppose you alternate between throwing a normal six-sided fair die and tossing a fair coin. You start by throwing the die. What is the probability that you will see a $5$ on the die before you see tails on the coin?

  1. $\frac{1}{12}$
  2. $\frac{1}{6}$
  3. $\frac{2}{9}$
  4. $\frac{2}{7}$

Two coins are tossed independently where $P$(head occurs when coin $i$ is tossed) $=p_i, \: i=1,2$. Given that at least one head has occurred, the probability that coins produced different outcomes is

  1. $\frac{2p_1p_2}{p_1+p_2-2p_1p_2}$
  2. $\frac{p_1+p_2-2p_1p_2}{p_1+p_2-p_1p_2}$
  3. $\frac{2}{3}$
  4. none of the above

If $A_1, A_2, \dots , A_n$ are independent events with probabilities $p_1, p_2, \dots , p_n$ respectively, then $P( \cup_{i=1}^n A_i)$ equals

  1. $\Sigma_{i=1}^n \: \: p_i$
  2. $\Pi_{i=1}^n \: \: p_i$
  3. $\Pi_{i=1}^n \: \: (1-p_i)$
  4. $1-\Pi_{i=1}^n \: \: (1-p_i)$

Let $A_1,A_2,A_3, \dots , A_n$ be $n$ independent events such that $P(A_i) = \frac{1}{i+1}$ for $i=1,2,3, \dots , n$. The probability that none of $A_1, A_2, A_3, \dots , A_n$ occurs is

  1. $\frac{n}{n+1}$
  2. $\frac{1}{n+1}$
  3. $\frac{n-1}{n+1}$
  4. none of these

If $P$ is an integer from $1$ to $50$, what is the probability that $P(P+1)$ is divisible by $4$?

  1. $0.25$
  2. $0.50$
  3. $0.48$
  4. none of these

The number of cars $(X)$ arriving at a service station per day follows a Poisson distribution with mean $4$. The service station can provide service to a maximum of $4$ cars per day. Then the expected number of cars that do not get service per day equals

  1. $4$
  2. $0$
  3. $\Sigma_{i=0}^{\infty} i P(X=i+4)$
  4. $\Sigma_{i=4}^{\infty} i P(X=i-4)$

Suppose $X$ is distributed as Poisson with mean $λ.$ Then $E(1/(X + 1))$ is

  1. $\frac{e^{\lambda }-1}{\lambda }$
  2. $\frac{e^{\lambda }-1}{\lambda +1}$
  3. $\frac{1-e^{-\lambda }}{\lambda}$
  4. $\frac{1-e^{-\lambda }}{\lambda + 1}$

Suppose $X$ and $Y$ are two independent random variables both following Poisson distribution with parameter $\lambda$. What is the value of $E(X-Y)^2$ ?

  1. $\lambda$
  2. $2 \lambda$
  3. $\lambda^2$
  4. $4 \lambda^2$

You have two normal, fair, dice, with faces labelled $1,2, \dots 6$. If you throw both dice, which of the following is true about the total value shown by the dice?

  1. The probability that the total is $6$ is less than the probability that the total is $9$.
  2. The probability that the total is $6$ is equal to the probability that the total is $9$.
  3. The probability that the total is $6$ is greater than the probability that the total is $9$.
  4. None of the above.

You have two six-sided cubic dice but they are numbered in a strange manner. On the first die, two opposite faces are numbered $1$, two opposite faces are numbered $3$ and the last pair of opposite faces are numbered $6$. On the second die, the three pairs of opposing faces are numbered $2$, $4$ and $5$. Both dice are fair: each side has an equal probability of coming face up when tossed. Which of the following statements is not true of this pair of unusual dice?

  1. The probability that the sum of the values shown by the dice is $5$ is the same as probability that the sum is $8$.
  2. The probability that the sum is odd is higher than the probability that the sum is even.
  3. The probability that the sum is strictly less than $7$ is the same as the probability that the sum is strictly greater than $7$.
  4. The probability that the sum is a multiple of $5$ is the same as the probability that the sum is a prime number.

You have a bag with $347$ black balls and $278$ white balls. Without looking, you pick up two balls from the bag and apply the following rule. If both balls are of the same colour, you throw them both away. Otherwise, you throw away the black ball and return the white ball to the bag. You keep repeating this process. If at some stage there is exactly one ball left in the bag, which of the following is true?

  1. The ball in the bag is definitely white.
  2. The ball in the bag is definitely black.
  3. Both colours are possible, but the probability of it being white is greater.
  4. Both colours are possible, but the probability of it being black is greater.

A man has three cats. At least one is male. What is the probability that all three are male?

  1. $\frac{1}{2}$
  2. $\frac{1}{7}$
  3. $\frac{1}{8}$
  4. $\frac{3}{8}$

The $12$ houses on one side of a street are numbered with even numbers starting at $2$ and going up to $24$. A free newspaper is delivered on Monday to $3$ different houses chosen at random from these $12$. Find the probability that at least $2$ of these newspapers are delivered to houses with numbers strictly greater than $14$.

  1. $\frac{7}{11}$
  2. $\frac{5}{12}$
  3. $\frac{4}{11}$
  4. $\frac{5}{22}$

You arrive at a snack bar and you can’t decide whether to order a lime juice or a lassi. You decide to throw a fair $6$-sided die to make the choice, as follows.

  • If you throw $2$ or $6$ you order a lime juice.
  • If you throw a $4$, you order a lassi.
  • Otherwise, you throw the die again and follow the same algorithm.

What is the probability that you end up ordering a lime juice?

  1. $\frac{1}{3}$
  2. $\frac{1}{2}$
  3. $\frac{2}{3}$
  4. $\frac{3}{4}$

An FM radio channel has a repository of $10$ songs. Each day, the channel plays $3$ distinct songs that are chosen randomly from the repository.

Mary decides to tune in to the radio channel on the weekend after her exams. What is the probability that no song gets repeated during these $2$ days?

  1. $\begin{pmatrix} 10\\ 3 \end{pmatrix}^{2}*\begin{pmatrix} 10\\ 6 \end{pmatrix}^{-1}$
  2. $\begin{pmatrix} 10\\ 6 \end{pmatrix}*\begin{pmatrix} 10\\ 3 \end{pmatrix}^{-2}$
  3. $\begin{pmatrix} 10\\ 3 \end{pmatrix}*\begin{pmatrix} 7\\ 3 \end{pmatrix}*\begin{pmatrix} 10\\ 3 \end{pmatrix}^{-2}$
  4. $\begin{pmatrix} 10\\ 3 \end{pmatrix}*\begin{pmatrix} 7\\ 3 \end{pmatrix}*\begin{pmatrix} 10\\ 6 \end{pmatrix}^{-1}$

Ravi asked his neighbor to water a delicate plant while he is away. Without water, the plant would die with probability 4/5 and with water it would die with probability 3/20. The probability that Ravi's neighbor would remember to water the plant is 9/10. If the plant actually died, what is the probability that Ravi's neighbor forgot to water the plant?

  1. 4/5
  2. 27/43
  3. 16/43
  4. 2/25

There are four machines and it is known that exactly two of them are faulty. They are tested one by one in a random order till both the faulty machines are identified. The probability that only two tests are required is

  1. $\left(\dfrac{1}{2}\right)$
  2. $\left(\dfrac{1}{3}\right)$
  3. $\left(\dfrac{1}{4}\right)$
  4. $\left(\dfrac{1}{6}\right)$

A box contains $5$ fair and $5$ biased coins. Each biased coin has a probability of head $\frac{4}{5}$. A coin is drawn at random from the box and tossed. Then the second coin is drawn at random from the box ( without replacing the first one). Given that the first coin has shown head, the conditional probability that the second coin is fair is

  1. $\frac{20}{39}\\$
  2. $\frac{20}{37}\\$
  3. $\frac{1}{2}\\$
  4. $\frac{7}{13}$

Let $X_1$, and $X_2$ and $X_3$ be chosen independently from the set $\{0, 1, 2, 3, 4\}$, each value being equally likely. What is the probability that the arithmetic mean of $X_1, X_2$ and $X_3$ is the same as their geometric mean?

  1. $\frac{1}{5^2}\\$
  2. $\frac{1}{5^3}\\$
  3. $\frac{3!}{5^3}\\$
  4. $\frac{3}{5^3}$

Consider a large village, where only two newspapers $P_1$ and $P_2$ are available to the families. It is known that the proportion of families

  1. not taking $P_1$ is $0.48$,
  2. not taking $P_2$ is $0.58$, 
  3. taking only $P_2$ is $0.30$.

The probability that a randomly chosen family from the village takes only $P_1$ is

  1. $0.24$
  2. $0.28$
  3. $0.40$
  4. can not be determined

There are eight coins, seven of which have the same weight and the other one weighs more. In order to find the coin having more weight, a person randomly chooses two coins and puts one coin on each side of a common balance. If these two coins are found to have the same weight, the person then randomly chooses two more coins from the rest and follows the same method as before. The probability that the coin will be identified at the second draw is

  1. $1/2$
  2. $1/3$
  3. $1/4$
  4. $1/6$

Let $A_1 = (0, 0), A_2 = (1, 0), A_3 = (1, 1)\ $and$\ A_4 = (0, 1)$ be the four vertices of a square. A particle starts from the point $A_1$ at time $0$ and moves either to $A_2$ or to $A_4$ with equal probability. Similarly, in each of the subsequent steps, it randomly chooses one of its adjacent vertices and moves there. Let $T$ be the minimum number of steps required to cover all four vertices. The probability $P(T = 4)$ is

  1. $0$
  2. $1/16$
  3. $1/8$
  4. $1/4$

Consider the set of all functions from $\{1, 2, . . . ,m\}$ to $\{1, 2, . . . , n\}$,where $n > m$. If a function is chosen from this set at random, the probability that it will be strictly increasing is

  1. $\binom{n}{m}/n^m\\$
  2. $\binom{n}{m}/m^n\\$
  3. $\binom{m+n-1}{m-1}/n^m\\$
  4. $\binom{m+n-1}{m}/m^n$

The chance of a student getting admitted to colleges $A$ and $B$ are $60\%$ and $40\%$, respectively. Assume that the colleges admit students independently. If the student is told that he has been admitted to at least one of these colleges, what is the probability that he has got admitted to college $A$?

  1. $3/5$
  2. $5/7$
  3. $10/13$
  4. $15/19$

A coin with probability $p (0 < p < 1)$ of getting head, is tossed until a head appears for the first time. If the probability that the number of tosses required is even is $2/5$, then the value of $p$ is

  1. $2/7$
  2. $1/3$
  3. $5/7$
  4. $2/3$

A permutation of $1,2, \dots, n$ is chosen at random. Then the probability that the numbers $1$ and $2$ appear as neighbour equals

  1. $\frac{1}{n}$
  2. $\frac{2}{n}$
  3. $\frac{1}{n-1}$
  4. $\frac{1}{n-2}$

Suppose that $X$ is chosen uniformly from $\{1,2,\ldots,100\}$ and given $X =x$, $Y$ is chosen uniformly from $\{1,2,\ldots,x\}. $Then $P(Y = 30)=$

  1. $\dfrac{1}{100}$
  2. $\dfrac{1}{100} \times \left(\dfrac{1}{30} + \ldots+\dfrac{1}{100}\right)$
  3. $\dfrac{1}{30}$
  4. $\dfrac{1}{100} \times \left(\dfrac{1}{1} + \ldots +\dfrac{1}{30}\right)$

Ball Mart has $10^7$ different items in stock across all its stores worldwide. The company has collected billing data for $10^{10}$ customer transactions. Each individual bill has at most $10$ distinct items in it. Ball Mart’s CEO wants to optimize the company’s inventory and has asked for a list of those items that appear in at least $2 \%$ of the billed transactions. Which of the following is the most precise upper bound one can compute for the number of such items, given the data?

  1. $500$
  2. $1000$
  3. $5000$
  4. $20000$

What are the possible values of $gcd(7p + 94,\: 7p^2 + 97p + 47)$, where $p$ is an arbitrary integer?

  1. Either $1$ or $94$
  2. Either $94$ or $47$
  3. Either $1$ or $47$
  4. None of these
A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more rotis.

Suppose the cook starts at the top with $R$ rupees. What are all the possible amounts of money she can have at the end?
A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more rotis.

Suppose the cook can hitch a quick ride from her stall downhill back to the kitchen uphill, by offering a paan to a truck driver. If she starts at the top with $P$ paans and $1$ rupee, what is the minimum and maximum amount of money she can have at the end?
Let $x=(x_1, x_2, \dots x_n) \in \{0,1\}^n$ By $H(x)$ we mean the number of 1's in $(x_1, x_2, \dots x_n)$. Prove that $H(x) = \frac{1}{2} (n-\Sigma^n_{i=1} (-1)^{x_i})$.
Let $A$ be a $30 \times 40$ matrix having $500$ non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column.

Show that there is a k such that $1 \leq k \leq 30$, $r_k \geq 17$ and there is an $l$ such that $1 \leq l \leq 40$, $m_l \leq 12$.

The inequality $\mid x^2 -5x+4 \mid > (x^2-5x+4)$ holds if and only if

  1. $1 < x < 4$
  2. $x \leq 1$ and $x \geq 4$
  3. $1 \leq x \leq 4$
  4. $x$ takes any value except $1$ and $4$

The digit in the unit's place of the number $2017^{2017}$ is

  1. $1$
  2. $3$
  3. $7$
  4. $9$

Which of the following statements is true?

  1. There are three consecutive integers with sum $2015$
  2. There are four consecutive integers with sum $2015$
  3. There are five consecutive integers with sum $2015$
  4. There are three consecutive integers with product $2015$

If $(x_1, y_1)$ and $(x_2, y_2)$ are the opposite end points of a diameter of a circle, then the equation of the circle is given by

  1. $(x-x_1)(y-y_1)+(x-x_2)(y-y_2)=0$
  2. $(x-x_1)(y-y_2)+(x-x_2)(y-y_1)=0$
  3. $(x-x_1)(x-x_2)+(y-y_1)(y-y_2)=0$
  4. $(x-x_1)(x-x_2)=(y-y_1)(y-y_2)=0$

What is the smallest degree of a polynomial with real coefficients and having root $2\omega , 2 + 3\omega , 2\omega^{2} , -1 -3\omega$ and $2-\omega - \omega^{2}?$ [Here $\omega\neq$1 is a cube root of unity.]

  1. $5$
  2. $7$
  3. $9$
  4. $10$

The number of polynomial function $f$ of degree $\geq$ 1 satisfying $f(x^{2})=(f(x))^{2}=f(f(x))$ for all real $x$, is

  1. $0$
  2. $1$
  3. $2$
  4. infinitely many

If $\alpha,\beta $ and $ \gamma$ are the roots of the equation $x^3+3x^2-8x+1=0$, then an equation whose roots are $\alpha +1 , \beta +1 , \gamma +1 $ is given by

  1. $y^3-11y+11=0$
  2. $y^3-11y-11=0$
  3. $y^3+13y+13=0$
  4. $y^3+6y^2+y-3=0$

The graph of a cubic polynomial $f(x)$ is shown below. If $k$ is a constant such that $f(x)=k$ has three real solutions, which of the following could be a possible value of $k$?

  1. $3$
  2. $0$
  3. $-7$
  4. $-3$

Let $n \geq 3$  be an integer.Then the statement  $$(n!)^{1/n} \leq \frac{n+1}{2}$$ is

  1. true for every $n \geq 3$
  2. true if and only if $n \geq 5$
  3. not true for $n \geq 10$
  4. true for even integers $n \geq 6$, not true for odd $n \geq 5$

The number of isosceles (but not equilateral) triangles with integer sides and no side exceeding $10$ is

  1. $65$
  2. $75$
  3. $81$
  4. $90$

The number of squares in the following figure is

$$\begin{array}{|c|c|c|c|}\hline \text{} & & & \\\hline \hline \text{} & & & \\\hline \hline \text{} & & & \\\hline \hline \text{} & & & \\\hline  \end{array}$$

  1. $25$
  2. $26$
  3. $29$
  4. $30$

The angle between the tangents drawn from the point $(1, 4)$ to the parabola $y^2 = 4x$ is

  1. $\pi /2$
  2. $\pi /3$
  3. $\pi /4$
  4. $\pi /6$

The $x$-axis divides the circle $x^2 + y^2 − 6x − 4y + 5 = 0$ into two parts. The area of the smaller part is

  1. $2\pi-1$
  2. $2(\pi-1)$
  3. $2\pi-3$
  4. $2(\pi-2)$

For $n\geq 1$, let

$a_n=\frac{1}{2^2} + \frac{2}{3^2}+ \dots +\frac{n}{(n+1)^2}$ and $b_n=c_0 + c_1r + c_2r^2 + \dots + c_nr^n$,where $\mid c_k \mid  \leq M$ for all integer $k$ and $\mid r \mid  <1$. Then

  1. both $\{a_n\}$ and $\{b_n\}$ are Cauchy sequences
  2. $\{a_n\}$ is a Cauchy sequence,and $\{b_n\}$ is not Cauchy sequence
  3. $\{a_n\}$ is not a Cauchy sequence,and $\{b_n\}$ is Cauchy sequence
  4. neither $\{a_n\}$ nor $\{b_n\}$ is a Cauchy sequence.

The sum of the infinite series $1+\frac{2}{3}+\frac{6}{3^2}+\frac{10}{3^3}+\frac{14}{3^4}+\dots $ is

  1. $2$
  2. $3$
  3. $4$
  4. $6$

Number of real solutions of the equation $x^7 + 2x^5 + 3x^3 + 4x = 2018$ is

  1. $1$
  2. $3$
  3. $5$
  4. $7$

The number of common terms in  the two sequences $\{ 3,7,11, \ldots , 407\}$ and $\{2,9,16,\ldots ,709\}$ is

  1. $13$
  2. $14$
  3. $15$
  4. $16$

One needs to choose six real numbers $x_1, x_2, . . . , x_6$ such that the product of any five of them is equal to other number. The number of such choices is

  1. $3$
  2. $33$
  3. $63$
  4. $93$

The volume of the region $S=\{(x,y,z) : \mid x \mid +\mid y \mid + \mid z \mid \leq 1\}$ is

  1. $\frac{1}{6}\\$
  2. $\frac{1}{3}\\$
  3. $\frac{2}{3}\\$
  4. $\frac{4}{3}$

The greatest common divisor of all numbers of the form $p^2 − 1$, where $p \geq 7$ is a prime, is

  1. $6$
  2. $12$
  3. $24$
  4. $48$

Let $a$ and $b$ be two positive integers such that $a = k_1b + r_1$ and $b = k_2r_1 + r_2,$ where $k_1,k_2,r_1,r_2$ are positive integers with $r_2 < r_1 < b$ Then $\text{gcd}(a, b)$ is same as

  1. $\text{gcd}(r_1,r_2)$
  2. $\text{gcd}(k_1,k_2)$
  3. $\text{gcd}(k_1,r_2)$
  4. $\text{gcd}(r_1,k_2)$

If $\alpha$ is a root of $x^2-x+1$, then $\alpha^{2018} + \alpha^{-2018}$ is

  1. $-1$
  2. $0$
  3. $1$
  4. $2$
Let $n,r\ $and$\ s$ be positive integers, each greater than $2$.Prove that $n^r-1$ divides $n^s-1$ if and only if $r$ divides $s$.

The highest power of $7$ that divides $100!$ is : 

  1. $14$
  2. $15$
  3. $16$
  4. $18$

How many triplets of real numbers $(x,y,z)$ are simultaneous solutions of the equations $x+y=2$ and $xy-z^2=1$?

  1. $0$
  2. $1$
  3. $2$
  4. infinitely many

Given a positive integer $m$, we define $f(m)$ as the highest power of $2$ that divides $m$. If $n$ is a prime number greater than $3$, then

  1. $f(n^3-1) = f(n-1)$
  2. $f(n^3-1) = f(n-1) +1$
  3. $f(n^3-1) = 2f(n-1)$
  4. None of the above is necessarily true

If $t = \begin{pmatrix} 200 \\ 100 \end{pmatrix}/4^{100} $, then

  1. $t < \frac{1}{3}$
  2. $\frac{1}{3} < t < \frac{1}{2}$
  3. $\frac{1}{2} < t < \frac{2}{3}$
  4. $\frac{2}{3} < t < 1$

The sum of all $3$ digit numbers that leave a remainder of $2$ when divided by $3$ is:

  1. $189700$
  2. $164850$
  3. $164750$
  4. $149700$

The shaded region in the following diagram represents the relation

  1. $y \leq x$
  2. $\mid y \mid \leq \mid x \mid$
  3. $y \leq \mid x \mid$
  4. $\mid y \mid \leq x$

The set $\{(x,y): \mid x \mid + \mid y \mid \leq 1\}$ is represented by the shaded region in

 

The area of the shaded region in the following figure (all the arcs are circular) is

  1. $\pi$
  2. $2 \pi$
  3. $3 \pi$
  4. $\frac{9}{8} \pi$

The area (in square unit) of the portion enclosed by the curve $\sqrt{2x}+ \sqrt{2y} = 2 \sqrt{3}$ and the axes of reference is

  1. $2$
  2. $4$
  3. $6$
  4. $8$

If the sum of the first $n$ terms of an arithmetic progression is $cn^2$, then the sum of squares of these $n$ terms is

  1. $\frac{n(4n^2-1)c^2}{6}$
  2. $\frac{n(4n^2+1)c^2}{3}$
  3. $\frac{n(4n^2-1)c^2}{3}$
  4. $\frac{n(4n^2+1)c^2}{6}$

If $a,b,c$ are in $A.P.$ , then the straight line $ax+by+c=0$ will always pass through the point whose coordinates are

  1. $(1,-2)$
  2. $(1,2)$
  3. $(-1,2)$
  4. $(-1,-2)$

If the co-efficient of $p^{th}, (p+1)^{th}$ and $(p+2)^{th}$ terms in the expansion of $(1+x)^n$ are in Arithmetic Progression (A.P.), then which one of the following is true?

  1. $n^2+4(4p+1)+4p^2-2=0$
  2. $n^2+4(4p+1)+4p^2+2=0$
  3. $(n-2p)^2=n+2$
  4. $(n+2p)^2=n+2$

The value of $(1.1)^{10}$ correct to $4$ decimal places is

  1. $2.4512$
  2. $1.9547$
  3. $2.5937$
  4. $1.4512$
Consider six distinct points in a plane. Let $m$ and $M$ denote the minimum and maximum distance between any pair of points. Show that $M/m \geq \sqrt{3}$.

The area of the largest square that can be drawn inside a circle with unit radius is

  1. $\sqrt{2}$
  2. $2$
  3. $1$
  4. None of the above

The equation of any circle passing through the origin and with its centre on the $X$-axis is given by

  1. $x^2+y^2-2ax=0$ where $a$ must be positive
  2. $x^2+y^2-2ax=0$ for any given $a \in \mathbb{R}$
  3. $x^2+y^2-2by=0$ where $b$ must be positive
  4. $x^2+y^2-2by=0$ for any given $b \in \mathbb{R}$

The angle between the tangents drawn from the point $(-1, 7)$ to the circle $x^2+y^2=25$  is

  1. $\tan^{-1} (\frac{1}{2})$
  2. $\tan^{-1} (\frac{2}{3})$
  3. $\frac{\pi}{2}$
  4. $\frac{\pi}{3}$

The coefficient of $x^2$ in the product $(1+x)(1+2x)(1+3x) \dots (1+10x)$ is

  1. $1320$
  2. $1420$
  3. $1120$
  4. None of these

Consider the following system of equivalences of integers,

$$x \equiv 2 \text{ mod } 15$$

$$x \equiv 4 \text{ mod } 21$$

The number of solutions in $x$, where $1 \leq x \leq 315$, to the above system of equivalences is

  1. $0$
  2. $1$
  3. $2$
  4. $3$

The series $\sum_{k=2}^{\infty} \frac{1}{k(k-1)}$ converges to

  1. $-1$
  2. $1$
  3. $0$
  4. does not converge

The condition that ensures that the roots of the equation $x^3-px^2+qx-r=0$ are in $H.P.$ is

  1. $r^2-9pqr+q^3=0$
  2. $27r^2-9pqr+3q^3=0$
  3. $3r^3-27pqr-9q^3=0$
  4. $27r^2-9pqr+2q^3=0$

If $\alpha, \beta$ and $\gamma$ are the roots of the equation $x^3+3x^2-8x+1=0$, then an equation whose roots are $\alpha+1, \beta+1$ and $\gamma+1$ is given by 

  1. $y^3-11y+11=0$
  2. $y^3-11y-11=0$
  3. $y^3+13y+13=0$
  4. $y^3+6y^2+y-3=0$
Suppose all the roots of the equation $x^3 +bx-2017=0$ (where $b$ is a real number) are real. Prove that exactly one root is positive.

The number of divisors of $6000$, where $1$ and $6000$ are also considered as divisors of $6000$ is

  1. $40$
  2. $50$
  3. $60$
  4. $30$ 

Let $n \geq 3$ be an integer. Then the statement $(n!)^{1/n} \leq \dfrac{n+1}{2}$ is

  1. true for every $n \geq 3$
  2. true if and only if $n \geq 5$
  3. not true for $n \geq 10$
  4. true for even integers $n \geq 6$, not true for odd $n \geq 5$

The number of ways in which the number $1440$ can be expressed as a product of two factors is equal to

  1. $18$
  2. $720$
  3. $360$
  4. $36$

The total number of factors of $3528$ greater than $1$ but less than $3528$ is

  1. $35$
  2. $36$
  3. $34$
  4. None of these

The total number of factors of $3528$ greater than $1$ but less than $3528$ is

  1. $35$
  2. $36$
  3. $34$
  4. None of these

Let $x_1$ and $x_2$ be the roots of the quadratic equation $x^2-3x+a=0$, and $x_3$ and $x_4$ be the roots of the quadratic equation $x^2-12x+b=0$. If $x_1, x_2, x_3$ and $x_4 \: (0 < x_1 < x_2 < x_3 < x_4)$ are in $G.P.,$ then $ab$ equals

  1. $64$
  2. $5184$
  3. $-64$
  4. $-5184$ 

Let $M$ be the maximum number of unit disks (disks of radius $1$) that can be placed inside a disk of radius $10$ so that each unit disk lies entirely within the larger disk and no two unit disks overlap. Then:

  1. $M < 25$
  2. $25 \leq M < 40$
  3. $40 \leq M < 55$
  4. $M \geq 55$
The vertices of a triangle $T$ are given. For an arbitrary point $P$ in the plane, give an algorithm to test if $P$ belongs to the interior of $T$. (The interior of $T$ does not include its edges).

Four squares of sides $x\: cm$ each are cut off from the four corners of a square metal sheet  having side $10\: cm.$ The residual sheet is then folded into an open box which is then filled with a liquid costing Rs. $x^{2}$ per $cm^{3}.$ The value of $x$ for which the cost of filling the box completely with the liquid is maximized, is

  1. $100$
  2. $50$
  3. $30$
  4. $10$

For natural numbers $n,$ the inequality $2^{n}>2n+1$ is valid when

  1. $n\geq 3$
  2. $n<3$
  3. $n=3$
  4. None of these

Let $S=\{6,10,7,13,5,12,8,11,9\},$ and $a=\sum_{x\in S}(x-9)^{2}\:\&\: b=\sum_{x\in S}(x-10)^{2}.$ Then

  1. $a<b$
  2. $a>b$
  3. $a=b$
  4. None of these

Let $0.01^x+0.25^x=0.7$ . Then

  1. $x\geq1$
  2. $0\lt x\lt1$
  3. $x\leq0$
  4. no such real number $x$ is possible.

The number of integer solutions for the equation $x^2+y^2=2011$ is

  1. $0$
  2. $1$
  3. $2$
  4. $3$

The area of the region formed by line segments joining the points of intersection of the circle $x^2+y^2-10x-6y+9=0$ with the two axes in succession in a definite order (clockwise or anticlockwise) is

  1. $16$
  2. $9$
  3. $3$
  4. $12$

The number of solutions of $\tan^{-1}(x-1) + \tan^{-1}(x) + \tan^{-1}(x+1) = \tan^{-1}(3x)$ is

  1. $1$
  2. $2$
  3. $3$
  4. $4$

Let $x_1 > x_2>0$. Then which of the following is true?

  1. $\log \big(\frac{x_1+x_2}{2}\big) > \frac{\log x_1+ \log x_2}{2}$
  2. $\log \big(\frac{x_1+x_2}{2}\big) < \frac{\log x_1+ \log x_2}{2}$
  3. There exist $x_1$ and $x_2$ such that $x_1 > x_2 >0$ and $\log \big(\frac{x_1+x_2}{2}\big) = \frac{\log x_1+ \log x_2}{2}$
  4. None of these

Let $y=[\:\log_{10}3245.7\:]$ where $[ a ]$ denotes the greatest integer less than or equal to $a$. Then

  1. $y=0$
  2. $y=1$
  3. $y=2$
  4. $y=3$

The value of $\log _2 e – \log _4 e + \log _8 e – \log _{16} e + \log_{32} e – \cdots$ is

  1. $-1$
  2. $0$
  3. $1$
  4. None of these

The sequence $\dfrac{1}{\log_{3} 2},\dfrac{1}{\log_{6} 2},\dfrac{1}{\log_{12} 2},\dfrac{1}{\log_{24} 2}\cdots$ is in

  1. Arithmetic progression (AP)
  2. Geometric progression (GP)
  3. Harmonic progression (HP)
  4. None of these

The value of $\log_{2}e-\log_{4}e+\log_{8}e-\log_{16}e+\log_{32}e-\cdots\:\:$ is

  1. $-1$
  2. $0$
  3. $1$
  4. None of these

The value of $\dfrac{1}{\log_2 n}+ \dfrac{1}{\log_3 n}+\dfrac{1}{\log_4 n}+ \dots + \dfrac{1}{\log_{2017} n}\:\:($ where $n=2017!)$ is

  1. $1$
  2. $2$
  3. $2017$
  4. none of these

The solution of $\log_5(\sqrt{x+5}+\sqrt{x})=1$ is

  1. $2$
  2. $4$
  3. $5$
  4. none of these

Lavanya has to complete $12$ courses for her degree. There are six compulsory courses: Basic and Advanced Mathematics, Basic and Advanced Physics and Basic and Advanced Electronics. She also has to complete six Optional Courses. Each course takes one semester to complete. There are some constraints because of prerequisites.

  • For Mathematics, Physics and Electronics, the Basic course must be completed before starting the Advanced course.
  • Advanced Physics must be completed before starting Basic Electronics.
  • Advanced Mathematics must be completed before starting Advanced Physics.
  • The Optional Courses can be done in any order, but no more than two Optional Courses can be taken in a semester

Given these constraints, what is the minimum number of semesters that Lavanya needs to complete her course requirements.

  1. $3$
  2. $4$
  3. $5$
  4. $6$

A valuable sword belonging to the Grand King was stolen, and the three suspects were Ibn, Hasan, and Abu. Ibn claimed that Hasan stole it, and Hasan claimed that Abu stole it. It was not clear that one of them stole it, but it was later learnt that no innocent person had lied. It was also learnt that the sword was stolen by only one person.
Who stole the sword?

  1. Ibn
  2. Hasan
  3. Abu
  4. None of them

Amma baked a cake and left it on the table to cool. Before going for her bath, she told her four children that they should not touch the cake as it was to be cut only the next day. However when she got back from her bath she found that someone had eaten a large piece of the cake. Since only her four children were present at home when this happened, she questioned them about who ate a piece of the cake. The four answers she got were:

  • Lakshmi: Aruna ate the piece of cake.
  • Ram: I did not eat the piece of cake.
  • Aruna: Varun ate the cake.
  • Varun: Aruna lied when she said I had eaten the piece of cake.

If exactly one of them was telling the truth and exactly one of them actually ate the piece of cake, who is the culprit that Amma is going to punish?

  1. Lakshmi
  2. Ram
  3. Aruna
  4. Varun

A company is due to send a shipment to a client and the CEO has resigned. To select a new CEO, some candidates have been interviewed. One of them will be chosen through a vote. If the workers union resort to a strike and the candidates have to be interviewed again, then the shipment deadline will be missed. If there are more abstainers than voters in the vote to choose the new CEO, then the candidates have to be interviewed again. Suppose that the shipment was sent on time. Which of the following is a valid conclusion?

  1. The workers union did not resort to a strike.
  2. The number of voters was more than the number of abstainers.
  3. (A) or (B).
  4. If the workers union resorted to a strike, then the number of voters was greater than or equal to the number of abstainers.

Avinash is taller than Abhay. Bharat is taller than Vinu and Vinay is taller than Bharat. Which of the following is a minimal set of additional information that can determine the tallest person?

  1. Vinay is taller than Avinash and Abhay is taller than Bharat.
  2. Avinash is taller than Vinay.
  3. Abhay is shorter than Vinay.
  4. None of the above.
Let there be a pile of $2018$ chips in the center of a table. Suppose there are two players who could alternately remove one, two or three chips from the pile. At least one chip must be removed, but no more than three chips can be removed in a single move. The player that removes the last chip wins. Does the first player (the player who starts playing the game) have a winning strategy in this game, that is, whatever moves his opponent makes, he can always make his moves in a certain way ensuring his win? Justify your answer.

In a triangle $ABC$, $AD$ is the median. If length of $AB$ is $7$, length of $AC$ is $15$ and length of $BC$ is $10$ then length of $AD$ equals

  1. $\sqrt{125}$
  2. $69/5$
  3. $\sqrt{112}$
  4. $\sqrt{864}/5$

The medians $AD$ and $BE$ of the triangle with vertices $A(0,b)$, $B(0,0)$ and $C(a,0)$ are mutually perpendicular if

  1. $b=\sqrt{2}a$
  2. $b=\pm \sqrt{2}b$
  3. $b= – \sqrt{2}a$
  4. $b=a$

If $a,b$ are positive real variables whose sum is a constant $\lambda$, then the minimum value of $\sqrt{(1+1/a)(1+1/b)}$ is

  1. $\lambda \: – 1/\lambda$
  2. $\lambda + 2/\lambda$
  3. $\lambda+1/\lambda$
  4. None of the above

The smallest integer $n$ for which $1+2+2^2+2^3+2^4+ \cdots +2^n$ exceeds $9999$, given that $\log_{10} 2=0.30103$, is

  1. $12$
  2. $13$
  3. $14$
  4. None of these

The symbol $\mid$ reads as "divides", and $\nmid$ as "does not divide". For instance, $2 \: \mid \:6$ and $2 \: \nmid \: 5$ are both true. Consider the following statements.

  1. There exists a positive integer $a$ such that $(2 \mid (a^3 -1))$ and $( 2 \mid a)$.
  2. There exists a positive integer $b$ such that $6 \nmid (b^3 -b)$.

What can you say about these statements?

  1. Only i is true
  2. Only ii is true
  3. Both i and ii are true
  4. Neither i nor ii is true

For all the natural number $n \geq 3, \: n^2+1$ is

  1. divisible by $3$
  2. not divisible by $3$
  3. divisible by $9$
  4. None of these

For natural numbers $n$, the inequality $2^n >2n+1$ is valid when

  1. $n \geq 3$
  2. $n < 3$
  3. $n=3$
  4. None of these

The expression $3^{2n+1} + 2^{n+2}$ is divisible by $7$ for

  1. all positive integer values of $n$
  2. all non-negative integer values of $n$
  3. only even integer values of $n$
  4. only odd integer values of $n$

The set $\{x \: : \begin{vmatrix} x+\frac{1}{x} \end{vmatrix} \gt6 \}$ equals the set

  1. $(0,3-2\sqrt{2}) \cup (3+2\sqrt{2}, \infty)$
  2. $(- \infty, -3-2\sqrt{2}) \cup (-3+2 \sqrt{2}, \infty)$
  3. $(- \infty, 3-2\sqrt{2}) \cup (3+2\sqrt{2}, \infty)$
  4. $(- \infty, -3-2\sqrt{2}) \cup (-3+2 \sqrt{2},3-2\sqrt{2}) \cup (3+2 \sqrt{2}, \infty )$

Let $x$ be a positive real number. Then

  1. $x^2+\pi ^2 + x^{2 \pi} > x \pi+ (\pi + x) x^{\pi}$
  2. $x^{\pi}+\pi^x > x^{2 \pi} + \pi ^{2x}$
  3. $\pi x +(\pi+x)x^{\pi} > x^2+\pi ^2 + x^{2 \pi}$
  4. none of the above

The value of $(1.1)^{10}$ correct to $4$ decimal places is

  1. $2.4512$
  2. $1.9547$
  3. $2.5937$
  4. $1.4512$

The coefficient of $x^{2}$ in the product $(1+x)(1+2x)(1+3x)\cdots (1+10x)$ is

  1. $1320$
  2. $1420$
  3. $1120$
  4. None of these

Suppose there are $n$ positive real numbers such that their sum is 20 and the product is strictly greater than 1. What is the maximum possible value of n?

  1. 18
  2. 19
  3. 20
  4. 21

The number of positive integers $n$ for which $n^2 +96$ is a perfect square

  1. $0$
  2. $1$
  3. $2$
  4. $4$

The number of positive integers $n$ for which $n^3 +(n+1)^3 +(n+2)^3 = (n+3)^3$ is

  1. $0$
  2. $1$
  3. $2$
  4. $3$
Let $a, b, c$ and $d$ be real numbers such that $a+b=c+d$ and $ab=cd$. Prove that $a^n+b^n=c^n+d^n$ for all positive integers $n$.

For integer values of $n$, the expression $\frac{n(5n + 1)(10n + 1)}{6}$

  1. Is always divisible by $5$.
  2. Is always divisible by $3$.
  3. Is always an integer.
  4. None of the above

The number of parallelograms that can be formed from a set of four parallel lines intersecting another set of three parallel lines is

  1. $6$
  2. $9$
  3. $12$
  4. $18$

In a certain town, $20\%$ families own a car, $90\%$ own a phone, $5 \%$ own neither a car nor a phone and $30, 000$ families own both a car and a phone. Consider the following statements in this regard:

  1. $10 \%$ families own both a car and a phone.
  2. $95 \%$ families own either a car or a phone.
  3. $2, 00, 000$ families live in the town.

Then which one of the following is true?

  1. (i) & (ii) are correct and (iii) is wrong.
  2. (i) & (iii) are correct and (ii) is wrong.
  3. (ii) & (iii) are correct and (i) is wrong.
  4. (i), (ii) & (iii) are correct.

A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest number of pieces of fruit that should be put in the basket in order to guarantee that either there are at least $8$ apples or at least $6$ bananas or at least $9$ oranges?

  1. $9$
  2. $10$
  3. $20$
  4. $21$
There are $n$ students in a class. The students have formed $k$ committees. Each committee consists of more than half of the students. Show that there is at least one student who is a member of more than half of the committees.
A group of $15$ boys plucked a total of $100$ apples. Prove that two of those boys plucked the same number of apples.
Prove that in any sequence of $105$ integers, there will always be a subsequence of consecutive elements in the sequence, whose sum is divisible by $99$.

Consider the polynomial  $x^5+ax^4+bx^3+cx^2+dx+4$ where $a,b,c,d$ are real numbers. If $(1+2i)$ and $(3-2i)$ are two two roots of this polynomial then the value of $a$ is

  1. $-524/65$
  2. $524/65$
  3. $-1/65$
  4. $1/65$

If $l=1+a+a^2+ \dots$, $m=1+b+b^2+ \dots$, and $n=1+c+c^2+ \dots$, where $\mid a \mid <1, \: \mid b \mid < 1, \: \mid c \mid <1$ and $a,b,c$ are in arithmetic progression, then $l, m, n$ are in

  1. arithmetic progression
  2. geometric progression
  3. harmonic progression
  4. none of these

The sequence $\dfrac{1}{\log_3 2}, \: \dfrac{1}{\log_6 2}, \: \dfrac{1}{\log_{12} 2}, \: \dfrac{1}{\log_{24} 2} \dots $ is in

  1. Arithmetic progression (AP)
  2. Geometric progression ( GP)
  3. Harmonic progression (HP)
  4. None of these