167 exercises

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

26

views

no

votes

Turan geometry

Let $x_1, x_2, \dots, x_n$ be a set of diameter one in the plane. Prove that the maximum number of pairs of points at di…

• GEOMETRY
• GRAPH THEORY

 

• extremal-graph-theor...

163

views

5

votes

Vertex cover using DFS

Consider the following algorithm for Vertex Cover of a graph $G$ : Run depth first search (DFS) on $G$. Output the ver…

• APPROXIMATION ALGORITHMS
• GRAPH THEORY

 

• vertex-cover

28

views

no

votes

SONET ring loading

Consider a telephone network that consists of a cycle on $n$ nodes, numbered $0$ through $n-1$ clockwise around the cycl…

• APPROXIMATION ALGORITHMS

 

• networks

33

views

1

vote

Volley planning

Suppose there are n soldiers in a row who want to fire at the same time. Each of them has a constant memory and can only…

• PUZZLES

 

• communication-comple...

76

views

no

votes

Primality is in NP $\cap$ co-NP

Primality is the following problem : Given a positive integer $n$, is $n$ prime ? Note that the size of the input…

• COMPLEXITY THEORY
• NUMBER THEORY

 

• primes

82

views

1

vote

Truthteller and Liar

You played a long role-playing treasure-hunting game for several hours and finally reached end of the last level of the…

• PUZZLES

 

• logic-puzzle

59

views

1

vote

A well known triangle

Let $ABC$ be an acute-angled triangle. Find points $X, Y, Z$ on sides $BC, CA$ and $AB$ such that the perimeter of the t…

• GEOMETRY

 

• optimization

46

views

no

votes

Togglers and Truthtellers

There are five people. Four of them are togglers, and the fifth person is a truthteller. A toggler tells either the…

• PUZZLES

 

• logic-puzzle

144

views

1

vote

100 perfect logicians

100 perfect logicians are told to sit in a circle in a room. Before they enter the room, they are told at least one pers…

• PUZZLES

 

• logic-puzzle

81

views

1

vote

The power of the majority function

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
• self-dual-function

131

views

1

vote

Gas stations in a circle

There are $n$ gas stations located on a circular route. Together they contain exactly enough gas to make one trip around…

• PUZZLES

 

• counting

137

views

1

vote

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

• PUZZLES

 

• math-puzzle

69

views

1

vote

Separator number of a tree

Let $T(V,E)$ be a tree with $|V| = n$ vertices. Let $W$ be a subset of $V$. Prove that there is a vertex $v \in V$ suc…

• ALGORITHMS
• GRAPH THEORY

 

• trees

82

views

2

votes

Complete balanced binary trees are graceful

Label the vertices of a tree (with $n$ vertices) with integers from $1$ to $n$. Now label each edge with the absolute di…

• GRAPH THEORY

 

• graph-labeling

91

views

2

votes

Row of Coins

There are 50 coins arranged in a line on a tabletop. The coins are of various denominations. You choose a coin from one…

• PUZZLES

 

• game-puzzle

177

views

2

votes

Unmatchable edges of bipartite graphs

Prove that the following algorithm finds the unmatchable edges of a bipartite graph $G$ (edges that aren't in any perfec…

• GRAPH THEORY

 

• matching
• bipartite-graph

94

views

1

vote

Integral Rectangles

A large rectangle is partitioned into smaller rectangles, each of which has either integer height or integer width or bo…

• GEOMETRY
• PUZZLES

 

• math-puzzle

68

views

1

vote

Coloring Planar Graphs

Prove that every planar graph has at least one vertex of degree at most five. Conclude that planar graphs are six-color…

• GRAPH THEORY

 

• planar-graphs
• eulers-formula

44

views

1

vote

Degree sequence is reconstructible

Given a graph $G(V,E)$, a vertex-deleted subgraph of $G$ is a subgraph formed by deleting exactly one vertex from $G$. F…

• GRAPH THEORY

 

• graph-reconstruction

74

views

2

votes

Coloring graphs with odd cycles

Let $G$ be a graph where every two odd cycles have at least a vertex in common. We call such graphs nicely-odd graphs.…

• GRAPH THEORY

 

• graph-coloring

137

views

1

vote

Top K elements in a read only array

Given a read only array of $n$ integers, find the $k$ largest numbers in the array in $O(n)$ time possibly using $O(k)$…

• ALGORITHMS

 

• linear-time-algorith...

37

views

no

votes

Recognizing bipartite k-extendable graphs

A graph $G$ is $k$-extendable, where $k \geq 1$ is an integer, if every matching of size at most $k$ is a subset of a pe…

• ALGORITHMS
• GRAPH THEORY

 

• matching

70

views

2

votes

Linear time tree isomorphism

Let $T_1 (V_1,E_2)$ and $T_2(V_2,E_2)$ be two undirected unlabeled trees. Design a linear-time algorithm to decide if…

• ALGORITHMS
• GRAPH THEORY

 

• graph-isomorphism
• trees
• linear-time-algorith...

98

views

1

vote

Minimum makespan problem

Minimum makespan scheduling problem : You are given $n$ jobs and $m$ identical machines. You are given processing times…

• APPROXIMATION ALGORITHMS

 

• scheduling

66

views

no

votes

Triangle avoidance game

A triangle avoidance game consists of two players (say $A$ and $B$) beginning with an empty graph on $n$ vertices. The t…

• GRAPH THEORY
• PUZZLES

 

• game-puzzle

65

views

1

vote

Cycle in k-connected graphs

Prove that every $k$-connected graph ($k > 1$) on at least $2k$ vertices has a cycle of length at least $2k$.

• GRAPH THEORY

 

• connectivity

49

views

1

vote

Linear recursion relations

Let $a_n$ denote the Fibonacci sequence $a_0 = 0$, $a_1 = 1$, $a_n = a_{n−1} + a_{n−2}$. Let $b_n = (a_n)^2$. Prove th…

• PUZZLES

 

• recursion

56

views

no

votes

Testing Endianness

Write a C program to determine whether a machine's byte order is big endian or little endian.…

• PROGRAMMING

 

• c-language

65

views

1

vote

Diameter of a tree

Let $T(V, E)$ be a tree given as an adjacency list. For vertices $u, v \in V$, let $d(u, v)$ denote the length of the pa…

• ALGORITHMS
• GRAPH THEORY

 

• linear-time-algorith...
• trees

79

views

2

votes

Edge coloring bipartite graphs

Prove the following : If $G$ is a regular bipartite graph, then $G$ has a perfect matching. If $G$ is $k$-regular bip…

• GRAPH THEORY

 

• graph-coloring
• edge-coloring