Design Analysis R1

What is an algorithm?

A well-defined computational procedure that takes input, performs a finite sequence of steps, and produces output.

What are the two main issues related to algorithms?

How to design algorithms and how to analyze their efficiency.

What resources can algorithm analysis consider?

Time, memory, communication bandwidth, energy, and other computational resources.

What is a data structure?

A scheme for organizing related data so it can be accessed and modified efficiently.

What is an array?

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

What is a linked list?

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

What does LIFO mean?

Last In, First Out; the behavior of a stack.

What operations are associated with a stack?

Push inserts at the top and pop removes from the top.

What does FIFO mean?

First In, First Out; the behavior of a queue.

What operations are associated with a queue?

Enqueue adds at the rear and dequeue removes from the front.

What is a priority queue?

A structure that supports inserting items and accessing/removing the highest-priority item.

What structure commonly implements a priority queue efficiently?

A heap.

What is a graph G=(V,E)?

A set V of vertices and a set E of edges connecting pairs of vertices.

What is an undirected edge?

An edge where (u,v) is equivalent to (v,u).

What is a directed edge?

An edge with direction from a tail vertex to a head vertex.

What is a weighted graph?

A graph whose edges have numerical weights or costs.

What are the two common graph representations?

Adjacency matrix and adjacency list.

What is a cycle?

A positive-length path that starts and ends at the same vertex without traversing the same edge more than once.

What is an acyclic graph?

A graph containing no cycles.

What is a tree?

A connected acyclic graph.

What is a forest?

An acyclic graph whose connected components are trees.

What is input size?

A parameter measuring how large an algorithm's input is, such as n elements or |V| and |E| for a graph.

What is an algorithm's basic operation?

The operation that contributes most to running time, usually because it is executed most often.

How is time efficiency analyzed theoretically?

By counting how many times the basic operation executes as a function of input size.

What is worst-case analysis?

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

What is best-case analysis?

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

What is average-case analysis?

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

Is average case the average of best and worst case?

No. It is an expected value based on a probability model for inputs.

Why is worst-case analysis important?

It provides an upper bound and is often easier and more useful to guarantee.

Insertion sort best-case complexity?

Theta(n), when the input is already sorted.

Insertion sort worst-case complexity?

Theta(n^2), such as reverse-sorted input.

Insertion sort average-case complexity?

Theta(n^2).

Sequential search best case?

1 comparison.

Sequential search worst case?

n comparisons, Theta(n).

Average successful comparisons for sequential search when positions are equally likely?

(n+1)/2.

Maximum-element scan complexity?

Theta(n), with n-1 comparisons.

Element uniqueness by comparing all pairs complexity?

Theta(n^2).

Number of unordered pairs among n items?

n(n-1)/2.

Standard matrix multiplication complexity?

Theta(n^3).

Counting binary digits by repeated division by 2 complexity?

Theta(log n).

What does Big-O describe?

An asymptotic upper bound.

Formal Big-O condition?

f(n)

What does Big-Omega describe?

An asymptotic lower bound.

Formal Big-Omega condition?

f(n) >= c g(n) for all n >= n0 for some positive c and suitable n0.

What does Big-Theta describe?

A tight asymptotic bound: both an upper and lower bound.

Formal Big-Theta condition?

c2 g(n)

What does lim f(n)/g(n)=0 imply about growth?

f grows asymptotically more slowly than g.

What does lim f(n)/g(n)=c>0 imply?

f and g have the same order of growth, so f is Theta(g).

What does lim f(n)/g(n)=infinity imply?

f grows asymptotically faster than g.

Growth rates from slowest to fastest?

1 < log n < sqrt(n) < n < n log n < n^2 < n^3 < 2^n < n!.

Why can constants and lower-order terms be ignored asymptotically?

The highest-growth term dominates as n becomes large.

What is Stirling's formula used for?

Approximating factorial growth, n! approximately sqrt(2 pi n)(n/e)^n.

Complexity of a loop that increments by 1 until n?

Theta(n).

Complexity of a loop that increments by 2 until n?

Theta(n).

Complexity of a loop that doubles its variable until n?

Theta(log n).

Complexity of a loop that repeatedly halves n?

Theta(log n).

Complexity of two independent nested n loops?

Theta(n^2).

Complexity of n outer iterations with log n inner iterations?

Theta(n log n).

What is 1+2+…+n?

n(n+1)/2, which is Theta(n^2).

If 1+2+…+k reaches n, what is k asymptotically?

Theta(sqrt(n)).

What is recursion?

A technique where a function calls itself to solve a smaller instance of the same problem.

What is a base case?

A condition that stops further recursive calls.

What is a recursive case?

The part of a recursive function that reduces the problem and calls itself again.

What happens if recursion has no reachable base case?

The call stack can grow until a stack overflow or recursion-depth error occurs.

Recursive definition of factorial?

F(n)=nF(n-1), with F(0)=1.

Work recurrence for recursive factorial multiplications?

M(n)=M(n-1)+1 with M(0)=0.

Complexity of recursive factorial?

Theta(n).

What is memoization?

Caching results of solved subproblems to avoid repeated computation.

Why is naive recursive Fibonacci inefficient?

It recomputes the same subproblems many times.

Naive recursive Fibonacci complexity in the course?

Exponential, approximately Theta(phi^n).

Iterative Fibonacci complexity?

Theta(n).

General first step in recursive analysis?

Choose a parameter indicating input size.

What do you write to analyze recursive running time?

A recurrence relation with an initial condition.

What is backward substitution?

Repeatedly expanding a recurrence until a pattern appears and then applying the base condition.

Solve T(n)=T(n-1)+n, T(1)=1 asymptotically.

Theta(n^2).

Solve T(n)=nT(n-1), T(1)=1 asymptotically.

Theta(n!).

Solve T(n)=T(n/3)+1 asymptotically.

Theta(log n).

Solve T(n)=2T(n-1)+1 asymptotically.

Theta(2^n).

Tower of Hanoi recurrence?

M(n)=2M(n-1)+1 with M(1)=1.

Tower of Hanoi exact number of moves?

2^n - 1.

Tower of Hanoi complexity?

Theta(2^n).

What is brute force?

A straightforward strategy that directly tries possibilities or uses the simplest obvious method rather than advanced optimization.

Why can brute force still be useful?

It is simple, widely applicable, useful for small inputs, and provides a baseline for better methods.

How does selection sort work?

Repeatedly find the smallest item in the unsorted portion and swap it into the next final position.

Selection sort complexity?

Theta(n^2) for all input arrangements in the presented algorithm.

How does bubble sort work?

Repeatedly compare adjacent items and swap out-of-order pairs, bubbling large items toward the end.

Bubble sort complexity in the presented version?

Theta(n^2).

How does brute-force string matching work?

Align the pattern at each possible text position and compare characters left to right until match or mismatch.

Worst-case brute-force string matching complexity?

O(nm) for text length n and pattern length m.

Closest-pair brute-force complexity?

Theta(n^2), because every pair of points is checked.

What is exhaustive search?

A brute-force strategy that generates candidate solutions, evaluates them, and selects a valid or optimal one.

Why does exhaustive search become impractical?

The candidate set often grows exponentially or factorially.

How many subsets exist for n items?

2^n.

Exhaustive 0/1 knapsack candidate count?

2^n subsets.

How many permutations exist for n items?

n!.

Exhaustive assignment-problem candidate count?

n! assignments.

What is the traveling salesman problem?

Find a minimum-cost tour visiting every city once and returning to the start.

Why is exhaustive TSP expensive?

It considers a factorial number of city orderings.

What data structure does DFS use?

A stack, explicitly or through recursive calls.

What is the main behavior of DFS?

Explore as deeply as possible before backtracking.