CS3 Data Structures & Algorithms
Public DepositedCreated as part of the OpenDSA hypertextbook project.
For more information, see http://opendsa.org.
JSAV library version v1.0.1-33-g556853c Resource hosted at https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/#. Course listed at https://palsave.palni.org/2020-2021-course-redesign-grant-participants/.
- Title
CS3 Data Structures & Algorithms
- Creator
- Learning resource type
- Education level
- Audience
- Table of contents
Chapter 0 Preface
0.1. How to Use this System
Chapter 1 Introduction
1.1. Data Structures and Algorithms
1.1.1. Data Structures and Algorithms
1.1.1.1. Introduction
1.1.1.2. A Philosophy of Data Structures
1.1.1.3. Selecting a Data Structure
1.1.1.4. Introduction Summary Questions
1.2. Abstract Data Types
1.2.1. Abstract Data TypesChapter 2 Programming Tutorials
2.1. Command Line Basics
2.1.1. What’s A CLI?
2.2. Parsing Command Line Parameters In Your Progam
2.2.1. Parameters In Programming
2.3. Using Parameters in Eclipse
2.3.1. Using Parameters in Eclipse
2.4. Installing the Web-CAT Submission Plug-in for Eclipse
2.4.1. Introduction
2.4.2. Installing the Plug-in
2.4.2.1. Un-Installing an Old Plug-in
2.4.2.2. Installing the Plug-in
2.4.3. Installing student.jar
2.4.4. Installing formatting support
2.5. Common Debugging Methods
2.5.1. Common Debugging Methods
2.5.1.1. Print Debugging
2.5.1.2. Rubber Duck Debugging
2.5.1.3. Wolf Fence Debugging
2.5.1.4. Print Debugging vs Source Debugging
2.6. Debugging In Eclipse
2.6.1. Debugging In Eclipse
2.6.1.1. What Is A Debugger?
2.6.1.2. Debugging Terms
2.6.1.3. Debugging A Memory Pool
2.6.1.4. The Eclipse Console
2.6.1.5. Conditional Breakpoints
2.7. Reading Input (from Files or Otherwise)
2.7.1. The Scanner Class
2.8. Random Access Files In Java
2.8.1. Understanding File I/O
2.8.1.1. Using RandomAccessFile Class
2.9. JUnit Testing And You
2.9.1. Getting Started
2.9.1.1. Design Considerations
2.9.1.2. Meaningful Tests
2.9.1.3. More Information
2.10. Writing JUnit Tests
2.10.1. Writing JUnit Tests
2.11. Code Coverage In JUnit
2.11.1. Code Coverage In JUnit
2.11.1.1. Using EclEmma
2.12. Testing
2.12.1. Testing vs. Debugging
2.13. Testing for Code Coverage
2.13.1. Testing for Code Coverage
2.14. Another Example
2.14.1. Another Example
2.15. Bowling Example
2.15.1. Bowling ExampleChapter 3 Mathematical Background
3.1. Chapter Introduction
3.2. Sets and Relations
3.2.1. Set Notation
3.2.1.1. Relations
3.2.2. Equivalence Relations
3.2.3. Partial Orders
3.3. Miscellaneous Notation
3.4. Logarithms
3.4.1. Logarithms
3.5. Summations
3.5.1. Summations
3.6. Recurrence Relations
3.6.1. Recurrence Relations
3.7. Mathematical Proof Techniques
3.7.1. Mathematical Proof Techniques
3.7.1.1. Direct Proof
3.7.1.2. Proof by Contradiction
3.7.1.3. Proof by Mathematical Induction
3.8. Estimation
3.9. Chapter Summary Questions
3.9.1. Chapter Summary QuestionsChapter 4 Algorithm Analysis
4.1. Chapter Introduction
4.2. Problems, Algorithms, and Programs
4.2.1. Problems, Algorithms, and Programs
4.2.1.1. Problems
4.2.1.2. Algorithms
4.2.1.3. Programs
4.2.1.4. Summary
4.2.1.5. Summary Questions
4.3. Comparing Algorithms
4.3.1. Comparing Algorithms
4.3.1.1. Introduction
4.3.1.2. Basic Operations and Input Size
4.3.1.3. Growth Rates
4.3.2. Growth Rates Ordering Exercise
4.4. Best, Worst, and Average Cases
4.4.1. Best, Worst, and Average Cases
4.5. Faster Computer, or Faster Algorithm?
4.5.1. Faster Computer, or Faster Algorithm?
4.6. Asymptotic Analysis and Upper Bounds
4.6.1. Asymptotic Analysis and Upper Bounds
4.6.1.1. Upper Bounds
4.6.1.2. Simplifying Rules
4.6.1.4. Summary
4.6.1.5. Practice Questions
4.7. Lower Bounds and ΘNotation
4.7.1. Lower Bounds and Theta Notation
4.7.1.1. Lower Bounds
4.7.1.2. Theta Notation
4.7.1.3. Classifying Functions
4.7.1.4. Summary Exercise
4.8. Calculating Program Running Time
4.8.1. Calculating Program Running Time
4.8.1.1. Case Study: Two Search Algorithms
4.8.1.2. Binary Search Practice Exercise
4.8.1.3. Analyzing Binary Search
4.8.2. Summary Exercise
4.9. Analyzing Problems
4.9.1. Analyzing Problems
4.10. Common Misunderstandings
4.10.1. Common Misunderstandings
4.11. Multiple Parameters
4.12. Space Bounds
4.13. Code Tuning and Empirical Analysis
4.13.1. Code Tuning and Empirical Analysis
4.13.1.1. Empirical Analysis
4.14. Algorithm Analysis Summary Exercises
4.14.1. Summary Exercise: CS3Chapter 5 Linear Structures
5.1. Chapter Introduction: Lists
5.2. The List ADT
5.2.1. The List ADT
5.2.1.1. Defining the ADT
5.2.2. List ADT Programming Exercise
5.3. Array-Based List Implementation
5.3.1. Array-Based List Implementation
5.3.1.1. Insert
5.3.1.2. Insert Practice Exericse
5.3.2. Append and Remove
5.3.2.1. Remove Practice Exericise
5.3.3. Array-based List Practice Questions
5.4. Linked Lists
5.4.1. Linked Lists
5.4.1.1. Why This Has Problems
5.4.1.2. A Better Solution
5.4.1.3. Linked List Implementation
5.4.2. Linked List Remove
5.5. Comparison of List Implementations
5.5.1. Space Comparison
5.5.2. Time Comparison
5.5.2.1. Practice Questions
5.6. Doubly Linked Lists
5.6.1. Doubly Linked Lists
5.6.1.1. Insert
5.6.1.2. Append
5.6.1.3. Remove
5.6.1.4. Prev
5.6.1.5. Mangling Pointers
5.7. List Element Implementations
5.7.1. List Element Implementations
5.7.1.1. Homogeneity
5.7.1.2. Element Deletion
5.7.1.3. Practice Questions
5.8. Stacks
5.8.1. Stack Terminology and Implementation
5.8.1.1. Array-Based Stacks
5.8.2. Pop
5.9. Linked Stacks
5.9.1. Linked Stack Implementation
5.9.1.1. Linked Stack Push
5.9.2. Linked Stack Pop
5.9.2.1. Comparison of Array-Based and Linked Stacks
5.10. Freelists
5.10.1. Freelists
5.11. Implementing Recursion
5.12. Queues
5.12.1. Queue Terminology and Implementation
5.12.1.1. Array-Based Queues
5.12.1.2. The Circular Queue
5.12.1.3. Array-based Queue Implementation
5.12.2. Array-based Dequeue Practice
5.13. Linked Queues
5.13.1. Linked Queues
5.13.2. Linked Dequeue
5.13.3. Comparison of Array-Based and Linked Queues
5.13.3.1. Stack and Queue Summary Questions
5.14. Linear Structure Summary Exercises
5.14.1. Practice Questions
5.14.2. Chapter Review QuestionsChapter 6 Design
6.1. Design Patterns
6.1.1. Design Patterns
6.1.1.1. Flyweight
6.1.1.2. Visitor
6.1.1.3. Composite
6.1.1.4. Strategy
6.1.1.5. Summary Questions
6.2. Alternative List ADT Designs
6.3. Comparing Records
6.3.1. Comparing Records
6.4. The Dictionary ADT
6.4.1. The Dictionary ADTChapter 7 Binary Trees
7.1. Binary Trees Chapter Introduction
7.2. Binary Trees
7.2.1. Definitions and Properties
7.2.2. Practice Questions
7.3. Binary Tree as a Recursive Data Structure
7.3.1. Binary Tree as a Recursive Data Structure
7.4. The Full Binary Tree Theorem
7.5. Binary Tree Traversals
7.5.1. Binary Tree Traversals
7.5.1.1. Preorder Traversal
7.5.1.2. Postorder Traversal
7.5.1.3. Inorder Traversal
7.5.1.4. Implementation
7.5.2. Postorder Traversal Practice
7.5.3. Inorder Traversal Practice
7.5.4. Summary Questions
7.6. Implementing Tree Traversals
7.6.1. Implementing Tree Traversals
7.6.1.1. Base Case
7.6.1.2. The Recursive Call
7.6.2. Binary Tree Increment By One Exercise
7.7. Information Flow in Recursive Functions
7.7.1. Information Flow in Recursive Functions
7.7.1.1. Local
7.7.1.2. Passing Down Information
7.7.2. Binary Tree Set Depth Exercise
7.7.3. Collect-and-return
7.7.4. Binary Tree Check Sum Exercise
7.7.5. Binary Tree Leaf Nodes Count Exercise
7.7.6. Binary Tree Sum Nodes Exercise
7.7.7. Combining Information Flows
7.7.8. Binary Tree Check Value Exercise
7.7.9. Combination Problems
7.7.10. Binary Tree Height Exercise
7.7.11. Binary Tree Get Difference Exercise
7.7.12. Binary Tree Has Path Sum Exercise
7.8. Binary Tree Node Implementations
7.8.1. Binary Tree Node Implementations
7.9. Composite-based Expression Tree
7.9.1. Composite-based Expression Tree
7.10. Binary Tree Space Requirements
7.10.1. Binary Tree Space Requirements
7.11. Binary Search Trees
7.11.1. Binary Search Tree Definition
7.11.1.1. BST Search
7.11.2. BST Insert
7.11.3. BST Remove
7.11.4. BST Analysis
7.12. Dictionary Implementation Using a BST
7.13. Binary Tree Guided Information Flow
7.13.1. Binary Tree Guided Information Flow
7.13.2. Binary Search Tree Small Count Exercise
7.14. Multiple Binary Trees
7.14.1. Mirror Image Binary Trees Exercise
7.14.2. Same Binary Tree Exercise
7.14.3. Structurally Identical Binary Trees Exercise
7.15. A Hard Information Flow Problem
7.16. Array Implementation for Complete Binary Trees
7.16.1. Array Implementation for Complete Binary Trees
7.17. Heaps and Priority Queues
7.17.1. Heaps and Priority Queues
7.17.2. Building a Heap
7.17.3. Removing from the heap or updating an object’s priority
7.17.4. Priority Queues
7.18. Huffman Coding Trees
7.18.1. Huffman Coding Trees
7.18.1.1. Building Huffman Coding Trees
7.18.1.2. Decoding
7.18.1.3. How efficient is Huffman coding?
7.19. Trees versus Tries
7.19.1. Trees versus Tries
7.20. Proof of Optimality for Huffman Coding
7.20.1. Proof of Optimality for Huffman Coding
7.21. Binary Tree Chapter Summary
7.21.1. Summary QuestionsChapter 8 Sorting
8.1. Chapter Introduction: Sorting
8.2. Sorting Terminology and Notation
8.2.1. Sorting Terminology and Notation
8.3. Insertion Sort
8.3.1. Insertion Sort
8.3.2. Insertion Sort Analysis
8.4. Bubble Sort
8.4.1. Bubble Sort
8.4.2. Bubble Sort Analysis
8.5. Selection Sort
8.5.1. Selection Sort
8.5.2. Selection Sort Analysis
8.6. The Cost of Exchange Sorting
8.6.1. The Cost of Exchange Sorting
8.6.2. Analysis
8.7. Optimizing Sort Algorithms with Code Tuning
8.7.1. Code Tuning for Simple Sorting Algorithms
8.8. Shellsort
8.8.1. Shellsort
8.8.2. Putting It Together
8.8.3. Shellsort Practice Exercise
8.8.4. Optimizing Shellsort
8.8.5. Shellsort Summary Questions
8.9. Mergesort Concepts
8.9.1. Mergesort Concepts
8.9.2. Mergesort Practice Exercise
8.10. Implementing Mergesort
8.10.1. Implementing Mergesort
8.11. Quicksort
8.11.1. Introduction
8.11.2. Partition
8.11.3. Putting It Together
8.11.4. Quicksort Analysis
8.12. Heapsort
8.12.1. Heapsort
8.12.2. Heapsort Proficiency Practice
8.12.3. Heapsort Analysis
8.13. Binsort
8.13.1. Binsort
8.14. Radix Sort
8.14.1. Radix Sort
8.14.2. Array-based Radix Sort
8.14.2.1. Radix Sort Analysis
8.15. An Empirical Comparison of Sorting Algorithms
8.15.1. An Empirical Comparison of Sorting Algorithms
8.16. Lower Bounds for Sorting
8.16.1. Lower Bounds for Sorting
8.17. Sorting Summary Exercises
8.17.1. Sorting Summary ExercisesChapter 9 File Processing
9.1. Chapter Introduction: File Processing
9.2. Primary versus Secondary Storage
9.3. Disk Drives
9.3.1. Disk Drives
9.3.1.1. Disk Drive Architecture
9.3.1.2. Disk Access Costs
9.3.1.3. Notes
9.4. Buffer Pools
9.4.1. Buffer Pools
9.4.1.1. Replacement Strategies
9.4.1.2. The Dirty Bit
9.4.1.3. Implementing Buffer Pools
9.5. The Programmer’s View of Files
9.6. External Sorting
9.6.1. External Sorting
9.6.1.1. Simple Approaches to External Sorting
9.6.1.2. Improving Performance
9.6.1.3. Replacement Selection
9.6.2. Multiway Merging
9.6.2.1. Empirical Results
9.6.2.2. SummaryChapter 10 Hashing
10.1. Introduction
10.1.1. Introduction
10.2. Hash Function Principles
10.2.1. Hash Function Principles
10.3. Sample Hash Functions
10.3.1. Sample Hash Functions
10.3.1.1. Simple Mod Function
10.3.1.2. Binning
10.3.1.3. The Mid-Square Method
10.3.2. A Simple Hash Function for Strings
10.3.3. String Folding
10.3.4. Hash Function Practice
10.3.5. Hash Function Review Questions
10.4. Open Hashing
10.4.1. Open Hashing
10.5. Bucket Hashing
10.5.1. Bucket Hashing
10.5.2. An Alternate Approach
10.6. Collision Resolution
10.6.1. Collision Resolution
10.6.1.1. The Problem with Linear Probing
10.7. Improved Collision Resolution
10.7.1. Linear Probing by Steps
10.7.2. Pseudo-Random Probing
10.7.3. Quadratic Probing
10.7.4. Double Hashing
10.8. Analysis of Closed Hashing
10.8.1. Analysis of Closed Hashing
10.9. Deletion
10.9.1. Deletion
10.9.2. Hashing Deletion Summary Questions
10.10. Hashing Chapter Summary Exercises
10.10.1. Hashing ReviewChapter 11 Memory Management
11.1. Chapter Introduction: Memory Management
11.2. Dynamic Storage Allocation
11.2.1. Dynamic Storage Allocation
11.3. Sequential-Fit Methods
11.3.1. Sequential-Fit Methods
11.4. First Fit
11.4.1. First Fit
11.5. Circular First Fit
11.5.1. Circular First Fit
11.6. Best Fit
11.6.1. Best Fit
11.7. Worst Fit
11.7.1. Worst Fit
11.8. Sequential Fit Peformance
11.8.1. Sequential Fit Peformance
11.9. Other Memory Allocation Methods
11.9.1. Other Memory Allocation Methods
11.9.1.1. Buddy Methods
11.9.1.2. Other Methods
11.10. Failure Policies and Garbage CollectionChapter 12 Indexing
12.1. Indexing Chapter Introduction
12.2. Linear Indexing
12.2.1. Linear Indexing
12.3. ISAM
12.4. Tree-based Indexing
12.4.1. Tree-based Indexing
12.5. 2-3 Trees
12.5.1. 2-3 Trees
12.6. B-Trees
12.6.1. B-Trees
12.6.1.1. B+ Trees
12.6.1.2. B-Tree Analysis
12.7. Indexing Summary Exercises
12.7.1. Indexing SummaryChapter 13 General Trees
13.1. General Trees
13.1.1. General Trees
13.1.1.1. General Tree Definitions and Terminology
13.1.1.2. An ADT for General Tree Nodes
13.1.1.3. General Tree Traversals
13.2. Union/Find and the Parent Pointer Implementation
13.2.1. The Union/Find Problem
13.2.1.1. Parent Pointer Trees
13.2.1.2. Equivalence Classes
13.2.1.3. Weighted Union
13.2.1.4. Path Compression
13.3. Sequential Tree Representations
13.3.1. Sequential Tree Representations
13.3.2. Alternative Sequential Representation
13.3.3. Bit Vector Representation
13.3.4. General Tree Sequential RepresentationChapter 14 Graphs
14.1. Graphs Chapter Introduction
14.1.1. Graph Terminology and Implementation
14.1.1.1. Graph Representations
14.1.2. Graph Terminology Questions
14.2. Graph Implementations
14.3. Graph Traversals
14.3.1. Graph Traversals
14.3.1.1. Depth-First Search
14.3.2. Breadth-First Search
14.4. Topological Sort
14.4.1. Topological Sort
14.4.1.1. Depth-first solution
14.4.1.2. Queue-based Solution
14.5. Shortest-Paths Problems
14.5.1. Shortest-Paths Problems
14.5.1.1. Single-Source Shortest Paths
14.6. Minimal Cost Spanning Trees
14.6.1. Minimal Cost Spanning Trees
14.6.1.1. Prim’s Algorithm
14.6.1.2. Prim’s Algorithm Alternative Implementation
14.7. Kruskal’s Algorithm
14.7.1. Kruskal’s Algorithm
14.8. All-Pairs Shortest Paths
14.9. Graph Concepts Summary
14.9.1. Graph Concepts SummaryChapter 15 Advanced Data Structures
15.1. Skip Lists
15.1.1. Skip Lists
15.2. Spatial Data Structures
15.2.1. Spatial Data Structures
15.2.1.1. Multdimensional Keys
15.3. The PR Quadtree
15.3.1. The PR Quadtree
15.4. KD Trees
15.4.1. KD Trees
15.5. The Bintree
15.5.1. The Bintree
15.5.1.1. Implementation Concerns
15.6. Other Spatial Data StructuresChapter 16 Appendix
16.1. Glossary
16.2. BibliographyIndex
Search Page
- Rights statement
- License
- Rights holder
- Language
- Publisher
- Type
MLA citation style (9th ed.)
OpenDSA. Cs3 Data Structures & Algorithms. OpenDSA. palsave.hykucommons.org/concern/oers/419c3dd9-f065-4066-8b2e-3695418be554?locale=en.APA citation style (7th ed.)
Opendsa. CS3 Data Structures & Algorithms. https://palsave.hykucommons.org/concern/oers/419c3dd9-f065-4066-8b2e-3695418be554?locale=enChicago citation style (CMOS 17, author-date)
OpenDSA. Cs3 Data Structures & Algorithms. OpenDSA. https://palsave.hykucommons.org/concern/oers/419c3dd9-f065-4066-8b2e-3695418be554?locale=en.Note: These citations are programmatically generated and may be incomplete.
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
Hyku_Palsave_Placeholder.pdf | 2021-06-21 | Public | Download |