Data & Analysis

What is an algorithm?

A well-defined computational procedure that takes input, produces output, and finishes in a finite amount of time.

What are the two main issues related to algorithms?

How to design algorithms and how to analyze algorithm efficiency.

What does analysis of algorithms mean?

Predicting the resources an algorithm requires, such as memory and computational time.

What are the two main efficiency measures emphasized in algorithm analysis?

Time efficiency and space efficiency.

How is time efficiency measured?

By counting how many times the algorithm's basic operation is executed as a function of input size.

How is space efficiency measured?

By counting the extra memory units consumed by the algorithm as a function of input size.

Why is actual clock time not the best way to analyze an algorithm?

It depends on the computer speed, implementation quality, compiler, and difficulty of accurately measuring runtime.

What is an algorithm's basic operation?

The operation that contributes most to running time, usually one executed most frequently.

For searching a list of n items, what is the input size and basic operation?

Input size: n, the number of items. Basic operation: key comparison.

For a typical graph problem, how is input size commonly measured?

By the number of vertices and/or edges.

What is the general plan for analyzing a nonrecursive algorithm?

Choose input size n; identify the basic operation; determine best, average, and worst cases if needed; set up a sum for the number of basic operations; simplify the sum.

What is worst-case efficiency?

The maximum number of basic operations among all inputs of size n.

What is best-case efficiency?

The minimum number of basic operations among all inputs of size n.

What is average-case efficiency?

The expected number of basic operations for inputs of size n under an assumed probability distribution.

Is average-case efficiency just the average of best case and worst case?

No. It is an expected value based on a probability distribution over possible inputs.

For sequential search, what is the best case?

The search key is the first element, so Cbest(n) = 1.

For the maximum-element algorithm on an array, what is the basic operation?

The comparison A[i] > maxval.

For the maximum-element algorithm on n items, how many comparisons are made?

n - 1 comparisons.

What identity is Euclid's algorithm based on?

gcd(m,n) = gcd(n, m mod n).

When does Euclid's algorithm stop?

When the second number becomes 0; then the first number is returned as the gcd.

Compute gcd(60,24) using Euclid's algorithm.

gcd(60,24) = gcd(24,12) = gcd(12,0) = 12.

What is the main idea of the Sieve of Eratosthenes?

Start with integers 2 through n and eliminate multiples of each remaining prime candidate. The numbers left are prime.

What three asymptotic notations are used to compare orders of growth?

O (Big-O), Ω (Big-Omega), and Θ (Big-Theta).

What does Big-O describe?

An asymptotic upper bound. t(n) is in O(g(n)) if t(n) ≤ c·g(n) for all sufficiently large n.

What does Big-Omega describe?

An asymptotic lower bound. t(n) is in Ω(g(n)) if t(n) ≥ c·g(n) for all sufficiently large n.

What does Big-Theta describe?

A tight asymptotic bound. t(n) is in Θ(g(n)) when it is bounded both above and below by constant multiples of g(n) for sufficiently large n.

What is an intuitive meaning of Θ(n²)?

The running time is roughly proportional to n² when n is large.

What are the major efficiency classes from better growth to worse growth?

1, log n, n, n log n, n², n³, 2ⁿ, n!.

How does n² change when n doubles?

It becomes 4 times as large: (2n)² = 4n².

How does n³ change when n doubles?

It becomes 8 times as large: (2n)³ = 8n³.

How does log₂ n change when n doubles?

It increases by 1 because log₂(2n) = 1 + log₂ n.

What does lim t(n)/g(n) = 0 mean for order of growth?

t(n) grows more slowly than g(n).

What does lim t(n)/g(n) = c, where c > 0, mean?

t(n) and g(n) have the same order of growth.

What does lim t(n)/g(n) = ∞ mean?

t(n) grows faster than g(n).

What asymptotic class do logarithms with any fixed base greater than 1 belong to?

Θ(log n).

What asymptotic class does a polynomial of degree k with positive leading coefficient belong to?

Θ(n^k).

What is the time complexity of repeatedly dividing n by 2 until reaching 1?

Θ(log₂ n), usually written Θ(log n).

What is an array?

A sequence of same-type items stored contiguously in memory and accessed using an index.

What is a linked list?

A sequence of nodes containing data and one or more pointers to other nodes.

What is a stack?

A list where insertions and deletions happen only at the top; it follows LIFO, last in first out.

What is a queue?

A structure where elements are added at the rear and removed from the front; it follows FIFO, first in first out.

What is a priority queue?

A collection that supports selecting the highest-priority item, deleting it, and adding new items.

What data structure is commonly used as a better implementation of a priority queue?

A heap.

What is a graph?

A set of vertices (nodes) together with a set of edges connecting pairs of vertices.

What is a tree?

A connected acyclic graph.

What is a forest?

An acyclic graph that is not necessarily connected; each connected component is a tree.

What is a rooted tree?

A tree with one designated root, usually shown at level 0, with vertices organized into levels below it.

What is a binary tree?

An ordered tree in which each vertex has at most two children, designated left and right.