PCS24101 Unit1 Role of Algorithms in Computing
Uploaded by
anuragPCS24101 Unit1 Role of Algorithms in Computing
Uploaded by
anuragPCS24101 – ADVANCED DATA STRUCTURES AND ALGORITHMS
UNIT – I: ROLE OF ALGORITHMS IN COMPUTING
1.1 Introduction to Algorithms
An algorithm is a finite, well-defined sequence of computational steps that transforms input
data into output results. Each step must be precise and unambiguous, and the algorithm
must terminate after a finite number of operations. Algorithms are the logical core of
computer science; they provide the instructions that software executes to accomplish tasks,
from simple arithmetic to complex machine learning models.
Characteristics of Algorithms:
Finiteness: The algorithm must terminate after a finite number of steps.
Definiteness: Each instruction must be precisely and unambiguously defined.
Input: Zero or more inputs from a well-defined domain.
Output: At least one output that is related to the input.
Effectiveness: Each operation must be basic enough to be executed within finite time.
Examples of Classic Algorithms (short descriptions)
Euclid's Algorithm: Computes the greatest common divisor (GCD) of two integers using
repeated remainder operations.
Binary Search: Searches a sorted array by repeatedly dividing search interval in half; O(log
n) time.
Merge Sort: A divide-and-conquer sorting algorithm that guarantees O(n log n) time in
worst case.
Quick Sort: A recursive partitioning-based sort with average O(n log n) time but worst-case
O(n^2).
Dijkstra's Algorithm: Computes shortest paths from a source node to all other nodes in a
weighted graph with non-negative edges.
1.2 Analyzing Algorithms
Algorithm analysis studies the resources consumed by an algorithm as a function of input
size. The primary resources considered are time (number of primitive operations) and
space (amount of memory used). Analysis can be theoretical (asymptotic) or empirical
(measured experimentally).
Time Complexity
Time complexity is typically expressed in terms of n, the size of the input. We consider best-
case, average-case, and worst-case complexities. Worst-case complexity is most commonly
used to provide guarantees.
Example: Linear Search
Pseudocode:
for i = 1 to n:
if A[i] == key:
return i
return -1
Complexities: Best-case O(1), Worst-case O(n)
Space Complexity
Space complexity accounts for the memory used by the algorithm, including input storage,
extra variables, and the call stack. Example: Merge Sort requires O(n) auxiliary space, while
in-place Quick Sort uses O(log n) stack space on average.
Empirical vs Theoretical Analysis
Empirical analysis measures runtime on specific hardware and input distributions.
Theoretical analysis uses asymptotic notations to reason about growth independent of
hardware. Both are valuable: theory guides design, experiments validate practice.
1.3 Algorithm Design Paradigms
Effective algorithm design relies on a set of powerful paradigms. Here are the most
important ones practiced in advanced computing.
Divide and Conquer: Split the problem into smaller subproblems, solve them recursively,
and combine the results. Examples: Merge Sort, Quick Sort.
Dynamic Programming: Solve problems with overlapping subproblems by storing
intermediate solutions (memoization or tabulation). Example: Sequence alignment, Matrix
Chain Multiplication.
Greedy Algorithms: Make the best local choice at each step with the hope of finding a
global optimum. Example: Kruskal's algorithm for MST.
Backtracking: Systematically search for solutions and backtrack when a partial solution
cannot lead to a valid full solution. Example: N-Queens, Sudoku.
Branch and Bound: Search with pruning based on bounds to eliminate subtrees that
cannot contain optimal solutions. Example: Branch and Bound for TSP.
Randomized Algorithms: Use random choices to simplify logic or improve expected
performance. Example: Randomized Quick Sort.
1.4 Growth of Functions and Asymptotic Notations
Comparing algorithms uses asymptotic notation to describe growth as n → ∞. These
notations abstract away constant factors and low-order terms.
Big O (O): Upper bound. f(n) = O(g(n)) if there exist constants c, n0 such that f(n) ≤ c·g(n)
for all n ≥ n0.
Omega (Ω): Lower bound. f(n) = Ω(g(n)) if there exist constants c, n0 such that f(n) ≥
c·g(n) for all n ≥ n0.
Theta (Θ): Tight bound. f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)).
Little o (o): f(n) = o(g(n)) iff lim_{n→∞} f(n)/g(n) = 0.
Little ω (ω): f(n) = ω(g(n)) iff lim_{n→∞} f(n)/g(n) = ∞.
Common growth rates: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).
1.5 Solving Recurrences
Divide-and-conquer algorithms often satisfy recurrence relations. Three principal methods
to solve them are: substitution, recursion-tree, and the Master Theorem.
Substitution Method
Guess a solution form and prove it by induction. Example: T(n) = 2T(n/2) + n; guess T(n) =
O(n log n) and apply induction to establish an upper bound.
Recursion Tree Method
Represent the recurrence as a tree where each node's value is the cost of a single
subproblem. Sum across levels to obtain total cost. For T(n)=2T(n/2)+n each level costs n
and the tree has log n levels, giving Θ(n log n).
Recursion tree (textual):
Level 0: n
Level 1: 2 × (n/2) = n
Level 2: 4 × (n/4) = n
...
Depth: log n
Total: n log n
Master Theorem
For recurrences T(n) = aT(n/b) + f(n), the Master Theorem gives asymptotic bounds based
on comparison between f(n) and n^{log_b a}.
Cases:
Case 1: If f(n) = O(n^{log_b a - ε}) for some ε > 0, then T(n) = Θ(n^{log_b a}).
Case 2: If f(n) = Θ(n^{log_b a}), then T(n) = Θ(n^{log_b a} log n).
Case 3: If f(n) = Ω(n^{log_b a + ε}) and regularity condition holds, then T(n) = Θ(f(n)).
Example: T(n) = 2T(n/2) + n ⇒ a=2, b=2, n^{log_b a} = n ⇒ f(n)=n ⇒ Case 2 ⇒ T(n)=Θ(n log
n)
1.6 Algorithm Correctness
Correctness requires demonstrating that an algorithm produces the desired output for all
valid inputs. Proof techniques include mathematical induction, loop invariants, and
contradiction. Partial correctness shows correctness if the algorithm terminates; total
correctness additionally proves termination.
Loop invariant example (Insertion Sort):
Invariant: At the start of each outer loop iteration, the subarray A[1..i] consists of the
elements originally in A[1..i] but in sorted order.
Initialization, Maintenance, Termination steps formally prove correctness.
1.7 Complexity Classes
Complexity classes organize problems by computational difficulty. Most relevant are P, NP,
NP-Complete, and NP-Hard.
P: problems solvable in polynomial time. NP: solutions verifiable in polynomial time. NP-
Complete: hardest problems in NP; if any NP-Complete problem is in P, then P=NP. NP-
Hard: at least as hard as NP problems, not necessarily in NP.
1.8 Iterative vs Recursive Algorithms
Iterative algorithms use explicit loops, whereas recursive algorithms call themselves on
smaller inputs. Recursion often leads to simpler expressions for divide-and-conquer
strategies but involves additional stack space.
Example: Factorial (iterative and recursive).
Iterative:
fact = 1
for i from 1 to n:
fact = fact * i
return fact
Recursive:
function fact(n):
if n == 0: return 1
else: return n * fact(n-1)
1.9 Empirical Case Studies and Practical Considerations
When applying algorithms in real systems, consider hidden constants, cache behavior,
memory allocation costs, and input characteristics.
Case study: Sorting 1 million records
- Bubble sort is infeasible due to O(n^2).
- Merge sort requires stable O(n log n) time and predictable performance.
- Quicksort often outperforms other methods due to low constants, but worst-case behavior
must be mitigated (randomized pivot).
1.10 Problem Types and Reductions
Problems can be decision, search, optimization, or enumeration. Reductions map one
problem to another to show relative difficulty—crucial for NP-Completeness proofs.
Example reduction sketch: 3-SAT to CLIQUE shows how satisfiability can be transformed
into graph problems.
1.11 Best Practices in Algorithm Design
1. Start with a correct brute-force solution and iteratively optimize.
2. Use invariants and proofs to ensure correctness before optimizing.
3. Profile before optimizing: identify real bottlenecks.
4. Prefer algorithms with provable guarantees for critical systems.
5. Document assumptions about input distributions.
1.12 Worked Examples and Derivations
Worked Example 1: Solve T(n) = 3T(n/3) + n
Here a=3, b=3 ⇒ n^{log_b a} = n. f(n)=n ⇒ Case 2 ⇒ T(n)=Θ(n log n).
Worked Example 2: T(n) = 4T(n/2) + n^2
a=4, b=2 ⇒ n^{log_b a} = n^{log_2 4} = n^2. f(n)=n^2 ⇒ Case 2 ⇒ T(n)=Θ(n^2 log n).
Worked Example 3: Binary Search recurrence T(n) = T(n/2) + O(1) ⇒ a=1, b=2 ⇒ n^{log_b
a} = n^0 = 1. f(n)=1 ⇒ Case 2 (since f(n)=Θ(1)) ⇒ T(n)=Θ(log n).
1.13 Sample Questions (University Examination)
PART A: Short Answer (10 × 2 = 20 marks)
Define algorithm and list its properties.
Differentiate between best-case and worst-case complexity.
State the Master Theorem.
What is a loop invariant? Give an example.
Explain the difference between P and NP.
List three algorithm design paradigms.
What is amortized analysis?
Explain the recursion-tree method in brief.
What is dynamic programming?
Why is randomized quicksort preferred in practice?
PART B: Descriptive (5 × 12 = 60 marks)
6. Explain the role of algorithms in modern computing and discuss time-space trade-offs
with examples.
7. Derive the solution of T(n) = 2T(n/2) + n using recursion-tree and Master Theorem.
8. Describe dynamic programming and solve the Longest Common Subsequence problem
with pseudocode.
9. Compare and contrast Divide-and-Conquer, Greedy and Dynamic Programming
paradigms with suitable examples.
10. Prove correctness of insertion sort using loop invariants and analyze its time
complexity.
References and Further Reading
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms
(3rd ed.). MIT Press.
