PythonDS3¶
Resources¶
Modules¶
Checklist¶
- 1. Introduction
- 1.1. Objectives
- 1.2. Getting Started
- 1.3. What Is Computer Science?
- 1.4. What Is Programming?
- 1.5. Why Study Data Structures and Abstract Data Types?
- 1.6. Why Study Algorithms?
- 1.7. Review of Basic Python
- 1.8. Getting Started with Data
- 1.8.1. Built-in Atomic Data Types
- 1.8.2. Built-in Collection Data Types
- 1.9. Input and Output
- 1.9.1. String Formatting
- 1.10. Control Structures
- 1.11. Exception Handling
- 1.12. Defining Functions
- 1.13. Object-Oriented Programming in Python: Defining Classes
- 1.13.1. A Fraction Class
- 1.13.2. Inheritance: Logic Gates and Circuits
- 1.14. Summary
- 1.15. Key Terms
- 1.16. Discussion Questions
- 1.17. Programming Exercises
- 2. A Proper Class
- 2.1. Writing a Proper Python Class
- 2.1.1. A Basic implementation of the MSDie class
- 2.2. Making your Class Comparable
- 2.1. Writing a Proper Python Class
- 3. Analysis
- 3.1. Objectives
- 3.2. What Is Algorithm Analysis?
- 3.3. Big-O Notation
- 3.4. An Anagram Detection Example
- 3.4.1. Solution 1: Checking Off
- 3.4.2. Solution 2: Sort and Compare
- 3.4.3. Solution 3: Brute Force
- 3.4.4. Solution 4: Count and Compare
- 3.5. Performance of Python Data Structures
- 3.6. Lists
- 3.7. Dictionaries
- 3.8. Summary
- 3.9. Key Terms
- 3.10. Discussion Questions
- 3.11. Programming Exercises
- 4. Basic Data Structures
- 4.1. Objectives
- 4.2. What Are Linear Structures?
- 4.3. What is a Stack?
- 4.4. The Stack Abstract Data Type
- 4.5. Implementing a Stack in Python
- 4.6. Simple Balanced Parentheses
- 4.7. Balanced Symbols (A General Case)
- 4.8. Converting Decimal Numbers to Binary Numbers
- 4.9. Infix, Prefix, and Postfix Expressions
- 4.9.1. Conversion of Infix Expressions to Prefix and Postfix
- 4.9.2. General Infix-to-Postfix Conversion
- 4.9.3. Postfix Evaluation
- 4.10. What Is a Queue?
- 4.11. The Queue Abstract Data Type
- 4.12. Implementing a Queue in Python
- 4.13. Simulation: Hot Potato
- 4.14. Simulation: Printing Tasks
- 4.14.1. Main Simulation Steps
- 4.14.2. Python Implementation
- 4.14.3. Discussion
- 4.15. What Is a Deque?
- 4.16. The Deque Abstract Data Type
- 4.17. Implementing a Deque in Python
- 4.18. Palindrome-Checker
- 4.19. Lists
- 4.20. The Unordered List Abstract Data Type
- 4.21. Implementing an Unordered List: Linked Lists
- 4.21.1. The Node Class
- 4.21.2. The Unordered List Class
- 4.22. The Ordered List Abstract Data Type
- 4.23. Implementing an Ordered List
- 4.23.1. Analysis of Linked Lists
- 4.24. Summary
- 4.25. Key Terms
- 4.26. Discussion Questions
- 4.27. Programming Exercises
- 5. Recursion
- 5.1. Objectives
- 5.2. What Is Recursion?
- 5.3. Calculating the Sum of a List of Numbers
- 5.4. The Three Laws of Recursion
- 5.5. Converting an Integer to a String in Any Base
- 5.6. Stack Frames: Implementing Recursion
- 5.7. Introduction: Visualizing Recursion
- 5.8. Sierpinski Triangle
- 5.9. Complex Recursive Problems
- 5.10. Tower of Hanoi
- 5.11. Exploring a Maze
- 5.12. Dynamic Programming
- 5.13. Summary
- 5.14. Key Terms
- 5.15. Discussion Questions
- 5.16. Glossary
- 5.17. Programming Exercises
- 6. Sorting and Searching
- 6.1. Objectives
- 6.2. Searching
- 6.3. The Sequential Search
- 6.3.1. Analysis of Sequential Search
- 6.4. The Binary Search
- 6.4.1. Analysis of Binary Search
- 6.5. Hashing
- 6.5.1. Hash Functions
- 6.5.2. Collision Resolution
- 6.5.3. Implementing the Map Abstract Data Type
- 6.5.4. Analysis of Hashing
- 6.6. Sorting
- 6.7. The Bubble Sort
- 6.8. The Selection Sort
- 6.9. The Insertion Sort
- 6.10. The Shell Sort
- 6.11. The Merge Sort
- 6.12. The Quick Sort
- 6.13. Summary
- 6.14. Key Terms
- 6.15. Discussion Questions
- 6.16. Programming Exercises
- 7. Trees and Tree Algorithms
- 7.1. Objectives
- 7.2. Examples of Trees
- 7.3. Vocabulary and Definitions
- 7.4. List of Lists Representation
- 7.5. Nodes and References
- 7.6. Parse Tree
- 7.7. Tree Traversals
- 7.8. Priority Queues with Binary Heaps
- 7.9. Binary Heap Operations
- 7.10. Binary Heap Implementation
- 7.10.1. The Structure Property
- 7.10.2. The Heap Order Property
- 7.10.3. Heap Operations
- 7.11. Binary Search Trees
- 7.12. Search Tree Operations
- 7.13. Search Tree Implementation
- 7.14. Search Tree Analysis
- 7.15. Balanced Binary Search Trees
- 7.16. AVL Tree Performance
- 7.17. AVL Tree Implementation
- 7.18. Summary of Map ADT Implementations
- 7.19. Summary
- 7.20. Key Terms
- 7.21. Discussion Questions
- 7.22. Programming Exercises
- 8. Graphs and Graph Algorithms
- 8.1. Objectives
- 8.2. Vocabulary and Definitions
- 8.3. The Graph Abstract Data Type
- 8.4. An Adjacency Matrix
- 8.5. An Adjacency List
- 8.6. Implementation
- 8.7. The Word Ladder Problem
- 8.8. Building the Word Ladder Graph
- 8.9. Implementing Breadth First Search
- 8.10. Breadth First Search Analysis
- 8.11. The Knight’s Tour Problem
- 8.12. Building the Knight’s Tour Graph
- 8.13. Implementing Knight’s Tour
- 8.14. Knight’s Tour Analysis
- 8.15. General Depth First Search
- 8.16. Depth First Search Analysis
- 8.17. Topological Sorting
- 8.18. Strongly Connected Components
- 8.19. Shortest Path Problems
- 8.20. Dijkstra’s Algorithm
- 8.21. Analysis of Dijkstra’s Algorithm
- 8.22. Prim’s Spanning Tree Algorithm
- 8.23. Summary
- 8.24. Key Terms
- 8.25. Discussion Questions
- 8.26. Programming Exercises
- 9. Advanced Topics
- 9.1. Objectives
- 9.2. Python Lists Revisited
- 9.3. Dictionaries Revisited: Skip Lists
- 9.3.1. The Map Abstract Data Type
- 9.3.2. Implementing a Dictionary in Python
- 9.4. Trees Revisited: Quantizing Images
- 9.4.1. A Quick Review of Digital Images
- 9.4.2. Quantizing an Image
- 9.4.3. An Improved Quantization Algorithm Using OctTrees
- 9.5. Recursion Revisited
- 9.5.1. Modular Arithmetic Theorems
- 9.5.2. Modular Exponentiation
- 9.5.3. The Greatest Common Divisor and Multiplicative Inverses
- 9.5.4. RSA Algorithm
- 9.6. Graphs Revisited: Pattern Matching
- 9.6.1. Biological Strings
- 9.6.2. Simple Comparison
- 9.6.3. Using Graphs: Finite State Automata
- 9.6.4. Using Graphs: Knuth-Morris-Pratt
- 9.7. Summary
- 9.8. Key Terms
- 9.9. Discussion Questions
- 9.10. Programming Exercises