Data Structures and Algorithms

The following sections are included:

• Preface

• Contents

The following sections are included:

• Introduction

• Ancient Algorithms

• Algorithm 1: Sum of the Powers of 2 with an Exponent from 1 to 10 (1800–1600 B.C.)

• Algorithm 2: Sum of the Squares of Numbers from 1 to 10 (1800–1600 B.C.)

• Algorithm 3: (1800–1600 B.C.)

• Data: Definition and Characteristics

• Algorithm Environment

• Algorithm: Definition and Characteristics
  • Definition
  • Characteristics
  • Algorithm and Program

• References

• Exercises

The following sections are included:

• General Considerations about the Execution Time

• Execution Time
  • The Execution Time of a Program as Function of the Dimension of the Data

• Comparisons Between Different Execution Times

• Big-O Notation: The Approximation of the Execution Time
  • Introduction
  • Big-O Notation
  • Some Examples

• Simplification of the Expressions in Big-O Notation
  • Transitive Law for Big-O Notation
  • The Choice of the Precision
  • Rule of the Sum
  • Incommensurable Functions

• Analysis of the Execution Time of a Program
  • The Execution Time of Simple Instructions
  • The Execution Time of the "for" Loop
  • The Execution Time of the "if" Structure
  • The Execution Time of a Sequence of Instructions
  • The Execution Time of Iterative Structures (While and Do-While)

• Recursion Rules for Execution Time Evaluation: The Nesting Tree Approach
  • Construction Rules of the Instructions
  • Rule for the Construction of Upper Limit of the Execution Time of a Program
  • Example for a Simple Program: The Execution Time of the Bubble Sort Program

• Exercises

The following sections are included:

• The Execution Time Analysis of a Program: The Case of Nonrecursive Functions

• Examples for Nonrecursive Function Calls

• The Execution Time Analysis of a Program: The Case of Recursive Function Units
  • Examples of Nonrecursive Calls

• Other Methods for the Solution of the Recurrence Equations

• Exercises

The following sections are included:

• Introduction to Abstract Data Types

• Abstract Data Types and Object-Oriented Languages

• Packages

• Generic Abstract Data Types

• Software Design with Abstract Data Types

• Conclusions

• Exercises

The following sections are included:

• Stacks
  • The LIFO Nature of Stacks
  • Reversing with a Stack
  • Stack Operations
  • Contiguous Implementation
  • Linked Implementation

• Recursion
  • Introduction
  • Procedure Calls and the Run-Time Stack
  • Sum of the First n Positive Integers
  • Factorials
  • Collatz 3x + 1 Problem
  • Greatest Common Divisor
  • Towers of Hanoi
  • Reversing a Line of Input

• Backtracking
  • Introduction
  • The Eight Queens Problem
  • Escape from a Maze

• Exercises

The following sections are included:

• Introduction

• The Concept of Queue

• An Array-Based Implementation of a Queue

• Pointers

• Linked Lists

• Pointers and Their Use in a Queue

• Variations of Queues

• Exercises

The following sections are included:

• Introduction

• Singly Linked Lists
  • Implementing Stacks with Singly Linked Lists
  • Implementing Queues with Singly Linked Lists
  • Double-Ended Linked Lists

• Doubly Linked Lists
  • Doubly Linked Lists Processing: Insertion, Deletion and Traversal
  • Implementing Deques with Doubly Linked Lists

• References

• Appendices

• Exercises

The following sections are included:

• Introduction

• Sequential Search
  • Search on Linked List
  • Search on Array

• Binary Search
  • Binary Search Algorithm

• Analysis
  • The Comparison Trees

• Fibonacci Search

• Exercises

The following sections are included:

• Basic Sorting
  • Selection Sort
  • Insertion Sort
  • Bubble Sort

• Quick Sort

• Heap Sort

• Merge Sort

• Shell Sort

• Radix Sort

• Comparison of Sorting Algorithms

• References

• Appendices

• Exercises

The following sections are included:

• Introduction

• Rectangular Arrays
  • Row-Major and Column-Major Ordering
  • Indexing Rectangular Arrays
  • Variation: An Access Table

• Tables of Various Shapes
  • Triangular Tables
  • Jagged Tables
  • Inverted Tables

• The Symbol Table Abstract Data Type
  • Functions and Tables
  • An Abstract Data Type
  • Comparisons

• Static Hashing
  • Hashing Function
  • Collision Resolution with Open Addressing
  • Collision Resolution by Chaining

• Dynamic Hashing
  • Dynamic Hashing Using Directories
  • Directory-Less Dynamic Hashing

• Conclusions

• Exercises

The following sections are included:

• Binary Tree
  • Definition and Properties
  • Traversal of Binary Tree
  • Implementation of Binary Trees

• Binary Search Trees
  • Definition
  • Insertion into a Binary Search Tree
  • Deletion from a Binary Search Tree
  • Search of a Binary Search Tree
  • Implementation of a Binary Search Tree

• An AVL Tree and Balancing Height
  • Definition
  • Insertion into an AVL tree
  • Deletion from an AVL tree
  • Implementation of an AVL tree

• Appendix

• Exercises

The following sections are included:

• Introduction

• Graphs and Their Representations

• Graph Algorithms for Search
  • Breadth-First-Search
  • Depth-First-Search

• Graph Algorithms for Topological Sort

• Strongly Connected Components

• Minimum Spanning Tree
  • Prim's Algorithm

• Shortest Path Algorithms
  • Single Source Shortest Paths Problem
    • Dijkstra's algorithm
    • Bellman–Ford algorithm
    • Single-source shortest path in DAG
  • All-Pairs Shortest Path

• References

• Exercises

The following sections are included:

• Introduction

• Interface Features

• Formal Approaches?

• The Functions of an Interface

• Interaction History

• Designing the Interface

• Interface Quality

• Human Issues

• Trustable Systems

• Conclusions

• References

• Exercises

The following sections are included:

• Index