Preface

Prerequisites

You need to know Discrete mathematics.

Learning ethics

Introduction

What is an Algorithm?

Informally, an algorithm is a series of computational steps that takes an input and returns an output in a finite amount of time. The input and output relationship is a way to describe a computational problem. So, you use algorithms because you have a problem, but no upside down.

A mathematical reader can think is a little floppy definition and maybe you thought “your definition is not the correct way to found any science” —what the heck is a computational step?— and you are right, it is an easy way to definite an algorithm, but it is not the full answer. A more accurate definition is given to you later.

Different ways to describe an algorithm:

# Notation 1
f: x: T -> y: T1 -> z: T2 ... -> output: TN
f = computational steps

# Notation 2
f(x: T, y: T1, ...): output: TN = computational steps

# Notation 3
f(x: T, y: T1, ...): output: TN {
   computational steps
}

Some authors don’t write types when they write algorithms, but we do since they give precision.

We say with $x:T$ that x is a term with type T. A type has values and operations —interface. We explain more later.

Why do algorithms matter to you?

Perhaps you are here to build a Skynet —Artificial intelligence, to solve the problem NP=P —Research, work in a Big Tech company —Industry.

Algorithms are foundations for building great systems and for research too.

Quality of algorithms.

Performance

Research

Ecosystem

Standards, jobs, industry, roles, …

How do you practice the Design of Algorithms?

Euler Project

IMO

Codeforces

LeetCode

HackerRank

Story

Notation

$n \in \mathbb{N}$ represents items for the algorithm given. This implies I either use $n=ceil(X)$or $n=floor(X)$ by a satisfies the problem presented.

$log_2(n)=lg(n)$

$f$ is faster than $g$, if $f$ is smaller than $g$ i.e. $f<g$

Classification

FAQ

1. Some exercises are Jupyter

Worked examples

Is an algorithm a type?

No. They are terms.

Summarize

• Mindmap

  @startmindmap
  * Introduction to Algorithms
  ** Objective: Study the fundamentals of algorithms and their analyses
  ** Contents
  *** Algorithms
  **** Properties
  **** Efficiency
  *** Sorting algorithms
  **** Bubble sort
  **** Insertion sort
  **** Merge sort
  **** Quick sort
  *** Asymptotic notation
  **** Big-Oh notation
  **** Omega notation
  **** Theta notation
  *** Recurrences
  **** Substitution method
  **** Recursion-tree method
  **** Master method
  *** Summary
  **** Algorithms solve computational problems
  **** Analyzing algorithms helps understand their properties and efficiency
  **** Key concepts: algorithms, efficiency, asymptotic notation, recurrences
  @endmindmap

Reference Notes

Definition of algorithm. (2022, December 04). Retrieved from https://www.merriam-webster.com/dictionary/algorithm

Theory of algorithms

Note that our definition means algorithms have to finish but exists other classes of computational methods can or can not be finished.

TODO: Mathematical definition.

Computational method.

Types.

Algorithm.

Computational problem.

If you write an algorithm it has to work for each valid input instance.

Models of computation.

There are several models of computation such as Lambda calculus, or Turing Machine, but in fact, they are equivalent (we are not proving that statement here, you can explore them in Models of computation). We are focusing on Von Neuman Languages and Random Access Machines, which are the current paradigm in computing. It means we describe algorithms with assignments and side effects, but by Turing-Church thesis, you can write your algorithms in a functional programming style.

Random Access Machine Emulator (by Simon Gottlieb and Simon Koennecke). (2014, October 24). Retrieved from https://farbtrommel.de/ram

Functional Algorithm Design, Part 0. (2020, November 15). Retrieved from https://blog.sigplan.org/2020/11/17/functional-algorithm-design-part-0

If you are interested in learning algorithms based on Lambda Calculus, you should read some of the following books

Stone, J. D. (2018). Algorithms for Functional Programming. Springer.

Bird, R., & Gibbons, J. (2020). Algorithm Design with Haskell. Cambridge University Press.

RUSSELL, D. (2003). Algorithms: A Functional Programming Approach by Fethi Rabhi and Guy Lapalme, Addison-Wesley, 1999, ISBN 0-201-59604-0, xi 235pp. Journal of Functional Programming, 13(4), 828-829. doi:10.1017/S0956796803244877

Representations and codification.

You can change your representation by encoding the way the underlying machine can do operations. So, you could write an algorithm in English and then change the representation to hardware circuit specification. For example, 3 can be represented as $III,$ 011, or Г. The last is the Cyrillic alphabet’s 3.

Language specification

A pseudocode is a way to learn algorithms, but somehow you should be capable to understand it.

f(n: NaturalNumber): NaturalNumber
     sum = 0
     for i in 0 <= i <= n where i++
           sum += i
     return sum

Data structures

Specification.

Immutability and Mutability. State.

In place.

Sequence

Extrinsic order

Array

Array in C

Linkedin list

Dynamic Array

List in Python

Sequence AVL

Set

Intrinsic query set.

Data structures

Array

Dynamic Array

Direct Access

Hash Table

Set AVL

Bits

Encode a set as bits. It is a faster data structure since you are changing your algorithm to a clever representation! Every operation works $T(n)=O(1)$.

class Set:
    set = 0
    GOAL = 100
    hasReachGoal():
       return set == GOAL
    remove(element: int)
       return set ^= (1 << element) 
    has(element: int)
       return (set & (1 << element)) == (1 << element)
    insert(element: int)
       return set |=  1 << element

Summary

Worked examples

// Each bit in our set is 2^n, where n is a integer.
// bin(2^0)=000001, bin(2^1)=000010, bin(2^2)=000100, ...
// 1 << n is equivalent to 2^n but faster

"insert" operation example
000000 // set = 0
000100 // n=2, bin(1 << n)=bin(2^2)=000100
000100 // set | 000100
"has" operation example
000101 // set = 5
000100 // n=2, bin(1 << n)=bin(2^2)=000100
000100 // (set & 000100) == 000100
"remove" operation example
000101 // set = 5
000100 // n=2, bin(1 << n)=bin(2^2)=000100
000001 // set ^ 000100
"goal"
000    // Suppose you want a full 3-bit vector 
// So
1000    // bin(1 << 3)=bin(2^3)=8
111     // bin((1<<3)-1)

Analysis of algorithms

Efficiency

Algorithm efficiency is more significant than differences due to hardware. Why should learn about algorithms? Applications use them either to solve larger problems than ever before or rely heavily upon algorithms.

Some authors write efficiency and complexity interchangeably, we prefer to refer to our analysis as time efficiency and space efficiency, but you can search for them as Time complexity and Space complexity.

Informally, We have the running time like $T: n \to time$ and $S: n \to space$ where $n$ is the size of the input. We usually compare algorithms based on their time and their results. The resources required by an algorithm on the instance size and instance representation.

Requirements for resource analysis.

Independence. The analysis must be independent of the hardware of a computer, the programming language used for pseudocode, and the programmer that wrote the code.

A priori.

Large instance requirement.

Growth rate classes

Time analysis

* Algorithmic Analysis ** Asymptotic Notation ** Recurrence Relations ** Amortized Analysis ** Probabilistic Analysis

Best case. The smallest amount of resources is needed to run any instance.

Worst case. The largest amount of resources is needed to run any instance.

Average case. The largest amount of resources is needed to run any instance.

https://cs.stackexchange.com/questions/33854/is-there-a-method-for-automatic-runtime-analysis-of-algorithms

Correctness

Correct and incorrect

The algorithm is correct if it can solve the given problem. An incorrect algorithm may halt with a partial or nothing solution. That algorithm could be useful if we control their error rate. However, most time we focused on the correct algorithms.

Formal verification and reasoning about algorithms

Proving Programs Correct

Your algorithm needs a way to prove if it is correct, a well-known way to verify formally your algorithms is the Hoare logic —including loop invariant and Weakest Precondition Calculus—. Indeed, it is a way to reason about your algorithm too.

Algorithms have some conditions that should be true to say an algorithm is correct such that the input would be correct, and the same as the output. They are predicates, the first kind is a precondition and the last one is a postcondition. You can have whatever number you need.

You can think of preconditions as a formal definition of the input problem, and postconditions as a formal definition of the output problem.

Another way to think about preconditions and postconditions is like you are designing a contract where your "interface client" (who will call your interface) and a "supplier" (your interface) agree on a "contract" that defines obligations (preconditions that definite the correct way to use your interface) in order to receive benefits (postconditions or output).

Typing your function is a way to definite them, but sometimes types are not enough to express the “contract”.

Depending on your algorithm, you have also to consider security.

Assert.

Invariant loop.

Hoare Logic, loop invariants, and weakest preconditions by Programming: The Derivation of Algorithms by Anne Kaldewaij.

https://allan-blanchard.fr/publis/frama-c-wp-tutorial-en.pdf

Defensive programming

This is a topic in software engineering, defensive programming

Design by contract

TODO: Does Hoare logic only work with imperative algorithms?

Amortized Analysis

https://www.youtube.com/watch?v=kNIcbsyu4zI&ab_channel=ConfEngine

Case analysis

Worst, Best, Average analysis.

Warning on Empirical Analysis —Testing and Benchmarking

Profiling and benchmarking

References

https://docs.python.org/3/library/functools.html

Exercises

1. Logic. Mathematics. Code. Automatic Verification such as Lean Proven or Frama-C.

2. Languages in Anki.

Projects

Summary

FAQ

How can we analyze algorithms with standard input or standard output? Network? or generally speaking input-output calls?

In this knowledge unit —Algorithms, we work with algorithms that don’t have to block calls such as network calls or standard input output calls, but if you have to measure the efficiency of an algorithm in such a situation it counts as constant time because it doesn’t depend on any input instance.

For example:

f(n: ℕ): void
   for i in 0 <= i <= n with i++
      fetch("some network call  {n}") # It is constant time

The algorithm time efficiency is $\Omega(n)$ since you are reducing your problem to call to another process.

But, you should know network calls and other I/O calls are the most time-consuming.

TODO

Reference Notes

Definition of efficiency versus complexity of algorithm. (2022, December 14). Retrieved from https://cs.stackexchange.com/questions/71858/definition-of-efficiency-versus-complexity-of-algorithm

Framework Thinking about the design and analysis of algorithms (Getting started)

Sum of sequence

Input: A non-null sequence of $n$ real numbers $[a_1,a_2,a_3,...,a_n]$.

Output: A real value $r$, such that $r=\sum_i^n a_i$

SUM(A)
	n = A.length                 c1(1)
  r = A[n]                     c2(1)        
	for j = n-1  downto 1        c3(n)
	     do r = r + A[j]         c4(n-1)
	return r                     c5(1)

Invariant loop. At the start of each iteration of for loop of lines 3-4, $r$ is equal to elements from $n$ to last values $n-j$.

• Initialization.

  Before the first loop iteration, $j=n-1$ and $r=a_n$, therefore $r$ equals the last value, $n-(n-1)=1$. Which checks with the invariant loop.

• Maintenance.

  Before the loop iteration, $j=k$, thus $r=a_n+a_{n-1}+a_{n-2}+...+a_{n-k}$ (the summation of last elements). At line $4$ $j=k+1$ element is added to $r$, i.e. the next loop iteration $r=a_n+a_{n-1}+a_{n-2}+...+a_{n-k}+a_{n-(k+1)}$. Which checks with the invariant loop.

• Termination.

  When loop terminates $j=n$, $n-j=n-n=0$. By invariant loop We have $r=a_n+a_{n-1}+a_{n-2}+...+a_{n-k}+a_{n-(k+1)}+...+a_1$.

Hence, the algorithm is correct.

We sum the product of the costs times columns $T(n)=c_1+c_2+c_3n+c_4(n-1)+c_5n=(c_4+c_5)n+(c_1+c_2+c_3-c_4)$.

Sorting problem by insertion sort

Input: A sequence (or array) of $n$ numbers $[a_1,a_2,...,a_n]$. The numbers that we wish to sort are also known as the keys.

Output: A reordering $[a_1^{'},a_2^{'},...,a_n^{'}]$ of the input sequence such that $a_1^{'}\le a_2^{'}\le ...\le a_n^{'}$.

// T should be support '>' or '<' operation
sort_by_insertion_sort_in_place(array: T[]): void
     for j in 2 <= j <= array.n where j++
           noSortedElement = array[j] // no sorted element
           // variant array[1:j-1-] is sorted
           i = search_the_right_position(array, j-1, noSortedElement)
           // i in j > i >= 0 with i--, so we need i+1 by size array.
           array[i+1] = noSortedElement // set a new mininum.       

search_the_right_position(array: T[], i: j-1 >= i >= 0, noSortedElement)
       // [2,3,1] 2 >= i >= 0 noSortedElement=1, here i==2
       // [2,3,3] because array[2]=3 > noSortedElement=1, here i==1
       // [2,2,3] because array[1]=2 > noSortedElement=1, here i==0
       // we are done because i == 0
       while i > 0 and array[i] > noSortedElement
             array[i+1] = array[i]
             i--
       // i+1 is the right position for noSortedElement
       return i

Visualizer

• Languages implementation

  def insertion_sort(numberSequence, compareFunction):
     for j in range(1,len(numberSequence)):
       key = numberSequence[j]
       i = j - 1
       while i >= 0 and compareFunction(numberSequence[i], key):
          numberSequence[i+1] = numberSequence[i]
          i = i - 1
       numberSequence[i+1] = key
     return numberSequence;
  
  insertion_sort([4,3,2,1], lambda a,b : a > b)

  void insertionSort ( int numberSequence[ ] , int length) 
  {
       for( int j = 1 ; j < length ; j++ ) {
            int key = numberSequence[ j ];    
            int i = j - 1;
            while(  i >= 0  && numberSequence[i] > key) {
                  numberSequence[i+1] = numberSequence[i];   
                  i = i - 1;
             }
             numberSequence[ i+1 ] = key;       
       }  
  }

Worked examples

• Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array $A=[31,41,59,26,41,58]$

  

• Rewrite the INSERTION-SORT procedure to sort into monotonically decreasing instead of monotonically increasing order.

  search_the_right_position(array: T[], i: j-1 >= i >= 0, noSortedElement)
         // We only change '>' to '<'. Invariant is the same.
         while i > 0 and array[i] < noSortedElement
               array[i+1] = array[i]
               i--
         return i

  insertion_sort(array, compare_as: a < b)

• Consider the searching problem: Input: A sequence of n numbers A D ha1; a2;:::;ani and a value . Output: An index i such that D AŒi or the special value NIL if does not appear in A. Write pseudocode for linear search, which scans through the sequence, looking for . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Worked examples

• 1. Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

  • Page Rank Algorithm by Google. Search web about Internet.

• 2. Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in $8n^2$ steps, while merge sort runs in $64nlg(n)$ steps. For which values of n does insertion sort beat merge sort?

  $When \text{ is }8n^2 \text{ faster than } 64nlg(n)?$ That implies $\forall n \mid8n^2<64nlg(n)$

  $$8n^2<64nlg(n)\\ 8n^2<64n\dfrac{ln(n)}{ln(2)}\\ nln(2)<8ln(n)\\ \dfrac{ln(2)}{8}<\dfrac{ln(n)}{n}\\ \dfrac{ln(2)}{8}<\dfrac{ln(n)}{e^{ln(n)}}\\ \dfrac{log(2)}{8}<ln(n)e^{-ln(n)}\\ -\dfrac{log(2)}{8}>-ln(n)e^{-ln(n)}\\ -ln(n)>W_(\dfrac{-log(2)}{8})\\ n<e^{-W(\dfrac{-log(2)}{8})}\\ e^{-W_{-1}(\dfrac{-log(2)}{8})}<n<e^{-W_{0}(\dfrac{-log(2)}{8})}\\ n\in[2,43]$$

  Note: If $f$ is a multivalued function, $f(2)=n_1$, $f(2)=n_2$ and $n_2>n_1$. We have $n<f(2)$ implies $n<n_2$ and $n_1<n$.

  https://www.wolframalpha.com/input/?i=8x^2<64xlog_2(x)

• 3. What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?

  $When \text{ is }100n^2 \text{ faster than } 2^n continually?$ That implies $\text{ from } n_0 \text{ to } \infty \text{, }100n^2<2^n \text{ i.e. } sup(n) \mid 100n^2<2^n$.

  $$100n^2=2^n\\ \dfrac{100n^2}{2^n}=1\\ \dfrac{n^2}{e^{ln(2^n)}}=\dfrac{1}{100}\\ \dfrac{n^2}{e^{nln(2)}}=\dfrac{1}{100}\\ n^2e^{-nln(2)}=\dfrac{1}{100}\\ ne^{-nln(2)/2}=\dfrac{1}{10}\\ \dfrac{-nln(2)}{2}e^{\dfrac{-nln(2)}{2}}=\dfrac{-ln(2)}{20}\\ W(\dfrac{-ln(2)}{20})=\dfrac{-nln(2)}{2}\\ n=\dfrac{-2W(\dfrac{-ln(2)}{20})}{ln(2)}=\{0,15\}\\ sup(n)=15\\ \text{ from } 15 \text{ to } \infty \text{, }100n^2<2^n$$

  https://www.wolframalpha.com/input/?i=100x^2%3D2^x

• Problem 1-1 Comparison of running times For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

  eg.

  If the size of a problem is $n=10^6$ and $f(n)=n$, the problem takes

  $f(10^6)=10^6$ microseconds = $1$ second.

  So, the problem is this statement:

  $$f(n) = t \text{ microseconds}$$

  Since the functions are monotone-increasing functions, $t$ increases when $n$, so $n$ is the largest size of the problem.

  The problem needs the inverse function.

  $$n = f^{-1}(t)$$

  But we need to transform the domain into seconds, now $t$ are seconds, but $f^{-1}$ receives microseconds.

  $$n = f^{-1}(t \times 10^6)$$

  eg. $n=f^{-1}(1 \times 10^6)$ means the largest size $n$ of a problem in 1 second if $f^{-1}$ is a monotone-increasing function.

  $$f(n)=lg(n),f^{-1}(t)=2^{t\times 10^6}\\ f(n)=\sqrt{n},f^{-1}(t)=(t\times 10^6)^2 \\ f(n)=n,f^{-1}(t)=t\times 10^6 \\ f(n)=nlg(n),f^{-1}(t)=\dfrac{t\times 10^6}{W(t\times 10^6)}\\ f(n)=n^2,f^{-1}(t)=\sqrt{t\times 10^6} \\ f(n)=n^3, f^{-1}(t)=(t\times10^6)^{1/3}\\ f(n)=2^n, f^{-1}(t)=lg(t \times 10^6)\\ f(n)=n!, f^{-1} (t) \approx \dfrac{ln(\dfrac{t\times 10^6}{\sqrt{2 \pi}})}{W(\dfrac{1}{e} ln(\dfrac{t\times 10^6}{\sqrt{2 \pi}}))}$$

  W(t) is the product log function or Lambert W.

  We use Stirling's approximation to calculate the factorial inverse.

  https://www.geogebra.org/graphing/k34t7yxw

  

Summary

Exponential algorithms are bad!

• Code

  @startmindmap
  * Sorting and Order Statistics
  ** Objectives: Learn different sorting algorithms and their properties, and study order statistics
  ** Contents
  *** Heapsort
  **** Heap data structure
  **** Building a heap
  **** Heapsort algorithm
  **** Analysis and efficiency
  *** Quicksort
  **** Partitioning
  **** Quicksort algorithm
  **** Analysis and efficiency
  **** Randomized quicksort
  *** Sorting in linear time
  **** Counting sort
  **** Radix sort
  **** Bucket sort
  *** Medians and order statistics
  **** Selection problem
  **** Lower-bound for comparison-based sorting
  **** Randomized selection algorithm
  **** Order statistics tree
  *** Summary
  **** Sorting is a fundamental problem in computer science
  **** Different sorting algorithms have different properties and efficiencies
  **** Order statistics deal with finding the kth smallest element in a set
  **** Key concepts: heapsort, quicksort, counting sort, selection problem, order statistics
  @endmindmap

Fundamental Data Structures and Algorithms

Topological sort

Where could you find the topological sort?

Makefile.

Dependency resolution.

Sentence Ordering

Critical Path Analysis

Course Schedule problem

Finding cycle in a graph. Compilers need to check cycles on inherency.

Operation System deadlock detection.

Accounting for Computer Scientists — Martin Kleppmann’s blog. (2023, March 16). Retrieved from https://martin.kleppmann.com/2011/03/07/accounting-for-computer-scientists.html

Wheeler, D. A. (2023, March 22). The Free-Libre / Open Source Software (FLOSS) License Slide. Retrieved from https://dwheeler.com/essays/floss-license-slide.html

Cheat code

Wayne, Robert Sedgewick, and Kevin. "Algorithms and Data Structures Cheatsheet." 3 Feb. 2023, algs4.cs.princeton.edu/cheatsheet.

• Code

  @startmindmap
  * Data Structures
  ** Objectives: Understand the basic data structures and their properties, and analyze their efficiency in terms of space and time
  ** Contents
  *** Elementary data structures
  **** Arrays
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Linked lists
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Stacks
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Queues
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Dequee
  *** Hash tables
  **** Direct-address tables
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Hash tables with chaining
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Hash functions
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Analysis and efficiency
  ***** Space complexity
  ***** Time complexity
  *** Binary search trees
  **** Binary Tree (AKA Binary Search Tree or BST)
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Tree traversals
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Binary search tree property
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Operations on binary search trees
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Balanced binary search trees
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Analysis and efficiency
  ***** Space complexity
  ***** Time complexity
  *** Priority queues
  **** Heaps
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Priority queue operations
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Implementations
  ***** Definition
  ***** Operations
  ***** Space complexity
  ***** Time complexity
  **** Analysis and efficiency
  ***** Space complexity
  ***** Time complexity
  *** Summary
  **** Data structures organize and store data for efficient access and modification
  **** Efficiency in terms of space and time is important in designing and analyzing data structures
  **** Key concepts: arrays, linked lists, stacks, queues, hash tables, binary search trees, priority queues
  @endmindmap

• Code

  @startmindmap
  
  skinparam shadowing false
  skinparam roundcorner 15
  skinparam linetype ortho
  
  * Advanced Data Structures
  ** Bloom Filter
  ** LRU Cache
  ** Red-Black Tree
  ** B-Trees
  *** Definition and Properties
  *** Insertion and Deletion
  *** Searching
  ** Augmenting Data Structures
  *** Interval Trees
  *** Order Statistics Trees
  *** Van Emde Boas Trees
  *** Fibonacci Heaps
  *** Dynamic Tables
  *** Disjoint Set Union
  ** Data Structures for Disjoint Sets
  *** Disjoint Set Operations
  *** Linked-List Representation
  *** Union by Rank and Path Compression
  *** Analysis of Union by Rank and Path Compression
  ** Splay Trees
  *** Definition and Properties
  *** Rotations
  *** Operations
  ** Skip Lists
  *** Definition and Properties
  *** Searching
  *** Insertion and Deletion
  ** Hash Tables
  *** Direct Address Tables
  *** Hash Functions
  *** Collision Resolution
  *** Perfect Hashing
  ** Binary Heaps
  *** Definition and Properties
  *** Insertion and Deletion
  *** Heap Operations
  ** Treaps
  *** Definition and Properties
  *** Randomized Search Trees
  *** Insertion and Deletion
  ** Pairing Heaps
  *** Definition and Properties
  *** Merge and Insert Operations
  *** Delete-Min Operation
  
  @endmindmap

• Code

  @startmindmap
  
  skinparam shadowing false
  skinparam roundcorner 15
  skinparam linetype ortho
  
  * Graph Algorithms
  ** Basic Graph Algorithms
  *** Breadth-First Search (BFS)
  *** Depth-First Search (DFS)
  *** Topological Sort
  *** Connected Components
  *** Strongly Connected Components (SCC)
  ** Minimum Spanning Trees
  *** Kruskal's Algorithm
  *** Prim's Algorithm
  *** Reverse-Delete Algorithm
  ** Single-Source Shortest Paths
  *** Dijkstra's Algorithm
  *** Bellman-Ford Algorithm
  *** DAG Shortest Paths
  *** Johnson's Algorithm
  ** All-Pairs Shortest Paths
  *** Floyd-Warshall Algorithm
  *** Johnson's Algorithm
  ** Maximum Flow
  *** Ford-Fulkerson Algorithm
  *** Edmonds-Karp Algorithm
  *** Dinic's Algorithm
  ** Computational Geometry Algorithms
  *** Convex Hulls
  *** Line Segment Intersection
  *** Closest Pair
  ** Randomized Algorithms
  *** Randomized Minimum Cut
  *** Global Minimum Cut
  ** NP-Completeness
  *** Decision Problems and Search Problems
  *** Polynomial-Time Reductions
  *** Examples of NP-Complete Problems
  ** Algorithmic Analysis
  *** Asymptotic Notation
  *** Recurrence Relations
  *** Amortized Analysis
  *** Probabilistic Analysis
  
  refnote "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS), "The Art of Computer Programming" by Donald Knuth"
  
  @endmindmap

• Code

  @startmindmap
  
  skinparam shadowing false
  skinparam roundcorner 15
  skinparam linetype ortho
  
  * Selected Topics
  ** Approximation Algorithms
  *** Vertex Cover
  *** Traveling Salesman Problem
  *** Knapsack Problem
  ** Linear Programming
  *** Simplex Algorithm
  *** Duality and Sensitivity Analysis
  *** Network Flow Formulations
  ** Number-Theoretic Algorithms
  *** Greatest Common Divisor
  *** Modular Arithmetic
  *** The Chinese Remainder Theorem
  ** String Matching
  *** The Naive Algorithm
  *** The Rabin-Karp Algorithm
  *** The Knuth-Morris-Pratt Algorithm
  ** Cryptography
  *** Public-Key Cryptography
  *** RSA Algorithm
  *** Cryptographic Hash Functions
  ** Parallel Algorithms
  *** PRAM Model
  *** Parallel Prefix Sum
  *** Matrix Multiplication
  ** Computational Complexity
  *** Time and Space Complexity
  *** The Class P and NP
  *** NP-Complete Problems
  
  @endmindmap

• Code

  @startmindmap
  
  skinparam shadowing false
  skinparam roundcorner 15
  skinparam linetype ortho
  
  * Design Techniques
  ** Divide and Conquer
  *** How?
  **** Recursively divide problem into smaller subproblems
  **** Solve subproblems independently
  **** Combine solutions into a single solution to the original problem
  *** Examples
  **** Mergesort: sort an array by dividing it into two halves, sorting the halves, and merging them together. [CLRS, Knuth]
  **** Quicksort: sort an array by partitioning it into two subarrays around a pivot element, and then recursively sorting the subarrays. [CLRS, Knuth]
  **** Strassen's Algorithm: multiply two matrices by recursively dividing them into smaller submatrices, computing intermediate matrices, and combining the results. [CLRS]
  **** The Closest Pair Problem: find the pair of points in a set that are closest together by recursively dividing the set and computing the closest pairs in each subset, and then combining the results. [CLRS]
  ** Dynamic Programming
  *** How?
  **** Divide problem into smaller subproblems
  **** Compute solutions to subproblems, storing intermediate results
  **** Combine solutions to subproblems into a solution to the original problem
  *** Examples
  **** Rod Cutting: find the maximum revenue from cutting a rod into pieces of different lengths with different values. [CLRS]
  **** Matrix-Chain Multiplication: find the optimal way to multiply a chain of matrices by dividing it into subproblems and combining the results. [CLRS]
  **** Longest Common Subsequence: find the longest common subsequence between two sequences by dividing the problem into subproblems and computing intermediate results. [CLRS, Knuth]
  **** Optimal Binary Search Trees: find the optimal binary search tree for a set of keys with given probabilities by computing subproblems and combining the results. [CLRS]
  ** Greedy Algorithms
  *** How?
  **** Make locally optimal choices
  **** Combine locally optimal choices into a global solution
  *** Examples
  **** Huffman Coding: compress a message by encoding frequently-occurring characters with shorter codes, using a prefix-free code. [CLRS, Knuth]
  **** Fractional Knapsack: fill a knapsack with a maximum weight by selecting items with the highest value per weight. [CLRS]
  **** Dijkstra's Algorithm: find the shortest path between two nodes in a graph by making locally optimal choices and updating distances. [CLRS, Knuth]
  **** Prim's Algorithm: find the minimum spanning tree of a graph by making locally optimal choices and adding edges. [CLRS]
  ** Randomized Algorithms
  *** How?
  **** Use randomness to solve problems
  **** Probability of success can be amplified
  **** Some problems can only be solved with randomness
  *** Examples
  **** Quicksort: randomize the choice of pivot element to avoid worst-case scenarios. [CLRS, Knuth]
  **** Las Vegas Algorithms: use randomness to guarantee a correct solution, but with uncertain running time. [CLRS]
  **** Monte Carlo Algorithms: use randomness to approximate a solution, with a known probability of error. [CLRS, Knuth]
  **** Skip Lists: use probabilistic skipping to create a data structure with logarithmic search time. [CLRS]
  
  @endmindmap

Sorting problem

Insertion sort

Selection sort

…

Searching

Algorithm design

Problem-solving strategies. Patterns.

How to solve an algorithm problem? Reduce to a problem you already know or design your own algorithm.

Brute-force algorithms

Greedy algorithms

Worked examples

16-1 Coin changing Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin’s value is an integer.

• a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies —25, 10, 5 y 1 respectively. Prove that your algorithm yields an optimal solution.

  Input. $n\in\mathbb{N}$ cents.

  Output. The fewest sequence of quarters, dimes, nickels, and pennies, such that their sum equals to $n$.

  Corollary 1. $quarters, dimes, nickels, pennies \in \mathbb{N}$

  Google Colaboratory

  https://colab.research.google.com/drive/1QdQAHotL6waCUzuMMEWjbxFCD-WcdT2V#scrollTo=EOhWJY3Jrds1&line=7&uniqifier=1

  

• b. Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are $c^0,c^1,...,c^k$ for some integers c>1 and $k\ge1$. Show that the greedy algorithm always yields an optimal solution.

• c. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n.

• d. Give an $O(nk)$-time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny.

Linear programming

Recursion algorithm design

Divide-and-conquer

Recursive backtracking

Dynamic Programming

We define our problem as recursion, now we can apply memoization. It is about remembering and reusing subsolutions. If subproblems wouldn't repeat, you cannot apply memoization. Optimization.

Suproblem design (trick).

Given a sequence $x$ with $|x|=n$,

Good subproblems are prefixes ($x[:i]$) with $\Theta(n)$, suffices ($x[i:]$) with $\Theta(n)$, and substrings ($x[i:j]$) with $\Theta(n^2)$

A general method to memoize is the following

def memoize(solver)
   memo = dict()
   def caller(problem):
      if problem in memo:
          return memo
      memo[problem] = solver(problem)
      return memo[problem]
   return caller

@memoize()
def solver(problem):
   # base case
   # relate
   # topological order

solver(original_problem)

Of course, we optimize changing recursion into an iterative version. Suppose we have definite the SRTBOT of a recursion algorithm, so you can transform it.

memo = [] * n
# start in base case 
for i=topological order
# instead using recursive calls, 
# you call the memo and you build it bottom-up
   relate memo
return memo[0] # the original problem

Recursive algorithm design paradigms.

We think subproblems as a graph and edges are dependencies between each other.

Roughly speaking, you can solve problems forward (or top-down) and backward (bottom-up).

Recursive Framework. SRT BOT.

Subproblem definition.

Definite Input and Output type.

suffix,

max, min

Relate recursively.

Relate subproblem solutions recursively $x(i)=f(x(j),...),j<i$ —mathematically.

Reduce subproblems into subproblems and brute force.

You have to find a recurrence relation.

Topological order.

Argue relation is acyclic

You must guarantee no cycles. Indeed, it must be a DAG. Because we don’t want infinite recurse.

a→b means b needs a.

Nodes are subproblems, and an edge is if a subproblem needs another one.

Base cases.

State solutions for reachable independent solutions.

Original problem.

Show how to compute a solution from the original problem.

Time analysis.

Normally $T(n)= \text{\# subproblems} \times \text{nonrecursive work in relation}$

If subproblems are for multiple inputs, you take the cross product and multiply the problem spaces.

Worked examples

Arithmetic Parenthesization

Branch-and-bound

Greedy algorithms

Heuristics

Approximation Algorithms

Optimization algorithms.

Reduction: transform-and-conquer

Bitwise operations

Information Structures

6.851

2.1 Timeline

Objects.

Functions.

Array.

Graph.

Tree.

...

Combinatorial Algorithms

Elementary Graph Algorithms

Breadth-first search

• Class: Search algorithm

• https://www.cs.usfca.edu/~galles/visualization/BFS.html

• $T(n)=O(V+E)$

• $S(n)=O(V)$

DFS

Full-BFS

Full-DFS

Summary

Graph reachability by DFS or DFS in $O(n)$.

You can checkout apply in IA.

MST

Network Flow

Graph and Matrix

6.890

8.889

String Matching

Programming Techniques

Memory hierarchy

Randomized Algorithms

6.842

Randomized algorithms change the definition of correct and efficient.

Las Vegas. Always efficient, probably correct.

Monte Carlo. Always efficient, probably correct.

Parallel Algorithms.

Shared memory.

6.816, 6.846

Distributed algorithms.

Message passing.

6.852

Online Algorithms

Tips on Constructive Algorithms

Algorithms for external sources

Persistent Data Structures

Constant Factors - Performance

6.172

Next steps

Systems.

Theory of computation. 6.045 6.840 6.841

Applications

TODO.

Biology (6.047)

Game Theory (6.853)

Cryptography (6.875)

Vision (6.873)

Graphics (6.837) 6.838

Geometry (6.850)

Folding (6.849)

Recreational algorithms. Algorithmic Lower bounds: Fun with hardness proofs (6.892)

3D Impression?

References

1. Data Structure Visualization. (2022, December 12). Retrieved from https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

2. MIT OpenCourseWare. (2022, December 02). MIT OpenCourseWare. Retrieved from https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/pages/lecture-notes

3. Fethi Rabhi and Guy Lapalme. 1999. Algorithms; A Functional Programming Approach (1st. ed.). Addison-Wesley Longman Publishing Co., Inc., USA.

4. Stone, J. D. . Algorithms for Functional Programming. Springer. Retrieved from https://link.springer.com/book/10.1007/978-3-662-57970-1

5. Bird, R., & Gibbons, J. (2020). Algorithm Design with Haskell. Cambridge University Press.

6. The Art of Computer Programming by Donald Knuth.

7. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 4ª Ed., 2022. ISBN: 9780262046305.

8. Interview to Ph.D. Cormen.

9. [Handbook] The cracking the coding interview

10. Horowitz, E., Sahni, S., & Rajasekaran, S. (1996). Computer Algorithms: Pseudocode Version (2nd ed.). W.H. Freeman.

11. [Advance] Knuth, D. E. The art of computer programming. Addison Wesley.

12. A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ISBN 0-201-00023-7

13. Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2008). Algorithms. McGraw-Hill. p. 317. ISBN 978-0-07-352340-8.

14. https://www.cl.cam.ac.uk/teaching/1819/Algorithms/2018-2019-stajano-algs-handout.pdf

15. Kleinberg, Tardos: Algorithm Design

16. https://www.pnjb.de/uni/ws1011/hoehere-algorithmik.pdf

17. MIT OpenCourseWare. (2023, January 12). MIT OpenCourseWare. Retrieved from https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020

https://programming.guide

TODO

Quantum mechanics

Where? Optimization.