Skip to content

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
  • 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