2-butterfly derangement

The hallmark of the Cooley-Tukey algorithm for  Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(NlogN). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].

Three butterflies – FFT flow graph, shuffling network, and a nonblocking interconnect

Advertisements

Maximum weighted independent set – connected component

Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight.

Maximum weighted independent set – singletons and forest

Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.

1. At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
2. Any two restaurants must be at least 2 miles apart.

Generalized heaps

Min-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.

Rational numbers in decimal

In decimal representation, rational numbers either terminate after a finite number of digits or produce a repeating sequence. Conversely, any repeating decimal can be converted into a rational number e.g. (10 * 0.333.. – 0.333…) / 9 = 1/3.

IP possibilities

A problem I was asked: suppose a file that stored many valid IPv4 addresses was corrupted such that all dot in the addresses were removed. Given such a corrupt IP, infer all possible corresponding IP addresses. For example, given 12345, all possible addresses are: 12.3.4.5, 1.23.4.5, 1.2.34.5 and 1.2.3.45. The hint that recursion should be used made the problem easier:

Sorting primer

A quick overview of several important comparison-based sorting algorithms:

Sorting technique	Time (avg)	Time (worst)	Memory
Insertion sort	O(N^2)	O(N^2)	O(1)
Heap sort	O(NlgN)	O(NlgN)	O(1)
Merge sort	O(NlgN)	O(NlgN)	O(N)
Quick sort	O(NlgN)	O(n^2)	O(lgN)