Introduction to Algorithms Lecture 1

Instructor Introduction

• Instructor: Jason Kuh
• Co-Instructors: Eric Domain, Justin Solomon
• Course: Introduction to Algorithms

Course Overview

• Objective: Teaching to solve computational problems
  • Solve problems
  • Communicate solutions to others
  • Prove correctness
  • Argue efficiency
• Emphasis on communication and writing over coding

Understanding Computational Problems

• **Definition of a Problem: ** Set of inputs and a set of possible outputs
  • Binary relation between inputs and outputs (bipartite graph)
  • Use predicates for problem definition
• Example: Birthday Problem
  • Check if any pair has the same birthday
  • Generalize by considering larger input spaces
• Algorithm Definition: Function mapping inputs to correct outputs

Proposed Algorithm for Birthday Problem

• Steps:
  • Maintain a record of birthdays
  • Interview students one by one
  • Check if birthday already exists in record
  • Return pair if match found, else add to record
• Algorithm Characteristics:
  • Function that maps inputs to outputs
  • Must produce correct outputs for all inputs

Proving Correctness

• Proof Method: Induction
  • Base Case: Verify hypothesis for initial simple case (e.g., 0 students)
  • Inductive Step: Assume true for k students, prove for k+1
  • Inductive Hypothesis: After interviewing k students, correct return or continue

Efficiency and Performance

• Efficiency: Measure of algorithm's performance
  • Not reliant on hardware specifics (e.g., computer speed)
• Concept: Asymptotic Analysis
  • Count fundamental operations rather than time
  • Measure dependence on input size

Common Running Time Complexities

• Constant Time: θ(1)
• Logarithmic Time: θ(log n)
• Linear Time: θ(n)
• Linearithmic Time: θ(n log n)
• Quadratic Time: θ(n²)
• Exponential Time: 2^θ(n)
  • Prefer lower-order polynomial time for efficiency

Measuring Efficiency

• Model of Computation: Word RAM model
  • Random Access Memory (RAM)
  • CPU operates on fixed-size words
• Operations: Binary operations, comparisons, read/write
• Data Structures: Key focus for efficient algorithms

Course Structure

• Focus Areas:
  • First Quiz: Data structures and sorting
  • Second Quiz: Shortest paths algorithms and graphs
  • Final Quiz: Dynamic programming
• Design Strategies:
  • Reduce to known problems
  • Design recursive algorithms

Conclusion

• Emphasis on critical thinking, problem-solving, and effective communication in algorithms
• Preparation for varied computational problem solving in real-world applications