Skip to content

Full index

Basic algorithms

  1. Representation of numbers
    • 1.1 Representation of natural numbers
    • 1.2 Representation of integer numbers
    • 1.3 Representation of real numbers
  2. Pseudo-code
    • 2.1 Introduction to pseudo-code
    • 2.2 Variables and assignments
    • 2.3 Basic operations
    • 2.4 Basic constructs
    • 2.5 Arrays
    • 2.6 Functions
    • 2.7 Sets
    • 2.8 Style conventions
  3. Sorting algorithms
    • 3.1 The sorting problem
    • 3.2 Insertion Sort
    • 3.3 Exchange Sort
    • 3.4 Selection Sort
    • 3.5 Comparison of the three algorithms
  4. Linear and binary search
    • 4.1 The search problem
    • 4.2 Linear search
    • 4.3 Binary search
  5. Numerical algorithms
    • 5.1 Change of base
    • 5.2 Primality test
    • 5.3 Sieve of Eratosthenes
    • 5.4 Greatest common divisor

Programming languages

  1. Introduction to C++
    • 6.1 Main characteristics of the programming language
    • 6.2 Variables and data types
    • 6.3 Input-output stream
    • 6.4 Operators
    • 6.5 Conditional statements
    • 6.6 Loops
    • 6.7 Arrays
    • 6.8 The main and custom functions
    • 6.9 A complete algorithm: the maximum value in an array
    • 6.10 Bitwise operators
  2. Introduction to Python
    • 7.1 Main characteristics of the programming language
    • 7.2 Variables and data types
    • 7.3 Input and output
    • 7.4 Operators
    • 7.5 Conditional statements
    • 7.6 Loops
    • 7.7 Lists
    • 7.8 Functions
    • 7.9 A complete algorithm: the maximum value in an array
    • 7.10 Bitwise operators
    • 7.11 Python and C++ side by side
  3. Introduction to Java
    • 8.1 Main characteristics of the programming language
    • 8.2 Variables and data types
    • 8.3 Input and output
    • 8.4 Operators
    • 8.5 Conditional statements
    • 8.6 Loops
    • 8.7 Arrays
    • 8.8 Methods (functions)
    • 8.9 A complete algorithm: the maximum value in an array
    • 8.10 Bitwise operators
    • 8.11 Java, C++ and Python side by side

Asymptotic notation and growth

  1. Asymptotic notation
    • 9.1 \(\Theta\), \(\bigO\) and \(\Omega\) notations
    • 9.2 \(o\) and \(\omega\) notations
    • 9.3 Limits and asymptotic notations
    • 9.4 Relational properties of asymptotic notations
    • 9.5 Asymptotic notation in the analysis of algorithms
  2. Asymptotic growth
    • 10.1 Families of increasing functions of a natural variable
    • 10.2 The hierarchy of infinities
    • 10.3 Comparison of orders of growth

Analysis of algorithms

  1. Input size
    • 11.1 Input size
    • 11.2 Asymptotic notation: a recall
    • 11.3 Input instance consisting of one natural number
    • 11.4 Input instance consisting of two natural numbers
    • 11.5 Input instance consisting of an array of natural numbers
    • 11.6 Input size and number of steps
  2. Running time
    • 12.1 Running time of an algorithm
    • 12.2 Find maximum
    • 12.3 Insertion sort
    • 12.4 Change of base
    • 12.5 Primality test
    • 12.6 Summary
  3. Correctness
    • 13.1 Correctness of an algorithm
    • 13.2 Correctness of Find Maximum
    • 13.3 Correctness of Insertion Sort
    • 13.4 Correctness of Binary Search
    • 13.5 Correctness of the Euclidean algorithm
    • 13.6 Correctness of recursive algorithms

Recursion

  1. Recursion
    • 14.1 Recursive algorithms
    • 14.2 Tree of recursive calls and call stack
    • 14.3 Correctness of recursive algorithms
    • 14.4 Factorial
    • 14.5 Fibonacci numbers
    • 14.6 Greatest common divisor
    • 14.7 Fast exponentiation
    • 14.8 Towers of Hanoi
    • 14.9 Summary
  2. Recurrences
    • 15.1 Recurrences
    • 15.2 The expansion method
    • 15.3 The substitution method
    • 15.4 The recursion-tree method
    • 15.5 Towards the Master Theorem
    • 15.6 Summary: which method when
  3. The Master Theorem
    • 16.1 Recurrences in standard form
    • 16.2 The Master Theorem
    • 16.3 Applying the Master Theorem
    • 16.4 When the Master Theorem does not apply
    • 16.5 Proof of the Master Theorem
    • 16.6 Summary
  4. Recursive algorithms
    • 17.1 The sum of the elements of an array
    • 17.2 Merge Sort
    • 17.3 Recursive Binary Search
    • 17.4 The maximum subarray problem
    • 17.5 Summary
  5. Recursive versus iterative algorithms
    • 18.1 Recursion and iteration
    • 18.2 Comparison at a glance
    • 18.3 Divide and conquer is what gives the gain, not recursion itself
    • 18.4 When subproblems overlap
    • 18.5 Space
    • 18.7 Experiment
    • 18.8 Guidelines