Problem Solving with Algorithms and Data Structures

Problem Solving with Algorithms and Data Structures (online Book)

By Brad Miller and David Ranum, Luther College

Introduction

• Introduction
  • Objectives
  • Getting Started
  • What Is Computer Science?
  • Review of Basic Python
  • Summary
  • Key Terms
  • Discussion Questions
  • Programming Exercises

Analysis

• Algorithm Analysis
  • Objectives
  • What Is Algorithm Analysis?
  • Performance of Python Data Structures
  • Summary
  • Key Terms
  • Discussion Questions
  • Programming Exercises

Basic Data Structures

• Basic Data Structures
  • Objectives
  • What Are Linear Structures?
• Stacks
  • What is a Stack?
  • The Stack Abstract Data Type
  • Implementing a Stack in Python
  • Simple Balanced Parentheses
  • Balanced Symbols (A General Case)
  • Converting Decimal Numbers to Binary Numbers
  • Infix, Prefix and Postfix Expressions
• Queues
  • What Is a Queue?
  • The Queue Abstract Data Type
  • Implementing a Queue in Python
  • Simulation: Hot Potato
  • Simulation: Printing Tasks
• Deques
  • What Is a Deque?
  • The Deque Abstract Data Type
  • Implementing a Deque in Python
  • Palindrome-Checker
• Lists
  • The Unordered List Abstract Data Type
  • Implementing an Unordered List: Linked Lists
  • The Ordered List Abstract Data Type
  • Implementing an Ordered List
• Summary
• Key Terms
• Discussion Questions
• Programming Exercises

Recursion

• Recursion
• Objectives
• What Is Recursion?
  • Calculating the Sum of a List of Numbers
  • The Three Laws of Recursion
  • Converting an Integer to a String in Any Base
• Stack Frames: Implementing Recursion
• Visualizing Recursion
  • Sierpinski Triangle
• Complex Recursive Problems
  • Tower of Hanoi
• Exploring a Maze
• Dynamic Programming
• Summary
• Key Terms
• Discussion Questions
• Programming Exercises

Sorting and Searching

• Sorting and Searching
  • Objectives
  • Searching
• Sorting
  • The Bubble Sort
  • The Selection Sort
  • The Insertion Sort
  • The Shell Sort
  • The Merge Sort
  • The Quick Sort
• Searching and Sorting
  • Summary
  • Key Terms
  • Discussion Questions
  • Programming Exercises

Trees and Tree Algorithms

• Trees
  • Objectives
  • Examples of Trees
  • Vocabulary and Definitions
• Implementation
  • List of Lists Representation
  • Nodes and References
• Binary Tree Applications
  • Parse Tree
  • Tree Traversals
• Priority Queues with Binary Heaps
  • Binary Heap Operations
  • Binary Heap Implementation
• Binary Search Trees
  • Search Tree Operations
  • Search Tree Implementation
  • Search Tree Analysis
• Balanced Binary Search Trees
  • AVL Tree Performance
  • AVL Tree Implementation
  • Summary of Map ADT Implementations
• Summary
• Key Terms
• Discussion Questions
• Programming Exercises

Graphs and Graph Algorithms

• Graphs
  • Objectives
  • Vocabulary and Definitions
  • The Graph Abstract Data Type
• Breadth First Search
  • The Word Ladder Problem
  • Building the Word Ladder Graph
  • Implementing Breadth First Search
  • Breadth First Search Analysis
• Depth First Search
  • The Knight’s Tour Problem
  • Building the Knight’s Tour Graph
  • Implementing Knight’s Tour
  • Knight’s Tour Analysis
  • General Depth First Search
  • Depth First Search Analysis
• Topological Sorting
• Strongly Connected Components
• Shortest Path Problems
  • Dijkstra’s Algorithm
  • Analysis of Dijkstra’s Algorithm
  • Prim’s Spanning Tree Algorithm
• Summary
• Key Terms
• Discussion Questions
• Programming Exercises