DSA Self-placed

GeeksForGeeks
A training report
Submitted in partial fulfillment of the requirements for the
award of degree of
Bachelor of Technology
(Computer Science and Engineering)
Submitted to
LOVELY PROFESSIONAL UNIVERSITY
PHAGWARA, PUNJAB

From 20/05/24 to 3/08/24

SUBMITTED BY
Name : Rishabh Vishwakarma
Registration No : 12219457
Programme Name : Btech. CSE

1|Page
 DECLARATION

I hereby declare that I have completed my six weeks summer training at

Geeks for Geeks platform from May 20,2024 to August 3,2024 under the
guidance of MR. Sandeep Jain. I declare that I have worked with full
dedication during there 8 weeks of training and my learning outcomes
fulfill the requirements of training for the award of degree of B.tech.
CSE , Lovely Proffesional University, Phagwara.

Name – Rishabh Vishwakarma

Reg No. – 12219457

2|Page
 ACKNOWLEDGEMENT

I would like to express my gratitude towards my University as well as

Geeks for Geeks for providing me the golden opportunity to do this
wonderful summer training regarding DSA, which also helped me in
doing a lot of homework and learning. As a result, I came to know about
so many new things. So, I am really thank full to them.

Moreover I would like to thank my friends who helped me a lot

whenever I got stuck in some problem related to my course. I am really
thankfull to have such a good support of them as they always have my
back whenever I need.

Also,I would like to mention the support system and consideration of my

parents who have always been there in my life to make me choose right
thing and oppose the wrong. Without them I could never had learned and
became a person who I am now.

I have taken efforts in this project. However, it would not have been
possible without the kind support and help of many individuals and
organizations. I would like to extend my sincere thanks to all of them.

3|Page
 SUMMER Training Certificate

Link for verification –

https://media.geeksforgeeks.org/courses/certificates/3e6f349274425a
a96d2a8eca3b13fc75.pdf

Table of Contents

S. No. Title Page no.

4|Page
1 Cover Page 1
2 Declaration of the student 2
3 Acknowledgement 3
4 Training Certification from organization 4
5 Table of Contents 5
6 List of abbreviation 6
7 Introduction 7
8 Technology learnt 8 – 32
9 Reason for choosing the Course 33
10 Learning Outcome 34-35
11 Bibliography 36
12 Project 37 - 40

Abbreviation

•DSA: Data Structures and Algorithms.

5|Page
 INTRODUCTION

6|Page
  The course name DSA stands for “Data Structures and Algorithms”
and Self-placed 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.
 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.

7|Page
  In today's fast expanding digital landscape, data structures and
algorithms (DSA) play an increasingly important role. These
essential building elements of computer science allow for efficient
data manipulation and problem solving, creating the foundation of
all software systems. As businesses and sectors around the world
adopt more complex and data-driven approaches, the demand for
DSA experts has increased substantially. Understanding DSA is
critical for designing cutting-edge applications, optimizing system
performance, and solving complicated computational issues.

 Given the critical nature of DSA, there is a rising emphasis on

education and training in this area. Universities, online platforms, and
IT firms have all acknowledged the importance of providing both new
and experienced developers with strong DSA expertise. Among the
many available learning tools, the GeeksforGeeks DSA Self-Placed
Course has emerged as a highly recognized program, distinguished by
its comprehensive curriculum and adaptable learning style. This report
goes into the numerous aspects of this course, with the goal of
providing a comprehensive review of its efficiency in conveying DSA
knowledge.

8|Page
 TECHNOLOGY LEARNT
 Learn Data Structures and Algorithms from basic to an advanced
level
 Learn Topic-wise implementation of different Data Structures &
Algorithms as follows-
 Analysis of Algorithm - In this I learned about background
analysis through a Program and its functions.
 Order of Growth - A mathematical explanation of the growth
analysis through limits and functions. A direct way of calculating
the order of growth.
 Asymptotic Notations - Best, Average and Worst-case explanation
through a program. Types of asymptotic notations- Big O
Notation, Omega Notation, Theta Notation,
 Loops - Single, multiple and nested loops
 Recursion- Various calculations through Recursion Tree method
 Complexicity – Space complexicity,Time Complexicity
 Mathematics- Mathematics is a cornerstone of computer science,
essential for problem-solving and understanding algorithms. The
Mathematics section of the GeeksforGeeks Self-Placed Course
provides learners with critical mathematical tools necessary for
success in programming and algorithm design.
Key topics covered include:
a) Finding the number of digits in a number

9|Page
 b) Arithmetic and Geometric Progressions.
c) Quadratic Equations.
d) Mean and Median
e) LCM and HCF
f) Permutations and Combinations
g) Modular Arithmetic

This section blends theoretical explanations with practical

applications, helping learners build a strong mathematical foundation
for more advanced topics like Data Structures and Algorithms.

 BIT MAGIC- Bit manipulation, often referred to as "Bit Magic,"

is a powerful technique in computer science that enables efficient
and optimized solutions to a variety of problems. The Bit Magic
section of the GeeksforGeeks Self-Placed Course is designed to
provide learners with a deep understanding of how to work with
bits, a fundamental aspect of low-level programming and
optimization.
Key topics covered include:
a) Bitwise Operators
b) Binary Representation
c) Check for Kth bit
d) Count set bits
e) Power
f) Power Set
g) Odd Occurring

10 | P a g e
 The Bit Magic section combines theoretical insights with
practical coding exercises, helping learners develop a solid grasp
of bitwise operations and their applications in real-world
programming scenarios. This foundational knowledge is
invaluable for tackling complex problems efficiently, making it
an essential skill for any programmer.
 Arrays- Arrays are one of the most fundamental and widely used
data structures in computer science. They provide a way to store
multiple elements of the same type in a contiguous block of
memory, enabling efficient access and manipulation. The Arrays
section of the GeeksforGeeks Self-Placed Course is designed to
help learners master this essential data structure and its various
applications.

Key topics covered include:

a) Array and types of array

b) Operations on array

11 | P a g e
 c) Rotation of an array
d) Some problems on array
The Arrays section offers a blend of theoretical explanations and
hands-on coding practice, helping learners develop a strong
understanding of arrays and their role in computer science.
Mastery of arrays is crucial for success in more advanced topics
such as Data Structures, Algorithms, and competitive
programming.

 Searching –
Searching is a fundamental operation in computer science, essential
for finding specific elements within data structures like arrays, linked
lists, and trees. The Searching section of the GeeksforGeeks Self-
Placed Course is designed to equip learners with the knowledge and
techniques needed to efficiently locate elements in various data
structures, which is critical for solving a wide range of computational
problems.
Key topics covered include:
Linear Search: Understanding the simplest search technique, which
involves checking each element sequentially. Though basic, linear
search is effective for small or unsorted data sets.
Binary Search: Learning the efficient divide-and-conquer approach for
searching in sorted arrays. Binary search dramatically reduces the
number of comparisons needed, making it a crucial technique for
optimizing search operations.

12 | P a g e
 Ternary and Exponential Search: Exploring advanced search methods
that are variations of binary search, tailored for specific types of data or
problem constraints.

Search in Rotated and Sorted Arrays: Techniques for handling more

complex scenarios, such as finding elements in rotated or partially
sorted arrays, which are common in many algorithmic challenges.
Searching in Strings: Applying search algorithms to strings, including
pattern matching techniques like the Knuth-Morris-Pratt (KMP)
algorithm, which are vital in text processing and computational
linguistics.
Search Optimization: Understanding the trade-offs and optimizations
available when choosing a search strategy, particularly in relation to
time complexity, space complexity, and the nature of the dataset.
Applications in Algorithms: Implementing search techniques in various
algorithmic contexts, such as in dynamic programming, graph traversal,
and real-time systems, where efficient searching is critical.

The Searching section combines theoretical concepts with practical

coding exercises, ensuring learners not only understand how these
algorithms work but also how to apply them effectively in real-world
scenarios. Mastery of searching algorithms is essential for success in
more advanced topics, such as sorting, data structures, and competitive
programming.

13 | P a g e
 Topics Covered-
a) Binary Search Iterative and Recursive
b) Binary Search and various associated problems
c) Two Pointer Approach Problems

 Sorting
Sorting is a fundamental operation in computer science that involves
arranging data in a particular order, typically ascending or descending.
Efficient sorting is critical for optimizing various algorithms and
improving the performance of applications. The Sorting section of the
GeeksforGeeks Self-Placed Course is designed to provide learners
with a thorough understanding of different sorting algorithms and
their practical applications.

14 | P a g e
 Key topics covered include:
Bubble Sort: A simple comparison-based algorithm that repeatedly
steps through the list, compares adjacent elements, and swaps them if
they are in the wrong order. Though not the most efficient, it's an
excellent introduction to the concept of sorting.
Selection Sort: An in-place comparison sorting algorithm that divides
the list into a sorted and unsorted region, repeatedly selecting the
smallest element from the unsorted region and swapping it with the
first unsorted element.
Insertion Sort: A straightforward algorithm that builds the final sorted
array one item at a time. It's particularly efficient for small datasets or
nearly sorted data.
Merge Sort: A highly efficient, stable, comparison-based algorithm
that uses the divide-and-conquer strategy to split the list into smaller
sublists, sort them, and then merge them back together.
Quick Sort: An efficient, in-place, divide-and-conquer algorithm that
selects a 'pivot' element and partitions the array around the pivot. It’s
widely used due to its average-case efficiency.

15 | P a g e
 Heap Sort: A comparison-based algorithm that uses a binary heap data
structure to sort elements. It is particularly effective in cases where
memory management is critical.
Radix Sort: A non-comparison-based algorithm that sorts numbers by
processing individual digits. It’s particularly useful for sorting large
datasets with fixed-size keys.

The Sorting section covers both the theory behind these algorithms
and their practical implementations. By working through these sorting
techniques, learners gain insight into how different algorithms
perform under various conditions, enabling them to choose the most
appropriate sorting method for specific tasks. Mastery of sorting
algorithms is essential for enhancing the efficiency of data processing
and is a critical skill for anyone involved in software development or
competitive programming.
Problemes Covered -
a) Implementation of C++ STL sort () function in Arrays and Vectors
b) Stability in Sorting Algorithms
c) Types of Sorting Algorithms(Insertion, Merge and quick sort)
d) Overview of Sorting Algorithms
 Matrix
Matrices are a crucial data structure in computer science, used for
representing and manipulating two-dimensional data. The Matrix
section of the GeeksforGeeks Self-Placed Course introduces learners
to essential matrix operations and their applications.
Key topics covered include:

16 | P a g e
 Basic Operations: Understanding matrix addition, subtraction, and
multiplication.
Transpose and Determinant: Techniques for calculating the transpose of
a matrix and finding its determinant.
Inversion: Methods for inverting matrices, critical for solving linear
equations.
Special Matrices: Exploring identity, diagonal, and symmetric matrices,
which have unique properties and applications.
Matrix Applications: Practical uses in computer graphics, linear algebra,
and algorithms like dynamic programming.
This section equips learners with the knowledge needed to handle
matrix-related problems efficiently, which is vital in areas such as data
processing, scientific computing, and algorithm design.

Problemes Covered

17 | P a g e
 a) Introduction to Matrix in C++ and Java
b) Multidimensional Matrix
c) Pass Matrix as Argument
d) Printing matrix in a snake pattern
e) Transposing a matrix
f) Rotating a Matrix
g) Check if the element is present in a row and column-wise sorted matrix.
h) Boundary Traversal
i) Spiral Traversal
j) Matrix Multiplication
k) Search in row-wise and column-wise Sorted Matrix
 Hashing - Hashing is a powerful technique used in computer science
for efficient data retrieval and storage. The Hashing section of the
GeeksforGeeks Self-Placed Course provides a comprehensive
overview of hashing concepts and their applications.
Key topics covered include:
Hash Functions: Understanding how hash functions map data to fixed-
size values, ensuring efficient access and retrieval.
Collision Resolution: Techniques such as chaining and open
addressing for handling situations where multiple inputs produce the
same hash value.
Hash Tables: Implementation of hash tables for fast data insertion,
deletion, and lookup operations.
Applications: Using hashing in real-world scenarios like database
indexing, caches, and cryptographic algorithms.

18 | P a g e
 This section helps learners grasp the fundamentals of hashing and
apply them to optimize data management and improve performance in
various computational tasks.

Topics Covered -
a). Introduction and Time complexity analysis
b) Application of Hashing
c) Discussion on Direct Address Table
d) Working and examples on various Hash Functions
e) Introduction and Various techniques on Collision Handling
f) Chaining and its implementation
g) Open Addressing and its Implementation.
h) Chaining V/S Open Addressing
i) Double Hashing
 String -
Strings are sequences of characters used for text manipulation and
processing. The Strings section covers:
Basic Operations: Concatenation, substring extraction, and
comparison.

19 | P a g e
 Searching and Matching: Techniques for finding patterns and
occurrences within strings.
String Manipulation: Methods for modifying and formatting strings.
This section equips learners with essential skills for handling and
processing textual data efficiently.
Topic Covered -
a)Discussion of String DS
b) Strings in CPP
c) Strings in Java
d) Rabin Karp Algorithm
e) KMP Algorithm
 Linked List - Linked lists are a fundamental data structure used
to store collections of elements. The Linked Lists section
covers:
Basic Operations: Insertion, deletion, and traversal of nodes.
Types of Linked Lists: Single, doubly, and circular linked lists.
Applications: Use cases in dynamic data management and algorithm
implementation.
This section provides learners with the knowledge to effectively
manage and manipulate linked lists for various computational tasks.

20 | P a g e
 Topic Covered -
a) Introduction
b) Implementation
c) Comparison with Array DS
d) Doubly Linked List
e) Circular Linked List
f) Loop Problems
g) Detecting Loops
 Stack - Stacks are a linear data structure that follows the Last In, First
Out (LIFO) principle. The Stacks section covers:
Basic Operations: Push, pop, and peek operations.
Implementation: Stack implementation using arrays and linked lists.
Applications: Usage in function calls, expression evaluation, and
backtracking.
This section equips learners with the tools to utilize stacks for
managing data and solving problems efficiently.

21 | P a g e
 Topic Covered -
a) Understanding the Stack data structure
b) Applications of Stack
c) Implementation of Stack in Array and Linked List
 Queue - Queues are a linear data structure that follows the First In,
First Out (FIFO) principle. The Queues section covers:
Basic Operations: Enqueue, dequeue, and front operations.
Implementation: Queue implementation using arrays and linked lists.
Applications: Use in scheduling, buffering, and resource management.
This section provides learners with essential techniques for managing
data in a sequential and orderly manner.

22 | P a g e
 Topic Covered -
a) Introduction and Application
b) Implementation of the queue using array and LinkedList.
 Dequeue - Deques, or double-ended queues, are a data structure that
allows insertion and deletion of elements from both ends. The Deques
section covers:
Basic Operations: Insert and remove elements from both the front and
rear.
Implementation: Deque implementation using arrays and linked lists.
Applications: Use cases in scheduling, algorithm optimization, and
maintaining order in complex data processing.
This section helps learners understand how to efficiently manage and
access data from both ends of a sequence.
Topic Covered -
a) Introduction and Application
b) Implementation

23 | P a g e
 c) Problems (With Video Solutions)
d) Maximums of all subarrays of size k , ArrayDeque in Java,
Design a DS with min max operations.

 Tree - Trees are hierarchical data structures used to represent

relationships and organize data efficiently. The Trees section covers:
Basic Concepts: Nodes, edges, root, leaves, and levels.
Types of Trees: Binary trees, binary search trees, AVL trees, and
heaps.
Traversal Methods: Inorder, preorder, and postorder traversal
techniques.
This section equips learners with fundamental knowledge to
implement and manipulate various tree structures for effective data
organization and retrieval.

Topic Covered -
a) Introduction
b) Implementation

24 | P a g e
  BST(Binary Search Tree) - Binary Search Trees (BST) are a
specialized type of binary tree where each node has at most two
children, and the left child is less than the parent node, while the right
child is greater. The BST section covers:
Basic Operations: Insertion, deletion, and search.
Traversal Methods: Inorder, preorder, and postorder traversals tailored
for BSTs.
Applications: Use in efficient data sorting, searching, and maintaining
a dynamically ordered dataset.
This section provides learners with the skills to manage and optimize
data using BSTs effectively.
Topic Covered -
a) Background, Introduction and Application
b) Implementation of Search in BST
c) Insertion in BST
d) Deletion in BST
e) Floor in BST
f) Self Balancing BST
g) AVL Tree
 Heap - Heaps are a type of binary tree used to efficiently manage and
retrieve the maximum or minimum element. The Heaps section
covers:
Basic Types: Max-Heap and Min-Heap, where the parent node is
either greater than (Max-Heap) or less than (Min-Heap) its children.
Heap Operations: Insertion, deletion, and heapify operations.

25 | P a g e
 Applications: Use in implementing priority queues, heap sort, and
efficient algorithms for dynamic data management.
This section equips learners with the skills to utilize heaps for
optimizing data retrieval and manipulation tasks.

Topic Covered -
a) Introduction & Implementation
b) Binary Heap-
Insertion
Heapify and Extract o Decrease Key, Delete and Build Heap
c) Heap Sort
d) Priority Queue in C++
e) PriorityQueue in Java

26 | P a g e
  Graph - Graphs are versatile data structures used to represent
relationships between entities. The Graphs section covers:
Basic Concepts: Nodes (vertices), edges, and types of graphs
(directed, undirected, weighted, and unweighted).
Traversal Algorithms: Depth-First Search (DFS) and Breadth-First
Search (BFS).
Graph Algorithms: Shortest path algorithms (Dijkstra's, Bellman-
Ford) and Minimum Spanning Tree (MST) algorithms (Kruskal's,
Prim's).
This section provides learners with the foundational knowledge to
model and solve problems involving complex relationships and
networks.

Topic Covered -
a) Introduction to Graph
b) Graph Representation
c) Breadth-First Search
e) Depth First Search
f) Shortest Path in Directed Acyclic Graph
g) Prim's Algorithm/Minimum Spanning Tree
h) Dijkstra's Shortest Path Algorithm

27 | P a g e
 i) Bellman-Ford Shortest Path Algorithm
j) Kosaraju's Algorithm
k) Articulation Point
l) Bridges in Graph
m) Tarjan’s Algorithm

 Greedy - Greedy algorithms are a paradigm for solving optimization

problems by making a series of choices, each of which looks best at
the moment. The Greedy Algorithms section covers:
Basic Concept: Making locally optimal choices with the hope of
finding a global optimum.
Key Techniques: Understanding how to apply greedy strategies to
problems such as interval scheduling, coin change, and Huffman
coding.
Algorithm Design: Developing and analyzing greedy algorithms for
efficiency and correctness.
This section helps learners master the greedy approach for solving
problems where local optimization leads to global solutions.
Topic Covered -
a)Introduction
b) Activity Selection Problem
c) Fractional Knapsack
d) Job Sequencing Problem
 Backtracking - Backtracking is a systematic method for solving
problems by exploring possible solutions and reverting changes when
a solution path fails. The Backtracking section covers:

28 | P a g e
 Basic Concept: Incrementally building candidates for solutions and
abandoning them if they fail to meet the problem's constraints.
Key Techniques: Implementing algorithms for problems like N-
Queens, Sudoku, and permutation generation.
Problem Solving: Using backtracking to explore all possible solutions
and find valid or optimal solutions.
This section equips learners with the skills to approach and solve
complex problems that require exploring multiple possibilities and
constraints.
Topics covered -
a) Concepts of Backtracking
b) Rat In a Maze
c) N Queen Problem
 Dynamic Programming - Dynamic Programming (DP) is a
technique for solving problems by breaking them down into simpler
subproblems and storing their solutions to avoid redundant work. The
Dynamic Programming section covers:
Basic Concept: Solving complex problems by dividing them into
overlapping subproblems and using previously computed solutions.
Key Techniques: Understanding memoization and tabulation methods
for efficient problem solving.
Common Problems: Applying DP to classic problems such as the
Knapsack problem, Longest Common Subsequence (LCS), and
Fibonacci sequence.
This section provides learners with the tools to optimize solutions for
problems with optimal substructure and overlapping subproblems.
Topic Covered -

29 | P a g e
 a) Introduction
b) Dynamic Programming
1)Memoization
2)Tabulation
 Trie - Tries, or prefix trees, are specialized tree-like data structures
used for efficient storage and retrieval of strings. The Tries section
covers:
Basic Concept: A tree where each node represents a character of a
string, enabling fast prefix-based searches and insertions.
Key Operations: Insertion, deletion, and search for strings and
prefixes.
Applications: Useful in tasks such as autocomplete, spell checking,
and dictionary implementations.
This section equips learners with the skills to handle string-related
operations efficiently and manage large sets of strings.
Topic Covered -
a) Introduction-
1)Representation
2) Search
3)Insert
4) Delete
b)Count Distinct Rows in a Binary Matrix

 Segment and Binary Indexed Trees – Segment Trees and Binary

Indexed Trees (BIT), or Fenwick Trees, are advanced data structures
designed for efficient range queries and updates.
Segment Trees:
Basic Concept: A binary tree used to store intervals or segments,
allowing efficient querying and updating of range-based information.

30 | P a g e
 Key Operations: Range queries, point updates, and constructing the
segment tree.
Applications: Useful for problems involving range sums,
minimum/maximum queries, and dynamic data modifications.
Binary Indexed Trees (BIT):
Basic Concept: A tree-like data structure that provides efficient
methods for cumulative frequency tables and prefix sum queries.
Key Operations: Point updates, prefix sum queries, and building the
BIT.
Applications: Ideal for problems requiring fast updates and queries on
prefix sums, such as cumulative frequency counts.
This section provides learners with techniques to efficiently manage
and query data over ranges, critical for handling complex data
processing tasks.
Topic Covered -
a) Introduction
b) Construction
c) Range Query
d) Update Query
 Disjoint Set - Disjoint Set, also known as Union-Find, is a data
structure used to manage and merge disjoint sets efficiently. The
Disjoint Set section covers:
Basic Concept: A structure that keeps track of a partition of a set into
disjoint subsets, supporting union and find operations.
Key Operations:
Union: Merging two subsets into a single subset.

31 | P a g e
 Find: Determining the representative or root of the subset containing a
particular element.
Optimizations: Path compression and union by rank/size to improve
efficiency.
Applications: Widely used in algorithms for network connectivity,
Kruskal's Minimum Spanning Tree algorithm, and equivalence class
problems.
This section helps learners manage and efficiently query connected
components in various computational problems.
Topic Covered -
a) Introduction
b) Find and Union Operations
c) Union by Rank
d) Path Compression
e) Kruskal's Algorithm

32 | P a g e
 Reason For Choosing This Course

 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.
 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 explaind solutions.
 It has track based learning and weekly assesment 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.
 This was a life time accessable course which I can use to learn even after my
training whenever I want to revise.

33 | P a g e
 LEARNING OUTCOMES

1. Fundamental Understanding of Data Structures: Understand the core

concepts and applications of fundamental data structures including arrays,
linked lists, stacks, queues, hash tables, trees, and graphs. Differentiate between
various data structures and choose the appropriate one based on problem
requirements.
2. Algorithm Design and Analysis: Grasp the principles of algorithm design,
including recursion, divide and conquer, dynamic programming, greedy
algorithms, and backtracking. Analyze the time and space complexity of
algorithms to evaluate their efficiency.
3. Problem-Solving Skills: Apply data structures and algorithms to solve a
variety of coding problems effectively. Develop the ability to break down
complex problems into manageable sub-problems.
4. Practical Coding Experience: Gain hands-on experience by implementing
data structures and algorithms in code. Enhance coding proficiency in
languages such as C++, Java, or Python.
5. Advanced Data Structures: Explore advanced data structures like segment
trees, Fenwick trees, tries, AVL trees, and red-black trees. Understand their
applications and performance benefits in solving complex problems.
6. Algorithmic Techniques for Optimization: Learn and apply advanced
algorithmic techniques for optimization problems. Implement algorithms to
handle real-world scenarios requiring optimization and efficient resource
management.
7. Graph Algorithms: Master graph algorithms including Depth-First Search
(DFS), Breadth-First Search (BFS), Dijkstra’s Algorithm, Floyd-Warshall

34 | P a g e
 Algorithm, and Kruskal’s Algorithm. Understand the application of graph
algorithms in network problems, pathfinding, and connectivity analysis.
8. Competitive Programming Preparation: Prepare for competitive
programming contests by solving a wide range of problems from easy to
advanced levels. Develop strategies for efficient problem-solving under time
constraints.
9. Coding Interview Readiness: Get ready for coding interviews by practicing
commonly asked interview questions. Learn to approach and solve problems in
a structured and efficient manner during interviews.
10. Critical Thinking and Debugging Skills: Improve critical thinking skills to
identify and rectify errors in algorithms and data structures. Develop effective
debugging techniques to resolve issues in code implementations. These
outcomes will equip learners with the necessary skills to excel in competitive
programming, technical interviews, and real-world software development
challenges.

35 | P a g e
 Bibliography

 Google
 Geekforgeeks
 DSA Self Placed Course

36 | P a g e
 Project Description: Sudoku Solver
Introduction:
Sudoku is a popular number puzzle that involves filling a 9x9 grid with digits such
that each column, each row, and each of the nine 3x3 subgrids contain all of the
digits from 1 to 9. This project aims to develop a Sudoku solver using the
backtracking technique, a fundamental concept in Data Structures and Algorithms
(DSA). The solver will be implemented in C/C++.

Objectives:
 To understand and implement the backtracking algorithm.
 To solve Sudoku puzzles efficiently.
 To improve problem-solving skills and algorithmic thinking.

Scope:

The project will focus on:

 Implementing the backtracking algorithm in C/C++.

 Solving given Sudoku puzzles.
 Handling edge cases and invalid puzzles gracefully.

Methodology:

1. Problem Representation:

The Sudoku puzzle is represented as a 9x9 matrix.

Empty cells are denoted by 0.

37 | P a g e
2. Backtracking Algorithm:

The algorithm attempts to place digits from 1 to 9 in empty cells.

For each empty cell, it tries each number from 1 to 9.

It checks if placing a number violates Sudoku rules (row, column, and subgrid
uniqueness).

If a number is valid, it places it and recursively attempts to fill the next empty cell.

If no number is valid, it backtracks by resetting the cell and trying the next
possibility in the previous cell.

3. Validation:

A function to check if placing a number in a given cell is valid.

This function ensures that the number does not already exist in the corresponding
row, column, or subgrid.

4. Optimization:

The algorithm can be optimized by choosing the empty cell with the fewest
possibilities first (using a heuristic like Minimum Remaining Values).

Implementation Steps:

 Define the Sudoku grid as a 2D array.

38 | P a g e
  Implement a function to print the Sudoku grid.
 Implement a function to check if placing a number in a cell is valid.
 Implement the backtracking function:
 Base case: If all cells are filled, the puzzle is solved.
 Recursive case: Try placing each number from 1 to 9 in the current cell,
check validity, and recurse to the next cell.
 Test the solver with various Sudoku puzzles.

Tools and Technologies:

Language: C/C++

Development Environment: Any C/C++ IDE (e.g., Visual Studio, Code::Blocks)

Expected Outcomes:

A functional Sudoku solver that can solve any valid Sudoku puzzle.

Demonstrated understanding of the backtracking algorithm and its application in

solving constraint satisfaction problems.

Link Of Project -> https://github.com/Ris-git/DSA.git

39 | P a g e
 THANK

40 | P a g e