Extra Credit Linear Time Algorithms
19 Aug 2008
Some problems below are easy while others are offered as "extra credit" problems in Introductory Algorithms courses. Try to minimize the amount of extra space utilized, and try not to destroy the input by treating it as read-only. Hope you have fun!
Largest Rectangle in a Matrix

Given an n by n matrix with zeros and ones, find the largest sub-matrix full of ones in O(n2) time.

Duplicate Integer in an Array

Given an array of size n+1 whose entries are integers in the range [1, n], find an integer that occurs two or more times. Use only O(1) space and treat the input as read-only. Solution.

Scorpion Problem

A scorpion is an undirected graph with 3 special vertices: the sting, the tail, and the body. The sting has degree one and is connected to the tail. The tail has degree two and is connected to the sting and the body. The body has degree n - 2 and is connected to all vertices except the sting. The other vertices may be arbitrarily connected with each other. Identify if a given graph is a scorpion or not.

Euler Tour

Find an Euler tour in an undirected graph, where an Euler tour is a closed circuit using all the edges of the graph.

Bottleneck Spanning Tree

Given an undirected graph, identify the 'Bottleneck Spanning Tree' of an undirected graph, which is defined to be any spanning tree that minimizes the weight of the heaviest edge used in the tree. In the usual 'Minimum Spanning Tree' problem, the sum of weights is minimized.

2-SAT

Find a satisfying assignment to variables in a 3-SAT formula where each clause has at most two literals.

Working Computer

A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible. Solution.

Given the head of a linked list, identify if it contains a loop or not. Solution.

2-Coloring

There are n persons at a party. Each person knows at most 3 other persons at the party. Split the party into two groups so that each person knows at most one other person within the group (s)he belongs to.

Maximum Sub-Array

Given an array with integers, find the sub-array with the maximum sum.

Gray Code for Fibonacci Sequences

The number of binary strings of length k such that two 1's are never adjacent in any string equals the k-th Fibonacci number. Further, these strings can be ordered to form a Gray code, which means that successive strings differ in only one position. For example, a Gray code for 3-bit strings is 100 101 001 000 010. The goal is to identify the starting string and then enumerate these positions in time proportional to the number of strings.

Random Permutation

Randomly permute an array of integers.