Slides

Topic

 Slides/Code

Coverage
Bags
  • The Bag
    • A Bag’s Behaviors
  • Specifying a Bag
    • An Interface
  • Using the ADT Bag
  • Using an ADT Is Like Using a Vending Machine
Bag Implantations That Uses Arrays
  • Using a Fixed-Size Array to Implement the ADT Bag
    • An Analogy
    • A Group of Core Methods
    • Implementing the Core Methods
    • Testing the Core Methods
    • Implementing More Methods
    • Methods That Remove Entries
  • Using Array Resizing to Implement the ADT Bag
    • Resizing an Array
    • A New Implementation of a Bag
  • The Pros and Cons of Using an Array to Implement the ADT Bag
 A Bag Implementations That Links Data
  • Linked Data
    • Forming a Chain by Adding to Its Beginning
  • A Linked Implementation of the ADT Bag
    • The Private Class Node
    • An Outline of the Class LinkedBag
    • Defining Some Core Methods
    • Testing the Core Methods
    • The Method getFrequencyOf
    • The Method contains
  • Removing an Item from a Linked Chain
    • The Methods remove and clear
  • The Pros and Cons of Using a Chain to Implement the ADT Bag
The efficiency of algorithms
  • Motivation
  • Measuring an Algorithm’s Efficiency
  • Big Oh Notation
  • Picturing Efficiency 
Stacks
  •  Specifications of the ADT Stack
  • Using a Stack to Process Algebraic Expressions
    • Checking for Balanced Parentheses, Brackets, and Braces in an Infix Algebraic Expression (Reading)
    • Transforming an Infix Expression to a Postfix Expression
    • Evaluating Postfix Expressions
    • Evaluating Infix Expressions
  • The Program Stack
 Stack Implementations
  • A Linked Implementation An Array-Based Implementation
Queues, Deques, and Priority Queues
  • ADT Queue
    • Simulating a waiting line (reading)
  • ADT Deque
  •  ADT Priority Queue
    • Using a Priority Queue to Track Your Assignments
Queue, Deque, and Priority Queue Implementation
  •  A Linked List Implementation of a Queue
  • An Array-Based Implementation of a Queue
    • A Circular Array
    • A circular array with one unused location
  • A Doubly Linked Implementation of a Deque
  • Possible Implementations of a Priority Queue
Lists
  • Specification for the ADT List
  • Using the ADT List
List Implementations that use arrays
  • Using an Array to Implement the ADT List
A list implementation that links data
  • Operations on a Chain of Linked Nodes
  • Beginning the Implementation
  • Continuing the Implementation
  • A Refined Implementation
  • The Efficiency of Using a Chain to Implement the ADT List
Sorted lists
  • Specifications for the ADT Sorted List
    • Using the ADT Sorted List
  • A Linked Implementation
  • The Method add
    • The Efficiency of the Linked Implementation
  • An Implementation that Uses the ADT List
    • Efficiency Issues
Searching
  • The Problem
  • Searching an Unsorted Array
    • Iterative Sequential Search
    • Recursive Sequential Search (reading)
    • Efficiency of Sequential Search
  • Searching a Sorted Array
    • Sequential search
    • Binary Search
    • Efficiency of Binary Search
  • Searching an Unsorted Chain
    • Iterative Sequential Search
    • Recursive Sequential Search (reading)
    • Efficiency of Sequential Search of a Chain
  • Searching a Sorted Chain
    • Sequential Search
    • Binary Search
  • Choosing a Search Method
Introducing Hashing
  •  What is Hashing?
  • Hash Functions
    • Computing Hash Codes
    • Compressing a Hash Code into an Index for the Hash Table
  • Resolving Collisions
    • Open Addressing with Linear Probing
    • Open Addressing with Quadratic Probing
    • Open Addressing with Double Hashing
    • A Potential Problem with Open Addressing
    • Separate Chaining 
Hashing as a Dictionary Implementation
    •  The Efficiency of Hashing
    • The Load Factor
    • The Cost of Open Addressing
    • The Cost of Separate Chaining
    • Rehashing
    • Comparing Schemes for collision resolution (section 22.8 Reading)
 Properties of ADT Properties of various ADTs
Iterators
  • What is an Iterator?
  • The interface Iterator
  • An Inner class Iterator
  • Why Are Iterator Methods in Their Own Class?
Trees
  • Tree Concepts
    • Hierarchical Organizations
    • Tree Terminology
  • Traversals of a Tree
    • Traversals of a Binary Tree
  • Java Interfaces for Trees
    • Interfaces for All Trees
    • An Interface for Binary Trees
  • Examples of Binary Trees
    • Expression Trees
    • Binary Search Trees
    • Heaps (23.31-23.33)
Tree Implementations
  • The Node in a Binary Tree
  • An implementation of the ADT Binary Tree. (Except: Preorder, Postorder page#646) 
  • An implementation of Expression tree (reading) 
A Binary Search Tree Implementation
  • Getting Started
    • An Interface for the Binary Search Tree
    • Duplicate Entries
    • Beginning the Class Definition
  • Searching and Retrieving
  • Traversing
  • Adding an Entry
    • Recursive Implementation
    • Iterative Implementation (reading) 
  • Removing an Entry
    • Whose Node is a leaf
    • Whose Node Has One Child
    • Whose Node has Two Children
    • In the Root
  • Efficiency of Operations
    • Importance of Balance
    • Order in Which Nodes Are Added
A Heap Implementation
  • Reprise: The ADT Heap
  • Using an Array to Represent a Heap
  • Adding an Entry
  • Removing the Root
  • Creating a Heap
  • Heap Sort
Balanced Search Trees
  •  AVL Trees
  • Single Rotations
  • Double Rotations
B_Trees

B_trees with example

  
Graphs
  • Some Examples and Terminology
  • Trees
  • Course Prerequisites
  • Mazes
  • Airline Routes
  • Road Maps
  • Traversals
    • Breadth-First Traversal
    • Dept-First Traversal
  • Paths
    • Finding a Path
    • Shortest Path in an Unweighted Graph
    • Shortest Path in a Weighted Graph
  • Java Interfaces for the ADT Graph
Graph Implementations
  •  An Overview of Two Implementations
  • The Adjacency Matrix
  • The Adjacency List
An Introduction to Sorting
  •  Organizing Java Methods that Sort an Array
  • Selection Sort
    • Iterative Selection Sort
    • Recursive Selection Sort
    • The Efficiency of Selection Sort
  • Insertion Sort
    • Iterative Insertion Sort
    • Recursive Insertion Sort
    • The Efficiency of Insertion Sort
    • Insertion Sort of a Chain of Linked Nodes
  • Comparing the Algorithms
Faster Sorting Methods
  • Merge Sort
    • Merging Arrays
    • Recursive Merge Sort
    • The Efficiency of Merge Sort
    • Iterative Merge Sort
  • Quick Sort
    • The Efficiency of Quick Sort
    • Creating the Partition
  • Comparing the Algorithms

Leave a comment