Table of Contents
S. No. Title Page
5 -.6%0$)*7% 5
8 !%+&*0*9:.;$.'$9<%$19/,%;9 8
= #+3;.>&%,7%?%;9 =
@ A0*:;:;7$-%09:':+*9:.;$'0.?$B07*;:C*9:.; @
D A*E&%$.'$-.;9%;91 D
F G:19$.'$*EE0%6:*9:.; F
H I;90.,/+9:.; H
J A%+<;.&.7K$G%*0;9 J
L M%*1.;$'.0$+<..1:;7$!"# 5J
5N G%*0;:;7$B/9+.?% 5L
55 "+0%%;1$.'$)0.O%+9$,.;%$,/0:;7$P/;%(P/&K 88
58 Q:E&:.70*R<K 8D
ABBREVIATION
DSA: Data Structures and Algorithms
Introduction
The course name DSA stands for “Data Structures and
Algorithms” and Self-paced means, one can join the course
anytime. All of the content will be available once one gets
enrolled. One can finish it at his own decided speed.
What is Data Structure? Data Structure is a way of
collecting and organizing data in such a way that we can
perform operations on these data in an effective way. Data
Structures is about rendering data elements in terms of
some relationship, for better organization and storage. For
example, we have some data which has, player's name
"Virat" and age 26. Here "Virat" is of String data type and
26 is of integer data type.
What is Algorithm? An algorithm is a finite set of
instructions or logic, written in order, to accomplish a
certain predefined task. Algorithm is not the complete code
or program, it is just the core logic(solution) of a problem,
which can be expressed either as an informal high-level
description as pseudocode or using a flowchart
This course is a complete package that helped me learn
Data Structures and Algorithms from basic to an advanced
level. The course curriculum has been divided into 8 weeks
where one can practice questions & attempt the assessment
tests according to his own pace. The course offers me a
wealth of programming challenges that will help me to
prepare for interviews with top-notch companies like
Microsoft, Amazon, Adobe etc.
Technology Learnt
> Learn Data Structures and Algorithms from basic to an
advanced level like:
> Learn Topic-wise implementation of different Data
Structures & Algorithms as
follows
• Analysis of Algorithm
o In this I learned about background analysis through a Program and its
functions.
• Order of Growth
o A mathematical explanation of the growth analysis through limits and
functions.
o A direct way of calculating the order of growth
• Asymptotic Notations
o Best, Average and Worst-case explanation through a program.
• Big O Notation
o Graphical and mathematical explanation. o Calculation
o Applications at Linear Search
• Omega Notation
o Graphical and mathematical explanation. o Calculation.
• Theta Notation
o Graphical and mathematical explanation. o Calculation.
• Analysis of common loops
o Single, multiple and nested loops
• Analysis of Recursion
o Various calculations through Recursion Tree method
• Space Complexity
o Basic Programs
o Auxiliary Space
o Space Analysis of Recursion
o Space Analysis of Fibonacci number
MATHEMATICS
• Finding the number of digits in a number.
• Arithmetic and Geometric Progressions.
• Quadratic Equations.
• Mean and Median.
• Prime Numbers.
• LCM and HCF
• Factorials
• Permutations and Combinations
• Modular Arithmetic
BITMAGIC
• Bitwise Operators in C++
o Operation of AND, OR, XOR operators
o Operation of Left Shift, Right Shift and Bitwise Not
• Bitwise Operators in Java
o Operation of AND, OR
o Operation of Bitwise Not, Left Shift
o Operation of Right Shift and unsigned Right Shift
• Problem (With Video Solutions): Check Kth bit is set or not
• o Method 1: Using the left Shift.
o Method 2: Using the right shift.
RECURSION
Introduction to Recursion Applications of Recursion Writing base cases
in Recursion Factorial
N-th Fibonacci number
ARRAYS
• Introduction and Advantages
• Types of Arrays
o Fixed-sized array
o Dynamic-sized array • Operations on Arrays
o Searching
o Insertions
o Deletion
o Arrays vs other DS
o Reversing - Explanation with complexity
SEARCHING
• Binary Search Iterative and Recursive
• Binary Search and various associated problems
• Two Pointer Approach Problems
SORTING
• Implementation of C++ STL sort () function in Arrays and Vectors o
Time Complexities
• Sorting in Java
• Arrays.sort() in Java
• Collection.sort() in Java
• Stability in Sorting Algorithms
o Examples of Stable and Unstable Algos
• Insertion Sort
• Merge Sort
• Quick Sort
o Using Lomuto and Hoare
o Time and Space analysis
o Choice of Pivot and Worst case
• Overview of Sorting Algorithms MATRIX
• Introduction to Matrix in C++ and Java
• Multidimensional Matrix
• Pass Matrix as Argument
• Printing matrix in a snake pattern
• Transposing a matrix
• Rotating a Matrix
• Check if the element is present in a row and column-wise sorted
matrix.
• Boundary Traversal
• Spiral Traversal
• Matrix Multiplication
• Search in row-wise and column-wise Sorted Matrix
HASHING
Introduction and Time complexity analysis
Application of Hashing
Discussion on Direct Address Table
Working and examples on various Hash Functions Introduction and Various
techniques on Collision Handling Chaining and its implementation
Open Addressing and its Implementation Chaining V/S Open Addressing
Double Hashing
C++
Unordered Set Unordered Map Java
HashSet HashMap
STRINGS
• Discussion of String DS
• Strings in CPP
• Strings in Java
• Rabin Karp Algorithm
• KMP Algorith
LINKED LIST
A linked list is a linear data structure, in which the elements are not stored at
contiguous memory locations. The elements in a linked list are linked using
pointers as shown in the below image:
• Introduction
o Implementation in CPP
o Implementation in Java
o Comparison with Array DS
• Doubly Linked List
• Circular Linked List
• Loop Problems
o Detecting Loops
o Detecting loops using Floyd cycle detection
o Detecting and Removing Loops in Linked List
STACK
• Understanding the Stack data structure
• Applications of Stack
• Implementation of Stack in Array and Linked List
QUEUE
o In C++
o In Java
Introduction and Application
Implementation of the queue using array and LinkedList
In C++ STL
In Java
Stack using queue
DEQUE
• Introduction and Application
• Implementation
o In C++ STL
o In Java
• Problems (With Video Solutions)
o Maximums of all subarrays of size k
o ArrayDeque in Java
o Design a DS with min max operations
TREE
A tree data structure is a non-linear data structure because it does not store in
a sequential manner. It is a hierarchical structure as elements in a Tree are
arranged in multiple levels. In the Tree data structure, the topmost node is
known as a root node. Each node contains some data, and data can be of any
type.
Basic Terminologies In Tree Data Structure:
Parent Node: The node which is a predecessor of a node is called the parent
node of that node. {2} is the parent node of {6, 7}.
Child Node: The node which is the immediate successor of a node is called the
child node of that node. Examples: {6, 7} are the child nodes of {2}.
Root Node: The topmost node of a tree or the node which does not have any
parent node is called the root node. {1} is the root node of the tree. A non-
empty tree must contain exactly one root node and exactly one path from the
root to all other nodes of the tree.
Leaf Node or External Node: The nodes which do not have any child nodes are
called leaf nodes. {6, 14, 8, 9, 15, 16, 4, 11, 12, 17, 18, 19} are the leaf nodes
of the tree.
Ancestor of a Node: Any predecessor nodes on the path of the root to that node
are called Ancestors of that node. {1, 2} are the ancestor nodes of the node
{7}
Descendant: Any successor node on the path from the leaf node to that node.
{7, 14} are the descendants of the node. {2}.
Sibling: Children of the same parent node are called siblings. {8, 9, 10} are
called siblings.
Level of a node: The count of edges on the path from the root node to that
node. The root node has level 0.
Internal node: A node with at least one child is called Internal Node.
Neighbour of a Node: Parent or child nodes of that node are called neighbors of
that node.
Subtree: Any node of the tree along with its descendant.
Properties of a Tree:
Number of edges: An edge can be defined as the connection between two
nodes. If a tree has N nodes then it will have (N-1) edges. There is only one
path from each node to any other node of the tree.
Depth of a node: The depth of a node is defined as the length of the path from
the root to that node. Each edge adds 1 unit of length to the path. So, it can
also be defined as the number of edges in the path from the root of the tree to
the node.
Height of a node: The height of a node can be defined as the length of the
longest path from the node to a leaf node of the tree.
Height of the Tree: The height of a tree is the length of the longest path from
the root of the tree to a leaf node of the tree.
Degree of a Node: The total count of subtrees attached to that node is called
the degree of the node. The degree of a leaf node must be 0. The degree of a
tree is the maximum degree of a node among all the nodes in the tree.
Some more properties are:
Traversing in a tree is done by depth first search and breadth first search
algorithm.
It has no loop and no circuit
It has no self-loop
Its hierarchical model.
Introduction
o Tree
o Application
o Binary Tree
o Tree Traversal
• Implementation of:
o Inorder Traversal
o Preorder Traversal
o Postorder Traversal
o Level Order Traversal (Line by Line) o Tree Traversal in Spiral Form
BINARY SEARCH TREE
• Background, Introduction and Application
• Implementation of Search in BST
• Insertion in BST
• Deletion in BST
• Floor in BST
• Self-Balancing BST
• AVL Tree
HEAP
• Introduction & Implementation
• Binary Heap
o Insertion
o Heapify and Extract
o Decrease Key, Delete and Build Heap
• Heap Sort
• Priority Queue in C++
• PriorityQueue in Java
• GRAPH
Graphs in data structures are non-linear data structures made up of a finite
number of nodes or vertices and the edges that connect them. Graphs in data
structures are used to address real-world problems in which it represents the
problem area as a network like telephone networks, circuit networks, and social
networks.
Vertices: Vertices are the fundamental units of the graph. Sometimes,
vertices are also known as vertex or nodes. Every node/vertex can be labeled
or unlabelled.
Edges: Edges are drawn or used to connect two nodes of the graph. It
can be ordered pair of nodes in a directed graph. Edges can connect any two
nodes in any possible way. There are no rules. Sometimes, edges are also
known as arcs. Every edge can be labeled/unlabelled.
• With advancement and innovation in technology, programming is
becoming a highly in-demand skill for Software Developers. Everything
you see around yourself from Smart TVs, ACs, Lights, Traffic Signals uses
some kind of programming for executing user commands.
•
“In order to be irreplaceable, one must always be efficient.”
•
Data Structures and Algorithms are the identity of a good Software
Developer. The interviews for technical roles in some of the tech giants
like Google, Facebook, Amazon, Flipkart is more focused on measuring
the knowledge of Data Structures and Algorithms of the candidates. The
main reason behind this is Data Structures and Algorithms improves the
problem-solving ability of a candidate to a great extent.
• This course has video lectures of all the topics from which one can easily
learn. I prefer learning from video rather than books and notes. I know
books and notes and thesis have their own significance but still video
lecture or face to face lectures make it easy to understand faster as we
are involved Practically.
• It has 200+ algorithmic coding problems with video explained solutions.
• It has track based learning and weekly assessment to test my skills.
• It was a great opportunity for me to invest my time in learning instead of
wasting it here and there during my summer break in this Covid-19
pandemic.
• This was a lifetime accessible course which I can use to learn even after
my training whenever I want to revise.
Conclusion
This course covered the basics of data structures. With
this we have only scratched the surface. Although we
have built a good foundation to move ahead.
Data Structures is not just limited to Stack, Queues, and
Linked Lists but is quite a vast area. There are many
more data structures which include Maps, Hash Tables,
Graphs, Trees, etc. Each data structure has its own
advantages and disadvantages and must be used
according to the needs of the application. A computer
science student at least know the basic data structures
along with the operations associated with them.
Learning Bibliography
•Google
•GeeksForGeeks website
• GeeksForGeeks DSA self-paced Course
