23,92 €
Mehr erfahren.
- Herausgeber: Packt Publishing
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Though your application serves its purpose, it might not be a high performer. Learn techniques to accurately predict code efficiency, easily dismiss inefficient solutions, and improve the performance of your application.
Key Features
- Explains in detail different algorithms and data structures with sample problems and Java implementations where appropriate
- Includes interesting tips and tricks that enable you to efficiently use algorithms and data structures
- Covers over 20 topics using 15 practical activities and exercises
Book Description
Learning about data structures and algorithms gives you a better insight on how to solve common programming problems. Most of the problems faced everyday by programmers have been solved, tried, and tested. By knowing how these solutions work, you can ensure that you choose the right tool when you face these problems.
This book teaches you tools that you can use to build efficient applications. It starts with an introduction to algorithms and big O notation, later explains bubble, merge, quicksort, and other popular programming patterns. You'll also learn about data structures such as binary trees, hash tables, and graphs. The book progresses to advanced concepts, such as algorithm design paradigms and graph theory. By the end of the book, you will know how to correctly implement common algorithms and data structures within your applications.
What you will learn
- Understand some of the fundamental concepts behind key algorithms
- Express space and time complexities using Big O notation.
- Correctly implement classic sorting algorithms such as merge and quicksort
- Correctly implement basic and complex data structures
- Learn about different algorithm design paradigms, such as greedy, divide and conquer, and dynamic programming
- Apply powerful string matching techniques and optimize your application logic
- Master graph representations and learn about different graph algorithms
Who this book is for
If you want to better understand common data structures and algorithms by following code examples in Java and improve your application efficiency, then this is the book for you. It helps to have basic knowledge of Java, mathematics and object-oriented programming techniques.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Seitenzahl: 246
Veröffentlichungsjahr: 2018
Ähnliche
Beginning Java Data Structures and Algorithms
Copyright © 2018 Packt Publishing
All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.
Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book.
Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.
Acquisitions Editor: Aditya Date, Bridget NealeContent Development Editors: Madhura Bal, Madhunikita Sunil ChindarkarProduction Coordinator: Ratan Pote
First published: July 2018
Production reference: 1270718
Published by Packt Publishing Ltd. Livery Place 35 Livery Street Birmingham B3 2PB, UK.
ISBN 978-1-78953-717-8
www.packtpub.com
Mapt is an online digital library that gives you full access to over 5,000 books and videos, as well as industry leading tools to help you plan your personal development and advance your career. For more information, please visit our website.
Why Subscribe?
Spend less time reading and more time coding with practical eBooks and Videos from over 4,000 industry professionals
Improve your learning with Skill Plans built especially for you
Get a free eBook or video every month
Mapt is fully searchable
Copy and paste, print, and bookmark content
PacktPub.com
Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at [email protected] for more details.
At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on Packt books and eBooks.
Contributors
About the Author
James Cutajar is a software developer with an interest in scalable, high-performance computing, and distributed algorithms. He is also an author, open source contributor, blogger, and a tech evangelist. When he is not writing software, he is riding his motorbike, surfing, or flying light aircraft. He was born in Malta, lived in London for almost a decade, and is now working in Portugal.
Packt Is Searching for Authors like You
If you're interested in becoming an author for Packt, please visit authors.packtpub.com and apply today. We have worked with thousands of developers and tech professionals, just like you, to help them share their insight with the global tech community. You can make a general application, apply for a specific hot topic that we are recruiting an author for, or submit your own idea.
Table of Contents
Title Page
Copyright and Credits
Beginning Java Data Structures and Algorithms
Packt Upsell
Why Subscribe?
PacktPub.com
Contributors
About the Author
Packt Is Searching for Authors like You
Preface
Who This Book Is For
What This Book Covers
To Get the Most out of This Book
Download the Example Code Files
Download the Color Images
Conventions Used
Get in Touch
Reviews
Algorithms and Complexities
Developing Our First Algorithm
Algorithm for Converting Binary Numbers to Decimal
Activity: Writing an Algorithm to Convert Numbers from Octal To Decimal
Measuring Algorithmic Complexity with Big O Notation
Complexity Example
Understanding Complexity
Activity: Developing a Timing Table Using the Exponential Algorithm
Complexity Notation
Identifying the Best and Worst Performance of an Algorithm While Checking for Duplicates in an Array
Activity: Converting Expressions to Big O Notations
Identifying Algorithms with Different Complexities
Linear Complexity
Quadratic Complexity
Logarithmic Complexity
Exponential Complexity
Constant Complexity
Activity: Developing a Faster Intersection Algorithm
Summary
Sorting Algorithms and Fundamental Data Structures
Introducing Bubble Sorting
Understanding Bubble Sorting
Implementing Bubble Sort
Improving Bubble Sorting
Implementing Bubble Sort Improvement
Activity: Implementing Selection Sort in Java
Understanding Quick Sort
Understanding Recursion
Implementing Binary Search Recursively
Quicksort Partitioning
Activity: Understanding the Partitioning Method
Putting It All Together
Implementing Quick Sort
Using Merge Sort
Dividing the Problem
Implementing Merge Sort
Merging the Problem
Activity: Implementing Merge Sort in Java
Getting Started with Fundamental Data Structures
Introducing Data Structures
Linked Lists Structure
Converting the Linked List to a Doubly Linked List Structure 
Linked Lists Operations
Activity: Traversing the Linked List
Queues
Adding and Deleting the Elements from the Queue
Stacks
Reversing a String
Modeling Stacks and Queues Using Arrays
Safe Enqueuing in an Array
Activity: Evaluating the Postfix Expression
Summary
Hash Tables and Binary Search Trees
Introducing Hash Tables
Understanding Hash Tables
Dealing with Collisions with Chaining
Dealing with Collisions with Open Addressing
Carrying out the Linear Probing Search Operation
Remainder and Multiplication Hash Functions
Implementing the Multiplication Method for a Hash Table
Universal Hashing
Activity: Implementing Open Addressing
Getting Started with Binary Search Trees
Binary Tree Structure
Binary Search Tree Operations
Searching for a Minimum Key in a Binary Tree
Traversing a Binary Search Tree
Activity: Implementing BFS in Java
Balanced Binary Search Trees
Applying Right Tree Rotation
Activity: Retrieving the Successor of an Element When the Tree is Traversed in Inorder
Summary
Algorithm Design Paradigms
Introducing Greedy Algorithms
The Activity Selection Problem
Solving the Activity Selection Problem
Ingredients of a Greedy Algorithm
Optimal Substructure Property
Greedy Choice Property
Huffman Coding
Building a Huffman Code
Developing an Algorithm to Generate Code Words Using Huffman Coding
Activity: Implementing a Greedy Algorithm to Compute Egyptian Fractions
Getting Started with Divide and Conquer Algorithms
The Divide and Conquer Approach
The Master Method
The Closest Pair of Points Problem
Activity: Solving the Maximum Subarray Problem
Understanding Dynamic Programming
Elements of a Dynamic Programming Problem
Optimal Substructure
Overlapping Subproblems
0-1 Knapsack
Solving the 0-1 Knapsack Problem Using Recursion
Longest Common Subsequence
Activity: The Coin Change Problem
Summary
String Matching Algorithms
Naive Search Algorithm
Implementing Naive Search
Developing the String Matching Algorithm in Java
Rationalization of the Naive Search Algorithm
Getting Started with the Boyer-Moore String Searching Algorithm
The Bad Character Rule
Activity: Implementing the Bad Character Rule
The Good Suffix Rule
Application of the Boyer-Moore Algorithm
Implementing the Boyer-Moore Algorithm 
Introducing Other String Matching Algorithms
Rabin-Karp
Applying the Rabin-Karp Algorithm
Knuth–Morris–Pratt
Aho–Corasick
Summary
Graphs, Prime Numbers, and Complexity Classes
Representing Graphs
Adjacency List Representation
Writing a Java Code to Add Weights to the Directed Graph
Adjacency Matrix Representation
Activity: Building the Adjacency Matrix Representation of a Weighted Undirected Graph
Traversing a Graph
Breadth-First Search
Depth-First Search
Cycle Detection
Activity: Using BFS to Find the Shortest Path Out of a Maze
Calculating Shortest Paths
Single Source Shortest Path: Dijkstra's Algorithm
All Pairs Shortest Paths: Floyd-Warshall Algorithm
Activity: Improving Floyd-Warshall's Algorithm to Reconstruct the Shortest Path
Prime Numbers in Algorithms
Sieve of Eratosthenes
Prime Factorization
Activity: Implementing the Sieve of Eratosthenes
Other Concepts in Graphs
Minimum Spanning Trees
A* Search
Maximum Flow
Understanding Complexity Classes of Problems
Summary
Other Books You May Enjoy
Leave a Review - Let Other Readers Know What You Think
Preface
A data structure is a way of organizing data so that it can be accessed and/or modified efficiently. Learning about data structures and algorithms gives you a better insight on how to solve common programming problems. Most of the problems faced everyday by programmers have been solved, tried and tested. Knowing how these solutions work, ensures that the right tool is chosen when faced with these problems.
This book teaches you tools that you can use to build efficient applications. It starts with an introduction to algorithms and big O notation, later explains bubble, merge, quicksort, and other popular programming patterns. You’ll also learn about data structures such as binary trees, hash tables, and graphs. The book progresses to advanced concepts, such as algorithm design paradigms and graph theory. By the end of the book, you will know how to correctly implement common algorithms and data structures within your applications.
Who This Book Is For
If you want to better understand common data structures and algorithms by following code examples in Java and improve your application efficiency, then this is the book for you. It helps to have basic knowledge of Java, mathematics and object-oriented programming techniques.
What This Book Covers
Chapter 1, Algorithms and Complexities, covers how to define an algorithm, measure algorithmic complexity, and identify algorithms with different complexities. It also covers how to assess various examples with different runtime complexities
Chapter 2, Sorting Algorithms and Fundamental Data Structures, explores bubble, quick, and merge sort. We will also introduce data structures and study various implementations and use cases of linked lists, queues, and stacks. We will also see how some data structures can be used as building blocks to build more complex ones.
Chapter 3, Hash Tables and Binary Search Trees, talks about data structures for implementing the data dictionary operation. In addition, binary trees also give us the ability to perform various range queries. We will also see examples of both data structures, and implementations of these operations.
Chapter 4, Algorithm Design Paradigms, discusses three different algorithm design paradigms along with example problems, and discusses how to identify whether problems may be solvable by one of the given paradigms.
Chapter 5, String Matching Algorithms, introduces the string matching problem. This chapter also introduces you to the string matching algorithms, starting from the naive search algorithm and improving it by using the rules introduced by Boyer and Moore. We'll also explore some other string matching algorithms without going into too much detail about them.
Chapter 6, Graphs, Prime Numbers, and Complexity Classes, introduces graphs, formalizing what they are and showing two different ways to represent them in computer programs. Later, we'll take a look at ways of traversing graphs, using them as building blocks for building more complex algorithms. We'll also look at two different algorithms for finding shortest paths in a graph.
To Get the Most out of This Book
For successful completion of this book, you will require a computer system with at least an i3 processor, 4 GB RAM, 10 GB hard disk and an internet connection. Along with this you would require the following software:
Java SE Development Kit, JDK 8 (or a later version)
Git clien
t
Java IDE (
IntelliJ or Eclipse
)
Download the Example Code Files
You can download the example code files for this book from your account at www.packtpub.com. If you purchased this book elsewhere, you can visit www.packtpub.com/support and register to have the files emailed directly to you.
You can download the code files by following these steps:
Log in or register at
www.packtpub.com
.
Select the
SUPPORT
tab.
Click on
Code Downloads & Errata
.
Enter the name of the book in the
Search
box and follow the onscreen instructions.
Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:
WinRAR/7-Zip for Windows
Zipeg/iZip/UnRarX for Mac
7-Zip/PeaZip for Linux
The code bundle for the book is also hosted on GitHub at https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java. In case there's an update to the code, it will be updated on the existing GitHub repository.
We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!
Download the Color Images
We also provide a PDF file that has color images of the screenshots/diagrams used in this book. You can download it here: https://www.packtpub.com/sites/default/files/downloads/BeginningJavaDataStructuresandAlgorithms_ColorImages.pdf.
Get in Touch
Feedback from our readers is always welcome.
General feedback: Email [email protected] and mention the book title in the subject of your message. If you have questions about any aspect of this book, please email us at [email protected].
Errata: Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you have found a mistake in this book, we would be grateful if you would report this to us. Please visit www.packtpub.com/submit-errata, selecting your book, clicking on the Errata Submission Form link, and entering the details.
Piracy: If you come across any illegal copies of our works in any form on the Internet, we would be grateful if you would provide us with the location address or website name. Please contact us at [email protected] with a link to the material.
If you are interested in becoming an author: If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, please visit authors.packtpub.com.
Reviews
Please leave a review. Once you have read and used this book, why not leave a review on the site that you purchased it from? Potential readers can then see and use your unbiased opinion to make purchase decisions, we at Packt can understand what you think about our products, and our authors can see your feedback on their book. Thank you!
For more information about Packt, please visit packtpub.com.
Algorithms and Complexities
An algorithm is a set of logical instructions to perform a particular task. Algorithms are everywhere nowadays. As a software developer, understanding the core principles of algorithms and data structures will enable you to make informed decisions on how to approach a particular problem. This is valid whether you're working in a bank writing accounting software or doing medical research data, mining genetic code. How do we determine which is the right algorithm to use when more than one solution to a problem exists? In this chapter, we will examine different types of algorithms and discuss how the performance varies in each. We will discuss what makes an algorithm more efficient than another and how to express the complexity of each.
By the end of this chapter, you will be able to:
Define an algorithm with an example
Measure algorithmic complexity
Identify algorithms with different complexities
Assess various examples with different runtime complexities
Developing Our First Algorithm
An algorithm can be seen as a roadmap or a set of instructions to accomplish a well-defined task. In this section, we will build a simple example of one such algorithm to help us get started.
Activity: Writing an Algorithm to Convert Numbers from Octal To Decimal
Scenario
In aviation, the aircraft's transponders transmit a code so that they can identify one another. This code uses the octal system, a number system which has a base of 8. We have been asked to write a method to convert octal numbers into decimals. For example, the octal number 17 is represented as 15 in the decimal system.
Aim
To be able to adapt the algorithm shown in the previous section to be used in a different scenario.
Prerequisites
Ensure that you have a class available on the following path:
https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson1/activity/octaltodecimal/OctalToDecimal.java
You will find the following method that needs implementing:
public int convertToDecimal (String octal)
If you have your project set up, you can run the unit test for this activity by running the following command:
gradlew test --tests com.packt.datastructuresandalg.lesson1.activity.octaltodecimal*
Steps for Completion
The algorithms shown in
Snippet 1.1
the preceding snippets of code can be adapted to work with octal numbers instead of binary.
Change the base from two to eight. This can be done by changing the conversion multiplier variable in
Snippet 1.1
.
Parse the digit being processed to convert it into an integer. This integer can then be multiplied by the conversion variable or result of the power function.
In this first section, we introduced the idea of algorithms by working on a simple example. It's important to note that for every problem multiple solutions exist. Choosing the right algorithm to solve your problem will depend on several metrics, such as performance and memory requirements.
Measuring Algorithmic Complexity with Big O Notation
Algorithmic complexity is a way to describe the efficiency of an algorithm as a relation of its input. It can be used to describe various properties of our code, such as runtime speed or memory requirements. It's also a very important tool programmers should understand to write efficient software. In this section, we will start by describing a scenario, introducing the section, and then dive into the details of the various types of complexities and the different techniques to measure them.
Understanding Complexity
To better understand algorithmic complexity, we can make use of an analogy. Imagine that we were to set different types of algorithms so that they compete against one another on a race track. However, there is a slight twist: The race course has no finish line.
Since the race is infinite, the aim of the race is to surpass the other, slower opponents over time and not to finish first. In this analogy, the race track distance is our algorithm input. How far from the start we get, after a certain amount of time, represents the amount of work done by our code.
Recall the quadratic method for measuring the closest pair of planes in the preceding section. In our fictitious race, the quadratic algorithm starts quite fast and is able to move quite a distance before it starts slowing down, similar to a runner that is getting tired and slowing down. The further it gets away from the start line, the slower it gets, although it never stops moving.
Not only do the algorithms progress through the race at different speeds, but their way of moving varies from one type to another. We already mentioned that O(n2) solutions slow down as they progress along the race. How does this compare to the others?
Another type of runner taking part in our imaginary race is the linear algorithm. Linear algorithms are described with the notation of O(n). Their speed on our race track is constant. Think of them as an old, reliable car moving at the same fixed speed.
In real life, solutions that have an O(n) runtime complexity have a running performance that is directly proportional to the size of their input.
This means, for example, that if you double the input size of a linear algorithm, the algorithm would also take about twice as long to finish.
The efficiency of each algorithm is always evaluated in the long run. Given a big enough input, a linear algorithm will always perform better than a quadratic one.
We can go much quicker than O(n). Imagine that our algorithm is continually accelerating along the track instead of moving constantly. This is the opposite of quadratic runtime. Given enough distance, these solutions can get really fast. We say that these type of algorithms have a logarithmic complexity written as O(log n).
In real life, this means that the algorithm doesn't slow much as the size of the input increases. Again, it doesn't matter if at the start, the algorithm performs slower than a linear one for a small input, as for a big enough input, a logarithmic solution will always outperform the linear one.
Can we go even faster? It turns out that there is another complexity class of algorithms that performs even better.
Picture a runner in our race who has the ability to teleport in constant time to any location along our infinite track. Even if the teleportation takes a long time, as long as it's constant and doesn't depend on the distance traveled, this type of runner will always beat any other. No matter how long the teleportation takes, given enough distance, the algorithm will always arrive there first. This is what is known as a constant runtime complexity, written as O(1). Solutions that belong to this complexity class will have a runtime independent of the input size given.
