41 items
Topic:

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

Sort By: trending ▼ date
2
Undergraduate
By Shiva Kintali on June 13, 2013 | Updated Jan. 29, 2018

Among the following sorting algorithms, which one has the least worst-case running time asymptotically ?
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 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 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 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 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 Shiva Kintali on May 19, 2013 | Updated Dec. 6, 2017

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 the number of pairs of chords that intersect inside the circle. For example, i…
0
Undergraduate
By Shiva Kintali on June 8, 2012 | Updated Dec. 6, 2017

Linear time algorithms on trees

Let \(T(V,E)\) be a tree. Design linear time (i.e., \(O(|V|)\) time) algorithms for the following problems : Find an optimal vertex cover in \(T\). Find a maximum matching in \(T\). Find a maximum i…
0
Undergraduate
By Shiva Kintali on May 19, 2013 | Updated Dec. 6, 2017

Randomized QuickSort

Consider Randomized-Quicksort operating on a sequence of \(n\) distinct input numbers. Prove that the expected running time of Randomized-Quicksort is \(O(n{\log}n)\) Prove that for any constant …
1 2 3 4 5 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