TAOCP 5.3.4: Networks for Sorting

Section 5.3.4 exercises: 6/6 solved.

6 items

Section 5.3.4. Networks for Sorting

Exercises from TAOCP Volume 3 Section 5.3.4: 6/6 solved.

#	Rating	Status	Time
1	[**]	verified	3m26s
2	[**]	solved	2m16s
3	[**]	solved	2m14s
4	[**]	solved	3m28s
5	[**]	verified	1m05s
6	[**]	solved	3m39s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.3.4: Networks for Sorting ›

TAOCP 5.3.4 Exercise 1

Let the input to the merge network be two sorted sequences of lengths $m=3$ and $n=5$: (x_1,x_2,x_3) \quad \text{and} \quad (y_1,y_2,y_3,y_4,y_5).

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.3.4: Networks for Sorting ›

TAOCP 5.3.4 Exercise 2

Let $n$ be fixed and consider Pratt’s sorting network constructed from all 3-smooth numbers d = 2^i 3^j \le n.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.3.4: Networks for Sorting ›

TAOCP 5.3.4 Exercise 3

Apply equation (5) twice, first with $(m,n)=(m,m-1)$ and then with $(m,n)=(m,m)$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.3.4: Networks for Sorting ›

TAOCP 5.3.4 Exercise 4

Let $T(6)$ denote the minimum depth of a sorting network on 6 inputs.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.3.4: Networks for Sorting ›

The odd-even merge network is composed of two independent recursive merge networks, one acting on the odd subsequences and one acting on the even subsequences, followed by a single layer of comparison...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 5.3.4: Networks for Sorting ›

TAOCP 5.3.4 Exercise 6

We work in the model where a _stage_ consists of a set of pairwise disjoint comparisons, and all comparisons in a stage are executed simultaneously.

TAOCP 5.3.4: Networks for Sorting

Section 5.3.4. Networks for Sorting

TAOCP 5.3.4 Exercise 1

TAOCP 5.3.4 Exercise 2

TAOCP 5.3.4 Exercise 3

TAOCP 5.3.4 Exercise 4

TAOCP 5.3.4 Exercise 5

TAOCP 5.3.4 Exercise 6