Administrivia¶

0.1. How to Use this System

Week 1 Introduction, Java Review¶

1.1. Chapter Introduction
1.2. Data Structures and Algorithms
- 1.2.1. Data Structures and Algorithms
- 1.2.2. Some Software Engineering Topics
1.3. Testing
- 1.3.1. Testing vs. Debugging
1.4. JUnit Testing And You
- 1.4.1. Getting Started
1.5. Writing JUnit Tests
- 1.5.1. Writing JUnit Tests
1.6. Writing JUnit Tests with student.TestCase
1.7. Code Coverage In JUnit
- 1.7.1. Code Coverage In JUnit
  - 1.7.1.1. Using EclEmma
1.8. Bowling Example
- 1.8.1. Bowling Example
1.9. Commenting guidelines

Week 2 Arrays, Linear and Binary Search¶

2.1. Chapter Introduction: Search
2.2. Analyzing Search in Unsorted Lists
- 2.2.1. Analyzing Search in Unsorted Lists
  - 2.2.1.1. Lower Bounds Proofs
2.3. Searching in an Array
- 2.3.1. Searching in an Array
  - 2.3.1.1. Sequential Search
  - 2.3.1.2. Binary Search
2.4. Search in Sorted Arrays
- 2.4.1. Analysis
2.5. Logarithms
- 2.5.1. Logarithms

Week 3 Hash Tables¶

3.1. Introduction
- 3.1.1. Introduction
3.2. Hash Function Principles
- 3.2.1. Hash Function Principles
3.3. Open Hashing
- 3.3.1. Open Hashing
3.4. Bucket Hashing
- 3.4.1. Bucket Hashing
- 3.4.2. An Alternate Approach
3.5. Collision Resolution
- 3.5.1. Collision Resolution
  - 3.5.1.1. The Problem with Linear Probing
3.6. Improved Collision Resolution
3.7. Deletion
- 3.7.1. Deletion
- 3.7.2. Hashing Deletion Summary Questions
3.8. Sample Hash Functions
3.9. Analysis of Closed Hashing
- 3.9.1. Analysis of Closed Hashing
3.10. Hashing Chapter Summary Exercises
- 3.10.1. Hashing Review

Week 5 Algorithm Analysis (Big O)¶

5.1. Chapter Introduction
5.2. Analyzing Problems
- 5.2.1. Analyzing Problems
5.3. Asymptotic Analysis and Upper Bounds
- 5.3.1. Asymptotic Analysis and Upper Bounds
5.4. Best, Worst, and Average Cases
- 5.4.1. Best, Worst, and Average Cases
5.5. Common Misunderstandings
- 5.5.1. Common Misunderstandings
5.6. Comparing Algorithms
- 5.6.1. Comparing Algorithms
- 5.6.2. Growth Rates Ordering Exercise
5.7. Faster Computer, or Faster Algorithm?
- 5.7.1. Faster Computer, or Faster Algorithm?
5.8. Problems, Algorithms, and Programs
- 5.8.1. Problems, Algorithms, and Programs
5.9. Algorithm Analysis Summary Exercises
- 5.9.1. Summary Exercise: CS2

Week 6 Recursion: Sorting and Binary Search Revisited¶

6.1. Introduction
- 6.1.1. Introduction
6.2. Tracing Practice Exercises
6.3. Tracing Recursive Code
- 6.3.1. Tracing Recursive Code
  - 6.3.1.1. A Domino Analogy
  - 6.3.1.2. Towers of Hanoi
6.4. Code Completion Practice Exercises
6.5. Quicksort
6.6. Quicksort
6.7. An Empirical Comparison of Sorting Algorithms
- 6.7.1. An Empirical Comparison of Sorting Algorithms
6.8. Sorting Summary Exercises
- 6.8.1. Sorting Summary Exercises

Week 8 Linear Linked Structures¶

8.1. Chapter Introduction: Lists
8.2. The List ADT
- 8.2.1. The List ADT
  - 8.2.1.1. Defining the ADT
- 8.2.2. List ADT Programming Exercise
8.3. Array-Based List Implementation
8.4. Link Nodes
- 8.4.1. Link Nodes
8.5. Link Nodes Practice Exercises
8.6. Linked Lists
- 8.6.1. Linked Lists
- 8.6.2. Linked List Remove
8.7. Queues
- 8.7.1. Queue Terminology and Implementation
- 8.7.2. Array-based Dequeue Practice
8.8. Stacks
- 8.8.1. Stack Terminology and Implementation
  - 8.8.1.1. Array-Based Stacks
- 8.8.2. Pop
8.9. Linked Queues
8.10. Linked Stacks
- 8.10.1. Linked Stack Implementation
  - 8.10.1.1. Linked Stack Push
- 8.10.2. Linked Stack Pop
  - 8.10.2.1. Comparison of Array-Based and Linked Stacks
8.11. Comparison of List Implementations
- 8.11.1. Space Comparison
- 8.11.2. Time Comparison
  - 8.11.2.1. Practice Questions
8.12. Linear Structure Summary Exercises
- 8.12.1. Practice Questions
- 8.12.2. Chapter Review Questions
8.13. Practice Exercises
8.14. More Practice Exercises

Week 10 Recursion¶

9.1. Writing a recursive function
- 9.1.1. Writing a recursive function
9.2. Writing Practice Exercises
9.3. Implementing Recursion
9.4. Harder Code Completion Practice Exercises
9.5. Writing More Sophisticated Recursive Functions

Week 11 Non-Linear Linked Structures: Trees¶

10.1. General Trees
- 10.1.1. General Trees
10.2. Sequential Tree Representations
10.3. Array Implementation for Complete Binary Trees
- 10.3.1. Array Implementation for Complete Binary Trees

Week 12 Tree Traversals¶

11.1. Binary Trees Chapter Introduction
11.2. Implementing Tree Traversals
- 11.2.1. Implementing Tree Traversals
  - 11.2.1.1. Base Case
  - 11.2.1.2. The Recursive Call
- 11.2.2. Binary Tree Increment By One Exercise
11.3. Binary Search Trees
11.4. Binary Trees
- 11.4.1. Definitions and Properties
- 11.4.2. Practice Questions
11.5. Binary Tree Chapter Summary
- 11.5.1. Summary Questions
11.6. Binary Tree Node Implementations
- 11.6.1. Binary Tree Node Implementations
11.7. Binary Tree Space Requirements
- 11.7.1. Binary Tree Space Requirements
11.8. Binary Tree Traversals
11.9. Binary Tree as a Recursive Data Structure
- 11.9.1. Binary Tree as a Recursive Data Structure

Week 13 Applications: Puzzles, Calculators¶

12.1. Huffman Coding Trees
- 12.1.1. Huffman Coding Trees
12.2. Proof of Optimality for Huffman Coding
- 12.2.1. Proof of Optimality for Huffman Coding

Week 14 Non-Linear Data Structures: Graphs¶

13.1. Graphs Chapter Introduction
- 13.1.1. Graph Terminology and Implementation
  - 13.1.1.1. Graph Representations
- 13.1.2. Graph Terminology Questions
13.2. Graph Implementations
13.3. Graph Concepts Summary
- 13.3.1. Graph Concepts Summary

Week 15 Graph Traversals¶

14.1. Graph Traversals
- 14.1.1. Graph Traversals
  - 14.1.1.1. Depth-First Search
- 14.1.2. Breadth-First Search

Week 16 Advanced Graph Algorithms¶

15.1. All-Pairs Shortest Paths
15.2. Kruskal’s Algorithm
- 15.2.1. Kruskal’s Algorithm
15.3. Minimal Cost Spanning Trees
- 15.3.1. Minimal Cost Spanning Trees
  - 15.3.1.1. Prim’s Algorithm
  - 15.3.1.2. Prim’s Algorithm Alternative Implementation
15.4. Shortest-Paths Problems
- 15.4.1. Shortest-Paths Problems
  - 15.4.1.1. Single-Source Shortest Paths
15.5. Topological Sort
- 15.5.1. Topological Sort
  - 15.5.1.1. Depth-first solution
  - 15.5.1.2. Queue-based Solution

Week 17 Last Week, Finals¶

16.1. Glossary
16.2. Bibliography

Index
Search Page

ITSC 2214 Data Structures and Algorithms Spr 24

Table Of Contents

Search the book

Administrivia¶

Week 1 Introduction, Java Review¶

Week 2 Arrays, Linear and Binary Search¶

Week 3 Hash Tables¶

Week 4 Sorting Arrays with loops¶

Week 5 Algorithm Analysis (Big O)¶

Week 6 Recursion: Sorting and Binary Search Revisited¶

Week 7 Java Review Objects¶

Week 8 Linear Linked Structures¶

Week 10 Recursion¶

Week 11 Non-Linear Linked Structures: Trees¶

Week 12 Tree Traversals¶

Week 13 Applications: Puzzles, Calculators¶

Week 14 Non-Linear Data Structures: Graphs¶

Week 15 Graph Traversals¶

Week 16 Advanced Graph Algorithms¶

Week 17 Last Week, Finals¶