Introduction to Algorithms - Lecture 1

Instructors

• Jason Kuh (teaching today)
• Eric Domain
• Justin Solomon

Course Goals

1. **Solve Computational Problems:

   • More than just solving, also
   • Prove Correctness
   • Argue Efficiency
   • Communicate solutions effectively**

2. Communication

   • Emphasis on writing over coding
   • Proving solutions are correct and better than others
   • Focus on convincing others, not just computers

What is a Computational Problem?

• Definition: Problem with a set of inputs and outputs, representing a binary relation.
• Requires Correct mapping: For each input, specify correct outputs
• Example: Given an array, find the index containing value '5'.
• Problem Specification: Usually defined by a predicate rather than exhaustively mapping all input-output pairs.

Generalization of Problems

• Design algorithms to apply to any input size
• Example: Birthday problem—checking if any students have the same birthday
• Target general, deterministic algorithms for any size of inputs

What is an Algorithm?

• Definition: Function mapping inputs to correct outputs
• Must produce correct output for every input
• Example: Algorithm to check for matching birthdays amongst students

Example Algorithm: Birthday Problem

• Steps:
  • Maintain a record
  • Interview students in order
  • Check if the birthday is in the record
  • If found, return the pair; otherwise, add to the record

Proving Correctness

• Techniques: Use mathematical induction
• Inductive Hypothesis: If the first K students contain a match, the algorithm returns a match before interviewing the K+1 student.
• Steps for Inductive Proof:
  1. Base Case: Zero students (trivially true)
  2. Inductive Step: Use the hypothesis to ensure the algorithm works for K+1

Efficiency

• Measure by counting fundamental operations, not actual time
• Avoid machine-dependent measures of time
• Use asymptotic analysis to abstract time complexity
• Efficiency Classes:
  • Constant time O(1)
  • Logarithmic time O(log n)
  • Linear time O(n)
  • Linearithmic time O(n log n)
  • Quadratic time O(n^2)
  • Polynomial time O(n^c)
  • Exponential time O(2^n)

Asymptotic Notation

• Big O (O): Upper bounds
• Omega (Ω): Lower bounds
• Theta (Θ): Tight bounds (both upper and lower)
• Visualizing Time Complexity: Constant
  • Constant: Flat line
  • Logarithmic: Rapid growth then flattening
  • Linear: Straight diagonal line
  • Quadratic: Steeper curve
  • Exponential: Very steep curve

Measuring Time in Algorithms

• Define a model of computation (e.g., word RAM)
• Operations: Binary operations, comparisons, reading/writing from memory
• Memory Access: Access in chunks (bytes, words)
• Efficiency in terms of operations: Ignore hardware

Data Structures & Recursion

• Static Arrays in Python analogous less useful
• Focus will be on data structures that make operations faster

Class Structure

• Lectures:
  1. Data Structures & Sorting (1st Quiz)
  2. Shortest Paths & Graph Algorithms (2nd Quiz)
  3. Dynamic Programming (3rd Quiz)

Conclusion

• This is the end of the first lecture.
• Review induction if unfamiliar. Get ready for more writing than coding.

Key Takeaways

• Understanding problem and algorithm definitions
• Importance of proving correctness and efficiency
• Introduction to asymptotic analysis and time complexity notations
• Structure of the course and focus areas