Toggle navigation
Mathematics
SAT
JEE
IMO
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▼
date
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 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
TrueShelf Inc.
on Sept. 28, 2013 | Updated Jan. 16, 2017
Murphy's Law
Let \(A_1, A_2, \ldots ,A_n\) be independent events, and let \(T\) be the number of these events that occur. Show that the probability that none of the events occur is at most \(e^{-E[T]}\), where…
Mathematics
Probability
expectation
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
Undergraduate
By
TrueShelf Inc.
on Oct. 3, 2013 | Updated Jan. 16, 2017
Leaves in a tree
Prove that every tree has at least two leaves (i.e., vertices of degree \(1\)). Prove that every tree with maximum degree \(\Delta>1\) has at least \(\Delta\) leaves.
Mathematics
Graph Theory
counting
trees
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 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
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 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
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
« previous
1
2
3
4
5
...
24
25
26
next page »
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
blog
jee
jee 2016
jee advanced
jee mathematics
limits
counting
fibonacci
induction
tiling
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
×