Toggle navigation
Mathematics
SAT
JEE
IMO
Vocabulary
Algorithms
Sign In
Shiva Kintali
member since:
May 7, 2012
About:
Founder & CEO of TrueShelf. Entrepreneur, Mathematician, Advisor, Investor, Cyclist. Visit
shivakintali.org
for more details.
0
articles
156
exercises
0
Undergraduate
By
Shiva Kintali
on June 13, 2012 | Updated Jan. 16, 2017
Corrupted linked-list
You are given a pointer to the head of singly linked list. Usually, each node in the list only has a pointer to the next element, and the last node’s pointer is NULL. Unfortunately, your list might ha…
Computer Science
Puzzles
Algorithms
Puzzles
linked list
0
High School
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Find the faulty Ball
There are 12 balls. They all look alike but one of them is faulty; it weights differently. It is not known, if this ball is heavier or lighter than the other balls. How do you find the faulty ball by …
Puzzles
Puzzles
counting
interview question
0
Graduate
By
Shiva Kintali
on May 7, 2012 | Updated Jan. 16, 2017
Graph Isomorphism, BPP and RP
The Graph Isomorphism Problem is to determine whether two given graphs are isomorphic to each other. Prove that if Graph Isomorphism is in BPP then it is in RP.
Computer Science
Complexity Theory
graph isomorphism
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Regular bipartite super-graph
Let \(G\) be a simple bipartite graph where each side of the bi-partition has size \(n\). The maximum degree of \(G\) is \(\Delta \le n/10\). Show that there exists a \(2 \Delta\)-regular simple bip…
Computer Science
Mathematics
Algorithms
Graph Theory
bipartite graph
graph algorithms
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Basics of decidability
State whether each of the following statements are TRUE or FALSE. Your answers should be accompanied by a proof. Every recognizable set has a decidable subset. Any subset of a recognizable language …
Computer Science
Complexity Theory
basics
true or false
undecidability
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Graphs with large min-degree
Let \(G\) be a graph in which every vertex has degree \(\geq 3\). Show that \(G\) contains a cycle of even length. Let \(G\) be a simple undirected graph in which every vertex has degree \(\ge k\). …
Mathematics
Graph Theory
cycle
path
0
Undergraduate
By
Shiva Kintali
on Oct. 20, 2012 | Updated Jan. 16, 2017
Randomly built binary search tree
A randomly built binary search tree on \(n\) keys is built by inserting the keys in random order into an initially empty tree, where each of the \(n!\) permutations of the input keys is equally likely…
Computer Science
Algorithms
data structures
0
Undergraduate
By
Shiva Kintali
on June 9, 2012 | Updated Jan. 16, 2017
Linear inequalities satisfied with equality
Let \(Ax \leq b\) be a system of linear inequalities. Describe a linear program to determine which inequalities among \(Ax \leq b\) are always satisfied with equality.
Optimization
Linear Programming
optimization
0
Graduate
By
Shiva Kintali
on Oct. 12, 2012 | Updated Jan. 16, 2017
Guess the average
Consider the following one-shot game : Each of \(n\) people announces a number in the set \({1,2,\dots,K}\). A prize of \(\\)1{,}000…
Mathematics
Game Theory
nash equilibrium
0
Undergraduate
By
Shiva Kintali
on June 13, 2012 | Updated Jan. 16, 2017
Basics of Pigeonhole Principle
Prove the following : Given \(n\) integers, some nonempty subset of them has sum divisible by \(n\). Let \(A\) be a set of \(n+1\) integers from {\({1, 2,\dots , 2n}\)}. Prove that some element of \…
Mathematics
Discrete Mathematics
basics
counting
pigeonhole principle
0
Undergraduate
By
Shiva Kintali
on May 31, 2013 | Updated Jan. 16, 2017
Characterizations of Eulerian graphs
It is well-known that a graph is Eulerian if and only if every vertex has even degree. Prove the following alternate characterization of Eulerian graphs Prove that if \(G\) is Eulerian and …
Mathematics
Graph Theory
eulerian graph
0
Undergraduate
By
Shiva Kintali
on June 26, 2012 | Updated Jan. 16, 2017
Complete balanced binary trees are graceful
Label the vertices of a tree (with \(n\) vertices) with integers from \(1\) to \(n\). Now label each edge with the absolute difference of the labels of its incident vertices. The labeling is said to b…
Mathematics
Graph Theory
graph labeling
0
Graduate
By
Shiva Kintali
on June 9, 2012 | Updated Jan. 16, 2017
Minimum edge cover vs Maximum matching
An edge cover of a graph \(G(V,E)\) is a subset \(F \subseteq E\) of edges such that every node is incident to at least one edge in \(F\). Show that a minimum cardinality edge cover can be determine…
Mathematics
Optimization
Graph Theory
Linear Programming
edge cover
matching
reduction
0
Undergraduate
By
Shiva Kintali
on June 7, 2012 | Updated Jan. 16, 2017
Caterpillars are Graceful
Graceful Labeling : Label the vertices of a simple undirected graph \(G(V,E)\) (where \(|V| = n\) and \(|E| = m\)) with integers from \(0\) to \(m\). Now label each edge with the absolute difference o…
Mathematics
Graph Theory
graph labeling
0
Undergraduate
By
Shiva Kintali
on Oct. 20, 2012 | Updated Jan. 16, 2017
Longest increasing subsequence
Give an \(O(n{\log}n)\) time algorithm to find the longest monotonically increasing subsequence of a sequence of \(n\) numbers.
Computer Science
Algorithms
dynamic programming
0
Graduate
By
Shiva Kintali
on Sept. 23, 2012 | Updated Jan. 16, 2017
Characterizing factor-critical graphs
A graph \(G\) is said to be factor-critical if \(G-v\) has perfect matching for every \(v \in V(G)\). Prove that no bipartite is factor-critical. Show that \(G\) is factor-critical if and only if …
Mathematics
Graph Theory
bipartite graph
matching
0
Graduate
By
Shiva Kintali
on June 7, 2012 | Updated Jan. 16, 2017
Fixed-parameter tractability of Vertex Cover
Let \(G(V,E)\) be an undirected graph. A subset \(S \subseteq V\) is a vertex cover of \(G\) if every edge has at least one end point in \(V\). Design an \(O(|V|{\cdot}k + k^2{2^k})\) time algorithm t…
Computer Science
Algorithms
fpt algorithms
vertex cover
0
High School
By
Shiva Kintali
on June 28, 2012 | Updated Jan. 16, 2017
Integral Rectangles
A large rectangle is partitioned into smaller rectangles, each of which has either integer height or integer width or both. Prove that the large rectangle also has this property.
Mathematics
Puzzles
Geometry
Puzzles
interview question
math puzzle
0
Graduate
By
Shiva Kintali
on Aug. 8, 2012 | Updated Jan. 16, 2017
Gallai Identities
Consider the following parameters of an undirected graph \(G\) on \(n\) vertices. \(\nu(G)\) is the size of a maximum matching of \(G\). \(\tau(G)\) is the size of a minimum vertex cover of \(G\). …
Mathematics
Graph Theory
edge cover
independent set
matching
vertex cover
0
Undergraduate
By
Shiva Kintali
on June 7, 2012 | Updated Jan. 16, 2017
Number of edges in a quasi-planar graph
A graph \(G(V,E)\) is called quasi-planar if it can be drawn in the plane with no three pairwise crossing edges. Prove that a quasi-planar graph with \(|V| = n\) vertices has at most \(O(n^{3/2})\) ed…
Mathematics
Graph Theory
planar graphs
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Basics of countability
Prove that every collection of disjoint intervals (of positive length) on the real line is countable.
Mathematics
Real Analysis
basics
counting
0
Undergraduate
By
Shiva Kintali
on June 12, 2012 | Updated Jan. 16, 2017
Subset Sum vs Partition
Consider the following problems : Partition problem : Given a collection of \(n\) integers \(a_1, a_2, \ldots, a_n\), is there a subset \(I~\subset~{1,2, \ldots, n }\) such that …
Computer Science
Algorithms
NP completeness
partition
reduction
subset sum
0
Graduate
By
Shiva Kintali
on June 12, 2012 | Updated Jan. 16, 2017
Solving Discrete-logarithm
Consider the following problem : Given a \(y\) such that \(0 < y < p\), where \(p\) is a prime number, find an \(x\) (if it exists) such that \(2^x ≡ y\ \mbox{mod}\ p\). Let \(n\) be the number …
Computer Science
Mathematics
Algorithms
Number Theory
primes
0
Undergraduate
By
Shiva Kintali
on Oct. 19, 2012 | Updated Jan. 16, 2017
Minimum Path Cover
A path cover of a directed graph \(G(V,E)\) is a set \(P\) of vertex-disjoint paths such that every vertex in \(V\) is included in exactly one path in \(P\). Paths may start and end anywhere, and they…
Computer Science
Algorithms
max flow
0
High School
By
Shiva Kintali
on June 2, 2013 | Updated Jan. 16, 2017
Prime magic
Let \(p\) be a prime number bigger than 3. Prove that \(p^2-1\) is always divisible by \(24\).
Mathematics
Number Theory
primes
0
Graduate
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Card shuffling using pairwise-swapping
You are given a deck of \(n\) cards. In each step you select two cards independently and uniformly at random and swap their positions. This defines a random walk on the set of all permutations of the …
Computer Science
Randomized Algorithms
canonical paths
coupling
random walk
0
Undergraduate
By
Shiva Kintali
on July 2, 2012 | Updated Jan. 16, 2017
Linear time tree isomorphism
Let \(T_1 (V_1,E_2)\) and \(T_2(V_2,E_2)\) be two undirected unlabeled trees. Design a linear-time algorithm to decide if \(T_1\) is isomorphic to \(T_2\).
Computer Science
Mathematics
Algorithms
Graph Theory
graph isomorphism
linear time algorithms
trees
0
High School
By
Shiva Kintali
on Nov. 28, 2012 | Updated Jan. 16, 2017
Infinite series
Prove the following : \(\sum_{n=1}^{\infty}{\frac{1}{(2n-1)(2n+1)}} = \frac{1}{2}\)
Mathematics
infinite series
0
High School
By
Shiva Kintali
on June 27, 2012 | Updated Jan. 16, 2017
Row of Coins
There are 50 coins arranged in a line on a tabletop. The coins are of various denominations. You choose a coin from one of the ends and put it in your pocket. Your opponent then chooses a coin from on…
Puzzles
Puzzles
game puzzle
interview question
0
Undergraduate
By
Shiva Kintali
on June 8, 2012 | Updated Jan. 16, 2017
Block Decomposition in Linear Time
A block of a graph \(G\) is a maximal connected subgraph of \(G\) that has no cut-vertex. If \(G\) itself is connected and has no cut-vertex then \(G\) is a block. Design a linear time algorithm to …
Computer Science
Mathematics
Algorithms
Graph Theory
depth first search
linear time algorithms
0
Undergraduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Happy Ending Problem
Prove the following : Any set of five points in the plane in general position has a subset of four points that from the vertices of a convex quadrilateral. For any positive integer \(N\), any suffic…
Mathematics
Combinatorics
Geometry
counting
0
Undergraduate
By
Shiva Kintali
on June 14, 2012 | Updated Jan. 16, 2017
Left move is decidable
Consider the problem of determining whether a Turing machine on an input \(w\) ever attempts to move its head left at any point during its computation on \(w\). Show that this problem is decidable.
Computer Science
Complexity Theory
turing machine
0
Undergraduate
By
Shiva Kintali
on June 17, 2013 | Updated Jan. 16, 2017
Random cars
The probability of observing a car during a 30 minute period on a road is 95%. What is the probability of observing a car in a 10 minute period ?
Mathematics
Puzzles
Probability
Puzzles
interview question
probability
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Treewidth vs Pathwidth
Let \(G(V,E)\) be an undirected graph with \(|V|=n\) vertices. Let \(tw(G)\) and \(pw(G)\) represent the treewidth and pathwidth of \(G\) respectively. Let \(H\) be a tree. Prove that …
Mathematics
Graph Theory
pathwidth
treewidth
0
Undergraduate
By
Shiva Kintali
on May 31, 2012 | Updated Jan. 16, 2017
Party Problem
Suppose there are six people at a party. Prove that there are always three of them so that every two know each other (or) no two know each other. In other words, let the edges of the complete graph o…
Mathematics
Puzzles
Combinatorics
Graph Theory
Puzzles
counting
extremal graph theory
interview question
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Randomized QuickSort
Consider Randomized-Quicksort operating on a sequence of \(n\) distinct input numbers. Prove that the expected running time of Randomized-Quicksort is \(O(n{\log}n)\) Prove that for any constant …
Computer Science
Algorithms
Randomized Algorithms
expectation
sorting
0
Undergraduate
By
Shiva Kintali
on June 8, 2013 | Updated Jan. 16, 2017
Petersen graph has ten 6-cycles
Petersen Graph is the graph shown below : Prove the following : If two vertices are non-adjacent in the Petersen Graph, then they have exactly one common neighbor. Petersen graph is 3-regular, so…
Mathematics
Graph Theory
counting
petersen graph
0
High School
By
Shiva Kintali
on June 20, 2012 | Updated Jan. 16, 2017
Truthteller and Liar
You played a long role-playing treasure-hunting game for several hours and finally reached end of the last level of the game. You see two doors (\(A\) and \(B\)), and your treasure is behind one of tw…
Puzzles
Puzzles
logic puzzle
0
Undergraduate
By
Shiva Kintali
on Aug. 12, 2012 | Updated Jan. 16, 2017
Finding perfect matching in bipartite graphs
Let \(G = (A,B)\) be a bipartite graph. Hall's theorem implies that \(G\) has a perfect matching if and only if \(|A| = |B|\) and for each \(X \subseteq A\), \(|X| \leq |\Gamma(X)|\), where …
Computer Science
Algorithms
matching
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Edge disjoint perfect matchings
Let \(G\) be a \(d\)-regular bipartite graph with \(n\) vertices in each partition. Prove that \(G\) can be decomposed into \(d\) edge disjoint perfect matchings.
Mathematics
Graph Theory
matching
0
Undergraduate
By
Shiva Kintali
on Nov. 12, 2012 | Updated Jan. 16, 2017
Alice, Bob and children
Alice and Bob decide to have children until either they have their first girl or they have \(k \geq 1\) children. Assume that each child is a boy or girl independently with probability 1/2, and that …
Mathematics
Probability
expectation
0
Undergraduate
By
Shiva Kintali
on July 17, 2012 | Updated Jan. 16, 2017
Number of triangles in a graph
Prove that a simple graph with \(n\) vertices and \(m\) edges has at least \(\frac{m}{3n}(4m − n^2)\) triangles.
Mathematics
Graph Theory
counting
0
Undergraduate
By
Shiva Kintali
on June 6, 2013 | Updated Jan. 16, 2017
Two points
Two points are chosen randomly and independently from the interval \([0,1]\) according to uniform distribution. What is the expected distance between the two points ?
Mathematics
Probability
expectation
interview question
0
Undergraduate
By
Shiva Kintali
on Oct. 21, 2012 | Updated Jan. 16, 2017
Hat Check problem
Each of \(n\) customers gives a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers who g…
Mathematics
Probability
expectation
0
Undergraduate
By
Shiva Kintali
on Nov. 13, 2012 | Updated Jan. 16, 2017
Turing reducibility
Let \(A \leq_T B\) denote that language \(A\) is Turing reducible to language \(B\). Prove the following : Show that for any two languages \(A\) and \(B\) a language \(J\) exists, where …
Computer Science
Complexity Theory
turing reducibility
0
Undergraduate
By
Shiva Kintali
on Oct. 23, 2012 | Updated Jan. 16, 2017
Randomly assigned jobs
Suppose we have \(n\) jobs to distribute among \(m\) processors. For simplicity we assume that \(m\) divides \(n\). A job takes one step with probability \(p\) and \(k > 1\) steps with probability …
Mathematics
Probability
chernoff bound
0
Undergraduate
By
Shiva Kintali
on June 17, 2012 | Updated Jan. 16, 2017
Turan geometry
Let \(x_1, x_2, \dots, x_n\) be a set of diameter one in the plane. Prove that the maximum number of pairs of points at distance greater than \(1/\sqrt{2}\) is \(\lfloor n^2/3\rfloor\).
Mathematics
Geometry
Graph Theory
extremal graph theory
0
High School
By
Shiva Kintali
on June 24, 2012 | Updated Jan. 16, 2017
Toggling 100 doors
There are 100 doors numbered 1 to 100 in a row. There are 100 people. The first person opens all the doors. The second person closes all the even-numbered doors. The third person changes the state of…
Puzzles
Puzzles
interview question
math puzzle
0
Undergraduate
By
Shiva Kintali
on July 11, 2012 | Updated Jan. 16, 2017
Edge coloring bipartite graphs
Prove the following : If \(G\) is a regular bipartite graph, then \(G\) has a perfect matching. If \(G\) is \(k\)-regular bipartite graph then it has an edge coloring using exactly \(k\) colors. If…
Mathematics
Graph Theory
edge coloring
graph coloring
0
Undergraduate
By
Shiva Kintali
on June 13, 2012 | Updated Jan. 16, 2017
Ramsey Number upper bound
The Ramsey Number \(R(s, t)\) is the minimum integer \(n\) for which every red-blue coloring of the edges of a complete graph \(K_n\) contains a completely red \(K_s\) or a completely blue \(K_t\). Pr…
Mathematics
Graph Theory
pigeonhole principle
0
Undergraduate
By
Shiva Kintali
on Oct. 21, 2012 | Updated Jan. 16, 2017
Unbiasing a biased coin
Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability \(p\) a…
Computer Science
Mathematics
Algorithms
Probability
expectation
0
Graduate
By
Shiva Kintali
on Dec. 3, 2012 | Updated Jan. 16, 2017
2-connectivity and bipartite minors
Prove that for every integer \(t\) there exists an integer \(n\) such that every 2-connected graph on at least \(n\) vertices has either a cycle of length at least \(t\) or a \(K_{2,t}\) minor.
Mathematics
Graph Theory
connectivity
graph minors
0
Undergraduate
By
Shiva Kintali
on Dec. 3, 2012 | Updated Jan. 16, 2017
Planar graphs and grid minors
Prove that for every planar graph \(G\) there exists an integer \(k\) such that \(G\) is isomorphic to a minor of the \(k \times k\) grid.
Mathematics
Graph Theory
graph minors
planar graphs
0
High School
By
Shiva Kintali
on April 1, 2014 | Updated Jan. 16, 2017
Designing two dice
You are given two blank dice i.e., all the sides of the dice are blank. You are allowed to write any integers on the sides of the dice. Only one integer on each side. Write the integers such that …
Puzzles
Puzzles
interview question
math puzzle
0
Graduate
By
Shiva Kintali
on June 9, 2012 | Updated Jan. 16, 2017
Basics of Pfaffians
Let \(G(V,E)\) be an undirected graph. An orientation of \(G\) is Pfaffian if every even cycle \(C\) such that \(G \setminus V(C)\) has a perfect matching, has an odd number of edges directed in eithe…
Mathematics
Graph Theory
basics
pfaffian
0
Undergraduate
By
Shiva Kintali
on June 8, 2012 | Updated Jan. 16, 2017
Minimum SetClique Completion Problem
Let \(1,2,...,n\) be a universe of \(n\) elements. Let \(S_1,S_2,\dots,S_m\) be \(m\) subsets of this universe. You are allowed to add new elements (from the universe) to these sets to make every pair…
Computer Science
Complexity Theory
NP completeness
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Maximum subarray problem
Given a array \(A\) of \(n\) integers (containing at least one positive number), the maximum subarray problem is the task of finding the contiguous non-empty subarray within \(A\) which has the larges…
Computer Science
Algorithms
linear time algorithms
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Minimum Flip Connectivity Problem
Let \(G(V,E)\) be a directed graph such that if \(e=(u,v) \in E\) then \((v,u) \notin E\), i.e., \(G\) is an orientation of the underlying undirected graph. Consider the following operations : …
Computer Science
Mathematics
Algorithms
Graph Theory
connectivity
0
Graduate
By
Shiva Kintali
on June 8, 2012 | Updated Jan. 16, 2017
Approximating (1,2)-TSP
Let \(G\) be a complete directed graph i.e., if \(u\) and \(v\) are vertices of \(G\) then both the directed edges \((u,v)\) and \((v,u)\) are present. \((1,2)\)-graphs are complete directed graphs wi…
Computer Science
Approximation Algorithms
traveling salesman
0
High School
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Basics of counting
Let \(S = {1,2,...,n}\). How many ordered pairs \((A,B)\) of subsets of \(S\) are there that satisfy \(A \subseteq B\) ?
Mathematics
Combinatorics
basics
counting
0
Undergraduate
By
Shiva Kintali
on June 9, 2012 | Updated Jan. 16, 2017
Termination of Ford-Fulkerson algorithm
Give an example of a directed graph with real numbers for edge capacities (as opposed to integer numbers) where the Ford-Fulkerson algorithm may not terminate. Explain the reason why the algorithm may…
Computer Science
Algorithms
max flow
0
Undergraduate
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Stick triangle
A stick is broken at random into three pieces. What is the probability that the pieces can form a triangle?
Mathematics
Puzzles
Geometry
Probability
Puzzles
math puzzle
0
Undergraduate
By
Shiva Kintali
on June 14, 2012 | Updated Jan. 16, 2017
Connectivity of cubic graphs
Prove that if \(G\) is 3-regular graph, then its vertex-connectivity equals its edge-connectivity.
Mathematics
Graph Theory
connectivity
0
Undergraduate
By
Shiva Kintali
on Feb. 12, 2013 | Updated Jan. 16, 2017
Coloring Hamiltonian plane graph
Prove that the faces of a Hamiltonian plane graph can be 4-colored in a such a way that whenever two faces are incident with the same edge they receive different colors.
Mathematics
Graph Theory
graph coloring
planar graphs
0
Graduate
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Basics of Treewidth
Treewidth of an undirected graph \(G\) measures how close \(G\) is to a tree. A tree decomposition of a graph \(G(V, E)\) is a pair \(\mathcal{D} = ({X_i\ |\ i \in I}, T(I, F))\) where …
Mathematics
Graph Theory
basics
treewidth
0
Graduate
By
Shiva Kintali
on June 12, 2012 | Updated Jan. 16, 2017
Hamiltonian cycles in odd graphs
Let \(G\) be a graph such that all vertices of \(G\) have odd degree. Let \(e\) be any edge of \(G\). Prove that there are an even number of Hamiltonian cycles using \(e\).
Mathematics
Graph Theory
hamiltonian cycle
0
Graduate
By
Shiva Kintali
on July 3, 2012 | Updated Jan. 16, 2017
Minimum makespan problem
Minimum makespan scheduling problem : You are given \(n\) jobs and \(m\) identical machines. You are given processing times (say \(t_i\)) for the \(n\) jobs. Your goal is to find an assignment of the …
Computer Science
Approximation Algorithms
scheduling
0
Undergraduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Distances between points in a plane
Let \(S\) be a set of \(n \geq 3\) points in the plane such that the distance between any two points is at least 1. Prove that there are at most \(3n - 6\) pairs of points at distance exactly 1. Pro…
Mathematics
Combinatorics
Geometry
counting
0
Undergraduate
By
Shiva Kintali
on Nov. 6, 2012 | Updated Jan. 16, 2017
Guessing Right
Players 1 and 2 each choose a member of the set \({1,2,\dots,K}\). If the players choose the same number then player 2 pays \(\\)1$ to player 1; otherwise no payment is made. Each player maximizes his…
Mathematics
Game Theory
nash equilibrium
0
Graduate
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Parity is non-monotone
A boolean function \(f(x_{1},x_{2},\dots,x_{n})\) is called monotone if it can be written as a formula with only the AND and OR operations. Prove that \(x_1 \oplus x_2 \oplus \dots \oplus x_n\) is n…
Mathematics
Logic
monotone function
0
High School
By
Shiva Kintali
on June 1, 2013 | Updated Jan. 16, 2017
The Sixth Sense
In the following, you are allowed to put any mathematical symbols on the left-hand side of the \("="\) sign to make the left-hand side evaluate to \(6\). For example, \(2+2+2=6\). Do this for all the …
Puzzles
Puzzles
math puzzle
0
High School
By
Shiva Kintali
on June 13, 2012 | Updated Jan. 16, 2017
Secret salaries
Three coworkers (A,B,C) would like to know their average salary. How can they achieve this without revealing their own salaries ? More details : No single person can know the salary of other person…
Puzzles
Puzzles
math puzzle
0
High School
By
Shiva Kintali
on June 23, 2012 | Updated Jan. 16, 2017
Gas stations in a circle
There are \(n\) gas stations located on a circular route. Together they contain exactly enough gas to make one trip around. Prove that there exists a gas station (say \(A\)), such that if you start …
Puzzles
Puzzles
counting
interview question
0
Graduate
By
Shiva Kintali
on July 2, 2012 | Updated Jan. 16, 2017
Recognizing bipartite k-extendable graphs
A graph \(G\) is \(k\)-extendable, where \(k \geq 1\) is an integer, if every matching of size at most \(k\) is a subset of a perfect matching of \(G\). Given a bipartite graph \(G\) and an integer …
Computer Science
Mathematics
Algorithms
Graph Theory
matching
0
Undergraduate
By
Shiva Kintali
on July 4, 2012 | Updated Jan. 16, 2017
Triangle avoidance game
A triangle avoidance game consists of two players (say \(A\) and \(B\)) beginning with an empty graph on \(n\) vertices. The two players take turns choosing edges within \(K_n\) and coloring them with…
Mathematics
Puzzles
Game Theory
Graph Theory
Puzzles
game puzzle
0
Undergraduate
By
Shiva Kintali
on June 8, 2012 | Updated Jan. 16, 2017
Linear time algorithms on trees
Let \(T(V,E)\) be a tree. Design linear time (i.e., \(O(|V|)\) time) algorithms for the following problems : Find an optimal vertex cover in \(T\). Find a maximum matching in \(T\). Find a maximum i…
Computer Science
Mathematics
Algorithms
Graph Theory
independent set
linear time algorithms
matching
trees
vertex cover
0
Undergraduate
By
Shiva Kintali
on July 30, 2012 | Updated Jan. 16, 2017
k-regular bipartite graphs are 2-connected
Prove that every connected \(k\)-regular bipartite graph on at least three vertices is 2-connected.
Mathematics
Graph Theory
bipartite graph
connectivity
0
High School
By
Shiva Kintali
on June 1, 2013 | Updated Jan. 16, 2017
Connect nine dots
Draw nine dots (in 3 rows and 3 columns, equally spaced) as shown in the figure. Your task is to connect all the dots by four straight lines. The next line has to start where the previous line ended. …
Puzzles
Puzzles
geometry puzzle
interview question
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Mycielskian graphs
A factor-critical graph is a graph with \(n\) vertices in which every subset of \(n-1\) vertices has a perfect matching. Let \(\mu(G)\) be the Mycielski graph of an undirected graph \(G\). Prove the …
Mathematics
Graph Theory
graph coloring
0
Graduate
By
Shiva Kintali
on Aug. 1, 2012 | Updated Jan. 16, 2017
Number of Hamiltonian paths
Let \(G\) be an undirected graph on at least five vertices let and \(\overline{G}\) its complement. Let \(h(G)\) be the number of Hamiltonian paths of \(G\). Prove that \(h(G) + h(\overline{G})\) is…
Mathematics
Graph Theory
counting
0
Undergraduate
By
Shiva Kintali
on July 6, 2012 | Updated Jan. 16, 2017
Linear recursion relations
Let \(a_n\) denote the Fibonacci sequence \(a_0 = 0\), \(a_1 = 1\), \(a_n = a_{n−1} + a_{n−2}\). Let \(b_n = (a_n)^2\). Prove that \(b_n\) satisfies a linear recursion relation i.e., \(b_n\) can be …
Puzzles
Puzzles
recursion
0
High School
By
Shiva Kintali
on June 2, 2013 | Updated Jan. 16, 2017
Die Hard Water Puzzle
You have a 3 litre jug and a 5 litre jug. Each jug has no markings on them. You have a running tap (i.e., infinite supply of water). You must use the jugs and the tap in such away as to exactly measur…
Puzzles
Puzzles
interview question
math puzzle
0
Undergraduate
By
Shiva Kintali
on June 22, 2012 | Updated Jan. 16, 2017
100 perfect logicians
100 perfect logicians are told to sit in a circle in a room. Before they enter the room, they are told at least one person has a blue forehead. When you determine your forehead is blue, you need to le…
Puzzles
Puzzles
logic puzzle
0
High School
By
Shiva Kintali
on Aug. 1, 2012 | Updated Jan. 16, 2017
Two Secret Integers
I am thinking of two integers, each of them is more than 1 and their sum is less than 100. I tell my friend A the sum of these two numbers, and another friend B, product of these two numbers. Then the…
Puzzles
Puzzles
math puzzle
0
Undergraduate
By
Shiva Kintali
on July 10, 2012 | Updated Jan. 16, 2017
Diameter of a tree
Let \(T(V, E)\) be a tree given as an adjacency list. For vertices \(u, v \in V\), let \(d(u, v)\) denote the length of the path from \(u\) to \(v\) in \(T\). Give a linear-time algorithm to determine…
Computer Science
Mathematics
Algorithms
Graph Theory
linear time algorithms
trees
0
Graduate
By
Shiva Kintali
on Sept. 11, 2012 | Updated Jan. 16, 2017
Vertex cover in bipartite graphs
The Vertex Cover of a graph \(G(V,E)\) is a set of vertices \(S \subseteq V\) such that each edge of the graph is incident to at least one vertex of the set \(S\). Minimum cost vertex cover : Given a…
Mathematics
Optimization
Graph Theory
Linear Programming
bipartite graph
vertex cover
0
Undergraduate
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Expanding expressions
You are given an algebraic expression \(E\) having variables, addition, multiplication and parenthesis. Your goal is to repeatedly expand \(E\) using the distributive law if possible. Prove that th…
Puzzles
Puzzles
convergence
0
Graduate
By
Shiva Kintali
on Dec. 5, 2012 | Updated Jan. 16, 2017
Hadwiger’s conjecture and Random graphs
A random graph \(G(n, \frac{1}{2})\) on \(n\) vertices, is obtained by starting with a set of \(n\) and adding every possible edge independently with probability \(\frac{1}{2}\). Hadwiger’s conjectur…
Mathematics
Graph Theory
graph coloring
random graphs
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Generating random numbers
You are given a fair coin that comes up with heads (or tails) with probability 1/2. Using this fair coin, implement a random number generator \(Random(a,b)\) that returns an integer between \(a\) and …
Computer Science
Randomized Algorithms
generator
0
Undergraduate
By
Shiva Kintali
on May 22, 2013 | Updated Jan. 16, 2017
Balls and bin game
Consider the following balls-and-bin game. We start with one black ball and one white ball in a bin. We repeatedly do the following : choose one ball from the bin uniformly at random, and then put the…
Mathematics
Probability
sampling
0
High School
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Cutting Corners
Prove that removing opposite corner squares from an \(8 \times 8\) chessboard leaves a subboard that cannot be partitioned (tiled) into \(1 \times 2\) and \(2 \times 1\) rectangles. Prove the ab…
Mathematics
Puzzles
Graph Theory
Puzzles
interview question
tiling
0
Graduate
By
Shiva Kintali
on Nov. 15, 2012 | Updated Jan. 16, 2017
Basics of Perfect Graphs
A perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Prove that bipartite graphs are perfect. Prove that the lin…
Mathematics
Graph Theory
basics
bipartite graph
chordal graph
graph coloring
interval graph
perfect graphs
0
Undergraduate
By
Shiva Kintali
on Oct. 17, 2012 | Updated Jan. 16, 2017
Comparison-based merging
You are given two sorted lists A and B of length \(m\) and \(n\) (where \(m \geq n\)). Your goal is to merge them into a new sorted list C. Prove that any comparison-based algorithm for merging A …
Computer Science
Algorithms
lower bound
sorting
0
Undergraduate
By
Shiva Kintali
on May 22, 2013 | Updated Jan. 16, 2017
Basics of bipartite graphs
Prove the following properties of bipartite graphs : Prove that a graph \(G\) is bipartite if and only if every subgraph \(H\) of \(G\) has an independent set consisting of at least half of \(V(H)\)…
Mathematics
Graph Theory
basics
bipartite graph
0
Graduate
By
Shiva Kintali
on June 8, 2012 | Updated Jan. 16, 2017
Simplicial vertices in Chordal graphs
Let \(G(V,E)\) be a simple undirected graph. Let \(v \in V\) and let \(N(v)\) denote the neighbors of \(v\) in \(G\). The vertex \(v\) is said to be simplicial if \(N(v)\) induces a clique in \(G\). …
Mathematics
Graph Theory
chordal graph
0
Undergraduate
By
Shiva Kintali
on May 22, 2013 | Updated Jan. 16, 2017
Basics of probability
Prove that, if \(E_1, E_2, \dots, E_n\) are mutually independent, then so are \(\overline{E_1}, \overline{E_2}, \dots, \overline{E_n}\) Give an example of three random events \(X,Y,Z\) for which any …
Mathematics
Probability
basics
conditional probability
0
Undergraduate
By
Shiva Kintali
on July 21, 2012 | Updated Jan. 16, 2017
Linear time shuffling
Consider the following algorithm to shuffle an array \(A\) of \(n\) elements (with indices from \(0\) to \(n-1\) : for \(i = 0\) to \(n - 1\) Let j be a random integer between 0 and i exchange A…
Computer Science
Randomized Algorithms
linear time algorithms
0
Undergraduate
By
Shiva Kintali
on June 30, 2012 | Updated Jan. 16, 2017
Degree sequence is reconstructible
Given a graph \(G(V,E)\), a vertex-deleted subgraph of \(G\) is a subgraph formed by deleting exactly one vertex from \(G\). For a graph \(G\), the deck of \(G\), denoted \(D(G)\), is the multiset of …
Mathematics
Graph Theory
counting
graph reconstruction
0
Graduate
By
Shiva Kintali
on Aug. 29, 2012 | Updated Jan. 16, 2017
Random Intervals
There are \(n\) points on a line. These points are paired up at random to form \(n/2\) intervals. Prove that the probability that among these intervals there is one which intersects all the others i…
Mathematics
Puzzles
Probability
Puzzles
counting
0
Undergraduate
By
Shiva Kintali
on Jan. 3, 2014 | Updated Jan. 16, 2017
Depth first search properties
Let \(G(V,E)\) be an undirected connected graph with \(|V| = n\). Let \(T\) be a depth-first search tree of \(G\) starting from an arbitrary vertex of \(G\). Let \(h\) be the height of tree \(T\). Pro…
Computer Science
Mathematics
Algorithms
Graph Theory
depth first search
0
Undergraduate
By
Shiva Kintali
on June 5, 2012 | Updated Jan. 16, 2017
Properties of Petersen Graph
Petersen Graph is the graph shown below : Prove the following properties of the Petersen Graph : It is not planar. It is strongly-regular. It has a Hamiltonian path but no Hamiltonian Cycle. It i…
Mathematics
Graph Theory
connectivity
hamiltonian cycle
matching
petersen graph
0
Graduate
By
Shiva Kintali
on June 19, 2012 | Updated Jan. 16, 2017
Primality is in NP $\cap$ co-NP
Primality is the following problem : Given a positive integer \(n\), is \(n\) prime ? Note that the size of the input is the number of bits used to represent \(n\). Easy : Show that Primality…
Computer Science
Mathematics
Complexity Theory
Number Theory
primes
0
Undergraduate
By
Shiva Kintali
on April 23, 2013 | Updated Jan. 16, 2017
Intersecting every line exactly twice
Prove that there is a set in \(\mathbb{R}^2\) that intersects every line exactly twice.
Mathematics
Real Analysis
axiom of choice
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Finding two elements
Design a \(\Theta(n{\log}n)\)-time algorithm that, given a set \(S\) of \(n\) integers and another integer \(x\), determines whether or not there exist two elements in \(S\) whose sum is exactly \(x\)…
Computer Science
Algorithms
searching
sorting
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Randomly built binary search tree
Define a randomly built binary search tree on \(n\) keys as one that arises from inserting the keys in random order into an initially empty tree, where each of the \(n!\) permutations of the input key…
Computer Science
Mathematics
Algorithms
Data Structures
Probability
binary tree
expectation
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Primes and Combinations
Prove that if \(p\) is prime and \(0 < k < p\), then \(p\ |\ {p \choose k}\). Conclude that for all integers \(a\) and \(b\) and all primes \(p\), \((a+b)^p \equiv a^p + b^p\ (\mbox{mod}\ p)\) Prove…
Mathematics
Number Theory
primes
0
Undergraduate
By
Shiva Kintali
on June 17, 2012 | Updated Jan. 16, 2017
Matching saturating high degree vertices
Let \(G\) be a bipartite multigraph and let \(\Delta\) be its maximum degree. Prove that \(G\) has a matching saturating every vertex of degree \(\Delta\).
Mathematics
Graph Theory
bipartite graph
matching
0
Graduate
By
Shiva Kintali
on June 7, 2012 | Updated Jan. 16, 2017
Planar Graphs are Pfaffians
Let \(G(V,E)\) be an undirected graph. An orientation of \(G\) is Pfaffian if every even cycle \(C\) such that \(G \setminus V(C)\) has a perfect matching, has an odd number of edges directed in eithe…
Mathematics
Graph Theory
pfaffian
planar graphs
0
Undergraduate
By
Shiva Kintali
on Nov. 14, 2012 | Updated Jan. 16, 2017
Randomized k-SAT algorithm
Consider an instance of SAT with \(m\) clauses, where every clause has exactly \(k\) literals. Give a Las Vegas algorithm that finds an assignment satisfying at least \(m(1-2^{-k})\) clauses, and an…
Mathematics
Probability
conditional expectation
derandomization
expectation
sat
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Basics of Hamiltonicity
Let \(G(V,E)\) be a simple graph with \(n\) vertices and minimum degree \(\delta\). Also, for every two vertices \(x, y \in V\), \(|N(x) \cup N(y)| + \delta \ge n + 10\). Prove that \(G\) has a Hami…
Mathematics
Graph Theory
basics
hamiltonian cycle
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Erdos-Szekeres Theorem
Prove that for given integers \(r, s\) any sequence of distinct real numbers of length at least \((r - 1)(s - 1) + 1\) contains either a monotonically increasing subsequence of length \(r\), or a mon…
Mathematics
Combinatorics
pigeonhole principle
0
Undergraduate
By
Shiva Kintali
on June 25, 2012 | Updated Jan. 16, 2017
Separator number of a tree
Let \(T(V,E)\) be a tree with \(|V| = n\) vertices. Let \(W\) be a subset of \(V\). Prove that there is a vertex \(v \in V\) such that every component of \(T - v\) contains at most …
Computer Science
Mathematics
Algorithms
Graph Theory
trees
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Self-complementary graphs
Let \(G\) be a self-complementary graph (i.e., \(G\) is isomorphic to its complement) on \(n\) vertices. Prove that \(n \equiv 0\ (mod\ 4)\) or \(n \equiv -1\ (mod\ 4)\). Prove that \(G\) has a cut…
Mathematics
Graph Theory
graph complement
0
High School
By
Shiva Kintali
on Aug. 4, 2012 | Updated Jan. 16, 2017
Olympic Number Puzzle
The Olympic emblem consists of five overlapping circles containing nine regions. Place numbers 1 to 9 in each of the 9 closed regions of olympic emblem such that the total inside each ring is the …
Puzzles
Puzzles
math puzzle
0
Graduate
By
Shiva Kintali
on June 17, 2012 | Updated Jan. 16, 2017
SONET ring loading
Consider a telephone network that consists of a cycle on \(n\) nodes, numbered \(0\) through \(n-1\) clockwise around the cycle. Let \(S\) be a set of calls. Each call is a pair \((i,j)\) originating …
Computer Science
Approximation Algorithms
networks
0
Undergraduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Subtrees of a Tree
Let \(T_1, T_2, \dots, T_k\) be subtrees of a tree \(T\). Prove that if every two of them have a vertex in common, then they all have a vertex in common.
Mathematics
Graph Theory
trees
0
Undergraduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Reservoir Sampling
You are watching a stream of packets go by one at a time, and want to take a random sample of \(k\) distinct packets from the stream. You only have room to save \(k\) packets at any one time. You do…
Computer Science
Randomized Algorithms
sampling
0
High School
By
Shiva Kintali
on June 21, 2012 | Updated Jan. 16, 2017
Togglers and Truthtellers
There are five people. Four of them are togglers, and the fifth person is a truthteller. A toggler tells either the truth or lie when you ask him a question. The second time you ask him a question…
Puzzles
Puzzles
logic puzzle
0
Graduate
By
Shiva Kintali
on July 28, 2012 | Updated Jan. 16, 2017
Petersen’s theorem
Prove that every 2-edge-connected 3-regular graph has a perfect matching
Mathematics
Graph Theory
connectivity
matching
0
Undergraduate
By
Shiva Kintali
on June 30, 2012 | Updated Jan. 16, 2017
Coloring graphs with odd cycles
Prove that a graph with at most two odd cycles has chromatic number of at most 3. Let \(G\) be a graph where every two odd cycles have at least a vertex in common. We call such graphs nicely-odd grap…
Mathematics
Graph Theory
graph coloring
0
High School
By
Shiva Kintali
on Oct. 9, 2012 | Updated Jan. 16, 2017
Number of positive divisors
For any positive integer \(n\), let \(d(n)\) denote the number of positive divisors of \(n\) (including \(1\) and \(n\) itself). Determine all positive integers \(k\) such that \(d(n^2)/d(n) = k\) for…
Mathematics
Number Theory
divisibility
math olympiad
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Lonely edges in bipartite graphs
Let \(G\) be an \(X,Y\)-bipartite graph with \(|X|=|Y|=n\). Suppose that \(G\) has a perfect matching. An edge in \(G\) is lonely if it belongs to no perfect matching. Prove that \(G\) has at most \…
Mathematics
Graph Theory
bipartite graph
matching
0
Graduate
By
Shiva Kintali
on June 8, 2012 | Updated Jan. 16, 2017
Exact Algorithms for Subset Sum
Let \(a_1, a_2, \dots, a_n\) be natural numbers in the range \([1,M]\). Let \(b\) be another natural number. Subset Sum Problem is to decide if there is a subset \(S\) of indices \(1,2,\dots,n\) such …
Computer Science
Algorithms
dynamic programming
exponential algorithms
subset sum
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Large min-degree implies perfect matching
Let \(G\) be a bipartite graph with partitions \(X\) and \(Y\) such that \(|X|=|Y|=n\). The degree of each vertex in \(G\) is at least \(n/2\). Prove that \(G\) has a perfect matching.
Mathematics
Graph Theory
matching
0
Graduate
By
Shiva Kintali
on June 11, 2012 | Updated Jan. 16, 2017
Embedding complete bipartite graphs
Let \(S\) be an orientable surface of genus \(g \geq 0\). Prove that for every \(g \geq 0\) there exists an integer \(t\) such that \(K_{3,t}\) cannot be drawn on \(S\) without any crossings. What is…
Mathematics
Graph Theory
graph embedding
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Counting intersections of chords
Consider \(n\) chords on a circle, each defined by its endpoints. Describe an \(O(n{\log}n)\)-time algorithm to determine the number of pairs of chords that intersect inside the circle. For example, i…
Computer Science
Algorithms
Data Structures
counting
sorting
0
Undergraduate
By
Shiva Kintali
on June 29, 2012 | Updated Jan. 16, 2017
Coloring Planar Graphs
Prove that every planar graph has at least one vertex of degree at most five. Conclude that planar graphs are six-colorable. Prove that every triangle-free planar graph has at least one vertex of deg…
Mathematics
Graph Theory
eulers formula
planar graphs
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Reverse a linked list
Design a \(\Theta(n)\)-time nonrecursive algorithm that reverses a singly linked list of \(n\) elements. The algorithm should use no more than constant space beyond that needed for the list itself.
Computer Science
Algorithms
Data Structures
linear time algorithms
linked list
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Algebraic dual of graphs
Let \(G\) be a connected graph. An algebraic dual of \(G\) is a graph \(G'\) such that \(G\) and \(G'\) have the same set of edges, any cycle of \(G\) is a cut of \(G'\), and any cut of \(G\) is a cyc…
Mathematics
Graph Theory
matroids
0
Graduate
By
Shiva Kintali
on June 17, 2012 | Updated Jan. 16, 2017
Vertex cover using DFS
Consider the following algorithm for Vertex Cover of a graph \(G\) : Run depth first search (DFS) on \(G\). Output the vertices which are not leaves in the DFS tree. Prove the following : The ou…
Computer Science
Mathematics
Approximation Algorithms
Graph Theory
vertex cover
0
Graduate
By
Shiva Kintali
on May 31, 2013 | Updated Jan. 16, 2017
Treewidth and circumference
Circumference of a graph is the length of its longest cycle. Prove that if a graph has circumference \(k\) then its treewidth is at most \(k-1\). Give a class of graphs showing that this bound is tigh…
Mathematics
Graph Theory
circumference
treewidth
0
Undergraduate
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Efficient cash register
You have a cash register that contains coins of denominations \(1 = d_{1} < d_{2} < \dots < d_{n}\). The register contains infinite number of coins of each denomination. A customer needs to get \(M\)…
Computer Science
Algorithms
dynamic programming
0
Undergraduate
By
Shiva Kintali
on Oct. 21, 2012 | Updated Jan. 16, 2017
Number of inversions
Let \(A\) be an array of \(n\) distinct numbers. If \(i < j\) and \(A[i] > A[j]\), then the pair \((i,j)\) is called an inversion of \(A\). Design an algorithm that determines the number of inversio…
Mathematics
Probability
expectation
0
High School
By
Shiva Kintali
on Aug. 15, 2012 | Updated Jan. 16, 2017
Two Eggs Puzzle
You have two eggs, and access to a 100 story building. There is some floor on the building below which the eggs will not break, if dropped. What is the worst upper case bound on the number of drops …
Puzzles
Puzzles
math puzzle
0
Graduate
By
Shiva Kintali
on June 4, 2013 | Updated Jan. 16, 2017
Treewidth and feedback vertex set
A feedback vertex set is a set of vertices whose removal results in an acyclic graph. Prove that if a graph has a feedback vertex set of size \(k\), then it has treewidth at most \(k+1\).
Mathematics
Graph Theory
treewidth
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Perfect Matchings in Cubic Graphs
Let \(G\) be a cubic graph with no cut-edge. Let \(PM(G)\) be the convex hull of the perfect matchings of \(G\). Prove that the vector \((1/3, 1/3, \dots, 1/3) \in PM(G)\). Prove that every two-conn…
Mathematics
Optimization
Combinatorial Optimization
Graph Theory
matching
0
Undergraduate
By
Shiva Kintali
on July 5, 2012 | Updated Jan. 16, 2017
Cycle in k-connected graphs
Prove that every \(k\)-connected graph (\(k > 1\)) on at least \(2k\) vertices has a cycle of length at least \(2k\).
Mathematics
Graph Theory
connectivity
0
Graduate
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Size of monotone circuits
Prove that there is a monotone boolean function \(f(x_{1}, x_{2},\dots,x_{n})\) such that any circuit (consisting of only AND, OR gates) computing \(f\) requires at least …
Computer Science
Complexity Theory
circuit complexity
lower bound
monotone function
0
Undergraduate
By
Shiva Kintali
on Jan. 21, 2013 | Updated Jan. 16, 2017
Characterizing outerplanar graphs
A graph is outerplanar if it is isomorphic to a plane graph such that every vertex is incident with the unbounded face. Prove that a graph is outerplanar if and only if it has no subgraph isomorph…
Mathematics
Graph Theory
planar graphs
0
High School
By
Shiva Kintali
on Dec. 31, 2013 | Updated Jan. 16, 2017
Prime gaps are not bounded
Prove that the gap between consecutive primes is not bounded, by proving the following theorem. Given any integer \(k \geq 1\), there is a number \(N\) such that \(N+1, N+2, N+3, \dots, N+k\) are …
Mathematics
Number Theory
primes
0
Graduate
By
Shiva Kintali
on Feb. 20, 2013 | Updated Jan. 16, 2017
Treewidth and Cliques
A tree decomposition of a graph \(G(V, E)\) is a pair \(\mathcal{D} = ({X_i\ |\ i \in I}, T(I, F))\) where \({X_i\ |\ i \in I}\) is a collection of subsets of \(V\) (called bags) and \(T(I, F)\) is a …
Mathematics
Graph Theory
treewidth
0
Undergraduate
By
Shiva Kintali
on June 16, 2012 | Updated Jan. 16, 2017
L shaped tiling
Consider a \(2^n × 2^n\) board with one (arbitrarily chosen) square removed, as in the following figure for \(n = 3\). Prove that any such board can be tiled (without gaps or overlaps) by \(L\)-shaped…
Puzzles
Puzzles
induction
tiling
0
Graduate
By
Shiva Kintali
on Aug. 8, 2012 | Updated Jan. 16, 2017
Halin's theorem and Mader's theorem
Prove the following : Halin's Theorem : (Easy) There is a node of degree \(k\) in any edge-minimal \(k\)-vertex-connected graph. Mader's Theorem : (Hard) In any edge-minimal \(k\)-vertex-connected …
Mathematics
Graph Theory
connectivity
0
Undergraduate
By
Shiva Kintali
on June 17, 2012 | Updated Jan. 16, 2017
Trees in a graph
Let \(k \geq 1\) be an integer, and let \(T\) be a tree on \(k+1\) vertices. Show that if a graph \(G\) has minimum degree at least \(k\), then \(G\) has a subgraph isomorphic to \(T\).
Mathematics
Graph Theory
trees
0
Graduate
By
Shiva Kintali
on Aug. 13, 2012 | Updated Jan. 16, 2017
Integer Factoring is in NP $\cap$ co-NP
Formulate an appropriate decision version of Integer Factorization and prove that it is in NP \(\cap\) co-NP. There are two ways of proving this : (Easy) Use the fact that Primality is in P. Witho…
Computer Science
Mathematics
Complexity Theory
Number Theory
factoring
NP completeness
0
Graduate
By
Shiva Kintali
on Aug. 12, 2012 | Updated Jan. 16, 2017
Matrix rank is submodular
A real-valued set function \(f : 2^S \rightarrow \mathcal{R}\) is called submodular if it satisfies the following property : \(f(X \cup Y) + f(X \cap Y) \leq f(X) + f(Y)\) for all …
Mathematics
Matrix Theory
submodularity
0
Undergraduate
By
Shiva Kintali
on June 17, 2012 | Updated Jan. 16, 2017
Edge connectivity vs Strong connectivity
A directed graph \(D\) is strongly connected if and only if \(\forall\) \(u,v\) there exists a directed path from \(u\) to \(v\). Prove that for an undirected graph \(G\) the following two are equival…
Mathematics
Graph Theory
connectivity
0
High School
By
Shiva Kintali
on March 24, 2013 | Updated Jan. 16, 2017
Infinite number of special primes
Prove that there are infinitely many primes of the form \(4n-1\) and \(4n+1\).
Mathematics
Number Theory
primes
0
Graduate
By
Shiva Kintali
on June 7, 2012 | Updated Jan. 16, 2017
Recognizing series-parallel graphs in linear time
Let \(G(V,E)\) be a simple undirected graph with \(|V| = n\) and \(|E| = m\). Let the treewidth of \(G\) be at most \(k\). Derive a tight upper bound of \(m\) in terms of \(n\) and \(k\). Show that …
Computer Science
Mathematics
Algorithms
Graph Theory
chordal graph
linear time algorithms
series parallel
treewidth
0
Undergraduate
By
Shiva Kintali
on May 21, 2013 | Updated Jan. 16, 2017
Covering complete graph with bipartite graphs
The union of graphs \(G_1, \dots, G_k\), written \(G_1 \cup \dots \cup G_k\), is the graph with vertex set \(V(G_1) \cup \dots \cup V(G_k)\) and edge set \(E(G_1) \cup \dots \cup E(G_k)\). Prove tha…
Mathematics
Graph Theory
bipartite graph
graph union
0
High School
By
Shiva Kintali
on July 18, 2012 | Updated Jan. 16, 2017
Red Blue Hats
There are 10 people and 10 hats. Each person is assigned a random hat, colored either RED or BLUE, but the number of each colored hat is not known to them. They will be lined up such that each person …
Puzzles
Puzzles
logic puzzle
0
Undergraduate
By
Shiva Kintali
on May 9, 2012 | Updated Jan. 16, 2017
$K_4$ subdivision and 3-colorability
Prove that every graph with no subgraph isomorphic to a subdivision of \(K_4\) is 3-colorable.
Mathematics
Graph Theory
graph coloring
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Detecting fair coin
You are given two coins: one is a fair coin and the other is a biased coin that produces heads with probability 3/4. One of the two coins is picked, and is tossed \(n\) times. How many tosses suffic…
Mathematics
Probability
conditional probability
0
High School
By
Shiva Kintali
on June 10, 2012 | Updated Jan. 16, 2017
Banana-eating Camel
You have 3,000 bananas that must be transported across a desert that is 1,000 kilometers wide. You have a camel that has a 1,000 banana capacity. However, the camel must eat one banana for each kilome…
Puzzles
Puzzles
counting
interview question
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Basics of Connectivity
Prove that a connected graph \(G\) with \(2k\) odd vertices (odd degree vertices) decomposes into \(k\) paths (not necessarily simple paths) if \(k > 0\). Does this remain true if \(G\) is not connec…
Mathematics
Graph Theory
basics
connectivity
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Connectivity of dual graph
Prove that if \(G\) is a simple 3-connected planar graph with at least 4 vertices, then the dual of \(G\) is also a simple 3-connected planar graph.
Mathematics
Graph Theory
planar graphs
5
multiple choice questions
0
Undergraduate
By
Shiva Kintali
on June 8, 2013 | Updated Jan. 16, 2017
Let \(G\) be a \(k\)-regular simple bipartite graph with vertex partitions \(A\) and \(B\). Then,
Mathematics
Graph Theory
counting
0
Undergraduate
By
Shiva Kintali
on May 31, 2013 | Updated Jan. 16, 2017
Let \(b > 1\). Then \(\log_b((n^2)!)\) is
Mathematics
asymptotic analysis
0
Undergraduate
By
Shiva Kintali
on June 6, 2013 | Updated Jan. 16, 2017
There are exactly _________ spanning trees on the vertex set {\(1, \dots , n\)}.
Mathematics
Graph Theory
counting
trees
0
Undergraduate
By
Shiva Kintali
on June 8, 2013 | Updated Jan. 16, 2017
Let \(G(V,E)\) be an undirected simple graph with \(|V|=n\) and \(|E|=m\). Let \(deg(v)\) be the degree of a vertex \(v \in V(G)\). Then, the sum of the degrees of all vertices in \(G\) i.e., …
Mathematics
Graph Theory
counting
0
Undergraduate
By
Shiva Kintali
on May 31, 2013 | Updated Jan. 16, 2017
Evaluate the following summation \(\sum_{i=1}^n {i^{-1/2}}\)
Mathematics
Discrete Mathematics
asymptotic analysis
summation
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
volume
differentiation
inequality
jee
jee 2016
jee advanced
jee mathematics
jee main
statistics
variance
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×