167 exercises

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

1

view

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

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

4

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

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

16

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

17

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

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

17

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

12

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

12

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

12

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

13

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

17

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

24

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

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

99

views

1

vote

Busy beavers and undecidability

A single tape Turing machine $M = \langle Q, \Gamma, \epsilon, \Sigma, \sigma, q_0, {q_{H}} \rangle$ with alphabet $\Sig…

• COMPLEXITY THEORY

 

• busy
• beavers
• undecidability

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

62

views

no

votes

Characterizing outerplanar graphs

A graph is outerplanar if it is isomorphic to a plane graph such that every vertex is incident with the unbounded face.…

• GRAPH THEORY

 

• planar-graphs

90

views

no

votes

Hadwiger’s conjecture and Random graphs

A random graph $G(n, \frac{1}{2})$ on $n$ vertices, is obtained by starting with a set of $n$ and adding every possible…

• GRAPH THEORY

 

• graph-coloring
• random-graphs