Algorithms and Analysis

Algorithms

• Simple ideas can be too slow, and algorithms require optimization
• There is no generic procedure to create algorithms, but there are design techniques and strategies such as:
  • Brute force
  • Divide and conquer
  • Greedy approach
  • Dynamic programming
  • Iterative improvement
  • Backtracking

Analysis of Algorithms

• Definition: Evaluating and comparing algorithms in terms of resource usage (time and space)
• Objective: Choosing the most efficient algorithm for a given problem
• Approaches: Theoretical analysis and Empirical analysis

Theoretical Analysis

• Time efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input size
• Basic operation: The operation that contributes most towards the running time of the algorithm
• T(n) ≈ copC(n), where T(n) is the running time, and C(n) is the number of times the basic operation is executed

Input Size and Basic Operation

• Examples of input size measures and basic operations for different problems:
  • Searching for a key in a list of n items: n, key comparison
  • Multiplication of two matrices: matrix dimensions or total number of elements, multiplication of two numbers
  • Checking primality of a given integer n: n’s size (number of digits in binary representation), division
  • Typical Graph problem: #vertices and/or edges, visiting a vertex or traversing an edge

Empirical Analysis

• Select a specific sample of inputs
• Use physical unit of time (e.g., milliseconds) or count actual number of basic operation’s executions
• Analyze the empirical data

Best-case, Average-case, Worst-case

• Efficiency depends on the form of input
• Worst case: maximum over inputs of size n
• Best case: minimum over inputs of size n
• Average case: "average" over inputs of size n

Formulas for Basic Operation’s Count

• Exact formula: e.g., C(n) = n(n-1)/2
• Formula indicating order of growth with specific multiplicative constant: e.g., C(n) ≈ 0.5 n2
• Formula indicating order of growth with unknown multiplicative constant: e.g., C(n) ≈ cn2

Order of Growth

• Most important: Order of growth within a constant multiple as n→∞
• Example: How much faster will an algorithm run on a computer that is twice as fast?

Running-Time Calculations

• Example 1: Calculate σ𝑁 𝑖=1 𝑖 3
• Example 2: Calculate the number of basic operations inside the inner loop

Arrays

• Definition: Contiguous area of memory consisting of equal-size elements indexed by contiguous integers
• Features:
  • Constant-time Access: array_address + element_size x ( i )

Multi-Dimensional Arrays

• Definition: array_address + element_size x ((i)x(j))
• Example: (3) x 8 + (5)

Array Operations

• Times for common operations:
  • Beginning: O(n) for add, O(1) for remove and modify
  • End: O(1) for add, remove, and modify
  • Middle: O(n) for add and remove, O(1) for modify