Starting with Data Structures and Algorithms

Hello Everyone, my name is Amit and I am a third-year undergrad at IPU. I have solved numerous problems based on Data Structures and Algorithms (also known as DSA by the community).

Prerequisites:

Intermediate knowledge of any one programming language. It could be C, C++, Java or Python. Knowledge of topics such as data types, variables,conditionals, loops ,input and output is a must.

Recommended: Buy "Let Us C" Book from Yashwant Kanetkar covers almost all topics from basic to advanced in simple and lucid language.

Note: I am not associated with him or the publisher in any form or way. It's just my personal preference.

https://www.amazon.in/Let-us-Solutions-Yashavant-Kanetkar/dp/8183331777

I'll start this blog with a simple Roadmap to start your journey in DSA.

1. Learn one Programming Language: Without a Programming Language, there is no meaning to just theoretically learning Data Structures, you need a programming language to implement it. Some preferred Programming Languages are

   C++ > Java >> Python > C.

2. Data Structures: These are a way to store data. In Computer Science, we have a lot of Data Structures such as Arrays which is just connected and contiguous ways of storing data. We'll learn more about this later in this section. You have to learn a lot of Data Structures to start solving some problems and implementing them in your preferred Programming language.

3. Algorithms: It basically means the way (or recipe) to get a specific result. Likewise, you need some specific way to solve some problems and all those ways come under this section i.e. Binary Search, Bubble Sort, Heap Sort, etc.

We'll understand all these with a basic example.

There are numerous kinds of data structures present out there, but for sake of explanation, I'll pick the simplest one (which is also the first topic of Data Structures).

DATA STRUCTURE: Arrays

Before diving into Arrays let's learn some basics about primitive data types because they'll be used to explain Arrays.

Data type means a type of data like a number, string or character. When we say primitive, we mean the first or most fundamental data types, i.e.

these are basic data types which are used to build Data Structures:

Array is a collection of items of the same data type stored in a continuous fashion.

For Example, A teacher wants to store the roll number of all students in a class. She could use an Array because in an array items are stored in a continuous fashion.

Note: Here, the type of data is a number(Integer) so we use int for it.

it'll be coded in C++ as follows:

int roll_numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

This is how numbers are stored inside the Memory, we filled out data i.e. 1,2,3,4,5,6,7,8,9,10 and it'll get stored somewhere in memory for example 200 and all the next elements will be stored sequentially.

If we want to access our data, we have to do it through indexes.

Suppose, the teacher wants to get the 5th roll number so she'll enter

 printf("%d",roll_numbers[4]);

Here, 4 is used because the index starts from 0 i.e. array is 0-indexed.

Below is the simple Code in C to use Arrays.

// Code by Amit Tripathi @AmitTwtts
#include <stdio.h>
int main() {
    int roll_numbers[]  = {1, 2, 3, 4, 5, 6 ,7, 8, 9};
    printf("%d",roll_numbers[5]);
    return 0;
}

The order in which you should learn data structures is given below :

Data structures: Array, Linked List, Stack, Queue, Hash Table, BST, Map (Hash vs Tree), Set, Trie, Graph.

Now, let us learn a little about algorithms.

Algorithms

An Algorithm is simply a set of finite rules to perform an activity. It is not code, but it's a mixture of Code and English to explain what to do irrespective of programming Language.

For example, suppose you have an Array of students names and now you want to know if "Yash" is there or not.

Simple, just compare each element with "Yash" and if is present stop and print 1 else if not present print -1.

Algorithms are formally written in below manner

//Language doensn't matter here

Linear_Search(a, n, val) 
'a' is the given array, 'n' is the size of given array, 'val' is the value to search  
for(int i=0; i<n; i++){
if(n[i]==0)
print(1);
break;
else
print(-1)

Code for the same: Linear Search

// Online C compiler to run C program online
#include <stdio.h>

int main() {

    int size = 5;
    int marks[]  = {10, 20, 99, 54,32};
    // checking if 99 is there or not
    int check = 99;
    for(int i=0; i<size; i++){
        if(marks[i]==check){
            printf("%d", 1);
            return;
        }
    }

    printf("%d", -1);
    return 0;
}

That is one algorithm we used to check if a number is present in an array or not. Likewise, there are a lot of algorithms present around of various difficulties used to solve different problems.

Some Algorithms you need to learn are:

Algorithms: Time complexity, Space complexity, Recursion, Sorting, Searching, BFS & DFS, Dynamic programming, Bit manipulations.

Thanks for reading.