TAOCP 2.2.1: Stacks, Queues, and Deques
Section 2.2.1 exercises: 14/14 solved.
Section 2.2.1. Stacks, Queues, and Deques
Exercises from TAOCP Volume 1 Section 2.2.1: 14/14 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [06] | simple | solved | - |
| 2 | [15] | simple | verified | 32s |
| 3 | [25] | medium | solved | - |
| 4 | [M34] | math-hard | solved | - |
| 5 | [M28] | math-hard | solved | - |
| 6 | [00] | immediate | solved | - |
| 7 | [25] | medium | solved | - |
| 8 | [22] | medium | solved | - |
| 9 | [M20] | math-medium | solved | - |
| 10 | [M25] | math-medium | solved | - |
| 11 | [M40] | math-project | verified | 1m12s |
| 12 | [HM34] | hm-hard | solved | - |
| 13 | [M48] | math-research | solved | - |
| 14 | [26] | hard | solved | - |
TAOCP 2.2.1 Exercise 1
Yes.
TAOCP 2.2.1 Exercise 2
We are asked to determine whether the permutations $325641$ and $154623$ of six railroad cars numbered $1,2,3,4,5,6$ can be obtained using a single stack in the manner of Fig.
TAOCP 2.2.1 Exercise 3
Let a sequence consist of the symbols `S` and `X`, where `S` means "move the next car from the input into the stack" and `X` means "move the top car from the stack into the output.
TAOCP 2.2.1 Exercise 4
Let $a_n$ denote the number of permutations of ${1,2,\ldots,n}$ obtainable by a stack of the type described in exercise 2.
TAOCP 2.2.1 Exercise 5
Let $p_1p_2\ldots p_n$ be a permutation of $1,2,\ldots,n$.
TAOCP 2.2.1 Exercise 6
With a queue, the first item inserted is always the first item removed.
TAOCP 2.2.1 Exercise 7
We consider permutations of $1234$ obtained by using deques, either input-restricted or output-restricted, following the definitions in Section 2.
TAOCP 2.2.1 Exercise 8
Let $p = p_1 p_2 \ldots p_n$ be a permutation of $12\ldots n$, and let $D$ be a deque that is neither input- nor output-restricted.
TAOCP 2.2.1 Exercise 9
We denote by $b_n$ the number of permutations on $n$ elements obtainable with an input-restricted deque.
TAOCP 2.2.1 Exercise 10
We are asked to define the concept of an _admissible_ sequence of the symbols $S$, $Q$, and $X$ for an output-restricted deque, in such a way that every permutation of $n$ elements obtainable with the...
TAOCP 2.2.1 Exercise 11
Let $b_n$ denote the number of permutations of $1,2,\ldots,n$ obtainable with an input-restricted deque.
TAOCP 2.2.1 Exercise 12
Let $a_n$ denote the number of permutations obtainable with a stack, as defined in Exercise 4, and let $b_n$ denote the number of permutations obtainable with an input-restricted deque, equivalently w...