/BeginningAlgorithms

Exercises from "Beginning algorithms" book

Primary LanguageJava

BeginningAlgorithms

Exercises from "Beginning algorithms" book

beginning algorithms 2006 -001

Chapter 1: Getting Started

  • Defining Algorithms
  • Understanding Complexity in Relation to Algorithms
  • Understanding Big-O Notation
  • Constant Time: O(1)
  • Linear Time: O(N)
  • Quadratic Time: O(N2)
  • Logarithmic Time: O(log N) and O(N log N)
  • Factorial Time: O(N!)
  • Unit Testing
  • What Is Unit Testing?
  • Why Unit Testing Is Important
  • A JUnit Primer
  • Test-Driven Development

Chapter 2: Iteration and Recursion

  • Performing Calculations
  • Processing Arrays
  • Using Iterators to Overcome Array-based Problems
  • Iterator Operations
  • The Iterator Interface
  • The Iterable Interface
  • Iterator Idioms - Standard Iterators
  • Recursion
  • Recursive Directory Tree Printer Exampl
  • Anatomy of a Recursive Algorithm
  • The Base Case
  • The General Case

Chapter 3: Lists

  • Understanding Lists
  • Testing Lists
  • Implementing Lists
  • An Array List
  • A Linked List

Chapter 4: Queues

  • Understanding Queues
  • Queue Operations
  • The Queue Interface7
  • A First-In-First-Out Queue
  • Implementing the FIFO Queue
  • Blocking Queues
  • Example: A Call Center Simulator
  • Running the Application

Chapter 5: Stacks

  • Stacks
  • The Tests
  • Implementation
  • Example: Implementing Undo/Redo
  • Testing Undo/Redo

Chapter 6: Basic Sorting

  • The Importance of Sorting
  • Sorting Fundamentals
  • Understanding Comparators
  • Comparator Operations
  • The Comparator Interface
  • Some Standard Comparators 117
  • Working with the Natural Comparator
  • Working with the Reverse Comparator
  • Understanding Bubble Sort
  • The ListSorter Interface
  • Testing AbstractListSorter
  • Working with a Selection Sort
  • Understanding Insertion Sort
  • Understanding Stability
  • Comparing the Basic Sorting Algorithms
  • CallCountingListComparator
  • ListSorterCallCountingTest
  • Understanding the Algorithm Comparison

Chapter 7: Advanced Sorting

  • Understanding the Shellsort Algorithm
  • Understanding Quicksort
  • Understanding the Compound Comparator and Stability
  • Understanding the Mergesort Algorithm
  • Merging
  • The mergesort Algorithm
  • Comparing the Advanced Sorting Algorithms

Chapter 8: Priority Queues

  • Understanding Priority Queues
  • A Simple Priority Queue Example
  • Working with Priority Queues
  • Understanding the Unsorted List Priority Queue
  • Understanding the Sorted List Priority Queue
  • Understanding Heap-ordered Priority Queues
  • Sink or Swim
  • Comparing the Priority Queue Implementations

Chapter 9: Binary Searching and Insertion

  • Understanding Binary Searching
  • Binary Search Approaches
  • A List Searcher
  • Recursive Binary Searcher
  • Iterative Binary Searcher
  • Assessing the List Searcher’s Performance
  • Linear Searching for Comparison
  • Tests for Performance
  • Understanding Binary Insertion
  • A List Inserter
  • Assessing Performance

Chapter 10: Binary Search Trees

  • Understanding Binary Search Trees
  • Minimum
  • Maximum
  • Successor
  • Predecessor
  • Search
  • Insertion
  • Deletion
  • In-order Traversal
  • Pre-order Traversal
  • Post-order Traversal
  • Balancing
  • Testing and Implementing a Binary Search Tree
  • Assessing Binary Search Tree Performance

Chapter 11: Hashing

  • Understanding Hashing
  • Working with Hashing
  • Linear Probing
  • Bucketing
  • Assessing Performanc

Chapter 12: Sets

  • Understanding Sets
  • Testing Set Implementations
  • Contents
  • A List Set
  • A Hash Set
  • A Tree Set 309

Chapter 13: Maps

  • Understanding Maps
  • Testing Map Implementations
  • A List Map
  • A Hash Map
  • A Tree Map

Chapter 14: Ternary Search Trees

  • Understanding Ternary Search Trees
  • Searching for a Word
  • Inserting a Word
  • Prefix Searching
  • Pattern Matching Putting Ternary Search Trees into Practice Crossword Helper Example

Chapter 15: B-Trees

  • Understanding B-Trees
  • Putting B-Trees into Practice

Chapter 16: String Searching

  • A Generic String Searcher Interface
  • A Generic Test Suite
  • A Brute-Force Algorithm
  • The Boyer-Moore Algorithm
  • Creating the Tests
  • Implementing the Algorithm
  • A String Match Iterator
  • Comparing the Performance
  • Measuring Performance
  • How They Compare

Chapter 17: String Matching

  • Understanding Soundex
  • Understanding Levenshtein Word Distance

Chapter 18: Computational Geometry

  • A Quick Geometry Refresher
  • Coordinates and Points
  • Lines
  • Triangles
  • Finding the Intersection of Two Lines
  • Slope
  • Crossing the y Axis
  • Finding the Intersection Point
  • Finding the Closest Pair of Points

Chapter 19: Pragmatic Optimization

  • Where Optimization Fits In
  • Understanding Profiling
  • The FileSortingHelper Example Program
  • Profiling with hprof
  • Profiling with JMP
  • Understanding Optimization
  • Putting Optimization into Practice