Suggested languages for you:

Americas

Europe

Q14E

Expert-verified
Found in: Page 370

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Give a recursive algorithm for finding a mode of a list of integers. (A mode is an element in the list that occurs at least as often as every other element.)

The recursive algorithm is,

$\mathrm{procedure}mod\left({\mathrm{a}}_{1},{\mathrm{a}}_{2},\dots ,{\mathrm{a}}_{\mathrm{n}}:\mathrm{integers}\mathrm{with}\mathrm{n}\ge 1\right)\phantom{\rule{0ex}{0ex}}\mathrm{L}:=\left\{{\mathrm{a}}_{1},{\mathrm{a}}_{2},\dots ,{\mathrm{a}}_{\mathrm{n}}\right\}\phantom{\rule{0ex}{0ex}}\mathrm{if}\mathrm{n}=1\mathrm{then}\phantom{\rule{0ex}{0ex}}\mathrm{return}{\mathrm{a}}_{1}\phantom{\rule{0ex}{0ex}}\mathrm{else}\phantom{\rule{0ex}{0ex}}\begin{array}{r}\mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{n}}\right\}\phantom{\rule{1em}{0ex}}\mathrm{k}:=1\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}=1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{i}}\right\}\phantom{\rule{1em}{0ex}}\mathrm{k}:=\mathrm{k}+1\end{array}\phantom{\rule{0ex}{0ex}}\mathrm{if}\mathrm{k}=\mathrm{n}\mathrm{then}\phantom{\rule{0ex}{0ex}}\mathrm{return}{\mathrm{a}}_{\mathrm{n}}\phantom{\rule{0ex}{0ex}}\mathrm{else}\phantom{\rule{0ex}{0ex}}\begin{array}{r}\mathrm{x}:=\mathrm{mod}\left(\mathrm{L}\right)\phantom{\rule{1em}{0ex}}\mathrm{m}:=0\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}-1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{m}:=\mathrm{m}+1\\ \text{if}\mathrm{k}\ge \mathrm{m}\text{then}\\ \text{return}{\mathrm{a}}_{\mathrm{n}}\end{array}\phantom{\rule{0ex}{0ex}}\mathrm{else}\phantom{\rule{0ex}{0ex}}\mathrm{return}\mathrm{x}$

See the step by step solution

## Step 1: Describe the given information

The objective is to write the recursive algorithm for finding a mode of a list of integers.

## Step 2: Give a recursive algorithm for computing finding a mode of a list of integers

Call the algorithm "mod" and the input is a list of integers.

$\text{procedure}mod\left({a}_{1},{a}_{2},\dots ,{a}_{n}\text{: integers with}n\ge 1\right)$

When the list contains only 1 integer, then the mode is the remaining integer.

$\mathrm{L}:=\left\{{\mathrm{a}}_{1},{\mathrm{a}}_{2},\dots ,{\mathrm{a}}_{\mathrm{n}}\right\}\phantom{\rule{0ex}{0ex}}\mathrm{if}\mathrm{n}=1\mathrm{then}\phantom{\rule{0ex}{0ex}}\mathrm{return}{\mathrm{a}}_{1}$

If the list contains more than 1 value, then check, if the last value in the list is repeated somewhere in the list. Remove this value along with all other repetitions of the value form the list, while represents the number of values that were deleted. If , then all elements in the list were deleted and therefore, there should be return of ${a}_{n}$. Otherwise, apply the algorithm to determine the mode of the reduced list,

which occurs times. If k > m , then ${a}_{m}$ is the mode. If k < m, then the mode is the mode of the reduced list.else

$\begin{array}{r}\mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{n}}\right\}\phantom{\rule{1em}{0ex}}\mathrm{k}:=1\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}=1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{i}}\right\}\phantom{\rule{1em}{0ex}}\mathrm{k}:=\mathrm{k}+1\end{array}$

And,

$\begin{array}{r}\mathrm{x}:=\mathrm{mod}\left(\mathrm{L}\right)\phantom{\rule{1em}{0ex}}\mathrm{m}:=0\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}-1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{m}:=\mathrm{m}+1\\ \text{if}\mathrm{k}\ge \mathrm{m}\text{then}\\ \text{return}{\mathrm{a}}_{\mathrm{n}}\\ \text{else}\\ \text{return}\mathrm{x}\end{array}$

By combining all the steps, the required algorithm will be as follows.

$\mathrm{procedure}mod\left({\mathrm{a}}_{1},{\mathrm{a}}_{2},\dots ,{\mathrm{a}}_{\mathrm{n}}:\mathrm{integers}\mathrm{with}\mathrm{n}\ge 1\right)\phantom{\rule{0ex}{0ex}}\mathrm{L}:=\left\{{\mathrm{a}}_{1},{\mathrm{a}}_{2},\dots ,{\mathrm{a}}_{\mathrm{n}}\right\}\phantom{\rule{0ex}{0ex}}\mathrm{if}\mathrm{n}=1\mathrm{then}\phantom{\rule{0ex}{0ex}}\mathrm{return}{\mathrm{a}}_{1}\phantom{\rule{0ex}{0ex}}\mathrm{else}\phantom{\rule{0ex}{0ex}}\begin{array}{r}\mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{n}}\right\}\phantom{\rule{1em}{0ex}}\mathrm{k}:=1\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}=1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{i}}\right\}\phantom{\rule{1em}{0ex}}\mathrm{k}:=\mathrm{k}+1\end{array}\phantom{\rule{0ex}{0ex}}\mathrm{if}\mathrm{k}=\mathrm{n}\mathrm{then}\phantom{\rule{0ex}{0ex}}\mathrm{return}{\mathrm{a}}_{\mathrm{n}}\phantom{\rule{0ex}{0ex}}\mathrm{else}\phantom{\rule{0ex}{0ex}}\begin{array}{r}\mathrm{x}:=\mathrm{mod}\left(\mathrm{L}\right)\phantom{\rule{1em}{0ex}}\mathrm{m}:=0\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}-1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{m}:=\mathrm{m}+1\\ \text{if}\mathrm{k}\ge \mathrm{m}\text{then}\\ \text{return}{\mathrm{a}}_{\mathrm{n}}\end{array}\phantom{\rule{0ex}{0ex}}\mathrm{else}\phantom{\rule{0ex}{0ex}}\mathrm{return}\mathrm{x}$

Therefore, the recursive algorithm is shown above.