Data Structures and Algorithms Notes

The time taken to perform an operation increases logarithmically with the size of the input (n). For every doubling of the input size, the time taken increases by a constant factor.

A data structure that follows the Last-In, First-Out (LIFO) principle. The last element added is the first one to be removed.

A type of data structure that uses a hash function to map keys to indices in an array. The hash function helps to distribute keys efficiently.

The worst-case scenario for inserting an element into a hash table occurs when all elements map to the same index, resulting in a linear search through all existing elements.

A data structure that implements a priority queue. It maintains a heap property, where the parent node is always greater than or equal to its children (for a max-heap).

A linked list where each node has pointers to both the previous and the next node. This allows for efficient traversal in both directions.

A type of binary tree traversal where the left subtree is visited first, followed by the root node, and then the right subtree.

A sorting algorithm that recursively divides the unsorted array into smaller sub-arrays, sorts them, and then merges them back into a sorted array. It has a time complexity of O(n*log n) for both best and worst case scenarios.

A queue is not LIFO (Last-In, First-Out). It follows FIFO (First-In, First-Out) principle, where the first element added is the first one to be removed.

The space complexity of DFS is proportional to the number of vertices in the graph. The algorithm uses a stack to store the visited nodes, and the maximum depth of the stack can be equal to the number of vertices.

A graph traversal algorithm that explores the graph level by level. It finds the shortest path in an unweighted graph.

A problem in computer science that involves finding the maximum value of items that can be placed into a knapsack with a fixed weight capacity. Dynamic programming is a commonly used technique to solve this problem.

A problem-solving technique that involves building up a solution from smaller subproblems. Dynamic programming often uses memoization to store the solutions to subproblems to avoid redundant computations.

A search strategy that systematically explores all possible solutions, often used for problems like Sudoku or N-Queens. It involves making choices at each step and backtracking if a choice leads to an invalid solution.

A search algorithm for finding a specific value in a sorted array. It repeatedly divides the search interval in half, eliminating half of the remaining elements in each step. It has a time complexity of O(log n) for best, average, and worst cases.

A bit manipulation operation that checks if the i-th bit of a number n is set (equal to 1). It uses the bitwise AND operator (&) with a mask that has only the i-th bit set.

A dynamic programming problem that involves finding the longest subsequence of characters in a string that is a palindrome (reads the same forwards and backwards).

Backtracking differs from brute force in that it eliminates partial solutions that cannot contribute to a valid result. This helps to reduce the search space and improve efficiency.

Reversing the digits of a number can be done using mathematical operations. Repeatedly extract the last digit using the modulo operator (%) and construct a new number by multiplying the current result by 10 and adding the extracted digit.

The time complexity of merging two sorted arrays using the two-pointer technique is O(n+m), where n and m are the sizes of the two arrays. This is because you need to iterate through both arrays to merge them.

A data structure used to store and manage elements in a specific order, with the restriction that elements can only be added at the end and removed from the front.

A data structure used to store and manage elements in a specific order, with the restriction that elements can only be added or removed from one end.

The time complexity of searching an element in a sorted array using a binary search algorithm.

The process of finding the shortest path between two vertices in a graph.

A type of algorithm that systematically explores all possible solutions to a problem, often used for optimization or finding all possible combinations.

A type of algorithm that explores a set of possible solutions to a problem, often used for constraint satisfaction problems, by systematically trying different choices and backtracking if a choice leads to an invalid solution.

The process of finding the smallest value in a collection of data.

A data structure used to store and manage a collection of elements, allowing for efficient insertion, deletion, and searching.

A data structure used to store and manage a collection of elements organized into a tree-like structure, which allows for efficient searching, insertion, and deletion.

A type of graph where edges have weights associated with them, often representing cost, distance, or time.

A type of algorithm used to solve problems that involve finding the optimal solution from a set of possible solutions, often by breaking down the problem into smaller subproblems and solving them recursively.

A type of algorithm that systematically explores a set of possible solutions to a problem, often used for constraint satisfaction problems, by making choices at each step and backtracking if a choice leads to an invalid solution.

The process of finding the largest value in a collection of data.

A type of algorithm used to solve problems involving finding the optimal solution from a set of possible solutions, often by systematically trying different combinations and selecting the best one.