TagsAnalysis of algorithmsComputer scienceProgrammingTheoy of algorithms



You need to know Discrete mathematics.

Learning ethics


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:Tx: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.




Standards, jobs, industry, roles, …

How do you practice the Design of Algorithms?

Euler Project







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


ff is faster than gg, if ff is smaller than gg i.e. f<gf<g



  1. Some exercises are Jupyter

Worked examples

Is an algorithm a type?

No. They are terms.


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.



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,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


Immutability and Mutability. State.

In place.


Extrinsic order


Array in C

Linkedin list

Dynamic Array

List in Python

Sequence AVL


Intrinsic query set.

Data structures


Dynamic Array

Direct Access

Hash Table



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)T(n)=O(1).

class Set:
    set = 0
    GOAL = 100
       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


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
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


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:ntimeT: n \to time and S:nspaceS: n \to space where nn 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.

Time analysis is …
Space analysis is …

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.

Don’t confuse asymptotic analysis with time analysis. Big O is not the worst case.
Time T(n) stepsTime in S



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.


Invariant loop.

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


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


Case analysis

Worst, Best, Average analysis.

Warning on Empirical Analysis —Testing and Benchmarking

Profiling and benchmarking




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




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 Ω(n)\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.


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 nn real numbers [a1,a2,a3,...,an][a_1,a_2,a_3,...,a_n].

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

	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, rr is equal to elements from nn to last values njn-j.

Hence, the algorithm is correct.

We sum the product of the costs times columns T(n)=c1+c2+c3n+c4(n1)+c5n=(c4+c5)n+(c1+c2+c3c4)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 nn numbers [a1,a2,...,an][a_1,a_2,...,a_n]. The numbers that we wish to sort are also known as the keys.

Output: A reordering [a1,a2,...,an][a_1^{'},a_2^{'},...,a_n^{'}] of the input sequence such that a1a2...ana_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+1 is the right position for noSortedElement
       return i


Worked examples

Worked examples


Exponential algorithms are bad!

Fundamental Data Structures and Algorithms

Topological sort

Where could you find the topological sort?


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.

Sorting problem

Insertion sort

Selection sort


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.

Linear programming

Recursion algorithm design


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 xx with x=n|x|=n,

Good subproblems are prefixes (x[:i]x[:i]) with Θ(n)\Theta(n), suffices (x[i:]x[i:]) with Θ(n)\Theta(n), and substrings (x[i:j]x[i:j]) with Θ(n2)\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

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


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.


max, min

Relate recursively.

Relate subproblem solutions recursively x(i)=f(x(j),...),j<ix(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)=# subproblems×nonrecursive work in relationT(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


Greedy algorithms


Approximation Algorithms

Optimization algorithms.

Reduction: transform-and-conquer

Bitwise operations

Information Structures


2.1 Timeline







Combinatorial Algorithms

Elementary Graph Algorithms

Breadth-first search





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

You can checkout apply in IA.


Network Flow

Graph and Matrix



String Matching

Programming Techniques

Memory hierarchy

Randomized Algorithms


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.


Online Algorithms

Tips on Constructive Algorithms

Algorithms for external sources

Persistent Data Structures

Constant Factors - Performance


Next steps


Theory of computation. 6.045 6.840 6.841



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?


  1. Data Structure Visualization. (2022, December 12). Retrieved from https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  1. 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
  1. Fethi Rabhi and Guy Lapalme. 1999. Algorithms; A Functional Programming Approach (1st. ed.). Addison-Wesley Longman Publishing Co., Inc., USA.
  1. Stone, J. D. . Algorithms for Functional Programming. Springer. Retrieved from https://link.springer.com/book/10.1007/978-3-662-57970-1
  1. Bird, R., & Gibbons, J. (2020). Algorithm Design with Haskell. Cambridge University Press.
  1. The Art of Computer Programming by Donald Knuth.
  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 4ª Ed., 2022. ISBN: 9780262046305.
  1. Interview to Ph.D. Cormen.
  1. [Handbook] The cracking the coding interview
  1. Horowitz, E., Sahni, S., & Rajasekaran, S. (1996). Computer Algorithms: Pseudocode Version (2nd ed.). W.H. Freeman.
  1. [Advance] Knuth, D. E. The art of computer programming. Addison Wesley.
  1. A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ISBN 0-201-00023-7
  1. Dasgupta, Sanjoy; Papadimitriou, Christos; Vazirani, Umesh (2008). Algorithms. McGraw-Hill. p. 317. ISBN 978-0-07-352340-8.
  1. https://www.cl.cam.ac.uk/teaching/1819/Algorithms/2018-2019-stajano-algs-handout.pdf
  1. Kleinberg, Tardos: Algorithm Design
  1. https://www.pnjb.de/uni/ws1011/hoehere-algorithmik.pdf
  1. MIT OpenCourseWare. (2023, January 12). MIT OpenCourseWare. Retrieved from https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020



Quantum mechanics

Where? Optimization.