1. Review of Data Structures and Algorithms¶

Review of Asymptotic Analysis and Complexity ¹¶

Algorithm complexity:
- It is something designed to compare two algorithms at the idea level ignoring low-level details such as the implementation programming language, the hardware the algorithm runs on, or the instruction set of the given CPU.
- Complexity analysis is also a tool that allows us to explain how an algorithm behaves as the input grows larger.
- So if we’ve measured our program’s behavior for a small input, we can get a good idea of how it will behave for larger inputs.
Asymptotic behavior:
- First, we’ll drop all the terms that grow slowly and only keep the ones that grow fast as n becomes larger (e.g. constants).
- Second, we’ll ignore is the constant multiplier in front of n.
- Asymptotic behavior is dropping all factors and keeping only the largest growing term.
Complexity:
- Any program that doesn’t have any loops will have f( n ) = 1, since the number of instructions it needs is just a constant.
- Any program with a single loop which goes from 1 to n will have f( n ) = n.
- Two nested loops within each other, we’ll have an asymptotic behavior described by f( n ) = n^2.
- A loop within a loop within a loop yields f( n ) = n^3.
- Two nested loops followed by a single loop is asymptotically the same as the nested loops alone, because the nested loops dominate the simple loop.
Theta notation:
- It represents the average case scenario of an algorithm (tight bound).
- It gives the actual growth rate of the function we’re analyzing.
- Examples:
  - \(n^6 + 3n \in \theta(n^6)\)
  - \(2^n + 12 \in \theta(2^n)\)
  - \(3^n + 2^n \in \theta(3^n)\)
  - \(n^n + 2^n \in \theta(n^n)\)
- Hence, theta contains all the functions that grow at the same rate as the function we’re analyzing.
O notation:
- O notation, represents the worst-case scenario of an algorithm (upper bound).
- Hence, \(O > \theta\), hence:
  - \(O(n) > \theta(n)\)
  - \(O(n^2) > \theta(n^2)\)
  - \(O(n^3) > \theta(n^3)\)
- O is always worse than theta.
- An algorithm of \(\theta(n)\) is also \(O(n^2)\) or even \(O(n^3)\) as the worst-case scenario is not determined, and we may found a case where the algorithm behaves worse than the average case.
- It’s easier to figure out the O-complexity of an algorithm than its Θ-complexity.
Omega notation \(\Omega\):
- \(\Omega\) notation, represents the best-case scenario of an algorithm (lower bound).
- The algorithm can’t be better than the best-case scenario.
Hence, Notations:
- Lower bound: \(\Omega\).
- Average case: \(\Theta\).
- Upper bound: \(O\).
Recursion Complexity is:
- \(O(n)\) if the recursion tree has a height of \(O(n)\) and each level of the tree has \(O(1)\) work.
- \(O(n \log n)\) if the recursion tree has a height of \(O(\log n)\) and each level of the tree has \(O(n)\) work.
- \(O(n^2)\) if the recursion tree has a height of \(O(n)\) and each level of the tree has \(O(n)\) work.
- By height, we mean the number of levels in the recursion tree (the number of times we call the function recursively until we reach the base case and conclude the recursion).
Logarithmic Complexity:
- Logarithmic complexity is the complexity of an algorithm that divides the problem in half at each step.
- The complexity of such an algorithm is \(O(\log n)\).
- Examples of such algorithms are binary search and the merge sort algorithm.

Algorithm Analysis ²¶

Asymptototic algorithm analysis:
- Is a method to compare the resource consumption of two algorithms.
- It does not show slight differences in resource consumption, but it flags the significant differences.
- It is an estimation of the cost of an algorithm.
- It measures the efficiency of an algorithm or its implementation (program) as the input size grows.
- It analyzes:
  - The time required for an algorithm to run (or an instantiation of an algorithm into a program to execute).
  - The space required for a data structure.

Analysis Techniques ³¶

14.1 Summation Techniques¶

\(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\).
Guess-and-test is useful whenever the solution is a polynomial expression. In particular, similar reasoning can be used to solve for \(\sum_{i=1}^{n} i^2\), or more generally \(\sum_{i=1}^{n} i^c\) for c any positive integer.
A more general approach is based on the subtract-and-guess or divide-and-guess strategies. To solve sum f, we pick a known function g and find a pattern in terms of f(n) - g(n) or f(n)/g(n).
One form of subtract-and-guess is known as the shifting method: subtracts the summation from a variation on the summation.

14.2 Recurrence Relations¶

Recurrence relations are often used to model the cost of recursive functions.
There are many approaches to solving recurrence relations, and we briefly consider three here:
- Guess the upper and lower bounds for the recurrence relation:
  - Use induction to estimate the upper and lower bounds.
  - Tighten as required.
- Expand the recurrence to a summation, and then solve the summation.
- Use already proven theorems for some special recurrences.

14.3 Amortized Analysis¶

Amortized analysis deals with the cost of a series of operations.
Rather than focusing on the individual cost of each operation independently and summing them, amortized analysis looks at the cost of the entire series and “charges” each individual operation with a share of the total cost.

Recurrence Relations ⁴¶

Solving Recurrence Relations ⁵¶

A recurrence relation is an equation which is defined in terms of itself.
The initial or boundary condition terminate the recursion.
Induction:
- Proof that the base case is true.
- Assume that it is true for n-1.
- Proof that it is true for n.
Realize that linear, finite history, and constant coefficient recurrences always can be solved.
Systems like Mathematica and Maple have packages for solving recurrences.
Famous algorithms and their recurrences:

Algorithm	Complexity	Recurrence Relation
Matrix Multiplication (m * n)	O(n^3)	T(n) = 8T(n/2) + O(n^2)
Polygon Triangulation	O(n^3)
Merge Sort	O(n log n)

L1: Asymptotic Analysis and Complexity ¹⁵¶

Growth functions:
- Constant: \(O(1)\).
- Logarithmic: \(O(\log n)\).
- Linear: \(O(n)\).
- Linearithmic: \(O(n \log n)\).
- Quadratic: \(O(n^2)\).
- Cubic: \(O(n^3)\).
- Exponential: \(O(2^n)\).
- Factorial: \(O(n!)\).
Big O defines the upper bound of the function, or the worst-case scenario.

L2: Sequences and Recurrence relations ¹⁶¶

Iterative processes can be implemented recursively; hence, algorithms can be modeled as recurrence relations.
Recurrence relations are equations that define a sequence of numbers.
- It defines the value of a function in terms of the values of the function at earlier points.
- E.g. \(f(n)= f(0) + f(1) + f(2) + ... + f(n-1)\). or \(f(n) = f(n-1) + f(n-2)\).
A Sequence can be defined as a solution to a recurrence relation, if its terms satisfy the relation.
Example: Linear Search:
- The recurrence relation for linear search is \(T(n) = T(n-1) + C\).
- This means that the time to search for an element in an array of size n is equal to the time to search for an element in an array of size n-1 plus a constant time.
- The solution to this recurrence relation is \(T(n) = n\).
- \(T(n) = T(n-1) + C = T(n-2) + 2C = T(n-3) + 3C = ... = T(0) + nC = nC\).
- Hence, the time complexity of linear search is \(O(n)\).
Techniques to solve recurrence relations:
- Guess and verify.
- Induction.
- Recursion tree.
- Master theorem:
  - Works best for divide-and-conquer algorithms.
  - Recurrence relation should be in the form \(T(n) = aT(n/b) + f(n)\). Where:
    - \(a\) is the number of subproblems.
    - \(n/b\) is the size of each subproblem.
    - \(f(n)\) is the cost of dividing the problem and combining the solutions.

L3: Brute Force Algorithms ¹⁷¶

Brute force algorithms are algorithms that try all possible solutions to a problem.
- They have straightforward approach usually based on the problem’s definition.
- It works well when the problem size is small.
- It is usually simple to implement, not creative, and not efficient.
Approaches of Brute Force:
- Exhaustive search: Try all possible solutions.
- Backtracking: Try all possible solutions and backtrack when a solution is not feasible.
- Branch and Bound: Try all possible solutions and prune the search space when a solution is not feasible.

L4: Backtracking and Branch and Bound ¹⁸¶

In both cases, we create a tree of possible solutions and traverse it to find the best solution, sorted in a way that makes sense for the problem.
Backtracing:
- Performs a depth-first search of the solution space.
- It continues until it finds a solution that is not feasible, then it skips the rest of the subtree, and backtracks to the previous node, where it start exploring the next child.
Branch and Bound:
- It is a more sophisticated version of backtracking.
- It performs a breadth-first search of the solution space.
- It uses a priority queue to decide which node to explore next.
- It uses a lower bound to prune the search space.
- It uses an upper bound to decide when to stop exploring a subtree.

Examples of Algorithms Solved in Different Approaches¶

Traveling Salesman Problem:
- The problem is to find the shortest path that visits all cities and returns to the starting city.
- Exhaustive search:
  - The brute force approach is to evaluate all possible paths and select the shortest one.
- Branch and Bound:
  - Start with a breadth-first search of the solution space to find the closest city for each city and compute the lower bound; say it is m.
  - This forms a lower bound for the solution, and it may not be a valid solution.
  - Start looking for real solution, while comparing the current path with the lower bound.
  - If the current path is longer than the lower bound, we backtrack to the previous node and try the next city.
  - This way, we
KnapSack Problem:
- The problem is to find the most valuable combination of items that can be carried in a knapsack of a given capacity.
- Exhaustive search:
  - The brute force approach is to evaluate all possible combinations of items and select the most valuable one.
N-Queens Problem:
- The problem is to place n queens on an n x n chessboard so that no two queens attack each other.
- Exhaustive search:
  - Evaluate all possible placements of queens and select the valid ones.
- Backtracking:
  - Start putting the first queen in a place (randomly or systematically).
  - Start adding one queen at a time, and evaluate if the queen is safe.
  - If it is safe, we place the next queen in the next column, and so on.
  - If it is not safe, we backtrack to the previous column and try the next row.

Extra Resources¶

Algorithms by Jeff Erickson. (2019). Illinois.edu. https://jeffe.cs.illinois.edu/teaching/algorithms/

References¶

Review of Asymptotic Analysis and Complexity - http://discrete.gr/complexity/ ↩
Chapter 3: Algorithm Analysis in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer. http://people.cs.vt.edu/~shaffer/Book/C++3e20100119.pdf ↩
Chapter 14 Sections 14.1 through 14.2 Analysis Techniques in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer. http://people.cs.vt.edu/~shaffer/Book/C++3e20100119.pdf ↩
Erickson, J. (2010). Algorithms. Available under Creative Commons 3.0 at http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf ↩
Read the following lecture notes on solving recurrence relations - http://www.cs.duke.edu/~reif/courses/alglectures/skiena.lectures/lecture3.pdf ↩
Introduction to Recurrence Relations. https://my.uopeople.edu/pluginfile.php/1951148/mod_book/chapter/554083/algo_ch4_recurrences.pdf ↩
Video Lecture detailing how to solve a recurrence relation https://youtu.be/u-I-qixs8oY ↩
Algorithm Strategies. https://my.uopeople.edu/pluginfile.php/1951148/mod_book/chapter/554083/chapter03-algointro.pdf ↩
Algorithm Design Paradigms. https://cgi.csc.liv.ac.uk/~ped/teachadmin/algor/algor.html ↩
Chapter 7: Internal Sorting in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer. ↩
Chapter 9: Searching in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer. ↩
Algorithm Animations. https://www.cs.auckland.ac.nz/software/AlgAnim/alg_anim.html ↩
Lecture 19: Asymptotic Analysis by Instructor Jonathan Shewchuk, University of California Berkley. Retrieved from https://youtu.be/X8Ba--V4sGA ↩
Lecture 20: Algorithm Analysis by Instructor Jonathan Shewchuk, University of California Berkley. Retrieved from https://youtu.be/q5BMmfGdWtU ↩
Unit 1 Lecture 1: Asymptotic Analysis and Complexity. https://my.uopeople.edu/mod/kalvidres/view.php?id=453882 ↩
Unit 1 Lecture 2: Sequences and Recurrence relations. https://my.uopeople.edu/mod/kalvidres/view.php?id=453883 ↩
Unit 1 Lecture 3: Brute Force Algorithms. https://my.uopeople.edu/mod/kalvidres/view.php?id=453884 ↩
Unit 1 Lecture 4: Backtracking and Branch and Bound. https://my.uopeople.edu/mod/kalvidres/view.php?id=453885 ↩

1. Review of Data Structures and Algorithms¶

Review of Asymptotic Analysis and Complexity 1¶

Algorithm Analysis 2¶

Analysis Techniques 3¶

14.1 Summation Techniques¶

14.2 Recurrence Relations¶

14.3 Amortized Analysis¶

Recurrence Relations 4¶

Solving Recurrence Relations 5¶

L1: Asymptotic Analysis and Complexity 15¶

L2: Sequences and Recurrence relations 16¶

L3: Brute Force Algorithms 17¶

L4: Backtracking and Branch and Bound 18¶

Examples of Algorithms Solved in Different Approaches¶

Extra Resources¶

References¶

Review of Asymptotic Analysis and Complexity ¹¶

Algorithm Analysis ²¶

Analysis Techniques ³¶

Recurrence Relations ⁴¶

Solving Recurrence Relations ⁵¶

L1: Asymptotic Analysis and Complexity ¹⁵¶

L2: Sequences and Recurrence relations ¹⁶¶

L3: Brute Force Algorithms ¹⁷¶

L4: Backtracking and Branch and Bound ¹⁸¶