Author: 👤 Brad Miller

Type: #book

Genres: #comp-sci

Date: 2021-10-26

---

Problem Solving with Algorithms and Data Structures using Python

1 Introduction

• What is procedural abstraction?
• Parent classes can call methods that don't yet exist
• IS-A vs HAS-A class relationships

3 Analysis

• Using the number of assignments as a unit of computation
• O(1) constant runtime function

4 Basic Data Structures

• What is a stack?
• Stacks reverse the items they contain
• Operations of a stack
• Implementing a stack in python
• What is a queue?
• Operations of a queue
• Implementing a queue in python
• What is a deque?
• Operations of a deque
• Implementing a deque in python
• What is an unordered list?
• Operations of an unordered list
• Implementing a linked list in python
• What is an ordered list?
• Operations of an ordered list
• Implementing an ordered list in python

5 Recursion

• The three characteristics of recursive algorithms
• What is a base case?

6 Sorting and Searching

• What is sequential search?
• Implementing a sequential search algorithm in python
• What is a binary search?
• Implementation of a binary search algorithm in python
• Runtime function of a binary search
• What is a hash table?
• Folding method hash function
• Mid-square method hash function
• Hashing a string in python
• Resolving hash collisions
• What is a map data type?
• Operations of a map datatype
• Implementing a hashmap in python
• Hashmap runtime analysis
• What is a bubble sort?
• Implementing a bubble sort algorithm in python
• Bubble sort runtime function
• What is a selection sort?
• Implementing a selection sort algorithm in python
• Selection sort runtime function
• What is an insertion sort?
• Implementing an insertion sort algorithm in python
• What is a shell sort?
• Implementing a shell sort algorithm in python
• What is a merge sort?
• Implementing a merge sort algorithm in python
• What is a quick sort?
• Implementing a quick sort algorithm using python

7 Trees and Tree Algorithms

• What is a binary tree?
• Implementing a binary tree using python
• Preorder tree traversal
• Postorder tree traversal
• Inorder tree traversal
• What is a binary heap?
• Operations of a binary heap
• Complete binary trees
• How a heap is ordered
• Implementing a binary heap using a list
• Implementing a binary heap using python
• What is a binary search tree?
• Implementing a binary search tree using python
• What is an AVL tree?
• Rebalancing a tree with rotations
• Implementing an AVL tree using python

8 Graphs and Graph Algorithms

• What is a graph?
• What is an adjacency matrix?
• What is an adjacency list?
• Implementing a graph using python
• What is breadth first search?
• Implementing breadth first search on a graph
• What is a depth first search?
• Implementing depth first search on a graph
• What is a topological sort algorithm?
• What is a strongly connected component?
• Graph transpositions
• Dijkstra's algorithm
• What is a spanning tree?
• What is a greedy algorithm?
• Prim's algorithm