R Data Structures and Algorithms

R Data Structures and Algorithms

by Dr. PKS Prakash, Achyutuni Sri Krishna Rao
Released November 2016
Publisher(s): Packt Publishing
ISBN: 9781786465153

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

Increase speed and performance of your applications with efficient data structures and algorithms

About This Book

  • See how to use data structures such as arrays, stacks, trees, lists, and graphs through real-world examples

  • Find out about important and advanced data structures such as searching and sorting algorithms

  • Understand important concepts such as big-o notation, dynamic programming, and functional data structured

    • Who This Book Is For

    This book is for R developers who want to use data structures efficiently. Basic knowledge of R is expected.

    What You Will Learn

  • Understand the rationality behind data structures and algorithms

  • Understand computation evaluation of a program featuring asymptotic and empirical algorithm analysis

  • Get to know the fundamentals of arrays and linked-based data structures

  • Analyze types of sorting algorithms

  • Search algorithms along with hashing

  • Understand linear and tree-based indexing

  • Be able to implement a graph including topological sort, shortest path problem, and Prim's algorithm

  • Understand dynamic programming (Knapsack) and randomized algorithms

    • In Detail

    In this book, we cover not only classical data structures, but also functional data structures.

    We begin by answering the fundamental question: why data structures? We then move on to cover the relationship between data structures and algorithms, followed by an analysis and evaluation of algorithms. We introduce the fundamentals of data structures, such as lists, stacks, queues, and dictionaries, using real-world examples. We also cover topics such as indexing, sorting, and searching in depth.

    Later on, you will be exposed to advanced topics such as graph data structures, dynamic programming, and randomized algorithms. You will come to appreciate the intricacies of high performance and scalable programming using R. We also cover special R data structures such as vectors, data frames, and atomic vectors.

    With this easy-to-read book, you will be able to understand the power of linked lists, double linked lists, and circular linked lists. We will also explore the application of binary search and will go in depth into sorting algorithms such as bubble sort, selection sort, insertion sort, and merge sort.

    Style and approach

    This easy-to-read book with its fast-paced nature will improve the productivity of an R programmer and improve the performance of R applications. It is packed with real-world examples.

    Table of contents

    1. R Data Structures and Algorithms
      1. R Data Structures and Algorithms
      2. Credits
      3. About the Authors
      4. Acknowledgments
      5. About the Reviewer
      6. www.PacktPub.com
        1. Why subscribe?
      7. 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. Downloading the color images of this book
          3. Errata
          4. Piracy
          5. Questions
      8. 1. Getting Started
        1. Introduction to data structure
        2. Abstract data type and data structure
        3. Relationship between problem and algorithm
        4. Basics of R
          1. Installation of R
          2. Basic data types in R
          3. Operations in R
          4. Control structures in R
            1. If condition
            2. If...else condition
            3. Ifelse function
            4. For() loop
            5. Nested for( ) loop
            6. While loop
            7. Special statements in loops
              1. Break statement
              2. Next statement
            8. Repeat loop
        5. First class functions in R
        6. Exercises
        7. Summary
      9. 2. Algorithm Analysis
        1. Getting started with data structure
        2. Memory management in R
          1. System runtime in R
          2. Best, worst, and average cases
          3. Computer versus algorithm
          4. Algorithm asymptotic analysis
            1. Upper bounds or Big O notation
            2. Lower bounds or Big Omega notation (Ω)
            3. Big θ notation
            4. Simplifying rules
            5. Classifying rules
          5. Computation evaluation of a program
            1. Component 1 - Assignment operator
            2. Component 2 - Simple loop
            3. Component 3 - Complex loop
            4. Component 4 - Loops with conditional statements
            5. Component 5 - Recursive statements
          6. Analyzing problems
          7. Space bounds
        3. Exercises
        4. Summary
      10. 3. Linked Lists
        1. Data types in R
          1. Vector and atomic vector
          2. Element data types
            1. Factor
            2. Matrix
            3. Array
            4. Dataframes
            5. List
        2. Object-oriented programming using R
        3. Linked list
          1. Linear linked list
          2. Doubly linked list
          3. Circular linked list
        4. Array-based list
        5. Analysis of list operations
        6. Exercises
        7. Summary
      11. 4. Stacks and Queues
        1. Stacks
          1. Array-based stacks
          2. Linked stacks
          3. Comparison of array-based and linked stacks
          4. Implementing recursion
        2. Queues
          1. Array-based queues
          2. Linked queues
          3. Comparison of array-based and linked queues
        3. Dictionaries
        4. Exercises
        5. Summary
      12. 5. Sorting Algorithms
        1. Sorting terminology and notation
        2. Three Θ(n²) sorting algorithms
          1. Insertion sort
          2. Bubble sort
          3. Selection sort
          4. The cost of exchange sorting
        3. Shell sort
        4. Merge sort
        5. Quick sort
        6. Heap sort
        7. Bin sort and radix sort
        8. An empirical comparison of sorting algorithms
        9. Lower bounds for sorting
        10. Exercises
        11. Summary
      13. 6. Exploring Search Options
        1. Searching unsorted and sorted vectors
        2. Self-organizing lists
          1. Heuristic 1 - Count
          2. Heuristic 2 - Move-to-front
          3. Heuristic 3 - Transpose
        3. Hashing
          1. Hash functions
          2. Open hashing
          3. Closed hashing
            1. Bucket hashing
            2. Linear probing
          4. Analysis of closed hashing
          5. Deletion
        4. Exercises
        5. Summary
      14. 7. Indexing
        1. Linear indexing
        2. ISAM
        3. Tree-based indexing
        4. 2-3 trees
        5. B-trees
          1. B+ trees
          2. B-tree analysis
        6. Exercises
        7. Summary
      15. 8. Graphs
        1. Terminology and representations
        2. Graph implementations
        3. Graph traversals
          1. Depth-first search
          2. Breadth-first search
          3. Topological sort
        4. Shortest path problems
          1. Single-source shortest paths
        5. Minimum-cost spanning tree
          1. Prim's algorithm
          2. Kruskal's algorithm
        6. Exercises
        7. Summary
      16. 9. Programming and Randomized Algorithms
        1. Dynamic programming
          1. The knapsack problem
          2. All pairs shortest paths
        2. Randomized algorithms
          1. Randomized algorithms for finding large values
          2. Skip lists
          3. Probabilistic analysis of skip lists
        3. Exercises
        4. Summary
      17. 10. Functional Data Structures
        1. Functional data structure
          1. Lazy evaluation
          2. Functional stacks
          3. Functional queues
            1. Fast fully-persistent queues
            2. Slowly-persistent queues and deques
        2. Summary

    Product information

    • Title: R Data Structures and Algorithms
    • Author(s): Dr. PKS Prakash, Achyutuni Sri Krishna Rao
    • Release date: November 2016
    • Publisher(s): Packt Publishing
    • ISBN: 9781786465153