170 exercises

Search tip: add tags and a query to focus your search

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

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

13

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

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

15

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

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

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

3

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

122

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

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

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

17

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

98

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

20

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

18

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

16

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

20

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

14

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

13

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

14

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

26

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

57

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