Marcello La Rocca - Algorithms and Data Structures in Action MEAP V05

MEAP Edition

Manning Early Access Program

Algorithms and Data Structures in Action

Version 5

Manning Publications Co. We welcome reader comments about anything in the manuscript - other than typos and other simple mistakes.

These will be cleaned up during production of the book by copyeditors and proofreaders.

https://livebook.manning.com/#!/book/algorithms-and-data-structures-in-action/discussion

For more information on this and other Manning titles go to

www.manning.com

Thanks for purchasing the MEAP for Algorithms and Data Structures in Action . This book is meant to help developers demystify algorithms, develop the ability to identify performance criticalities and improve the quality and speed of code.

Algorithms and data structures are the hearth of software and hardware, they are pervasive, even if we dont realize it. They handle everything from low-level tasks on chips, like divisions or square roots, to complex tasks on different chips, like reconstructing a sampled audio signals using discrete Fourier transform on your smartphone, to even more complex tasks on the cloud, as in scheduling the allocation of resources on a Kubernetes master node.

It would be impossible to gather a comprehensive catalog of all existing algorithms, many of them are designed to run in a very narrow context, and even just considering the general purpose ones, there are so many that no single engineer, computer scientist or part-time-genius could possibly remember them all; the goal for the interested reader should be, instead, to build awareness and familiarity with increasingly complex algorithmic concepts, developing the ability to look at problems with a critical eye and spot opportunities to make code or design more efficient by using the right data structure.

Algorithms are a challenging topic to teach; we approach it from a different angle, with the goal of making algorithms theory, usually covered only in textbooks, readily available and more easily digestible also to the practitioners; we provide optional in-depth analysis of the algorithms, but each chapter focus on explaining how data structures work, why they do work in a certain way, and above all how can they be applied to real-world problems.

Although we will use pseudo-code to describe how each data structure works, to get the most benefit from this book, you should have basic established skills in programming, be familiar with concept like loops or conditionals, and some knowledge of Object-oriented programming; basic knowledge of core data structures could make your learning path faster, but we also provide a crash-course in the appendixes section, if you start from scratch on algorithms.

The book is divided into three parts, plus an extra part with appendixes at the end.

Part 1 will focus on data structures of low-medium complexity that, nonetheless, can provide a significant improvement over the basic structures covered in typical algorithms 101 courses.

Part 2 covers more advanced topics, introducing data structures that can handle multi-dimensional data and their applications.

Part 3 explains some of the most important optimization methods, all applied to graphs, the main data structure used in this section.

The appendixes are, instead, optional material provided to readers to refresh and delve into core algorithmic topics, from big-oh notation to basic data structures, whose understanding will help readers go through the bulk of this book.

Be sure to post any feedback you have about the book in the liveBook discussion forum.

Thanks again for your interest and for purchasing the MEAP!

Marcello La Rocca

This chapter covers

Why you should learn about data structures and algorithms

What benefits reading this book can give you

What you need to get started

Abstracting a problem

Moving from problems to solutions

Its great to have you on board for this journey into the world of data structures and algorithms.

We hope this will be as an exciting journey for you as it was for us.

The topics discussed in this book have contributed to advance software engineering and changed the world around us. They still do make a difference and likely, on average, you get in contact with dozens of devices and services using these algorithms, every day.

The short answer is: to try and become a better software developer. Knowing about data structures and algorithms is like adding a tool to your tool belt.

Have you ever heard of Maslows hammer, aka the law of the instrument? Its a conjecture, driven by observation, about how people who only know one way to do things, tend to apply what they know to all kind of different situations.

If your tool belt only has a hammer, you will be tempted to treat everything as a nail. If you only know one way to sort a list of numbers, you will never be able to leverage the context to find more efficient solutions.

The purpose of this book is giving you many tools you can use when approaching a problem. We will build upon the basic algorithms to which you normally are introduced to in a computer science 101 course (or alike) and introduce the reader to more advanced material.

After reading this book you should be able to recognize situations where you could improve the performance of your code by using a specific data structure and/or algorithm.

Obviously, your goal should not be remembering by heart all the details of all the data structures we will discuss. We will rather try to show you how to reason about issues, where to find ideas about algorithms that might help you in solving problems. This book will also serve as a handbook, sort of a recipe collection, with indications about some common scenarios that could be used to categorize those problems and the best structures you could use to attack them.

Keep in mind that some topics are quite advanced and, when we delve into the details, it might require a few reads to understand everything. The book is structured in such a way to provide many levels of in-depth analysis, with advanced sections generally grouped together towards the end of each chapter, so if youd like to get only an understanding of the topics, you are not required delve into the theory.

Yes, they are not exactly the same thing, technically they are not equivalent. Nevertheless, we might sometimes use the two terms interchangeably and, for the sake of brevity, use data structure to intend a DS and all its relevant methods.

There are many ways to point out the difference between the two terms, but I particularly like this metaphor: data structures are like nouns , while algorithms are like verbs .

I like this angle because, besides hinting at their different behavior, implicitly reveals the mutual dependency between them. For instance, in English, to build a meaningful phrase, we need both nouns and verbs, subject (or object) and action performed (or endured).

Data structures and algorithms are interconnected, they need each other.

Data structures are the substrate, a way to organize an area of memory to represent data.

Algorithms are procedures, sequence of instructions aimed to transform data.

Without algorithms to transform them, data structures would just be useless bits on a memory chip; without data structures to operate on, most algorithms wouldnt even exist.