CSE310 Exam Review

Comprehensive Study Guide

Modules 1, 2, and 6 - Algorithm Analysis Fundamentals

1

Problems & Algorithms

Core definitions, algorithm properties, and complexity analysis fundamentals

2

Asymptotic Notations

Big O, Omega, Theta notations and summation analysis techniques

6

Decision Trees & Sorting

Tree construction, lower bound proofs, and algorithm comparison

Course Overview

Module 1: Problems, Instances, Solutions, Algorithms

Core definitions Algorithm properties Complexity analysis

Module 2: Asymptotic Notations

Big O, Ω, Θ Summations Function analysis

Module 6: Decision Trees & Sorting Lower Bound

Tree construction Lower bound proof Algorithm comparison

Module 1: Fundamental Definitions

Problem

A general computational question to be answered, specified as a relationship between input and desired output

Examples:

Sorting: arrange n numbers in non-decreasing order
Searching: find target element in a collection
Graph traversal: find path between vertices
String matching: locate pattern in text

Instance

A specific case of a problem with concrete input data

Examples:

Sort array [3, 1, 4, 2]
Find 7 in [2, 5, 7, 9, 12]
Find path from A to D in specific graph

Solution

The correct answer to a specific problem instance

Examples:

[1, 2, 3, 4]
Index 2
Path: A→B→D

Algorithm

A finite sequence of unambiguous instructions for solving any instance of a problem

Examples:

Merge Sort
Binary Search
Dijkstra's Algorithm

Algorithm Properties & Requirements

✓

Correctness

Produces the correct output for every valid input

Verified through proof by induction, loop invariants, or formal verification methods

⏹

Finiteness

Must terminate after a finite number of steps

Proven by showing that some measure decreases with each iteration

📋

Definiteness

Each step must be precisely and unambiguously defined

No ambiguous operations or undefined behaviors allowed

📥

Input

Zero or more quantities that are externally supplied

Input specification must be clear and complete

📤

Output

One or more quantities with specified relation to inputs

Output specification must define success conditions

Time & Space Complexity Analysis

Time Complexity

Measure of how an algorithm's running time scales with input size n

Worst-case: Maximum time over all inputs of size n

Best-case: Minimum time over all inputs of size n

Average-case: Expected time over all inputs of size n

Analysis: Count primitive operations, focus on asymptotic growth

Space Complexity

Measure of how memory usage scales with input size n

Auxiliary space: Extra space used by algorithm

Total space: Input space + auxiliary space

Analysis: Count variables, data structures, recursion stack

Example: Linear Search

for i = 1 to n:
  if A[i] == x:
    return i
return -1
                        

Time Analysis: T(n) = O(n) - may check all elements

Space Analysis: S(n) = O(1) - only uses constant extra variables

Practice Problem Set 1: Algorithm Analysis

Problem:

Analyze the following recursive algorithm:

Mystery(A, n):
if n ≤ 1: return A[1]
mid = ⌊(left + right) / 2⌋
maxLeft = Mystery(A[1...⌊n/2⌋], ⌊n/2⌋)
maxRight = Mystery(A[⌊n/2⌋+1...n], ⌈n/2⌉)
return max(maxLeft, maxRight)
                            

a) What problem does this algorithm solve?

b) Write the recurrence relation for time complexity

c) Solve the recurrence using Master Theorem

Solution:

Part A: This algorithm finds the maximum element in an array using divide-and-conquer approach

Part B: T(n) = 2T(n/2) + O(1)
Base case: T(1) = O(1)

Part C: Using Master Theorem: a=2, b=2, f(n)=O(1)
log₂(2) = 1, and f(n) = O(n⁰)
Since 0 < 1, this is Case 1: T(n) = Θ(n¹) = Θ(n)

Practice Problem Set 2: Asymptotic Analysis

Problem:

For each function, determine the tightest asymptotic bound:

a) f₁(n) = 5n³ + 3n² - 100n + 50

b) f₂(n) = n²log₂(n) + n√n + 1000

c) f₃(n) = 2^(log₂ n) + (log₂ n)²

d) f₄(n) = ∑(i=1 to n) ∑(j=i to n) 1

Solutions:

Part A: f₁(n) = Θ(n³)
The cubic term 5n³ dominates for large n

Part B: f₂(n) = Θ(n²log n)
n²log n grows faster than n^1.5 = n√n

Part C: f₃(n) = Θ(n)
2^(log₂ n) = n, and n dominates (log₂ n)²

Part D: f₄(n) = Θ(n²)
∑(i=1 to n) (n-i+1) = ∑(k=1 to n) k = n(n+1)/2 = Θ(n²)