Geeks for Geeks

Data Structure and Algorithms (self-paced)

Submitted in partial fulfillment of the requirements for

the award of degree of

Bachelor of Technology
Computer Science and Engineering

LOVELY PROFESSIONAL

UNIVERSITY PHAGWARA, PUNJAB

From 05/10/20 to 12/07/20 SUBMITTED

BY

Name of Student: Adarsh P Nair

Registration Number: 11804530
 Declaration

To whom so ever it may concern

I, Adarsh P Nair, 11804530, hereby declare that the work done by me on Geeks for Geeks DSA-
Self Paced from May, 2020 to July, 2020, is a record of original work for the partial fulfillment
of the requirements for the award of the degree, Bachelor of Technology Computer Science and
Engineering.

Name: Adarsh P Nair (11804530)

Dated: 25/09/2020
Certificate:

Title
1 Declaration by Student
2 Training Certification from organization
3 List of Tables
4 Introduction
5 The Basics
6 Data Structures
7 Advance Algorithms
8 Conclusion
9 References

Link:
link:https://media.geeksforgeeks.org/courses/certificates/62c42ece75a446a7e64b8a23aee22
bf3.pdf

List of Tables:
Introduction
Geeks for Geeks is a popular website among the developer community, with its amazing content
and popular article about various topics which is hard to get grasp within the computer science
community, founded by Mr. Sandeep Jain an IIT graduate. Not only they produce articles about
various algorithms and techniques regarding coding interviews they also provide some free and
paid courses. One of the most famous courses among all is their popular Data Structure and
Algorithms.
Data Structure
The Data Structure is efficient manner of storing the data in an organized way. When we are
dealing with the multiple data, old primitive type data like int, float, char, double etc. will not
come handy in order to store large amount of input we need data structures like array. But the
question is array is efficient and organized to store data. Array is linear data structure since it can
store in linear manner. Now there are many types of data structure some of which we learned in
the DSA - self paced course provided by geeks for geeks.
Algorithms
Real world application needs efficiency, time, memory and precision. In order to become a good
programmer you generally need to keep all of these in your mind when you are creating an real
world application since a wrong moment can have a devastated effects on people, country or
even world itself. Algorithms in sense it means step by step guide to do something. In computer
science world these can be demonstrated by telling a computer what to do. The more efficient,
less time consuming also generally known as time complexity, less memory that is space
complexity and more the precision is present better the algorithm.
DSA (Self-paced)
This course helped me to get deep understanding of the data structures and algorithms from the
beginner level to intermediate level. Although the course curriculum is divided for 10 weeks but
putting in lot of effort can lessen that time span. The course not only provides the theoretical part
but also there are lots of programming problems for easy to hard which helps us to implement
those theory we just learned into the program. By solving those problem not only help to get
more understanding of the topics.
The Basics:
The Basics is where you get the base of your knowledge. In order to build strong building, you
need to have a strong base. It covers the following fundamentals:
Introduction
This where we learn about the complexities
The time complexity: deals with the time required to perform certain task by the program
The space complexity: deals with the amount of auxiliary space required by the program
Generally calculating the time for the program to execute it task depends on various components
such as system, RAM, processor, and other factors in order to calculate a universal time we need
other method called Asymptotic notation.
Theta notation
Big O notation
Omega notation
Generally, we use big O notation since it uses upper bound. From here we calculate worst,
average and best-case time complexities.

Mathematics
The technology is built with the use of mathematical concepts and theory. In order get an
understanding of the algorithms one must have basic knowledge in mathematics.
Concepts like
Arithmetic and Geometric Progression
Quadratic Equation
Mean and Median
Prime Numbers
LCM and HCF
Factorials
Permutation and Combinations Basics
Modular Arithmetic
Mathematics sections covers all the necessary basics.

Bit Magic
Computer only understand binary digits that is 0 and 1. This 0 and 1 are called bit. The smallest
unit of memory in the we learned about the basic bitwise algorithms.
Basics of bitwise operation like ADD, OR, XOR, left shift and right shift operator.
Bit algorithms important tactics
Basic problems on bit manipulation
Maximum AND value

Recursion
Recursion happens when a function calls itself. Recursion is a very powerful concept to reduces
the time complexity and in creating the binary tree. In recursion we need a base case to stop the
recursion.
Recursion Basics (some basic concepts of recursion and identifying the base case to stop
recursion)
Basic Problems on Recursion
Tail Recursion
Explanation of subsets Generation
Explanation of Josephus problem
Explanation of permutation of a string

String
Strings are defined as a stream of characters.
What we learnt:
In Built function of string in C++
Built in methods for string in Java
Naïve pattern Searching
Rabin-Karp Algorithm for pattern searching
KMP Algorithms for pattern Searching

Data Structure:
Storing the data in efficient structured manner so that it can be easily access and readable. Data
Structure make program to traverse through the data with better time complexity.
Array
Fundamental Linear data structure, it uses index to allocate address to the data it stores index
generally starts with 0 in any data structure.
What we learnt:
Introduction to array
Insertion and Deletion in array
Array rotation
Reversing an Array
Sliding Window Technique
Prefix Sum Array
Implementing Arrays in C++ using STL (vectors and List)
Iterators in C++ STL
Implementing Arrays In java (Arrays, ArrayList, and Vectors)

Searching
To find a particular data we search through the collections of data like array. But how can find
those data in more efficient way.
Algorithms: Linear Search (traverse through every single data. Less time complexity friendly)
Binary Search (only applicable on sorted data traverse in efficient manner)
Ternary Search (Uses Divide and Conquer algorithms)
Binary Search Functions in C++ STL
Binary Search Using Built in methods in JAVA

Sorting
Sorting the data in given data structure either in ascending order or descending order.
Introduction to sorting
Sorting any sequence means to arrange the elements of that sequence according to some specific
criterion.
Types of sorting techniques: Insertion sort and Bubble sort
Quick Sort
Merge Sort
Counting Sort
 Heap Sort
Standard sort() function in C++ STL
Sorting using built in methods in java

Matrix
The 2-Dimensional array is called matrix. A matrix represents a collection of numbers arranged
in order of rows and columns. It is necessary to enclose the elements of a matrix in parentheses
or brackets.
What we learnt:
Matrix Implementation
Matrix Operations (Addition, Subtraction, Multiplication)
Matrix Rotation
2D Vector in C++
2D Arrays in java

Hashing
Hashing is a method of storing and retrieving data from a database efficiently. Hashing is the
solution that can performs extremely well compared to data structures like Array, Linked List,
Balanced BST in practice. With hashing we get O(1) search time on average (under reasonable
assumptions) and O(n) in worst case.
What We learnt:
Open Addressing (method for handling collisions)
Hashing in C++ using STL
Implementing Hashing in Java

Linked List
Linked Lists are linear or sequential data structures in which elements are stored at non-
contiguous memory location and are linked to each other using pointers.
Each element in a linked list contains of two parts:
Data
This part stores the data value of the node. That is the information to be stored at the current
node.
Next Pointer
This is the pointer variable or any other variable which stores the address of the next node in the
memory.
What we learnt:
Insertion in singly Linked list
Deletion in singly Linked list
Doubly Linked List
XOR Linked List
Circular Linked list

Stack
The Stack is a linear data structure which follows a particular order in which the operations are
performed. The order may be LIFO (Last in First Out) or FILO (First in Last Out).
What we Learnt:
Implementing Stack in C++ and Java using Built in class
Infix and Postfix Conversion Using stack
Evaluating Postfix expression using stack
Implementing two stacks using one Array

Queue
Like Stack data structure, Queue is also a linear data structure which follows a particular order in
which the operations are performed. The order is First in First Out (FIFO) which means that the
element which is inserted first in the queue will be the first one to be removed from the queue. A
good example of queue is any queue of consumers for a resource where the consumer that came
first is served first.
What we learnt:
Implementing Queue in C++ and Java Using Built in class.
Circular Linked List
Implementing Stack using Queue
Implementing Queue using stack

Deque
Deque or double ended queue is generalized version of Queue data structure that allows insert
and delete at both ends. Deque supports both stack and queue operations, it can be used as both.
What we learnt:
Array implementation of deque
Deque in C++ STL and java
ArrayDeque in java
Design a Data Structure with min and max operations
Maximums of all subarrays of size k

Tree
A Tree is a non-linear data structure where each node is connected to several nodes with the help
of pointers or references.
Binary Tree: A Tree is said to be a Binary Tree if all its nodes have at most 2 children. That is, all
its node can have either no child, 1 child or 2 child nodes.
What we learnt:
Binary Tree Traversals
Level Order Traversal of a Binary Tree
Insertion in a Binary Tree
Deletion in a Binary Tree
Finding LCA in Binary Tree
Threaded Binary Tree

Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:
he left subtree of a node contains only nodes with keys lesser than or equal to the node's key. The
right subtree of a node contains only nodes with keys greater than the node's key. The left and
right subtree each must also be a binary search tree. There must be no duplicate nodes.
What we learnt:
Deletion in Binary Search tree
Finding LCA in Binary Search Tree
Introduction to AVL Tree
Heap
A Heap is a Tree-based data structure, which satisfies the below properties: A Heap is a complete
tree (All levels are completely filled except possibly the last level and the last level has all keys
as left as possible).A Heap is either Min Heap or Max Heap. In a Min-Heap, the key at root must
be minimum among all keys present in the Binary Heap. The same property must be recursively
true for all nodes in the Tree. Max Heap is like MinHeap.
Binary Heap: A Binary Heap is a heap where each node can have at most two children.
What we learnt:
Insertion and deletion in heaps
Building heaps
Implementing Heaps using in built classes in C++ and Java

Graphs
A Graph is a data structure that consists of the following two components: A finite set of vertices
also called nodes. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered
because (u, v) is not the same as (v, u) in case of a directed graph(digraph). The pair of the form
(u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain
weight/value/cost.
Directed Graphs: The Directed graphs are such graphs in which edges are directed in a single
direction.
Undirected Graphs: Undirected graphs are such graphs in which the edges are directionless or in
other words bi-directional.
What we learnt:
Breadth first traversal of a graph
Depth first traversal of a graph
Detecting cycle in a graph
Dijkstra’s Algorithms for shortest path in a weight graph
Bellman-Ford Algorithms for shortest path
Number of strongly Connected Components in an undirected Graph
Minimum Spanning Tree Algorithm
Kosaraju’s Algorithms
Bridge in a Graph
Trie
The Trie data structure is an efficient information re-trie-val data structure. The Trie data
structure is used to efficiently search for a particular string key among a list of such keys. Using
the trie, the lookup operation can be performed in time complexity of O (key length).
What we learnt:
Insertion and Deletion in a Trie
Implementing Auto Complete Feature using Trie

Segment Trees
Segment Trees are Binary Tree which is used to store intervals or segments. That is each node in
a segment tree basically stores the segment of an array. Segment Trees are generally used in
problems where we need to solve queries on a range of elements in arrays.

Disjoint Set
A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned
into several disjoint (non-overlapping) subsets.
Operations performed on Disjoint Sets:
Union (A, B): This operation tells to merge the sets containing elements A and B respectively by
performing a Union operation on the sets.
Find (A): This operation tells to find the subset to which the element A belongs.
What we learnt:
Union by Rank and Path Compression
Kruskal’s Minimum Spanning Tree Algorithms
Advance Algorithms

Greedy
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the
next piece that offers the most obvious and immediate benefit. So, the problems where choosing
locally optimal also leads to the global optimal solution are best fit for Greedy.
What we learnt:
Job Sequencing problem

Backtracking
Backtracking is an algorithmic technique for solving problems recursively by trying to build a
solution incrementally, one piece at a time, removing those solutions that fail to satisfy the
constraints of the problem at any point of time.
Some of the problems that can be solved using backtracking are:
Rat in a maze
N Queen Problem
Sudoku Problem

Dynamic Programing
Dynamic Programming is an algorithmic approach to solve some complex problems easily and
save time and number of comparisons by storing the results of past computations. The basic idea
of dynamic programming is to store the results of previous calculation and reuse it in future
instead of recalculating them.
What we learnt:
Properties of a dynamic programming problem
Overlapping Subproblems Property
Optimal Substructure Property
Conclusion:

Algorithm is vast topic and it is all about making a program more efficient. These Algorithms are
the ones that make our experience smother with the software. Take google search engine for
example how fast it provides the best search result in few seconds of times. That is the power of
algorithms. That is why many companies ask questions related to algorithms during interview.
Through this Course I have Learnt a vast number of interesting topics like Trees, Graphs, Linked
List and many other more. Their implementation in practical problems and understanding their
base concepts.
While working in IT sector we need to solve the problems and make programs write tons of code
which will help us with the given problem and to write a program one need to make different
algorithms. Many algorithms combine to make a program. Now, algorithm are writen in some
lenguages but they are not dependen ton them, one need to make a plan and algo first then write
it into any language wether i tis C++ or JAVA or C or any other programing language. Algorithm
is based on data structure and its implementation and working. So, basiclly one need to have a
good grip on DSA to work in programing sector.
References:
https://www.geeksforgeeks.org/