Exercises
Multiple Choice
Articles
Open Problems
Login
47 exercises
Level:
GRADUATE
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Graduate
By
domotorp
on June 6, 2012 | Updated Dec. 6, 2017
Read Once Promised Majority
Suppose the input is \(n\) numbers from \(1\) to \(n\), separated by commas and we know that one of the number occurs more than \(n/2\) times. How can we decide which if we can read the input tape onl…
Computer Science
Puzzles
Complexity Theory
Puzzles
read once
0
Graduate
By
Shiva Kintali
on June 17, 2012 | Updated Dec. 6, 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 Aug. 29, 2012 | Updated Dec. 6, 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
Graduate
By
Shiva Kintali
on Sept. 11, 2012 | Updated Dec. 6, 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
Graduate
By
Shiva Kintali
on Aug. 8, 2012 | Updated Dec. 6, 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
Graduate
By
Shiva Kintali
on May 7, 2012 | Updated Dec. 6, 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
Graduate
By
Shiva Kintali
on Oct. 12, 2012 | Updated Dec. 6, 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
Graduate
By
Shiva Kintali
on Dec. 5, 2012 | Updated Dec. 6, 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
Graduate
By
Shiva Kintali
on June 19, 2012 | Updated Dec. 6, 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
Graduate
By
Shiva Kintali
on June 8, 2012 | Updated Dec. 6, 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
1
2
3
4
5
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 OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
dynamic programming
counting
perfect square
primes
axiom of choice
circuit complexity
lower bound
monotone function
arithmetic progression
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
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×