170 exercises

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

80

views

2

votes

The cube of a connected graph is hamiltonian

Prove that the vertices of any connected graph $G$ can be listed in a cyclic order so that the distance in $G$ of every…

• ALGORITHMS
• GRAPH THEORY

 

• hamiltonian-cycle

20

views

no

votes

Minimum SetClique Completion Problem

Let $1,2,...,n$ be a universe of $n$ elements. Let $S_1,S_2,\dots,S_m$ be $m$ subsets of this universe. You are allowed…

• COMPLEXITY THEORY

 

• NP-completeness

100

views

no

votes

Minimum edge cover vs Maximum matching

An edge cover of a graph $G(V,E)$ is a subset $F \subseteq E$ of edges such that every node is incident to at least one…

• GRAPH THEORY
• LINEAR PROGRAMMING

 

• edge-cover
• matching
• reduction

30

views

no

votes

Linear inequalities satisfied with equality

Let $Ax \leq b$ be a system of linear inequalities. Describe a linear program to determine which inequalities among $Ax…

• LINEAR PROGRAMMING

 

• optimization

91

views

no

votes

Termination of Ford-Fulkerson algorithm

Give an example of a directed graph with real numbers for edge capacities (as opposed to integer numbers) where the Ford…

• ALGORITHMS

 

• max-flow

34

views

no

votes

Basics of Pfaffians

Let $G(V,E)$ be an undirected graph. An orientation of $G$ is Pfaffian if every even cycle $C$ such that $G \setminus V(…

• GRAPH THEORY

 

• basics
• pfaffian

26

views

no

votes

Card shuffling using pairwise-swapping

You are given a deck of $n$ cards. In each step you select two cards independently and uniformly at random and swap thei…

• RANDOMIZED ALGORITHMS

 

• random-walk
• coupling
• canonical-paths

40

views

no

votes

Efficient cash register

You have a cash register that contains coins of denominations $1 = d_{1} < d_{2} < \dots < d_{n}$. The registe…

• ALGORITHMS

 

• dynamic-programming

63

views

1

vote

Size of monotone circuits

Prove that there is a monotone boolean function $f(x_{1}, x_{2},\dots,x_{n})$ such that any circuit (consisting of only…

• COMPLEXITY THEORY

 

• circuit-complexity
• monotone-function
• lower-bound

42

views

no

votes

Parity is non-monotone

A boolean function $f(x_{1},x_{2},\dots,x_{n})$ is called monotone if it can be written as a formula with only the AND a…

• LOGIC

 

• monotone-function

36

views

1

vote

Expanding expressions

You are given an algebraic expression $E$ having variables, addition, multiplication and parenthesis. Your goal is to r…

• PUZZLES

 

• convergence

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

 

• basics
• treewidth

89

views

1

vote

Banana-eating Camel

You have 3,000 bananas that must be transported across a desert that is 1,000 kilometers wide. You have a camel that has…

• PUZZLES

 

• counting

65

views

1

vote

Find the faulty Ball

There are 12 balls. They all look alike but one of them is faulty; it weights differently. It is not known, if this ball…

• PUZZLES

 

• counting

48

views

no

votes

Stick triangle

A stick is broken at random into three pieces. What is the probability that the pieces can form a triangle?

• GEOMETRY
• PROBABILITY
• PUZZLES

 

• math-puzzle

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

79

views

1

vote

Non-double words form a context-free language

Define double words whose first and second half is the same, e.g. baba or aaaa but not abba, bab or bababa. Prove that o…

• COMPLEXITY THEORY

 

• formal-languages

37

views

no

votes

Solving Discrete-logarithm

Consider the following problem : Given a $y$ such that $0 < y < p$, where $p$ is a prime number, find an $x$ (…

• ALGORITHMS
• NUMBER THEORY

 

• primes

83

views

1

vote

Subset Sum vs Partition

Consider the following problems : Partition problem : Given a collection of $n$ integers $a_1, a_2, \ldots, a_n$, is…

• ALGORITHMS

 

• reduction
• NP-completeness

41

views

1

vote

Hamiltonian cycles in odd graphs

Let $G$ be a graph such that all vertices of $G$ have odd degree. Let $e$ be any edge of $G$. Prove that there are an…

• GRAPH THEORY

 

• hamiltonian-cycle

70

views

1

vote

Basics of Pigeonhole Principle

Prove the following : Given $n$ integers, some nonempty subset of them has sum divisible by $n$. Let $A$ be a set of $…

• MATHEMATICS

 

• basics
• pigeonhole-principle
• counting

24

views

no

votes

Ramsey Number upper bound

The Ramsey Number $R(s, t)$ is the minimum integer $n$ for which every red-blue coloring of the edges of a complete grap…

• GRAPH THEORY

 

• pigeonhole-principle

166

views

2

votes

Corrupted linked-list

You are given a pointer to the head of singly linked list. Usually, each node in the list only has a pointer to the next…

• ALGORITHMS
• PUZZLES

 

• linked-list

101

views

no

votes

Secret salaries

Three coworkers (A,B,C) would like to know their average salary. How can they achieve this without revealing their own s…

• PUZZLES

 

• math-puzzle

31

views

no

votes

Connectivity of cubic graphs

Prove that if $G$ is 3-regular graph, then its vertex-connectivity equals its edge-connectivity.

• GRAPH THEORY

 

• connectivity

53

views

no

votes

Left move is decidable

Consider the problem of determining whether a Turing machine on an input $w$ ever attempts to move its head left at any…

• COMPLEXITY THEORY

 

• turing-machine

84

views

1

vote

L shaped tiling

Consider a $2^n × 2^n$ board with one (arbitrarily chosen) square removed, as in the following figure for $n = 3$. Prove…

• PUZZLES

 

• induction

45

views

1

vote

Trees in a graph

Let $k \geq 1$ be an integer, and let $T$ be a tree on $k+1$ vertices. Show that if a graph $G$ has minimum degree at le…

• GRAPH THEORY

 

• trees

41

views

no

votes

Matching saturating high degree vertices

Let $G$ be a bipartite multigraph and let $\Delta$ be its maximum degree. Prove that $G$ has a matching saturating every…

• GRAPH THEORY

 

• matching
• bipartite-graph

31

views

no

votes

Edge connectivity vs Strong connectivity

A directed graph $D$ is strongly connected if and only if $\forall$ $u,v$ there exists a directed path from $u$ to $v$.…

• GRAPH THEORY

 

• connectivity