141 exercises with kintali's contributions

Search tips: start over - to expand, or dig in by adding more tags and revising the query.

1

view

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

no

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

2

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

2

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

1

view

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...

2

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

2

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...

118

views

no

votes

Number of inversions

Let $A$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i,j)$ is called an inve…

• PROBABILITY

 

• expectation

2

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

Let $G$ be any 3-connected graph, and let $e_1, e_2, e_3$ be 3 edges of $G$ such that (i) no two have a common endpoint…

• GRAPH THEORY

 

• 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

 

• hamiltonian-cycle

62

views

1

vote

Embedding complete bipartite graphs

Prove that for every surface $S$ there exists an integer $t$ such that $K_{3,t}$ does not embed in $S$. What is the min…

• GRAPH THEORY

 

• graph-embedding

15

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

97

views

no

votes

Basics of Perfect Graphs

A perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique…

• GRAPH THEORY

 

• perfect-graphs
• bipartite-graph
• chordal-graph
• graph-coloring
• interval-graph

15

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

 

• 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

 

• counting

15

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

13

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

 

• undecidability

16

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

11

views

no

votes

Large min-degree implies cycle

Let $G$ be a simple undirected graph where each vertex has degree $\ge k$ (where $k \geq 2$). Prove that $G$ contains…

• GRAPH THEORY

 

• cycle

11

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

10

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

12

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

23

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

56

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

153

views

1

vote

Random Intervals

There are $n$ points on a line. These points are paired up at random to form $n/2$ intervals. Prove that the probabili…

• PROBABILITY
• PUZZLES

 

• counting

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

72

views

no

votes

Basics of Treewidth

Treewidth of an undirected graph $G$ measures how close $G$ is to a tree. A tree decomposition of a graph $G(V, E)$ is…

• GRAPH THEORY

 

• treewidth