Algorithms and Problem Solving

Introduction to Algorithms and Problem Solving

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.

Diagram loads as you scroll.

Essential Criteria of an Algorithm

• Non-ambiguity (Definiteness): Each computational step must be clear and precisely defined.
• Range of inputs: The set of valid inputs must be clearly demarcated.
• Finiteness: For every legitimate input, the algorithm must terminate after a finite number of steps.
• Correctness: It must produce the correct output for every valid input.
• Efficiency: It should make optimal use of computing time and space resources.

---

Review of Fundamental Data Structures

Levitin organizes data structures based on how elements are arranged and accessed.

1. Linear Data Structures

Data Structure	Access Time	Insert / Delete	Typical Use Case in Algorithms
Array	$\Theta(1)$ by index	$\Theta(n)$ arbitrary position	Contiguous storage, sorting buffers, lookup tables
Singly Linked List	$\Theta(n)$ search	$\Theta(1)$ at given node	Dynamic memory allocation, chaining in hash tables
Stack (LIFO)	$\Theta(1)$ top	$\Theta(1)$ push / pop	DFS traversal, function call stack, undo operations
Queue (FIFO)	$\Theta(1)$ front	$\Theta(1)$ enqueue / dequeue	BFS traversal, task scheduling, level-order trees

2. Graphs

A graph $G = (V, E)$ consists of a set of vertices $V$ and edges $E$.

• Adjacency Matrix: An $|V| \times |V|$ 2D matrix where $A[i][j] = 1$ if $(i, j) \in E$, else $0$.
  • Space: $\Theta(|V|^2)$.
  • Check edge $(u, v)$: $\Theta(1)$.
  • Find all neighbors of $u$: $\Theta(|V|)$.
  • Best for dense graphs where $|E| \approx |V|^2$.
• Adjacency Lists: An array of $|V|$ lists, with list $i$ containing all neighbors of vertex $i$.
  • Space: $\Theta(|V| + |E|)$.
  • Check edge $(u, v)$: $\Theta(\text{deg}(u))$.
  • Find all neighbors of $u$: $\Theta(\text{deg}(u))$.
  • Best for sparse graphs where $|E| \ll |V|^2$.

3. Trees

A tree is an undirected connected graph without cycles. A rooted tree has a distinguished root vertex.

• Binary Tree: Every vertex has at most 2 children (left child and right child).
• Binary Search Tree (BST): For every node $x$, all keys in the left subtree are $< \text{key}(x)$, and all keys in the right subtree are $> \text{key}(x)$.
• Height of a Tree $h$: The length of the longest simple path from the root to a leaf node.
  • Minimal height for $n$ nodes: $\lfloor \log_2 n \rfloor$ (balanced tree).
  • Maximal height for $n$ nodes: $n - 1$ (degenerate linear chain).

---

Exercises

Exercise 1

Explain the difference between an algorithm and a heuristic. Does a heuristic qualify as an algorithm under the formal Levitin definition?

Show solution ↓Hide solution ↑

Solution

• An algorithm guarantees finding the exact correct solution for every legitimate input within a finite number of steps.
• A heuristic is a practical rule of thumb or guideline that finds good or near-optimal solutions quickly, but does not mathematically guarantee correctness or optimality in all instances.
• Under the formal definition given by Levitin, a procedure that fails to produce guaranteed correct output for all valid inputs is strictly classified as an approximation heuristic rather than a classical exact algorithm.

Exercise 2

Suppose a web crawler graph has $|V| = 50{,}000$ pages and each page links to an average of 10 other pages ($|E| = 500{,}000$). Compare the memory footprint of an Adjacency Matrix versus an Adjacency List.

Show solution ↓Hide solution ↑

Solution

1. Adjacency Matrix:

• Requires $|V|^2 = 50{,}000 \times 50{,}000 = 2{,}500{,}000{,}000$ entries ($2.5 \times 10^9$ booleans / bytes $\approx 2.5\text{ GB}$).

2. Adjacency List:

• Stores $|V| = 50{,}000$ head pointers plus $|E| = 500{,}000$ edge nodes.
• Total stored references $\approx 550{,}000$ entries ($\approx \text{a few megabytes}$).

Conclusion: The graph is extremely sparse ($|E| \ll |V|^2$). The Adjacency List uses less than 0.2% of the memory required by the Adjacency Matrix and enables neighbor exploration in $\Theta(\text{deg}(v)) \approx 10$ operations instead of scanning 50,000 matrix columns.