Toggle navigation
Mathematics
SAT
JEE
IMO
Vocabulary
Algorithms
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▼
date
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
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 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
TrueShelf Inc.
on Sept. 30, 2013 | Updated Jan. 16, 2017
Friends and Parties
Show that at a party of \(n\) people, there are two people who have the same number of friends in the party. Assume that friendship is symmetric. There are \(2n\) people at a party. Each person has a…
Mathematics
Discrete Mathematics
counting
pigeonhole principle
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
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
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
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 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 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
« previous
1
2
3
4
...
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
vertex cover
basics
pfaffian
modular arithmetic
interview question
tiling
conditional probability
np
reduction
sat
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
×