TAOCP 3.1: Introduction

Section 3.1 exercises: 23/23 solved.

23 items

Section 3.1. Introduction

Exercises from TAOCP Volume 2 Section 3.1: 23/23 solved.

#	Rating	Category	Status	Time
1	▶ [20]	medium	verified	1m06s
2	[M22]	math-medium	solved	3m12s
3	[10]	simple	verified	3m58s
4	[20]	medium	verified	3m22s
5	[15]	simple	verified	1m03s
6	▶ [M21]	math-medium	verified	1m41s
7	▶ [**]		verified	2m46s
8	[**]		solved	5m47s
9	[**]		verified	1m07s
10	[**]		verified	4m11s
11	▶ [**]		verified	2m58s
12	[**]		solved	4m27s
13	[**]		verified	3m50s
14	[**]		verified	2m55s
15	[**]		verified	1m11s
16	[**]		solved	4m40s
17	[**]		verified	1m22s
18	[**]		verified	2m03s
19	[**]		verified	1m18s
20	[**]		solved	9m12s
21	[**]		verified	2m48s
22	[**]		verified	1m24s
23	▶ [**]		solved	5m57s

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 1

A suitable method for obtaining a decimal digit at random is one that produces each of the digits $0,1,\dots,9$ with equal probability and independently of prior choices.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 2

The proposed solution answers the question being asked.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 3

In the middle-square method with a fixed length of $10$ digits, we begin with x=1010101010.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 4

Step K11 of Algorithm K is the normalization step.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 5

Algorithm K, as described in Section 3.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 6

Since each $X_n$ lies in the set ${0,1,\ldots,m-1}$, there are only $m$ possible values.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 7

Let $X_0, X_1, X_2, \ldots$ be a sequence generated by $X_{n+1} = f(X_n)$, where $f$ maps a finite set ${0, 1, \dots, m-1}$ into itself.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 8

Let f(x)=\left\lfloor \frac{x^{2}}{10}\right\rfloor \bmod 100, so that $f(x)$ is the middle two digits of the four-digit representation of $x^{2}$.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 9

Suppose we are generating a sequence of $2n$-digit numbers in base $b$ by the middle-square method.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 10

**Exercise 3.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 11

Let $S=\{0,1,\dots,m-1\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 12

**Exercise 3.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 13

Let $L_m$ denote the length of the longest cycle in a random mapping $f:\{1,\ldots,m\}\to\{1,\ldots,m\}$, chosen uniformly from the $m^m$ possible functions.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 14

Let $C(f)$ denote the number of distinct final cycles of a mapping $f$ on an $m$-element set $M=\{1,\ldots,m\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 15

Suppose $f$ is a random function from a set of $m$ elements to itself, as in exercise 11.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 16

**Exercise 3.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 17

In the generalized scheme, each term is determined by the preceding $k$ values: X_{n+1}=f(X_n,X_{n-1},\ldots,X_{n-k+1}), where $0\le X_i<m$.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 18

Suppose a sequence is generated by a function $f$ of the preceding $k$ values, as in exercise 17.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 19

Let $Y_n=(X_n,X_{n-1},\ldots,X_{n-k+1}).$ Then $Y_n$ ranges over the $m^k$ possible $k$-tuples, and the recurrence $X_{n+1}=f(X_n,\ldots,X_{n-k+1})$ induces a function $Y_{n+1}=F(Y_n)$

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 20

Solution to TAOCP 3.1 Exercise 20.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 21

The proposed disproof is invalid.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 22

Using the sequence $f(0), f(1), f(2), \ldots$ where $f$ is a random function is not a practical way to generate random numbers.

Practice › Mathematics › TAOCP › TAOCP Vol 2: Seminumerical Algorithms › TAOCP 3.1: Introduction ›

TAOCP 3.1 Exercise 23

**Exercise 3.