Introduction to Algorithms - Lecture 1: Algorithms and Computation

This post is a derivative from Introduction to Algorithms of MIT OpenCourseWare, used under CC BY-NC-SA 4.0.

You can watch this lecture on Youtube and see PDF.

Goal

The goal of this class is to teach you to solve computation problems, and to communicate that your solutions are correct and efficient.

Problems

• Binary relation from problem inputs to correct outputs
  • Essentially, for each input, I specify which of these outputs is correct. It doesn’t necessarily have to be one. If I say, give me the index in an array containing the value 5, there could be multiple 5’s in that array, and so any of those indices would be correct.
  • Edges represent a binary relation. These are specifying which of these outputs are correct for these inputs.
• Usually don’t specify every correct output for all inputs (too many!)
  • E.g., for input 1, the correct answer is 0, and for input 2…
• Provide a verifiable predicate (a property) that correct outputs must satisfy
• 6.006 studies problems on large general input spaces
• Not general: small input instance
  • Example: In this room, is there a pair of students with same birthday?
  • If birthday is just one of 365, for n > 365, answer always true by pigeon-hole
• General: arbitrarily large inputs
  • Example: Given any set of n students, is there a pair of students with same birthday (include year, time, etc.)?
  • Assume resolution of possible birthdays exceeds n

Algorithm

• Procedure mapping each input to a single output (deterministic)
  • If I give it an input, it will generate an output.
• Algorithm solves a problem if it returns a correct output for every problem input
• Example: An algorithm to solve birthday matching
  • Maintain a record of names and birthdays (initially empty)
  • Interview each student in some order
    • If birthday exists in record, return found pair!
    • Else add name and birthday to record
  • Return None if last student interviewed without success

Correctness

• Programs/algorithms have fixed size, so how to prove correct?
• For small inputs, can use case analysis
• For arbitrarily large inputs, algorithm must be recursive or loop in some way
• Must use induction (why recursion is such a key concept in computer science)
• Example: Proof of correctness of birthday matching algorithm
  • Induct on k: the number of students in record
  • Hypothesis: if first k contain match, returns match before interviewing student k+1
  • Base case: k = 0, first k contains no match
  • Assume for induction hypothesis holds for k = k’, and consider k = k’+1
  • If first k’ contains a match, already returned a match by induction
  • Else first k’ do not have match, so if first k’+1 has match, match contains k’+1
  • Then algorithm checks directly whether birthday of student k’+1 exists in first k’

Efficiency

• How fast does an algorithm produce a correct output? (compare to other possible ways)
  • Could measure time, but want performance to be machine independent
  • Idea! Don’t measure time, instead ount number of fixed-time operations algorithm takes to return
  • Expect to depend on size of input: larger input suggests longer time
  • Size of input is often called ‘n’, but not always!
  • Efficient if returns in polynomial time with respect to input
  • Sometimes no efficient algorithm exists for a problem! (See L20)
• Asymptotic Notation: ignore constant factors and low order terms
  • Upper bounds (O), lower bounds (Ω), tight(both) bounds (Θ)
  • ∈,=, is, order
  • Time estimate below based on one operation per cycle on a 1 GHz single-core machine
  • Particles in universe estimated < 10^100

input	constant	logarithmic	linear	log-linear	quadratic	polynomial	exponential
n	Θ(1)	Θ(log n)	Θ(n)	Θ(n log n)	Θ(n^2)	Θ(n^c)	2^Θ(n^c)
1000	1	≈ 10	1000	≈ 10,000	1,000,000	1000^c	2^1000 ≈ 10^301
Time	1 ns	10 ns	1 μs	10 μs	1 ms	10^(3c−9) s	10^281 millenia

Model of Computation

• Specification for what operations on the machine can be performed in O(1) time
• Model in this class is called the Word-RAM
• Machine word: block of w bits (w is word size of a w-bit Word-RAM)
• Memory: Addressable sequence of machine words
• Processor supports many constant time operations on a O(1) number of words (integers):
  • integer arithmetic: (+, -, *, //, %)
  • logical operators: (&&, ||, !, ==, <, >, <=, =>)
  • bitwise arithmetic: (&, |, «, », …)
  • Given word a, can read word at address a, write word to address a
• Memory address must be able to access every place in memory
  • Requirement: w ≥ # bits to represent largest memory address, i.e., log2 n
  • 32-bit words → max ∼ 4GB memory, 64-bit words → max ∼ 16 exabytes of memory
• Python is a more complicated model of computation, implemented on a Word-RAM

Data Structure

• A data structure is a way to store non-constant data, that supports a set of operations
• A collection of operations is called an interface
  • Sequence: Extrinsic order to items (first, last, nth)
  • Set: Intrinsic order to items (queries based on item keys)
• Data structures may implement the same interface with different performance
• Example: Static Array -fixed width slots, fixed length, static sequence interface
  • StaticArray(n): allocate static array of size n initialized to 0 in Θ(n) time
  • StaticArray.get at(i): return word stored at array index i in Θ(1) time
  • StaticArray.set at(i, x): write word x to array index i in Θ(1) time
• Stored word can hold the address of a larger object
• Like Python tuple plus set at(i, x), Python list is a dynamic array (see L02)

How to Solve an Algorithms Problem

1. Reduce to a problem you already know (use data structure or algorithm)

   Search Problem (Data Structures)	Sort Algorithms	Shortest Path Algorithms
   Static Array (L01)	Insertion Sort (L03)	Breadth First Search (L09)
   Linked List (L02)	Selection Sort (L03)	DAG Relaxation (L11)
   Dynamic Array (L02)	Merge Sort (L03)	Depth First Search (L10)
   Sorted Array (L03)	Counting Sort (L05)	Topological Sort (L10)
   Direct-Access Array (L04)	Radix Sort (L05)	Bellman-Ford (L12)
   Hash Table (L04)	AVL Sort (L07)	Dijkstra (L13)
   Balanced Binary Tree (L06-L07)	Heap Sort (L08)	Johnson (L14)
   Binary Heap (L08)		Floyd-Warshall (L18)

2. Design your own (recursive) algorithm

   • Brute Force
   • Decrease and Conquer
   • Divide and Conquer
   • Dynamic Programming (L15-L19)
   • Greedy / Incremental