Algorithms and Analysis

Study Notes

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

Description

Learn about optimization techniques and strategies for creating algorithms, as well as evaluating their efficiency in terms of time and space usage. Understand brute force, divide and conquer, greedy approach, dynamic programming, iterative improvement, and backtracking methods.