Java 9 data structures and algorithms : a step-by-step guide to data structures and algorithms

Java 9 data structures and algorithms a step-by-step guide to data structures and algorithms

Gain a deep understanding of the complexity of data structures and algorithms and discover the right way to write more efficient code About This Book This book provides complete coverage of reactive and functional data structures Based on the latest version of Java 9, this book illustrates the impac...

Descripción completa

Detalles Bibliográficos
Otros Autores: Chawdhuri, Debasish Ray, author (author)
Formato: Libro electrónico
Idioma:Inglés
Publicado: Birmingham, England ; Mumbai, [India] : Packt 2017.
Edición:1st edition
Materias:
Java (Computer program language)
Data structures (Computer science)
Algorithms.
Ver en Biblioteca Universitat Ramon Llull:https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009630152606719
Tabla de Contenidos:
  • Cover
  • Copyright
  • Credits
  • About the Author
  • About the Reviewer
  • www.PacktPub.com
  • Customer Feedback
  • Table of Contents
  • Preface
  • Chapter 1: Why Bother? - Basic
  • The performance of an algorithm
  • Best case, worst case and the average case complexity
  • Analysis of asymptotic complexity
  • Asymptotic upper bound of a function
  • Asymptotic upper bound of an algorithm
  • Asymptotic lower bound of a function
  • Asymptotic tight bound of a function
  • Optimization of our algorithm
  • Fixing the problem with large powers
  • Improving time complexity
  • Summary
  • Chapter 2: Cogs and Pulleys - Building Blocks
  • Arrays
  • Insertion of elements in an array
  • Insertion of a new element and the process of appending it
  • Linked list
  • Appending at the end
  • Insertion at the beginning
  • Insertion at an arbitrary position
  • Looking up an arbitrary element
  • Removing an arbitrary element
  • Iteration
  • Doubly linked list
  • Insertion at the beginning or at the end
  • Insertion at an arbitrary location
  • Removing the first element
  • Removing an arbitrary element
  • Removal of the last element
  • Circular linked list
  • Insertion
  • Removal
  • Rotation
  • Summary
  • Chapter 3: Protocols - Abstract Data Types
  • Stack
  • Fixed-sized stack using an array
  • Variable-sized stack using a linked list
  • Queue
  • Fixed-sized queue using an array
  • Variable-sized queue using a linked list
  • Double ended queue
  • Fixed-length double ended queue using an array
  • Variable-sized double ended queue using a linked list
  • Summary
  • Chapter 4: Detour - Functional Programming
  • Recursive algorithms
  • Lambda Expressions in Java
  • Functional interface
  • Implementing a functional interface with lambda
  • Functional data structures and monads
  • Functional linked lists
  • The forEach method for a linked list
  • Map for a linked list.
  • Fold operation on a list
  • Filter operation for a linked list
  • Append on a linked list
  • The flatMap method on a linked list
  • The concept of a monad
  • Option monad
  • Try monad
  • Analysis of the complexity of a recursive algorithm
  • Performance of functional programming
  • Summary
  • Chapter 5: Efficient Searching - Binary Search and Sorting
  • Search algorithms
  • Binary search
  • Complexity of the binary search algorithm
  • Sorting
  • Selection sort
  • Complexity of the selection sort algorithm
  • Insertion sort
  • Complexity of insertion sort
  • Bubble sort
  • Inversions
  • Complexity of the bubble sort algorithm
  • A problem with recursive calls
  • Tail recursive functions
  • Non-tail single recursive functions
  • Summary
  • Chapter 6: Efficient Sorting - Quicksort and Merge Sort
  • Quicksort
  • Complexity of quicksort
  • Random pivot selection in quicksort
  • Merge sort
  • The complexity of merge sort
  • Avoiding the copying of tempArray
  • Complexity of any comparison-based sorting
  • The stability of a sorting algorithm
  • Summary
  • Chapter 7: Concepts of Tree
  • A tree data structure
  • The traversal of a tree
  • The depth-first traversal
  • The breadth-first traversal
  • The tree abstract data type
  • Binary tree
  • Types of depth-first traversals
  • Non-recursive depth-first search
  • Summary
  • Chapter 8: More About Search - Search Trees and Hash Tables
  • Binary search tree
  • Insertion in a binary search tree
  • Invariant of a binary search tree
  • Deletion of an element from a binary search tree
  • Complexity of the binary search tree operations
  • Self-balancing binary search tree
  • AVL tree
  • Complexity of search, insert, and delete in an AVL tree
  • Red-black tree
  • Insertion
  • Deletion
  • The worst case of a red-black tree
  • Hash tables
  • Insertion
  • The complexity of insertion
  • Search
  • Complexity of the search.
  • Choice of load factor
  • Summary
  • Chapter 9: Advanced General Purpose Data Structures
  • Priority queue ADT
  • Heap
  • Insertion
  • Removal of minimum elements
  • Analysis of complexity
  • Serialized representation
  • Array-backed heap
  • Linked heap
  • Insertion
  • Removal of the minimal elements
  • Complexity of operations in ArrayHeap and LinkedHeap
  • Binomial forest
  • Why call it a binomial tree?
  • Number of nodes
  • The heap property
  • Binomial forest
  • Complexity of operations in a binomial forest
  • Sorting using a priority queue
  • In-place heap sort
  • Summary
  • Chapter 10: Concepts of Graph
  • What is a graph?
  • The graph ADT
  • Representation of a graph in memory
  • Adjacency matrix
  • Complexity of operations in a sparse adjacency matrix graph
  • More space-efficient adjacency-matrix-based graph
  • Complexity of operations in a dense adjacency-matrix-based graph
  • Adjacency list
  • Complexity of operations in an adjacency-list-based graph
  • Adjacency-list-based graph with dense storage for vertices
  • Complexity of the operations of an adjacency-list-based graph with dense storage for vertices
  • Traversal of a graph
  • Complexity of traversals
  • Cycle detection
  • Complexity of the cycle detection algorithm
  • Spanning tree and minimum spanning tree
  • For any tree with vertices V and edges E, |V| = |E| + 1
  • Any connected undirected graph has a spanning tree
  • Any undirected connected graph with the property |V| = |E| + 1 is a tree
  • Cut property
  • Minimum spanning tree is unique for a graph that has all the edges whose costs are different from one another
  • Finding the minimum spanning tree
  • Union find
  • Complexity of operations in UnionFind
  • Implementation of the minimum spanning tree algorithm
  • Complexity of the minimum spanning tree algorithm
  • Summary
  • Chapter 11: Reactive Programming.
  • What is reactive programming?
  • Producer-consumer model
  • Semaphore
  • Compare and set
  • Volatile field
  • Thread-safe blocking queue
  • Producer-consumer implementation
  • Spinlock and busy wait
  • Functional way of reactive programming
  • Summary
  • Index.

Ejemplares similares