Week1

Introduction

Solving problems using algorithms

This course is about designing algorithms for solving practical problems. We will deal only with sequential deterministic algorithms.

Here are some Examples Of Algorithms

• Two Thieves
• Three Thieves
• n Thieves

Proofs

We need to give a mathematical proof that an algorithm we have designed terminates and returns a solution to the problem at hand when this is not obvious by inspecting the algorithm using common sense.

Here is an example of role of proofs

• Stable Matching Problem

Preliminaries

Asymptotic notation

We need a way to compare two functions, in this case representing the runtime of each algorithm. We prefer to talk in terms of asymptotics.

• “Big-Oh” notation

  • Definition

    We say f(n) = O(g(n)) if there exist positive constants C and N such that 0 ≤ f(n) ≤ C · g(n) for all n ≥ N.

  • g(n) is said to be an asymptotic upper bound for f(n).

  • Informally, f (n) is eventually (i.e. for large n) controlled by a multiple of g(n), i.e. f (n) grows “no faster than g(n)”.

• Big Omega notation
  • Definition We say f (n) = Ω(g(n)) if there exist positive constants c and N such that 0 ≤ C · g(n) ≤ f (n) for all n ≥ N.
  • g(n) is said to be an asymptotic lower bound for f (n).
  • Informally, f (n) eventually (i.e. for large n) dominates a multiple of g(n), i.e. f (n) grows “no slower than g(n)”.
• Landau notation
  • Definition We say f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)).
  • f(n) and g(n) are said to have the same asymptotic growth rate