Discrete Mathematics: Chapter 4 Algorithms

Flashcards covering key definitions, characteristics, algorithms (text search, insertion sort, recursion), and asymptotic analysis from Chapter 4: Algorithms.

What is an algorithm and what are its key characteristics?

An algorithm is a finite set of instructions characterized by: input, output, precision, deterministic execution, finiteness, correctness, and generality.

What does the "deterministic" characteristic of an algorithm mean?

The results of each step of execution are uniquely defined and depend only on the inputs and the results of preceding steps.

What is a trace of an algorithm?

A trace is a simulation or trial run that checks the algorithm using specific input values.

In pseudocode, what does the assignment statement "$x = y$" signify?

It means "copy the value of $y$ into $x$".

For an input sequence of size $n$, how many loop iterations are performed in Algorithm 4.1.2 (Finding the Maximum Value in a Sequence)?

The loop is always executed $n - 1$ times, making the worst-case, best-case, and average-case times each equal to $n - 1$.

What value does Algorithm 4.2.1 (Text Search) return if the pattern $p$ does not occur in text $t$?

It returns $0$.

In Algorithm 4.2.1 (Text Search), why is the outer loop upper bound set to $n - m + 1$?

Because index $n - m + 1$ is the last possible starting position in $t$ where a substring of length $m$ can fit.

What algorithm and inputs are being traced in this diagram?

A trace of Algorithm 4.2.1 (Text Search) searching for the pattern "001" in the text "010001", which successfully returns index $i = 4$.

For what size of sequences is insertion sort considered one of the fastest sorting algorithms?

Small sequences of fewer than $50$ items.

What is the state of the subsequence $s_1, \text{...}, s_i$ at the $i$-th iteration of insertion sort?

The first part of the sequence, $s_1, \text{...}, s_i$, has been rearranged so that it is sorted.

What is the analysis of an algorithm?

The process of estimating the time and space needed to execute an algorithm.

Why is an algorithm that examines all subsets of a set of size $n$ impractical for large $n$?

A set with $n$ elements has $2^n$ subsets, requiring at least $2^n$ units of time, which grows too rapidly as $n$ increases.

What are the definitions of best-case, worst-case, and average-case execution times?

Best-case time is the minimum execution time for inputs of size $n$; worst-case time is the maximum execution time for inputs of size $n$; and average-case time is the average execution time across inputs of size $n$.

What is the formal definition of $f(n) = O(g(n))$?

There exist two positive constants $c$ and $n_0$ such that $|f(n)| \le c\,|g(n)|$ for all $n \ge n_0$.

According to the polynomial theorem for Big O, what is the asymptotic upper bound of $A(n) = a_m n^m + \dots + a_1 n + a_0$?

$A(n) = O(n^m)$.

What is the formal definition of the asymptotic lower bound $f(n) = \Omega(g(n))$?

There exists a positive constant $C_2$ such that $|f(n)| \ge C_2\,|g(n)|$ for all but finitely many $n$.

When is a function $f(n)$ said to be of order $\Theta(g(n))$?

When $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$, meaning $g(n)$ is an asymptotic tight bound for $f(n)$.

Why is the expression $3n + 2$ not $O(1)$?

Because $3n + 2$ is not less than or equal to any constant $c$ for all $n$.

What is a recursive algorithm?

An algorithm that contains a recursive function, which is a function that invokes itself.

What is the base case in Algorithm 4.4.2 (Computing $n$ Factorial)?

When $n == 0$, where the function returns $1$.

What recurrence relation calculates the number of ways a robot can walk $n\text{ meters}$ using only $1\text{-meter}$ and $2\text{-meter}$ steps?

$\text{walk}(n) = \text{walk}(n - 1) + \text{walk}(n - 2)$ for $n > 2$, with base cases $\text{walk}(1) = 1$ and $\text{walk}(2) = 2$.

How is the Fibonacci sequence $f_1, f_2, \dots$ recursively defined?

$f_1 = 1$, $f_2 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n > 3$.

What botanical phenomenon related to Fibonacci numbers is displayed in this figure?

Spiral phyllotaxis on a pine cone, consisting of $13$ clockwise spirals and $8$ counterclockwise spirals, reflecting Fibonacci numbers that optimize seed distribution.