Shiva Kintali's profile - overview

691 karma follow kintali

Site Adminstrator real name Shiva Kintali member since May 06 '12 last seen 6 hours ago website http://www.cs.princeton.edu/~k... location Princeton, United States todays unused votes 30 votes left

146 exercises, 3 videos, 2 notes, 0 multiple-choice questions

146 exercises

1

view

no

votes

Basics of probability

We have a fair coin and a two-headed coin. We choose one of the two coins randomly with equal probability and toss it.…

• PROBABILITY

 

• basics
• conditional-probabil...

16

views

no

votes

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 th…

• PROBABILITY

 

• sampling

2

views

no

votes

Basics of bipartite graphs

Prove the following properties of bipartite graphs : Prove that a graph $G$ is bipartite if and only if every subgraph…

• GRAPH THEORY

 

• basics
• bipartite-graph

4

views

no

votes

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 \dot…

• GRAPH THEORY

 

• bipartite-graph
• graph-union

4

views

no

votes

Self-complementary graphs

Let $G$ be a self-complementary graph (i.e., $G$ is isomorphic to its complement) on $n$ vertices. Prove that $n \equ…

• GRAPH THEORY

 

• graph-complement

3

views

no

votes

Cutting Corners

Prove that removing opposite corner squares from an $8 \times 8$ chessboard leaves a subboard that cannot be partitioned…

• GRAPH THEORY
• PUZZLES

 

• tiling

4

views

no

votes

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 th…

• ALGORITHMS
• DATA STRUCTURES

 

• sorting
• counting

5

views

no

votes

Randomized QuickSort

Consider Randomized-Quicksort operating on a sequence of $n$ distinct input numbers. Prove that the expected running t…

• ALGORITHMS
• RANDOMIZED ALGORITHMS

 

• sorting
• expectation

3

views

no

votes

Reverse a linked list

Design a $\Theta(n)$-time nonrecursive algorithm that reverses a singly linked list of $n$ elements. The algorithm shoul…

• ALGORITHMS
• DATA STRUCTURES

 

• linked-list
• linear-time-algorith...

3

views

no

votes

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 ra…

• RANDOMIZED ALGORITHMS

 

• generator

3

views

no

votes

Maximum subarray problem

Given a array $A$ of $n$ integers (containing at least one positive number), the maximum subarray problem is the task of…

• ALGORITHMS

 

• linear-time-algorith...

3

views

no

votes

Finding two elements

Design a $\Theta(n{\log}n)$-time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whe…

• ALGORITHMS

 

• sorting
• searching

1

view

no

votes

Basics of Connectivity

Prove that a connected graph $G$ with $2k$ odd vertices (odd degree vertices) decomposes into $k$ paths (not necessaril…

• GRAPH THEORY

 

• basics
• connectivity

1

view

no

votes

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…

• GRAPH THEORY

 

• basics
• hamiltonian-cycle

18

views

no

votes

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…

• GRAPH THEORY

 

• planar-graphs

21

views

no

votes

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…

• PROBABILITY

 

• conditional-probabil...

1

view

no

votes

Basics of countability

Prove that every collection of disjoint intervals (of positive length) on the real line is countable.…

• REAL ANALYSIS

 

• basics
• counting

1

view

no

votes

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$ ?…

• COMBINATORICS

 

• basics
• counting

17

views

no

votes

Basics of decidability

State whether each of the following statements are TRUE or FALSE. Your answers should be accompanied by a proof. Every…

• COMPLEXITY THEORY

 

• basics
• undecidability

21

views

no

votes

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 l…

• GRAPH THEORY

 

• matching

16

views

no

votes

Large min-degree implies cycle

Let $G$ be a simple undirected graph in which every vertex has degree $\ge k$. Prove that $G$ contains a path of lengt…

• GRAPH THEORY

 

• cycle
• path

15

views

no

votes

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…

• GRAPH THEORY

 

• matching

14

views

no

votes

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 $\Del…

• ALGORITHMS
• GRAPH THEORY

 

• bipartite-graph
• graph-algorithms

15

views

no

votes

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…

• GRAPH THEORY

 

• bipartite-graph
• matching

19

views

no

votes

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 $…

• NUMBER THEORY

 

• primes

27

views

no

votes

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 a…

• ALGORITHMS
• DATA STRUCTURES
• PROBABILITY

 

• binary-tree
• expectation

58

views

no

votes

Intersecting every line exactly twice

Prove that there is a set in $\mathbb{R}^2$ that intersects every line exactly twice.

• REAL ANALYSIS

 

• axiom-of-choice

36

views

no

votes

Infinite number of special primes

Prove that there are infinitely many primes of the form $4n-1$ and $4n+1$.

• NUMBER THEORY

 

• primes

45

views

no

votes

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…

• GRAPH THEORY

 

• treewidth

43

views

no

votes

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…

• GRAPH THEORY

 

• planar-graphs
• graph-coloring

3 videos

82

views

no

votes

The Pigeonhole Principle : Part II

Introduction to the Pigeonhole Principle.

• MATHEMATICS

 

• pigeonhole-principle

64

views

no

votes

The Pigeonhole Principle : Part I

Introduction to the Pigeonhole Principle.

• MATHEMATICS

 

• pigeonhole-principle

136

views

1

vote

Graceful Tree Conjecture

A quick introduction to Graceful Tree Conjecture.

• GRAPH THEORY

 

• graph-labeling

2 notes

104

views

no

votes

Lecture Notes in Probability

Probability lecture notes by Raz Kupferman.

• PROBABILITY

 

• expectation
• conditional-probabil...
• markov-chains
• random-variables
• statistics

67

views

no

votes

Notes on Probability

Peter Cameron's notes on probability.

• PROBABILITY

 

• expectation
• conditional-probabil...
• random-variables
• statistics

0 multiple-choice questions

26 Votes

26

0

50 Tags

12 Badges