Recensione libro “Essential Algorithms”

image

Booksite:
http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1118612108.html
Autore: Rod Stephens
ISBN: 978-1-118-61210-1
Fogliazione: 624 pagine
Edizione: Settembre 2013

Lo studio degli algoritmi mi ha sempre appassionato, anche da prima di iniziare a frequentare l’Università.

Nei miei studi universitari ho avuto a che fare con la codifica di questi algoritmi, utilizzando il linguaggio di programmazione JAVA.

Prima di questo bellissimo libro di Rod Stephens non avevo trovato un libro che fosse orientato agli algoritmi in sé, non espressamente codificati in un linguaggio di programmazione specifico (per esempio in JAVA o in C++). Il libro, infatti, utilizza uno pseudo-codice che può essere facilmente adattato a qualsiasi linguaggio di programmazione.

Questo libro, quindi, copre un vuoto di moltissimi anni, durante il quale i programmatori dovevano riuscire ad adattare il codice JAVA o C++ in un altro linguaggio di programmazione. Questo compito era tutt’altro che facile!

Nel libro potete trovare gli argomenti più disparati, perfino quelli notoriamente considerati più “difficili” che di solito si studiano in corsi di ricerca operativa: per esempio l’algoritmo dello zaino (knapsack) o l’algoritmo dei filosofi.

L’approccio non è teorico e matematico, ma bensì molto più pratico, cercando di stimolare l’interesse del lettore e del programmatore a capire i meccanismi che stanno alla base degli algoritmi.

Mi sembra inutile dire quanto mi ha appassionato questo libro: voto massimo a Rod Stephens e naturalmente anche a Wiley che punta sempre su autori di massimo spessore.

Ecco quindi l’elenco dei 19 capitoli del libro e dei relativi paragrafi:

Chapter 1 Algorithm Basics

Approach
Algorithms and Data Structures
Pseudocode
Algorithm Features
Big O Notation
Common Runtime Functions
Visualizing Functions
Practical Considerations
Summary
Exercises

Chapter 2 Numerical Algorithms

Randomizing Data
Generating Random Values
Randomizing Arrays
Generating Nonuniform Distributions
Finding Greatest Common Divisors
Performing Exponentiation
Working with Prime Numbers
Finding Prime Factors
Finding Primes
Testing for Primality
Performing Numerical Integration
The Rectangle Rule
The Trapezoid Rule
Adaptive Quadrature
Monte Carlo Integration
Finding Zeros
Summary
Exercises

Chapter 3 Linked Lists

Basic Concepts
Singly Linked Lists
Iterating Over the List
Finding Cells
Using Sentinels
Adding Cells at the Beginning
Adding Cells at the End
Inserting Cells After Other Cells
Deleting Cells
Doubly Linked Lists
Sorted Linked Lists
Linked-List Algorithms
Copying Lists
Sorting with Insertionsort
Linked List Selectionsort
Multithreaded Linked Lists
Linked Lists with Loops
Marking Cells
Using Hash Tables
List Retracing
List Reversal
Tortoise and Hare
Loops in Doubly Linked Lists
Summary
Exercises

Chapter 4 Arrays

Basic Concepts
One-dimensional Arrays
Finding Items
Finding Minimum, Maximum, and Average
Inserting Items
Removing Items
Nonzero Lower Bounds
Two Dimensions
Higher Dimensions
Triangular Arrays
Sparse Arrays
Find a Row or Column
Get a Value
Set a Value
Delete a Value
Matrices
Summary
Exercises

Chapter 5 Stacks and Queues

Stacks
Linked-List Stacks
Array Stacks
Double Stacks
Stack Algorithms
Queues
Linked-List Queues
Array Queues
Specialized Queues
Summary
Exercises

Chapter 6 Sorting

O(N2) Algorithms
Insertionsort in Arrays
Selectionsort in Arrays
Bubblesort
O(N log N) Algorithms
Heapsort
Quicksort
Mergesort
Sub O(N log N) Algorithms
Countingsort
Bucketsort
Summary
Exercises

Chapter 7 Searching

Linear Search
Binary Search
Interpolation Search
Summary
Exercises

Chapter 8 Hash Tables

Hash Table Fundamentals
Chaining
Open Addressing
Removing Items
Liner Probing
Quadratic Probing
Pseudorandom Probing
Double Hashing
Ordered Hashing
Summary
Exercises

Chapter 9 Recursion

Basic Algorithms
Factorial
Fibonacci Numbers
Tower of Hanoi
Graphical Algorithms
Koch Curves
Hilbert Curve
Sierpin´ ski Curve
Gaskets
Backtracking Algorithms
Eight Queens Problem
Knight’s Tour
Selections and Permutations
Selections with Loops
Selections with Duplicates
Selections Without Duplicates
Permutations with Duplicates
Permutations Without Duplicates
Recursion Removal
Tail Recursion Removal
Storing Intermediate Values
General Recursion Removal
Summary
Exercises

Chapter 10 Trees

Tree Terminology
Binary Tree Properties
Tree Representations
Building Trees in General
Building Complete Trees
Tree Traversal
Preorder Traversal
Inorder Traversal
Postorder Traversal
Depth-first Traversal
Traversal Run Times
Sorted Trees
Adding Nodes
Finding Nodes
Deleting Nodes
Threaded Trees
Building Threaded Trees
Using Threaded Trees
Specialized Tree Algorithms
The Animal Game
Expression Evaluation
Quadtrees
Tries
Summary
Exercises

Chapter 11 Balanced Trees

AVL Trees
Adding Values
Deleting Values
2-3 Trees
Adding Values
Deleting Values
B-Trees
Adding Values
Deleting Values
Balanced Tree Variations
Top-down B-trees
B+trees
Summary
Exercises

Chapter 12 Decision Trees

Searching Game Trees
Minimax
Initial Moves and Responses
Game Tree Heuristics
Searching General Decision Trees
Optimization Problems
Exhaustive Search
Branch and Bound
Decision Tree Heuristics
Other Decision Tree Problems
Summary
Exercises

Chapter 13 Basic Network Algorithms

Network Terminology
Network Representations
Traversals
Depth-first Traversal
Breadth-first Traversal
Connectivity Testing
Spanning Trees
Minimal Spanning Trees
Finding Paths
Finding Any Path
Label-Setting Shortest Paths
Label-Correcting Shortest Paths
All-Pairs Shortest Paths
Summary
Exercises

Chapter 14 More Network Algorithms

Topological Sorting
Cycle Detection
Map Coloring
Two-coloring
Three-coloring
Four-coloring
Five-coloring
Other Map-coloring Algorithms
Maximal Flow
Work Assignment
Minimal Flow Cut
Summary
Exercises

Chapter 15 String Algorithms

Matching Parentheses
Evaluating Arithmetic Expressions
Building Parse Trees
Pattern Matching
DFAs
Building DFAs for Regular Expressions
NFAs
String Searching
Calculating Edit Distance
Summary
Exercises

Chapter 16 Cryptography

Terminology
Transposition Ciphers
Row/column Transposition
Column Transposition
Route Ciphers
Substitution Ciphers
Caesar Substitution
Vigenère Cipher
Simple Substitution
One-Time Pads
Block Ciphers
Substitution-Permutation Networks
Feistel Ciphers
Public-Key Encryption and RSA
Euler’s Totient Function
Multiplicative Inverses
An RSA Example
Practical Considerations
Other Uses for Cryptography
Summary
Exercises

Chapter 17 Complexity Theory

Notation
Complexity Classes
Reductions
3SAT
Bipartite Matching
NP-Hardness
Detection, Reporting, and Optimization Problems
Detection ≤p Reporting
Reporting ≤p Optimization
Reporting ≤p Detection
Optimizatio
Reporting
NP-Complete Problems
Summary
Exercises

Chapter 18 Distributed Algorithms

Types of Parallelism
Systolic Arrays
Distributed Computing
Multi-CPU Processing
Race Conditions
Deadlock
Quantum Computing
Distributed Algorithms
Debugging Distributed Algorithms
Embarrassingly Parallel Algorithms
Mergesort
Dining Philosophers
The Two Generals Problem
Byzantine Generals
Consensus
Leader Election
Snapshot
Clock Synchronization
Summary
Exercises

Chapter 19 Interview Puzzles

Asking Interview Puzzle Questions
Answering Interview Puzzle Questions
Summary
Exercises

Appendix A Summary of Algorithmic Concepts
Appendix B Solutions to Exercises

Annunci

Pubblicato il 13 agosto 2015 su Novità. Aggiungi ai preferiti il collegamento . Lascia un commento.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: