• Exercises
  • Multiple Choice
  • Articles
  • Open Problems
  • Login
41 items
Topic:
  • Algorithms x

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 ?
  • Computer Science
  • Algorithms
  • sorting
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…
  • Computer Science
  • Algorithms
  • dynamic programming
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…
  • Computer Science
  • Mathematics
  • Algorithms
  • Graph Theory
  • trees
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.
  • Computer Science
  • Mathematics
  • Algorithms
  • Graph Theory
  • linear time algorithms
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 …
  • Computer Science
  • Mathematics
  • Algorithms
  • Graph Theory
  • hamiltonian cycle
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…
  • Computer Science
  • Mathematics
  • Algorithms
  • Graph Theory
  • counting
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…
  • Computer Science
  • Algorithms
  • amortized analysis
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…
  • Computer Science
  • Algorithms
  • Data Structures
  • counting
  • sorting
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…
  • Computer Science
  • Mathematics
  • Algorithms
  • Graph Theory
  • independent set
  • linear time algorithms
  • matching
  • trees
  • vertex cover
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 …
  • Computer Science
  • Algorithms
  • Randomized Algorithms
  • expectation
  • sorting
1 2 3 4 5 next page »
  • icon Sign In or Sign Up
  • icon Invite Friends
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

  • Articles
  • Open Problems
  • Exercises
  • Multiple-Choice Questions

Levels

  • High school
  • Undergraduate
  • Graduate

Subjects

  • Mathematics
  • Computer Science
  • Puzzles
  • Optimization

Trending tags

  • trees
  • dynamic programming
  • polynomials
  • infinite series
  • digraphs
  • fermats little theorem
  • asymptotic analysis
  • differentiation
  • integration
  • jee

Topics

  • Algebra
  • Algorithms
  • Approximation Algorithms
  • Calculus
  • Combinatorial Optimization
  • Combinatorics
  • Complexity Theory
  • Data Structures
  • Discrete Mathematics
  • Game Theory
  • Geometry
  • Graph Theory
  • Linear Algebra
  • Linear Programming
  • Logic
  • Mathematical Analysis
  • Mathematics
  • Matrix Theory
  • Number Theory
  • Optimization
  • Probability
  • Programming
  • Puzzles
  • Randomized Algorithms
  • Real Analysis
  • Trigonometry
Home
Team Terms of Service Privacy Policy Careers Contact Us
Tags Topics IIT JEE Problems International Mathematical Olympiad
Twitter Instagram Slack Telegram
Social learning platform. © 2016 True Group Inc. All Right Reserved