Chapter 4

Compute the 36th triangular number. (It is the so-called beastly number.)

Show that it takes \(O\left(n^{2}\right)\) additions to compute the sum of two square matrices of order \(n .\)

Prove that the given predicate \(\mathrm{P}(n)\) in each algorithm is a loop invariant. Algorithm exponential \((x, n)\) (" This algorithm computes\(x^{n},\) where \(x \in \mathbb{R}^{+}\) and \(n \in W .^{*} )\)

Using the big-oh notation, estimate the growth of each function. $$f(n)=2 n+3$$

Express each number in base 10 . $$ 1101_{\mathrm{two}} $$

Is the set of positive odd integers well-ordered?

Prove that the given predicate \(P(n)\) in each algorithm is a loop invariant. Algorithm exponent ial \((x, n)\) (* This algori thm computes \(x^{n},\) where \(x \in \mathbb{R}^{+}\) and \(\left.n \in W .^{*}\right)\) \(0 .\) Begin \(\left(^{\star} \text { algorithm }^{\star}\right)\) 1. answer \(\leftarrow 1\) 2\. while \(n>0\) do 3\. begin \(\left(^{\star} \text { whi } 1 \text { e }^{\star}\) ) \right. 4\. answer \leftarrow answer \cdot \(x\) \(5 . \quad n \leftarrow n-1\) \(6 .\) endwhile 7\. End \(\left(^{\star} \text { algorithm }^{\star}\) ) \right. \(P(n): a_{n}=x^{n},\) where \(a_{n}\) denotes the value of answer after \(n\) iterations of the while \(100 p\)

Show that it takes \(\mathrm{O}\left(n^{2}\right)\) additions to compute the sum of two square matrices of order \(n\)

Express each number in base \(10 .\) $$1101_{\text {two }}$$

Determine if each positive integer is a prime. $$727$$

Prove that the sum of two consecutive triangular numbers is a perfect square.

Let \(A\) and \(B\) be two square matrices of order \(n\). Let \(c_{n}\) denote the number of comparisons needed to determine whether or not \(A \leq B\) Show that \(c_{n}=\mathrm{O}\left(n^{2}\right)\)

Using the big-oh notation, estimate the growth of each function. $$f(n)=4 n^{2}+2 n-3$$

Express each number in base \(10 .\) $$11011_{\text {two }}$$

Is the set of positive even integers well-ordered?

(Twelve Days of Christmas) Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. How many gifts did you send on the 12 th day of Christmas?

Let \(A\) be a square matrix of order \(n\). Let \(s_{n}\) denote the number of swappings of elements needed to find the transpose \(A^{\mathrm{T}}\) of \(A\) Find a formula for \(s_{n}\)

Using the big-oh notation, estimate the growth of each function. $$f(n)=2 n^{3}-3 n^{2}+4 n$$

Express each number in base \(10 .\) \(1776_{\text {eight }}\)

In Exercises \(3-6,\) find the quotient and the remainder when the first integer is divided by the second. $$ 137,11 $$

Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. How many gifts did you send on the 12th day of Christmas?

Find the quotient and the remainder when the first integer is divided by the second. $$137,11$$

Determine if each positive integer is a prime. $$1681$$

(Twelve Days of Christmas) Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. How many gifts did your love receive in the 12 days of Christmas? Using PMI, prove each for every integer \(n \geq 1\) .

Prove that the given predicate \(\mathrm{P}(n)\) in each algorithm is a loop invariant. Algorithm gcd \((x, y)\) (" This algorithm computes the gcd of two positive integers \(x\) and \(y .^{*}\) ) \(0 .\) Begin \((* \text { algorithm } *)\) 1\. while \(x \neq y\) do 2\. \(\quad\) if \(x>y\) then \(\begin{array}{ll}{3 .} & {x+x-y} \\ {4 .} & {\text { else }}\end{array}\) \(5 . \quad y \leftarrow y=x\) \(6 . \quad \operatorname{gcd}-x\) 7\. End \((* \text { al gorithm } *)\) \(P(n) : \operatorname{gcd}\left(x_{n}, y_{n}\right\\}=\operatorname{gcd}(x, y\\}\) where \(x_{n}\) and \(y_{n}\) denote the values of \(x\) and \(y\) at the end of \(n\) iterations of the loop.

Let \(A\) be a square matrix of order \(n .\) Let \(s_{n}\) denote the number of swappings of elements needed to find the transpose \(A^{\mathrm{T}}\) of \(A\). $$\text { Show that } s_{n}=\mathrm{O}\left(n^{2}\right)$$

Using the big-oh notation, estimate the growth of each function. $$f(n)=3+\lg n$$

Express each number in base \(10 .\) \(1976_{\text {sixteen }}\)

In Exercises \(3-6,\) find the quotient and the remainder when the first integer is divided by the second. $$ 15,23 $$

Prove that the given predicate \(P(n)\) in each algorithm is a loop invariant. Algorithm gcd(x, y) (* This al gori thm computes the gcd of two positive integers \(x\) and \(y .^{\star}\) ) \(0 .\) Begin \(\left(^{\star} \text { algorithm }^{\star}\right)\) 1\. while \(x \neq y\) do 2\. if \(x>y\) then \(3 . \quad x \leftarrow x-y\) \(4 . \quad\) else \(5 . \quad y \leftarrow y-x\) \(6 . \quad g c d \leftarrow x\) 7\. End \(\left(^{\star} \text { algorithm }^{\star}\) ) \right. \(P(n): \operatorname{gcd}\left\\{x_{n}, y_{n}\right\\}=\operatorname{gcd}\\{x, y\\}\) where \(x_{n}\) and \(y_{n}\) denote the values of \(x\) and \(y\) at the end of \(n\) iterations of the loop.

Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. How many gifts did your love receive in the 12 days of Christmas? Using PMI, prove each for every integer \(n \geq 1\).

Find the quotient and the remainder when the first integer is divided by the second. $$15,23$$

Determine if each positive integer is a prime. $$1723$$

(Twelve Days of Christmas) Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. $$ \sum_{i=1}^{n}(2 i-1)=n^{2} $$

Prove that the given predicate \(\mathrm{P}(n)\) in each algorithm is a loop invariant. Prove that the given predicate \(\mathrm{P}(n)\) in each algorithm is a loop invariant. Algorithm sum \((x, y)\) (* This algorthm prints the sum of two nonnegat ive integers \(x\) and \(y . * )\) 0\. Begin (* algorithm *) 1\. \( \operatorname{sun} \leftarrow x\) 2\. count \(\leftarrow 0(* \text { counter } *)\) 3\. while count \( < y\) do 4\. begin (* while ") 5\. \(\operatorname{sun} \leftarrow \operatorname{sun}+1\) 6\. count \(\leftarrow\) count \(+1\) 7\. endwhile 8\. End \((* \text { algorthm } *)\) \(P(n) : x=q_{n} y+r_{n},\) where \(q_{n}\) and \(r_{n}\) denote the quotient and the remainder after \(n\) iterations.

Let \(A\) be a square matrix of order \(n .\) Let \(s_{n}\) denote the number of swappings of elements needed to find the transpose \(A^{\mathrm{T}}\) of \(A .\) Show that the number of additions of two \(n\) -bit integers is \(\mathrm{O}(n).\)

Using the big-oh notation, estimate the growth of each function. $$f(n)=3 \lg n+2$$

Express each decimal number as required. $$ 1076=( \quad )_\text{Two} $$

In Exercises \(3-6,\) find the quotient and the remainder when the first integer is divided by the second. $$ -43,16 $$

Prove that the given predicate \(P(n)\) in each algorithm is a loop invariant. Algorithm sum \((x, y)\) (* This algori thm prints the sum of two nonnegative integers \(x\) and \(\left.y .^{\star}\right)\) \(0 .\) Begin \(\left(\star \text { algori thm }^{\star}\right)\) \(1 . \quad\) sum \(\leftarrow x\) 2\. count \(\leftarrow 0\) (* counter \(^{\star}\) ) 3\. while count \(<\) y do 4\. begin \(\left(^{\star} \text { while }^{\star}\right)\) \(5 . \quad \mathrm{sum} \leftarrow \mathrm{sum}+1\) \(6 . \quad\) count \(\leftarrow\) count +1 7\. endwhile 8\. End \(\left(^{\star} \text { algorithm }^{\star}\right)\) \(P(n): x=q_{n} y+r_{n},\) where \(q_{n}\) and \(r_{n}\) denote the quotient and the remainder after \(n\) i terations.

Show that the number of additions of two \(n\) -bit integers is \(\mathrm{O}(n)\)

Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. $$\sum_{i=1}^{n}(2 i-1)=n^{2}$$

Find the quotient and the remainder when the first integer is divided by the second. $$-37,73$$

(Twelve Days of Christmas) Suppose you sent your love 1 gift on the first day of Christmas, \(1+2\) gifts on the second day, \(1+2+3\) gifts on the third day and so on. $$ \sum_{i=1}^{n} i^{2}=\frac{(n+1)(2 n+1)}{6} $$

Express each decimal number as required. $$676=(\quad)_{\text {eight }}$$

In Exercises \(3-6,\) find the quotient and the remainder when the first integer is divided by the second. $$ -37,73 $$

Prove that the given predicate \(P(n)\) in each algorithm is a loop invariant. Algorithm square \((x)\) ( \(^{\star}\) This algori thm prints the square of \(x \in W\). \(^{\star}\) ) 0\. Begin ( \(^{\star}\) algorithm \(^{\star}\) ) 1\. answer \(\leftarrow 0\) \(2 . \quad i \leftarrow 0 \quad\left(^{\star} \text { counter } *\right)\) 3\. While i < x do 4\. begin \(\left(^{\star} \text { while }^{\star}\) ) \right. 5\. answer \(\leftarrow\) answer \(+(2 i+1):\) \(6 . \quad i \leftarrow i+1\) 7\. endwhile 8\. End \(\left(^{\star} \text { algorithm }^{\star}\) ) \right. \(P(n): a_{n}=n^{2},\) where an denotes the value of answer at the end of \(n\) i iterations.

Find the quotient and the remainder when the first integer is divided by the second. $$-37,73$$

Using the euclidean algorithm, find the gcd of the given integers. $$2024,1024$$

Using the big-oh notation, estimate the growth of each function. $$f(n)=\lg (5 n) !$$