Hands-On Data Structures and Algorithms with Python

Hands-On Data Structures and Algorithms with Python

by Dr. Basant Agarwal, Benjamin Baka
Released October 2018
Publisher(s): Packt Publishing
ISBN: 9781788995573

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Learn to implement complex data structures and algorithms using Python

Key Features

  • Understand the analysis and design of fundamental Python data structures
  • Explore advanced Python concepts such as Big O notation and dynamic programming
  • Learn functional and reactive implementations of traditional data structures

Book Description

Data structures allow you to store and organize data efficiently. They are critical to any problem, provide a complete solution, and act like reusable code. Hands-On Data Structures and Algorithms with Python teaches you the essential Python data structures and the most common algorithms for building easy and maintainable applications.

This book helps you to understand the power of linked lists, double linked lists, and circular linked lists. You will learn to create complex data structures, such as graphs, stacks, and queues. As you make your way through the chapters, you will explore the application of binary searches and binary search trees, along with learning common techniques and structures used in tasks such as preprocessing, modeling, and transforming data. In the concluding chapters, you will get to grips with organizing your code in a manageable, consistent, and extendable way. You will also study how to bubble sort, selection sort, insertion sort, and merge sort algorithms in detail.

By the end of the book, you will have learned how to build components that are easy to understand, debug, and use in different applications. You will get insights into Python implementation of all the important and relevant algorithms.

What you will learn

  • Understand object representation, attribute binding, and data encapsulation
  • Gain a solid understanding of Python data structures using algorithms
  • Study algorithms using examples with pictorial representation
  • Learn complex algorithms through easy explanation, implementing Python
  • Build sophisticated and efficient data applications in Python
  • Understand common programming algorithms used in Python data science
  • Write efficient and robust code in Python 3.7

Who this book is for

This book is for developers who want to learn data structures and algorithms in Python to write complex and flexible programs. Basic Python programming knowledge is expected.

Table of contents

  1. Title Page
  2. Copyright and Credits
    1. Hands-On Data Structures and Algorithms with Python Second Edition
  3. Dedication
  4. Packt Upsell
    1. Why subscribe?
    2. Packt.com
  5. Contributors
    1. About the authors
    2. About the reviewers
    3. Packt is searching for authors like you
  6. Acknowledgments
  7. Preface
    1. Who this book is for
    2. What this book covers
    3. To get the most out of this book
      1. Download the example code files
      2. Download the color images
      3. Conventions used
    4. Get in touch
      1. Reviews
  8. Python Objects, Types, and Expressions
    1. Technical requirements
    2. Installing Python
    3. Understanding data structures and algorithms
      1. Python for data
      2. The Python environment
      3. Variables and expressions
      4. Variable scope
    4. Flow control and iteration
    5. Overview of data types and objects
      1. Strings
      2. Lists
        1. Functions as first class objects
      3. Higher order functions
      4. Recursive functions
    6. Generators and co-routines
      1. Classes and object programming
      2. Special methods
        1. Inheritance
        2. Data encapsulation and properties
    7. Summary
    8. Further reading
  9. Python Data Types and Structures
    1. Technical requirements
    2. Built-in data types
    3. None type
    4. Numeric types
    5. Representation error
    6. Membership, identity, and logical operations
    7. Sequences
    8. Learning about tuples
    9. Beginning with dictionaries
      1. Python
    10. Sorting dictionaries
    11. Dictionaries for text analysis
    12. Sets
      1. Immutable sets
    13. Modules for data structures and algorithms
      1. Collections
        1. Deques
        2. ChainMap objects
        3. Counter objects
        4. Ordered dictionaries
        5. defaultdict
        6. Learning about named tuples
        7. Arrays
    14. Summary
  10. Principles of Algorithm Design
    1. Technical requirements
    2. An introduction to algorithms
      1. Algorithm design paradigms
    3. Recursion and backtracking
      1. Backtracking
        1. Divide and conquer – long multiplication
        2. The recursive approach
      2. Runtime analysis
        1. Asymptotic analysis
    4. Big O notation
      1. Composing complexity classes
        1. Omega notation (Ω)
        2. Theta notation (ϴ )
      2. Amortized analysis
    5. Summary
  11. Lists and Pointer Structures
    1. Technical requirements
    2. Beginning with an example
    3. Arrays
    4. Pointer structures
      1. Nodes
        1. Finding endpoints
      2. Node class
        1. Other node types
    5. Introducing lists
      1. Singly linked lists
        1. Singly linked list class
        2. The append operation
        3. A faster append operation
        4. Getting the size of the list
        5. Improving list traversal
        6. Deleting nodes
        7. List search
        8. Clearing a list
      2. Doubly linked lists
        1. A doubly linked list node
        2. Doubly linked list class
        3. Append operation
        4. The delete operation
        5. List search
      3. Circular lists
        1. Appending elements
        2. Deleting an element in a circular list
        3. Iterating through a circular list
    6. Summary
  12. Stacks and Queues
    1. Technical requirements
    2. Stacks
      1. Stack implementation
      2. Push operation
      3. Pop operation
      4. Peek operation
      5. Bracket-matching application
    3. Queues
      1. List-based queues
        1. The enqueue operation
        2. The dequeue operation
      2. Stack-based queues
        1. Enqueue operation
        2. Dequeue operation
      3. Node-based queues
        1. Queue class
        2. The enqueue operation
        3. The dequeue operation
      4. Application of queues
        1. Media player queues
    4. Summary
  13. Trees
    1. Technical requirements
    2. Terminology
    3. Tree nodes
    4. Tree traversal
      1. Depth-first traversal
        1. In-order traversal and infix notation
        2. Pre-order traversal and prefix notation
        3. Post-order traversal and postfix notation
      2. Breadth-first traversal
    5. Binary trees
      1. Binary search trees
      2. Binary search tree implementation
      3. Binary search tree operations
        1. Finding the minimum and maximum nodes
      4. Inserting nodes
      5. Deleting nodes
      6. Searching the tree
      7. Benefits of a binary search tree
      8. Balancing trees
      9. Expression trees
        1. Parsing a reverse Polish expression
    6. Heaps
    7. Ternary search tree
    8. Summary
  14. Hashing and Symbol Tables
    1. Technical requirements
    2. Hashing
      1. Perfect hashing functions
    3. Hash tables
      1. Storing elements in a hash table
      2. Retrieving elements from the hash table
      3. Testing the hash table
      4. Using [] with the hash table
      5. Non-string keys
      6. Growing a hash table
      7. Open addressing
      8. Chaining
    4. Symbol tables
    5. Summary
  15. Graphs and Other Algorithms
    1. Technical requirements
    2. Graphs
    3. Directed and undirected graphs
    4. Weighted graphs
    5. Graph representations
      1. Adjacency lists
      2. Adjacency matrices
    6. Graph traversals
      1. Breadth-first traversal
      2. Depth-first search
    7. Other useful graph methods
    8. Priority queues and heaps
      1. Insert operation
      2. Pop operation
      3. Testing the heap
    9. Selection algorithms
    10. Summary
  16. Searching
    1. Technical requirements
    2. Introduction to searching
      1. Linear search
      2. Unordered linear search
      3. Ordered linear search
    3. Binary search
    4. Interpolation search
      1. Choosing a search algorithm
    5. Summary
  17. Sorting
    1. Technical requirements
    2. Sorting algorithms
    3. Bubble sort algorithms
    4. Insertion sort algorithms
    5. Selection sort algorithms
    6. Quick sort algorithms
      1. List partitioning
        1. Pivot selection
      2. An illustration with an example
      3. Implementation
    7. Heap sort algorithms
    8. Summary
  18. Selection Algorithms
    1. Technical requirements
    2. Selection by sorting
    3. Randomized selection
      1. Quick select
        1. Understanding the partition step
    4. Deterministic selection
      1. Pivot selection
      2. Median of medians
      3. Partitioning step
    5. Summary
  19. String Algorithms and Techniques
    1. Technical requirements
    2. String notations and concepts
    3. Pattern matching algorithms
      1. The brute-force algorithm
      2. The Rabin-Karp algorithm
        1. Implementing the Rabin-Karp algorithm
      3. The Knuth-Morris-Pratt algorithm
        1. The prefix function
        2. Understanding KMP algorithms
        3. Implementing the KMP algorithm
      4. The Boyer-Moore algorithm
        1. Understanding the Boyer-Moore algorithm
        2. Bad character heuristic
        3. Good suffix heuristic
        4. Implementing the Boyer-Moore algorithm
    4. Summary
  20. Design Techniques and Strategies
    1. Technical requirements
    2. Classification of algorithms
      1. Classification by implementation
        1. Recursion
        2. Logic
        3. Serial or parallel algorithms
        4. Deterministic versus nondeterministic algorithms
      2. Classification by complexity
        1. Complexity curves
      3. Classification by design
        1. Divide and conquer
        2. Dynamic programming
        3. Greedy algorithms
    3. Technical implementation
      1. Implementation using dynamic programming
        1. Memoization
        2. Tabulation
      2. The Fibonacci series
        1. The memoization technique
        2. The tabulation technique
      3. Implementation using divide and conquer
        1. Divide
        2. Conquer
        3. Merge
        4. Merge sort
      4. Implementation using greedy algorithms
        1. Coin-counting problem
        2. Shortest path algorithm
    4. Complexity classes
      1. P versus NP
      2. NP-Hard
      3. NP-Complete
    5. Summary
  21. Implementations, Applications, and Tools
    1. Technical requirements
    2. Knowledge discovery in data
    3. Data preprocessing
      1. Processing raw data
      2. Missing data
      3. Feature scaling
        1. Min-max scalar form of normalization
        2. Standard scalar
        3. Binarizing data
    4. Learning about machine learning
      1. Types of machine learning
      2. The hello classifier
      3. A supervised learning example
        1. Gathering data
        2. Bag of words
        3. Prediction
      4. An unsupervised learning example
        1. K-means algorithm
        2. Prediction
    5. Data visualization
      1. Bar chart
      2. Multiple bar charts
      3. Box plot
      4. Pie chart
      5. Bubble chart
    6. Summary
  22. Other Books You May Enjoy
    1. Leave a review - let other readers know what you think

Product information

  • Title: Hands-On Data Structures and Algorithms with Python
  • Author(s): Dr. Basant Agarwal, Benjamin Baka
  • Release date: October 2018
  • Publisher(s): Packt Publishing
  • ISBN: 9781788995573