DSpy - Data Structures using Python

Created by idebtor@gmail.com

Collaborators: 박준혁, 이경준

Open textbook referenced here: https://runestone.academy/runestone/books/published/pythonds3/index.html

Chapter 1. Introduction to Data Structures and Python

1.1 Objectives

- 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.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
- 2.1. Writing a Proper Python Class
    - 2.1.1. A Basic implementation of the MSDie class
- 2.2. Making your Class Comparable

1.14. Summary

1.16. Discussion Questions

1.17. Programming Exercises

Chapter 2. Performance Analysis

Introduction

- 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.10. Discussion Questions

3.11. Programming Exercises

Chapter 3. Linear Data Structures

Introduction

- 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.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.26. Discussion Questions
- 4.27. Programming Exercises

Chapter 4. Recursion

Introduction

- 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.13. Summary

5.15. Discussion Questions

5.17. Programming Exercises

Chapter 5. Sorting, Hashing and Searching

Introduction

- 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.15. Discussion Questions

6.16. Programming Exercises

Chapter 6. Trees and Tree Algorithms

Introduction

- 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.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.21. Discussion Questions

7.22. Programming Exercises

Chapter 7. Heap and Priority Queues

Introduction

Objectives
- 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
- Heap Sort

7.19. Summary

7.21. Discussion Questions

7.22. Programming Exercises

Chapter 8. Graph and Graph Algorithms

Introduction

- 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.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.25. Discussion Questions

8.26. Programming Exercises

Chapter 9. Advanced Topics