Java and Data structure & algorithms (DSA) - Introduction

 

Introduction to DSA

A computer program is a collection of instructions to perform a specific task. For this, a computer program may need to store data, retrieve data, and perform computations on the data.

A data structure is a named location that can be used to store and organize data. And, an algorithm is a collection of steps to solve a particular problem. Learning data structures and algorithms allow us to write efficient and optimized computer programs.

What is an Algorithm?

In computer programming terms, an algorithm is a set of well-defined instructions to solve a particular problem. It takes a set of input(s) and produces the desired output. For example,

An algorithm to add two numbers:

1. Take two number inputs

2. Add numbers using the + operator

3. Display the result

---

Qualities of a Good Algorithm

• Input and output should be defined precisely.
• Each step in the algorithm should be clear and unambiguous.
• Algorithms should be the most effective among many different ways to solve a problem.
• An algorithm shouldn't include computer code. Instead, the algorithm should be written in such a way that it can be used in different programming languages.

Algorithm Examples

Algorithm 1: Add two numbers entered by the user

Step 1: Start
Step 2: Declare variables num1, num2 and sum. 
Step 3: Read values num1 and num2. 
Step 4: Add num1 and num2 and assign the result to sum.
        sum←num1+num2 
Step 5: Display sum 
Step 6: Stop

Data Structure and Types

What are Data Structures?

The data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

Depending on your requirement and project, it is important to choose the right data structure for your project. For example, if you want to store data sequentially in the memory, then you can go for the Array data structure.

Note: Data structure and data types are slightly different. A data structure is the collection of data types arranged in a specific order.

Types of Data Structure

Basically, data structures are divided into two categories:

• Linear data structure
• Non-linear data structure

Linear data structures

In linear data structures, the elements are arranged in sequence one after the other. Since elements are arranged in a particular order, they are easy to implement.

However, when the complexity of the program increases, the linear data structures might not be the best choice because of operational complexities.

Popular linear data structures are:

a. Arrays

b. Stack

c. Queue

d. Linked List

Non-linear data structures

Unlike linear data structures, elements in non-linear data structures are not in any sequence. Instead, they are arranged in a hierarchical manner where one element will be connected to one or more elements.

Non-linear data structures are further divided into graph and tree-based data structures.

1. Graph Data Structure

Popular Graph-Based Data Structures:

a. Spanning tree and minimum spanning tree

b. Strongly connected components

c. Adjacency Matrix

d. Adjacency Lists

2. Trees Data Structure

Popular Tree-based Data Structure

a. Binary Tree

b. Binary Search Tree

c. AVL Tree 

d. B-Tree 

e. B+ Tree 

f. Red-Black Tree

Why Data Structure?

Knowledge about data structures helps you understand the working of each data structure. And, based on that you can select the right data structures for your project.

This helps you write memory and time-efficient code.

It is also for those who wonder why big companies like Google, Facebook, and Amazon hire programmers who are exceptionally good at optimizing Algorithms.

Asymptotic Notations

The efficiency of an algorithm depends on the amount of time, storage, and other resources required to execute the algorithm. The efficiency is measured with the help of asymptotic notations.

An algorithm may not have the same performance for different types of inputs. With the increase in the input size, the performance will change.

Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.

There are mainly three asymptotic notations:

• Big-O notation
• Omega notation
• Theta notation

Some useful links: for IT students to grow.

🔗 Frontend developer roadmap

🔗 Backend developer roadmap

🔗 Python developer roadmap

🔗 A quick guide to OOPs in PHP

🔗 StackOverflow survey 2022

🔗 All about flutter development

🔗 9 skills you must learn in college

🔗 Helpful projects links for internships and jobs