Python Data Structures and Algorithms

Python Data Structures and Algorithms

by Benjamin Baka
Released May 2017
Publisher(s): Packt Publishing
ISBN: 9781786467355

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

Implement classic and functional data structures and algorithms using Python

About This Book

  • A step by step guide, which will provide you with a thorough discussion on the analysis and design of fundamental Python data structures.

  • Get a better understanding of advanced Python concepts such as big-o notation, dynamic programming, and functional data structures.

  • Explore illustrations to present data structures and algorithms, as well as their analysis, in a clear, visual manner.

    • Who This Book Is For

    The book will appeal to Python developers. A basic knowledge of Python is expected.

    What You Will Learn

  • Gain a solid understanding of Python data structures.

  • Build sophisticated data applications.

  • Understand the common programming patterns and algorithms used in Python data science.

  • Write efficient robust code.

    • In Detail

    Data structures allow you to organize data in a particular way efficiently. They are critical to any problem, provide a complete solution, and act like reusable code.

    In this book, you will learn the essential Python data structures and the most common algorithms.

    With this easy-to-read book, you will be able to understand the power of linked lists, double linked lists, and circular linked lists. You will be able to create complex data structures such as graphs, stacks and queues. We will explore the application of binary searches and binary search trees. You will learn the common techniques and structures used in tasks such as preprocessing, modeling, and transforming data. We will also discuss how to organize your code in a manageable, consistent, and extendable way. The book will explore in detail sorting algorithms such as bubble sort, selection sort, insertion sort, and merge sort.

    By the end of the book, you will learn how to build components that are easy to understand, debug, and use in different applications.

    Style and Approach

    The easy-to-read book with its fast-paced nature will improve the productivity of Python programmers and improve the performance of Python applications.

    Table of contents

    1. Preface
      1. What this book covers
      2. What you need for this book
      3. Who this book is for
      4. Conventions
      5. Reader feedback
      6. Customer support
        1. Downloading the example code
        2. Errata
        3. Piracy
        4. Questions
    2. Python Objects, Types, and Expressions
      1. Understanding data structures and algorithms
      2. Python for data
        1. The Python environment
        2. Variables and expressions
          1. Variable scope
        3. Flow control and iteration
        4. Overview of data types and objects
          1. Strings
        5. Lists
        6. Functions as first class objects
          1. Higher order functions
          2. Recursive functions
          3. Generators and co-routines
        7. Classes and object programming
          1. Special methods
          2. Inheritance
        8. Data encapsulation and properties
      3. Summary
    3. Python Data Types and Structures
      1. Operations and expressions
        1. Boolean operations
        2. Comparison and Arithmetic operators
        3. Membership, identity, and logical operations
      2. Built-in data types
        1. None type
        2. Numeric Types
          1. Representation error
        3. Sequences
          1. Tuples
          2. Dictionaries
          3. Sorting dictionaries
          4. Dictionaries for text analysis
      3. Sets
        1. Immutable sets
      4. Modules for data structures and algorithms
        1. Collections
          1. Deques
          2. ChainMaps
          3. Counter objects
          4. Ordered dictionaries
          5. defaultdict
        2. Named tuples
        3. Arrays
      5. Summary
    4. Principles of Algorithm Design
      1. Algorithm design paradigms
      2. Recursion and backtracking
        1. Backtracking
        2. Divide and conquer - long multiplication
        3. Can we do better? A recursive approach
      3. Runtime analysis
        1. Asymptotic analysis
        2. Big O notation
          1. Composing complexity classes
          2. Omega notation (Ω)
          3. Theta notation (ϴ)
      4. Amortized analysis
      5. Summary
    5. Lists and Pointer Structures
      1. Arrays
      2. Pointer structures
      3. Nodes
      4. Finding endpoints
        1. Node
          1. Other node types
      5. Singly linked lists
        1. Singly linked list class
        2. Append operation
      6. A faster append operation
      7. Getting the size of the list
      8. Improving list traversal
      9. Deleting nodes
        1. List search
      10. Clearing a list
      11. Doubly linked lists
        1. A doubly linked list node
          1. Doubly linked list
        2. Append operation
        3. Delete operation
        4. List search
      12. Circular lists
        1. Appending elements
        2. Deleting an element
          1. Iterating through a circular list
      13. Summary
    6. Stacks and Queues
      1. Stacks
        1. Stack implementation
        2. Push operation
        3. Pop operation
          1. Peek
        4. Bracket-matching application
      2. Queues
        1. List-based queue
          1. Enqueue operation
          2. Dequeue operation
        2. Stack-based queue
          1. Enqueue operation
          2. Dequeue operation
        3. Node-based queue
          1. Queue class
          2. Enqueue operation
          3. Dequeue operation
        4. Application of queues
          1. Media player queue
      3. Summary
    7. Trees
      1. Terminology
      2. Tree nodes
      3. 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. 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
        8. Benefits of a binary search tree
        9. Expression trees
          1. Parsing a reverse Polish expression
        10. Balancing trees
        11. Heaps
      4. Summary
    8. Hashing and Symbol Tables
      1. Hashing
        1. Perfect hashing functions
      2. Hash table
        1. Putting elements
        2. Getting elements
        3. Testing the hash table
        4. Using [] with the hash table
        5. Non-string keys
        6. Growing a hash table
        7. Open addressing
          1. Chaining
        8. Symbol tables
      3. Summary
    9. Graphs and Other Algorithms
      1. Graphs
      2. Directed and undirected graphs
      3. Weighted graphs
      4. Graph representation
        1. Adjacency list
        2. Adjacency matrix
      5. Graph traversal
        1. Breadth-first search
        2. Depth-first search
      6. Other useful graph methods
      7. Priority queues and heaps
        1. Inserting
        2. Pop
        3. Testing the heap
      8. Selection algorithms
      9. Summary
    10. Searching
      1. Linear Search
        1. Unordered linear search
        2. Ordered linear search
      2. Binary search
      3. Interpolation search
        1. Choosing a search algorithm
      4. Summary
    11. Sorting
      1. Sorting algorithms
      2. Bubble sort
      3. Insertion sort
      4. Selection sort
      5. Quick sort
        1. List partitioning
          1. Pivot selection
        2. Implementation
        3. Heap sort
      6. Summary
    12. Selection Algorithms
      1. Selection by sorting
      2. Randomized selection
        1. Quick select
          1. Partition step
      3. Deterministic selection
        1. Pivot selection
        2. Median of medians
        3. Partitioning step
      4. Summary
    13. Design Techniques and Strategies
      1. Classification of algorithms
        1. Classification by implementation
          1. Recursion
          2. Logical
          3. Serial or parallel
          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
      2. Technical implementation
        1. Dynamic programming
          1. Memoization
          2. Tabulation
        2. The Fibonacci series
          1. The Memoization technique
          2. The tabulation technique
        3. Divide and conquer
          1. Divide
          2. Conquer
          3. Merge
          4. Merge sort
        4. Greedy algorithms
          1. Coin-counting problem
          2. Dijkstra's shortest path algorithm
      3. Complexity classes
        1. P versus NP
        2. NP-Hard
        3. NP-Complete
      4. Summary
    14. Implementations, Applications, and Tools
      1. Tools of the trade
      2. Data preprocessing
        1. Why process raw data?
        2. Missing data
        3. Feature scaling
          1. Min-max scalar
          2. Standard scalar
          3. Binarizing data
      3. Machine learning
        1. Types of machine learning
        2. 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
      4. Data visualization
        1. Bar chart
        2. Multiple bar charts
        3. Box plot
        4. Pie chart
        5. Bubble chart
      5. Summary

    Product information

    • Title: Python Data Structures and Algorithms
    • Author(s): Benjamin Baka
    • Release date: May 2017
    • Publisher(s): Packt Publishing
    • ISBN: 9781786467355