006: Introduction to Algorithms - Lecture 2

Lecture Overview

• Instructor: Eric Domain
• Focus: Data Structures (not algorithms directly)
• Topics: Sequences, Sets, Linked Lists, Dynamic Arrays

Key Concepts

Interface vs. Data Structure

• Interface (API/ADT): Specifies what you want to do (operations and their meanings).
• Data Structure: Specifies how you do it (actual representation and storage methods).
• The same problem can have multiple data structure solutions, each with different advantages.
• Important to maintain the interface while choosing the right data structure based on use case.

Sequences and Sets

• Set: Stores items without regard to order (mathematical set concept).
• Sequence: Maintains a specific order of elements.
• Operations may include keeping elements in order, searching, or modifying sequences.

Sequence Data Structures

Static Sequence Interface

• Consists of operations: build, length, iteration, get, set.
• Designed for sequences where the number of items (n) does not change.
• Static Array: Common implementation, supports constant time get and set operations.

Memory Model

• Word RAM Model: Assumes memory is an array of w-bit words.
• Memory Allocation: Creating an array of size n takes linear time.
• Word Size: Must be at least log n to address all items efficiently.

Dynamic Sequence Interface

• Supports additional operations: insert, delete, insert first/last, delete first/last.
• Insertions and deletions change the sequence size dynamically.

Data Structures for Dynamic Sequences

Linked Lists

• Nodes containing an item and a pointer to the next node.
• Efficient for inserting and deleting the first element.
• Inefficient for random access (requires traversing nodes).
• Insert/Delete at first: Constant time.
• Get/Set at arbitrary position: Linear time.

Dynamic Arrays

• Aim to combine the advantages of arrays and linked lists.
• Resize Strategy: Double the array size when full.
• Allows for amortized constant time for inserting at the end (inserting n items takes linear total time).
• Supports constant get and set operations.

Summary of Data Structures

• Static Arrays: Efficient random access, inefficient dynamic operations.
• Linked Lists: Efficient for dynamic operations at the start, inefficient random access.
• Dynamic Arrays: Combines efficient random access with amortized efficient dynamic operations.

Amortized Analysis

• An operation takes T(n) amortized time if any k operations take at most k*T(n) time in total.
• Essential for understanding the efficiency of operations over a sequence of actions.

Conclusion

• Dynamic arrays are vital in understanding how languages like Python handle lists efficiently.
• Focusing on amortized analysis helps in balancing the efficiency of various operations in data structures.