161 exercises
Level:
 UNDERGRADUATE

Start over - to expand, or dig in by adding more tags and revising the query.

Sort By: trending ▼ date
2
Undergraduate
By JeffE on June 6, 2012 | Updated Dec. 6, 2017

Longest increasing digital subsequence

Let \(S[1..n]\) be a sequence of integers between \(0\) and \(9\). A digital subsequence of \(S\) is a sequence \(D[1..k]\) of integers such that each integer \(D[i]\) is the numerical value of a sub…
0
Undergraduate
By rizwanhudda on Aug. 24, 2012 | Updated Dec. 6, 2017

Second Minimum spanning tree

Given an weighted undirected graph \( G = (V, E)\), and \(w : E \mapsto R^+\). Let T be MST i,e minimum spanning tree of graph G. Second MST is a Tree T' different from T, and its weight is less t…
0
Undergraduate
By John Doe on Nov. 3, 2012 | Updated Dec. 6, 2017

Direct reduction from Graph Homomorphism to SAT

The decision problem \(GraphHomo\) is defined as follows: \(GraphHomo = \{\langle G, H\rangle \mid \text{there is a graph homomorphism from G to H}\}\) Give a direct reduction from \(GraphHomo\) to …
0
Undergraduate
By neeldhara on Aug. 1, 2012 | Updated Dec. 6, 2017

Determining a polynomial

Let \(p\) be a polnyomial with natural coefficients. An oracle can evaluate \(p\) at any value you like. Can you determine all the coefficients by making two queries to the oracle? Note: You are free…
0
Undergraduate
By Chandra Chekuri on July 29, 2012 | Updated Dec. 6, 2017

Simple path containing three given nodes

Let \(G=(V,E)\) be an undirected graph. Describe a linear time algorithm that given \(G\) and three distinct nodes \(u,v,w\) decides whether there is a simple path in \(G\) that contains all of them.
0
Undergraduate
By diego on June 8, 2012 | Updated Dec. 6, 2017

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 two consecutive vertices is at most \(3\). Moreover, show that this can be …
0
Undergraduate
By Chandra Chekuri on July 29, 2012 | Updated Dec. 6, 2017

Diameter and low-degree vertex

Let \(G = (V,E)\) be an undirected connected graph. Suppose \(G\) has a pair of nodes \(s,t\) that are distance \(d\) apart. Show that there is a vertex \(v\in G\) such that the degree of \(v\) is at…
0
Undergraduate
By diego on June 27, 2012 | Updated Dec. 6, 2017

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 perfect matching): find a perfect matching in \(G\), orient the unmatched edges from…
0
Undergraduate
By JeffE on June 7, 2012 | Updated Dec. 6, 2017

Maintaining fitstrings

Every non-negative integer can be represented as the sum of distinct positive Fibonacci numbers. (As a warmup exercise, prove this claim!) In other words, instead of a string of bits, we can represe…
0
Undergraduate
By domotorp on June 11, 2012 | Updated Dec. 6, 2017

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 over a finite alphabet the language of non-double words is context-free. (Context…
1 2 3 ... 15 16 17 next page »
Post Something
x

Select What You'd Like To Post

POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION

Content Types

Social learning platform. © 2016 True Group Inc. All Right Reserved