Lecture 2: Introduction to Algorithms

Instructor: Eric Domain

Key Topics

• Data Structures
• Interfaces vs. Data Structures
• Sequence and Set Interfaces
• Linked Lists
• Dynamic Arrays

Interfaces vs. Data Structures

• Interface (API/ADT): Says what you want to do.
  • Specifies operations and their meanings.
• Data Structure: Says how you do it.
  • Provides algorithms to support operations.
• Important distinction: Specify problem vs. solve problem.

Main Interfaces

• Set: Store n arbitrary things (integers, strings) with operations like sorting/searching.
• Sequence: Maintain specific order (e.g., list in Python).
  • Operations: Build, Length, Iteration, Get, Set.

Sequence Data Structures

• Static Sequence Interface: (fixed number of items)

  • Operations: Build, Length, Iteration, Get, Set.
  • Implementation: Static Array
    • Array access in constant time if elements are stored consecutively in memory.
    • Linear time for building and accessing the entire array.
    • Assumes memory allocation in linear time (memory allocation model).

• Dynamic Sequence Interface: (number of items can change)

  • Operations: Get/Add, Insert/Delete First/Last, Insert/Delete at any position.
  • Challenges: Efficiently support dynamic operations.

Data Structure Implementations

Static Array

• Efficient random access but poor at dynamic operations.
• Insert/Delete at specific position: Linear Time
• Insert/Delete last: Linear Time (due to memory reallocation)

Linked List

• Efficient insert/delete at both ends, poor at random access.
• Structure: Nodes with item and next pointer.
  • Head: Points to first node.
  • Insert/Delete first: Constant time.
  • Get/Set at: Linear time (proportional to position).

Dynamic Array

• Combines benefits of arrays and linked lists.
• Basic Idea: Size of array is roughly n (number of items).
  • When full, double the size of the array (constant factor larger: e.g., 2 * size).
  • Use amortized analysis to manage resizing costs efficiently.

Implementing Dynamic Array

• Insert Last: (when space available)
  • Place new item at A[length] and increment length: Constant time.
  • Manage actual array resizing by doubling size when needed: Amortized constant time (over sequence of operations).

Amortized Analysis

• Key Idea: Spread out the cost of resizing over many operations.
• Amortized Time: If k operations take at most k * T(n) time, average out expensive operations.
  • Example: Resizing costs linear but averages out to constant time over many insertions.

Summary of Sequence Data Structures

| Operation | Static Array | Linked List | Dynamic Array | |-------------------|-----------------|--------------|-------------------------| | Get/Add | Constant | Linear | Constant | | Insert/Delete First| Linear | Constant | Linear | | Insert/Delete Last | Linear | Linear | Amortized constant | | Insert/Delete At | Linear | Linear | Linear |

• Static Array: Good for random access, bad for dynamic changes.
• Linked List: Good for dynamic changes at ends, bad for random access.
• Dynamic Array: Balance of both; good for random access and dynamic changes, with amortized efficiency.