Algorithms: An algorithm is a step-by-step procedure or formula for solving a problem.

It takes input, processes it,

and produces output. Algorithms are fundamental in computer science because they provide efficient solutions to
problems.

Analysis of Algorithms: The analysis of algorithms is the process of determining the computational complexity of
algorithms. The goal is to assess how the algorithm performs, in terms of time (speed) and space (memory usage),
under different conditions.
Key Aspects:
Time Complexity: Measures how the running time of an algorithm grows as the size of the input grows.
Space Complexity: Measures how the memory usage of an algorithm grows as the size of the input grows.

Design of Algorithms: Designing an algorithm is about creating a method to solve a specific problem in an efficient
manner. There are several standard approaches to algorithm design:
• Divide and Conquer
• Greedy Methods
• Dynamic Programming
• Backtracking
• Branch and Bound

Complexity of Algorithms: The complexity of an algorithm refers to the computational resources it requires,
typically time and space. The most important concept here is Big O notation, which provides an upper bound on the
growth rate of an algorithm’s runtime.
• Big O Notation: Describes the worst-case scenario, where the time/space grows as the input size grows.
• O(1): Constant time (e.g., accessing an element in an array).
• O(n): Linear time (e.g., finding an element in a list).
• O(n^2): Quadratic time (e.g., nested loops).
• O(log n): Logarithmic time (e.g., binary search).

Asymptotic Notations: These are used to describe the behavior of an algorithm as the input size grows to infinity.
• Big O (O): Upper bound (worst case).
• Omega (Ω): Lower bound (best case).
• Theta (Θ): Tight bound (average case).

Growth of Functions: When analyzing algorithms, we often describe how the time complexity grows relative to the
size of the input. The common growth rates are:
• Constant (O(1))
• Logarithmic (O(log n))
• Linear (O(n))
• Linearithmic (O(n log n))
• Quadratic (O(n²))
• Cubic (O(n³)), and so on.

Recurrences and Their Solution Methods: Recurrences describe problems where the solution depends on smaller
instances of the same problem. Solving recurrences helps in determining the time complexity of divide-and-conquer
algorithms.
Common Methods for Solving Recurrences:
• Substitution Method
• Recursion Tree Method
• Master Theorem
Sorting in Polynomial Time: Sorting algorithms are a major part of algorithm design. When discussing sorting
algorithms in polynomial time, these are the algorithms that are efficient and scalable for large input sizes.
1. Insertion Sort:
Time Complexity: O(n²)
Simple algorithm that builds the final sorted array one item at a time.
Efficient for small datasets or nearly sorted data.
2. Merge Sort:
Time Complexity: O(n log n)
A divide-and-conquer algorithm that splits the array into two halves, recursively sorts them, and then merges them
back together.
Stable and guarantees O(n log n) time complexity.
3. Heap Sort:
Time Complexity: O(n log n)
Builds a heap (binary tree) and repeatedly extracts the maximum element.
Not stable, but has a good worst-case time complexity.
4. Quick Sort:
Time Complexity: O(n log n) on average (worst-case O(n²))
Another divide-and-conquer algorithm that picks a "pivot" element and partitions the array around it.
Very efficient for large datasets, but not stable.

Sorting in Linear Time:

Some sorting algorithms can sort elements in linear time (O(n)) but with some limitations, like requiring a specific
range of input or additional memory space.
1. Counting Sort:
Time Complexity: O(n + k), where n is the number of elements and k is the range of the numbers.
Works by counting the frequency of each element in the array and using that information to place the elements in
the correct position.
Only works for non-negative integers or small integer ranges.
2. Radix Sort:
Time Complexity: O(nk), where n is the number of elements and k is the number of digits in the largest number.
Sorts the elements based on individual digits (or bits), from least significant to most significant (or vice versa).
Works efficiently when the range of digits is small.
3. Bucket Sort:
Time Complexity: O(n + k), where n is the number of elements and k is the number of buckets.
Works by distributing elements into several buckets and then sorting each bucket individually (often using another
sorting algorithm like insertion sort).
Efficient for uniformly distributed data.

Graph Algorithms: Graphs are a fundamental data structure in computer science used to model relationships
between objects. In graph algorithms, vertices (or nodes) are connected by edges (or arcs). The primary goal of
graph algorithms is to traverse the graph or find certain properties within it.
1. Elementary Graph Algorithms: Elementary graph algorithms deal with basic graph traversal and manipulation,
forming the foundation for more advanced algorithms. They typically involve:
Graph Representation: Adjacency matrix, adjacency list, edge list.
Graph Traversal: Visiting every vertex and edge in the graph.
2. Breadth-First Search (BFS):
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
Description: BFS is an algorithm for traversing or searching a graph in a level-order fashion. It starts at a source
vertex and explores all of its neighbors before moving on to the neighbors of those neighbors. It's typically
implemented using a queue.
Use Cases:
Shortest path in an unweighted graph.
Finding the connected components of a graph.
BFS Algorithm:
Initialize an empty queue and add the starting node.
While the queue is not empty:
Remove a node from the queue.
Visit all its unvisited neighbors and add them to the queue.
3. Depth-First Search (DFS):
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
Description: DFS is an algorithm for traversing or searching a graph by exploring as far along a branch as possible
before backtracking. It's typically implemented using recursion or a stack.
Use Cases:
Detecting cycles in a graph.
Solving problems like topological sorting, strongly connected components, and pathfinding.
DFS Algorithm:
Start from a node and mark it as visited.
Recursively visit all unvisited neighbors of the node.
4. Topological Sort:
Time Complexity: O(V + E).
Description: Topological sort is an ordering of vertices in a directed acyclic graph (DAG) such that for every directed
edge (u, v), vertex u comes before v in the ordering. Topological sort can be implemented using DFS or BFS.
Use Cases: Task scheduling.
Compilation order in programming languages.
Topological Sort Algorithm:
Perform a DFS on the graph.
Once a vertex has no unvisited neighbors, push it to the front of a stack.
The stack will hold the topologically sorted vertices in reverse order.
5. Strongly Connected Components (SCCs):
Time Complexity: O(V + E) using Kosaraju’s or Tarjan's algorithm.
Description: A strongly connected component of a directed graph is a maximal subgraph where every vertex is
reachable from every other vertex. Tarjan’s and Kosaraju’s algorithms are commonly used to find SCCs.
Use Cases:
Analyzing the structure of web pages (e.g., finding clusters of strongly related pages).
Optimizing database queries.
Kosaraju’s Algorithm:
Perform DFS and store the finishing times of each vertex.
Reverse the graph.
Perform DFS again on the reversed graph, starting from vertices in order of decreasing finishing times. Each DFS tree
will represent an SCC.
6. Minimum Spanning Tree (MST):
Description: A spanning tree of a graph is a subgraph that includes all vertices, and a minimum spanning tree is a
spanning tree with the minimum possible sum of edge weights.
Use Cases:
Network design (e.g., connecting cities with the least cost).
Designing circuits.
Algorithms:
Kruskal's Algorithm:
Time Complexity: O(E log E), where E is the number of edges.
Description: Sort the edges by weight, then add edges to the MST in order of increasing weight, ensuring no cycles
are formed.
Prim's Algorithm:
Time Complexity: O(V^2) with a simple implementation, but can be improved to O(E + V log V) using a priority
queue.
Description: Start with any vertex and grow the MST by repeatedly adding the smallest edge that connects a vertex
in the MST to a vertex outside it.
7. Single Source Shortest Path (SSSP):
Description: The problem is to find the shortest paths from a single source vertex to all other vertices in a weighted
graph.
Use Cases:
Finding the shortest route in a map (e.g., GPS navigation).
Networking (e.g., routing algorithms).
Algorithms:
Dijkstra’s Algorithm:
Time Complexity: O(V^2) for a simple implementation, but O(E + V log V) with a priority queue.
Description: A greedy algorithm that builds the shortest path incrementally by selecting the vertex with the smallest
tentative distance.
Bellman-Ford Algorithm:
Time Complexity: O(V * E).
Description: Works for graphs with negative weights and can detect negative weight cycles.
8. All-Pairs Shortest Path (APSP):
Description: The problem is to find the shortest paths between every pair of vertices in a graph.
Use Cases:
Transitive closure in databases.
Network analysis.
Algorithms:
Floyd-Warshall Algorithm:
Time Complexity: O(V^3).
Description: A dynamic programming algorithm that finds the shortest paths between all pairs of vertices by
progressively improving the shortest path estimates.
9. Traveling Salesman Problem (TSP):
Description: The Traveling Salesman Problem asks for the shortest possible route that visits every vertex exactly
once and returns to the starting point. It’s a classic example of an NP-hard problem.
Use Cases:
Logistics and route planning.
DNA sequencing (in bioinformatics).
Algorithms:
Exact Algorithms:
Dynamic Programming: Solves TSP in O(n^2 * 2^n) time (using bitmasking and DP).