Toggle navigation
Mathematics
SAT
JEE
IMO
Vocabulary
Algorithms
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▼
date
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
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
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
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
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
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 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 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 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
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
« 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
geometry puzzle
connectivity
planar graphs
regular graphs
counter example
hamiltonian path
path
digraphs
fermats little theorem
jee
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
×