• Exercises
  • Multiple Choice
  • Articles
  • Open Problems
  • Login
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…
  • 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 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 …
  • Computer Science
  • Mathematics
  • Complexity Theory
  • Graph Theory
  • Logic
  • np
  • reduction
  • sat
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…
  • Puzzles
  • Puzzles
  • polynomials
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 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…
  • Mathematics
  • Graph Theory
  • bipartite graph
  • matching
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 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…
  • Computer Science
  • Complexity Theory
  • formal languages
1 2 3 ... 15 16 17 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

  • imo
  • imo 2016
  • polygon
  • jee
  • jee 2016
  • jee advanced
  • jee mathematics
  • pyramid
  • sorting
  • summation

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