Foundation level DSA
● Basic Data Structures: Arrays, Strings, Stacks, Queues
● Asymptotic analysis (Big-O notation)
● Basic math operations (addition, subtraction, multiplication, division,
exponentiation)
● Sqrt(n) primality testing
● Euclid’s GCD Algorithm
● Basic Recursion
● Greedy Algorithms
● Basic Dynamic Programming
● Naive string searching
● O(n logn) Sorting
● Binary Searching
Basic Data Structures: Arrays, Strings, Stacks, Queues
Arrays:
An array is a data structure that stores a collection of elements of the same type. It is a
linear data structure, meaning that elements are stored in a sequential order. Arrays are
used to store data in a structured way, allowing for efficient retrieval and manipulation of the
data. Arrays can be one-dimensional, two-dimensional, or multi-dimensional.
One-dimensional arrays are the simplest type of array. They are used to store a single list of
elements. Each element in the array is assigned an index, which is used to access the
element. For example, an array of integers could be used to store a list of numbers.
Two-dimensional arrays are used to store data in a matrix-like structure. Each element in
the array is assigned two indices, one for the row and one for the column. This allows for
efficient retrieval and manipulation of data. For example, a two-dimensional array of
integers could be used to store a matrix of numbers.
,Multi-dimensional arrays are used to store data in a more complex structure. Each element
in the array is assigned multiple indices, allowing for efficient retrieval and manipulation of
data. For example, a three-dimensional array of integers could be used to store a cube of
numbers.
Strings:
A string is a data structure that stores a sequence of characters. It is a linear data structure,
meaning that characters are stored in a sequential order. Strings are used to store text data
in a structured way, allowing for efficient retrieval and manipulation of the data.
Strings are immutable, meaning that once they are created, they cannot be changed. This
makes them ideal for storing text data, as the data will not be modified. Strings can be
manipulated using various string functions, such as concatenation, substring, and search.
Stacks:
A stack is a data structure that stores a collection of elements in a Last-In-First-Out (LIFO)
order. It is a linear data structure, meaning that elements are stored in a sequential order.
Stacks are used to store data in a structured way, allowing for efficient retrieval and
manipulation of the data.
Stacks are used for a variety of tasks, such as evaluating arithmetic expressions,
implementing recursion, and reversing a list. Stacks are also used in memory management,
as they can be used to store the return address of a function call.
Queues:
A queue is a data structure that stores a collection of elements in a First-In-First-Out (FIFO)
order. It is a linear data structure, meaning that elements are stored in a sequential order.
Queues are used to store data in a structured way, allowing for efficient retrieval and
manipulation of the data.
Queues are used for a variety of tasks, such as implementing a task scheduler,
implementing a priority queue, and implementing a buffer. Queues are also used in memory
management, as they can be used to store the address of a memory block.
, Asymptotic analysis (Big-O notation)
Asymptotic analysis is a mathematical tool used to analyze the performance of algorithms. It
is used to measure the complexity of an algorithm in terms of time and space. Asymptotic
analysis is used to determine the best algorithm for a given problem.
Asymptotic analysis is based on the concept of Big-O notation. Big-O notation is a
mathematical notation used to describe the upper bound of an algorithm’s running time. It is
used to measure the complexity of an algorithm in terms of time and space. Big-O notation
is used to compare the performance of different algorithms.
Big-O notation is used to describe the upper bound of an algorithm’s running time. It is
expressed as a function of the input size. The Big-O notation is used to describe the worst-
case running time of an algorithm. It is expressed as a function of the input size.
For example, if an algorithm has a running time of O(n2), it means that the algorithm’s
running time is proportional to the square of the input size. This means that if the input size
is doubled, the running time will be four times as long.
Big-O notation is used to compare the performance of different algorithms. It is used to
determine which algorithm is the most efficient for a given problem. For example, if two
algorithms have the same running time, but one algorithm has a Big-O notation of O(n2)
and the other has a Big-O notation of O(n), then the algorithm with the Big-O notation of
O(n) is more efficient.
Big-O notation is also used to measure the space complexity of an algorithm. It is
expressed as a function of the input size. For example, if an algorithm has a space
complexity of O(n2), it means that the algorithm’s space complexity is proportional to the
square of the input size. This means that if the input size is doubled, the space complexity
will be four times as large.
Asymptotic analysis is used to determine the best algorithm for a given problem. It is used
to compare the performance of different algorithms and determine which algorithm is the
● Basic Data Structures: Arrays, Strings, Stacks, Queues
● Asymptotic analysis (Big-O notation)
● Basic math operations (addition, subtraction, multiplication, division,
exponentiation)
● Sqrt(n) primality testing
● Euclid’s GCD Algorithm
● Basic Recursion
● Greedy Algorithms
● Basic Dynamic Programming
● Naive string searching
● O(n logn) Sorting
● Binary Searching
Basic Data Structures: Arrays, Strings, Stacks, Queues
Arrays:
An array is a data structure that stores a collection of elements of the same type. It is a
linear data structure, meaning that elements are stored in a sequential order. Arrays are
used to store data in a structured way, allowing for efficient retrieval and manipulation of the
data. Arrays can be one-dimensional, two-dimensional, or multi-dimensional.
One-dimensional arrays are the simplest type of array. They are used to store a single list of
elements. Each element in the array is assigned an index, which is used to access the
element. For example, an array of integers could be used to store a list of numbers.
Two-dimensional arrays are used to store data in a matrix-like structure. Each element in
the array is assigned two indices, one for the row and one for the column. This allows for
efficient retrieval and manipulation of data. For example, a two-dimensional array of
integers could be used to store a matrix of numbers.
,Multi-dimensional arrays are used to store data in a more complex structure. Each element
in the array is assigned multiple indices, allowing for efficient retrieval and manipulation of
data. For example, a three-dimensional array of integers could be used to store a cube of
numbers.
Strings:
A string is a data structure that stores a sequence of characters. It is a linear data structure,
meaning that characters are stored in a sequential order. Strings are used to store text data
in a structured way, allowing for efficient retrieval and manipulation of the data.
Strings are immutable, meaning that once they are created, they cannot be changed. This
makes them ideal for storing text data, as the data will not be modified. Strings can be
manipulated using various string functions, such as concatenation, substring, and search.
Stacks:
A stack is a data structure that stores a collection of elements in a Last-In-First-Out (LIFO)
order. It is a linear data structure, meaning that elements are stored in a sequential order.
Stacks are used to store data in a structured way, allowing for efficient retrieval and
manipulation of the data.
Stacks are used for a variety of tasks, such as evaluating arithmetic expressions,
implementing recursion, and reversing a list. Stacks are also used in memory management,
as they can be used to store the return address of a function call.
Queues:
A queue is a data structure that stores a collection of elements in a First-In-First-Out (FIFO)
order. It is a linear data structure, meaning that elements are stored in a sequential order.
Queues are used to store data in a structured way, allowing for efficient retrieval and
manipulation of the data.
Queues are used for a variety of tasks, such as implementing a task scheduler,
implementing a priority queue, and implementing a buffer. Queues are also used in memory
management, as they can be used to store the address of a memory block.
, Asymptotic analysis (Big-O notation)
Asymptotic analysis is a mathematical tool used to analyze the performance of algorithms. It
is used to measure the complexity of an algorithm in terms of time and space. Asymptotic
analysis is used to determine the best algorithm for a given problem.
Asymptotic analysis is based on the concept of Big-O notation. Big-O notation is a
mathematical notation used to describe the upper bound of an algorithm’s running time. It is
used to measure the complexity of an algorithm in terms of time and space. Big-O notation
is used to compare the performance of different algorithms.
Big-O notation is used to describe the upper bound of an algorithm’s running time. It is
expressed as a function of the input size. The Big-O notation is used to describe the worst-
case running time of an algorithm. It is expressed as a function of the input size.
For example, if an algorithm has a running time of O(n2), it means that the algorithm’s
running time is proportional to the square of the input size. This means that if the input size
is doubled, the running time will be four times as long.
Big-O notation is used to compare the performance of different algorithms. It is used to
determine which algorithm is the most efficient for a given problem. For example, if two
algorithms have the same running time, but one algorithm has a Big-O notation of O(n2)
and the other has a Big-O notation of O(n), then the algorithm with the Big-O notation of
O(n) is more efficient.
Big-O notation is also used to measure the space complexity of an algorithm. It is
expressed as a function of the input size. For example, if an algorithm has a space
complexity of O(n2), it means that the algorithm’s space complexity is proportional to the
square of the input size. This means that if the input size is doubled, the space complexity
will be four times as large.
Asymptotic analysis is used to determine the best algorithm for a given problem. It is used
to compare the performance of different algorithms and determine which algorithm is the
