6.006 Introduction to Algorithms, Lecture 1: Introduction

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 1: Introduction Lecture 1: Introduction The goal of this class is to teach you to solve computation problems, and to communicate that your solutions are correct and efficient. Problem • Binary relation from problem inputs to correct outputs • Usually don’t specify every correct output for all inputs (too many!) • 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? • General: arbitrarily large inputs – Example: Given any set of n students, 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 – Assume resolution of possible birthdays exceeds n (include year, time, etc.) Algorithm • Procedure mapping each input to a single output (deterministic) • 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 2 Lecture 1: Introduction 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 = k0 , and consider k = k 0 + 1 – If first k 0 contains a match, already returned a match by induction – Else first k 0 do not have match, so if first k 0 + 1 has match, match contains k 0 + 1 – Then algorithm checks directly whether birthday of student k 0 + 1 exists in first k 0 Efficiency • How fast does an algorithm produce a correct output? – Could measure time, but want performance to be machine independent – Idea! Count 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 bounds (Θ) ∈, =, is, order – Time estimate below based on one operation per cycle on a 1 GHz single-core machine – Particles in universe estimated < 10100 input n 1000 Time constant Θ(1) 1 1 ns logarithmic Θ(log n) ≈ 10 10 ns linear Θ(n) 1000 1 µs log-linear Θ(n log n) ≈ 10,000 10 µs quadratic Θ(n2 ) 1,000,000 1 ms polynomial Θ(nc ) 1000c 103c−9 s exponential c 2Θ(n ) 21000 ≈ 10301 10281 millenia Lecture 1: Introduction 3 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 ∼ 4 GB 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) 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Lecture 1: Introduction def birthday_match(students): ’’’ Find a pair of students with the same birthday Input: tuple of student (name, bday) tuples Output: tuple of student names or None ’’’ n = len(students) # O(1) record = StaticArray(n) # O(n) for k in range(n): # n (name1, bday1) = students[k] # O(1) # Return pair if bday1 in record for i in range(k): # k (name2, bday2) = record.get_at(i) # O(1) if bday1 == bday2: # O(1) return (name1, name2) # O(1) record.set_at(k, (name1, bday1)) # O(1) return None # O(1) Example: Running Time Analysis • Two loops: outer k ∈ {0, . . . , n − 1}, inner is i ∈ {0, . . . , k} P 2 • Running time is O(n) + n−1 k=0 (O(1) + k · O(1)) = O(n ) • Quadratic in n is polynomial. Efficient? Use different data structure for record! How to Solve an Algorithms Problem 1. Reduce to a problem you already know (use data structure or algorithm) Search Problem (Data Structures) Static Array (L01) Linked List (L02) Dynamic Array (L02) Sorted Array (L03) Direct-Access Array (L04) Hash Table (L04) Balanced Binary Tree (L06-L07) Binary Heap (L08) Sort Algorithms Insertion Sort (L03) Selection Sort (L03) Merge Sort (L03) Counting Sort (L05) Radix Sort (L05) AVL Sort (L07) Heap Sort (L08) 2. Design your own (recursive) algorithm • Brute Force • Decrease and Conquer • Divide and Conquer • Dynamic Programming (L15-L19) • Greedy / Incremental Shortest Path Algorithms Breadth First Search (L09) DAG Relaxation (L11) Depth First Search (L10) Topological Sort (L10) Bellman-Ford (L12) Dijkstra (L13) Johnson (L14) Floyd-Warshall (L18)