Book Image

Beginning Java Data Structures and Algorithms

By : James Cutajar
Book Image

Beginning Java Data Structures and Algorithms

By: James Cutajar

Overview of this book

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.
Table of Contents (12 chapters)

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.

Algorithm for Converting Binary Numbers to Decimal

Number systems have different bases. Decimals numbers with a base of ten are what most of us are familiar with. Computers, on the other hand, use only ones and zeros (binary). Let's try to write some code that converts binary numbers to decimals.

Specifically, we want to develop an algorithm that accepts a string containing ones and zeros and returns an integer.

We can convert the binary string by following these steps:

  1. Start from the end of the string and process each character at a time. The position of each digit in the binary string corresponds to a decimal number in a sequence.
  2. To generate this sequence, you start from one and multiply by two every time, so one, two, four, eight, and so on (see Conversion Sequence row of Table 1.1). More formally, the sequence is a geometric progression that starts at one and progresses in a common ratio of two.
  3. We then apply the binary string as a mask on this sequence (seethe Binary String (Mask) row of Table 1.1).
  4. The result is a new sequence where the values are only kept if the corresponding position in the binary string has a value of one (see the Result row of Table 1.1).
  5. After applying the mask, we just need to sum up the resulting numbers together.

Conversion Sequence

16

8

4

2

1

Binary String (Mask)

1

0

1

1

0

Result

16

0

4

2

0

Table 1.1: Binary to decimal masking

In the preceding example (Table 1.1), resulting total is 22. This is our decimal number corresponding to the binary number 10110.

Note

To design our algorithm, it's important to realize that we don't need to store the entire conversion sequence. Since we are processing one binary digit at a time (starting from the back), we only need to use the conversion number corresponding to the binary position we are processing.

Snippet 1.1 shows us how we can do this. We use a single conversion variable instead of a sequence and initialize this variable to the value of one. We then use a loop to iterate over the length of the binary string starting from the end. While iterating, if the digit at our current position is one, we add the current conversion variable to the final result. We then simply double the current conversion variable and repeat. The code snippet is as follows:

public int convertToDecimal(String binary) {
  int conversion = 1;
  int result = 0;
  for (int i = 1; i <= binary.length(); i++) {
    if (binary.charAt(binary.length() - i) == '1')
      result += conversion;
    conversion *= 2;
  }
  return result;
}

Snippet 1.1: Binary to decimal. Source class name: BinaryToDecimal.

Note

Go tohttps://goo.gl/rETLfqto access the code.

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

  1. The algorithms shown in Snippet 1.1 the preceding snippets of code can be adapted to work with octal numbers instead of binary.
  2. Change the base from two to eight. This can be done by changing the conversion multiplier variable inSnippet 1.1.
  3. 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.