Introduction to Algorithms - Lecture 1

Instructor Introduction

• Instructor: Jason Kuh
• Co-instructors: Eric Domain and Justin Solomon
• Structure: Jason teaches the first lecture, then each co-instructor teaches one of the next two lectures

Course Goals

• Primary Goal: Solve computational problems
• Secondary Goals:
  • Prove correctness of solutions
  • Argue efficiency of solutions
• Communication: Emphasis on communicating solutions' correctness and efficiency. Expect more writing than coding.
  • Be able to write proofs and explain logic.

Definition of Computational Problems

• Inputs and Outputs:
  • A set of inputs and a set of outputs
  • Binary relation between inputs and outputs
• Predicate: Check if a given input-output pair is correct
• Example: Birthday problem with students in a classroom
  • Determine if any two students have the same birthday (considering years and hours for a larger input space)

Definition of Algorithms

• Concept: Fixed-size procedure to generate correct outputs for given inputs
• Function: Maps inputs to outputs, must be correct for all valid inputs
• Algorithm Example: Checking for matching birthdays in a class
  • Maintain a record, interview students in order, check for matches, and update record
• Algorithm Steps:
  • Maintain a record
  • Interview students (check if birthday is in record, return pair if matched, add to record if not)
  • Return 'none' if no matches found

Proving Correctness: Induction

• Inductive Hypothesis: After interviewing the first k students, a match is found if it exists
• Base Case: k = 0 (vacuously true)
• Inductive Step:
  • Assume true for k
  • Prove for k + 1 (check current student against record, update record, maintain hypothesis)

Efficiency and Asymptotic Analysis

• Goal: Compare algorithmic efficiency abstractly (without actual time measurement)
• Fundamental Operations: Count operations instead of measuring real-world time
• Asymptotic Notation:
  • Big O (upper bound)
  • Omega (lower bound)
  • Theta (tight bound)
• Common Running Times:
  • Constant time (O(1))
  • Logarithmic time (O(log n))
  • Linear time (O(n))
  • Log-linear time (O(n log n))
  • Quadratic time (O(n^2))
  • Polynomial time (O(n^c))
  • Exponential time (O(2^n))
• Graphical Representation:
  • Comparison of different time complexities (constant, linear, logarithmic, exponential)

Model of Computation

• Word RAM: Utilized for theoretical brevity
• Random Access Memory (RAM): Assumes constant-time access to any part of memory
• Memory Operations: Read/write operations, addressing by bytes (typically 64 bits in modern CPUs)
• CPU Operations: Binary operations, integer arithmetic, reading/writing words in constant time

Data Structures

• Importance: To operate on/store large amounts of data efficiently
• Python Data Structures: Lists, sets, dictionaries, etc. (abstracted from direct memory access)
• Focus on static arrays and other efficient data structures

Course Structure and Topics

• Major Topics: Data structures, sorting, shortest paths, dynamic programming
• Course Outline:
  • Quiz 1: Data structures and sorting (first 8 lectures)
  • Quiz 2: Shortest paths algorithms
  • Final Quiz: Dynamic programming

Final Remarks

• Expect to use induction, be comfortable with proofs, and communicate effectively.
• Prepare for writing detailed algorithm descriptions and efficiency proofs.