Sorting and Searching Algorithms Quiz

Definition: Algorithms that rearrange a collection of elements into a specified order (e.g., ascending or descending).
Types:
- Comparison-based:
  - Bubble Sort: Simple, O(n^2), stable
  - Selection Sort: O(n^2), in-place, not stable
  - Insertion Sort: O(n^2), adaptive, stable
  - Merge Sort: O(n log n), stable, uses additional space
  - Quick Sort: O(n log n) average, O(n^2) worst, in-place, not stable
  - Heap Sort: O(n log n), in-place, not stable
- Non-comparison-based:
  - Counting Sort: O(n + k), stable, assumes integer keys
  - Radix Sort: O(nk), stable, processes digits
  - Bucket Sort: O(n + k), stable, distributes into buckets

Definition: Techniques for finding specific data within a structure.
Types:
- Linear Search: O(n), checks each element sequentially.
- Binary Search: O(log n), requires sorted data, divides search space in half.
- Depth-First Search (DFS): Explores as far as possible along a branch before backtracking, can be implemented using recursion or a stack.
- Breadth-First Search (BFS): Explores all neighbors at the present depth before moving deeper, uses a queue.

Definition: A method of analyzing the efficiency of algorithms in terms of time and space.
Big O Notation: Describes the upper limit of time complexity.
- Common complexities:
  - O(1): Constant time
  - O(log n): Logarithmic time
  - O(n): Linear time
  - O(n log n): Linearithmic time
  - O(n^2): Quadratic time
  - O(2^n): Exponential time
Space Complexity: The amount of memory an algorithm uses relative to input size.

Definition: Ways to organize and store data for efficient access and modification.
Types:
- Arrays: Fixed size, indexed, O(1) access time.
- Linked Lists: Dynamic size, nodes containing data and pointers, O(n) access time.
- Stacks: LIFO structure, O(1) for push/pop.
- Queues: FIFO structure, O(1) for enqueue/dequeue.
- Trees: Hierarchical structure, binary trees, binary search trees, O(log n) search time.
- Hash Tables: Key-value pairs, average O(1) access time, handles collisions with chaining or open addressing.
- Graphs: Collections of nodes and edges, can be represented using adjacency lists or matrices.

Definition: Algorithms for processing graph structures.
Key Algorithms:
- Dijkstra's Algorithm: Finds shortest path from a source to all nodes in a weighted graph.
- Kruskal's Algorithm: Finds minimum spanning tree by sorting edges and adding them without creating cycles.
- Prim's Algorithm: Builds minimum spanning tree starting from a single node, adding the cheapest edge at each step.
- Floyd-Warshall Algorithm: Computes shortest paths between all pairs of nodes, dynamic programming approach.
- Topological Sort: Orders vertices in a directed acyclic graph (DAG), can be done using DFS or Kahn’s algorithm.

Algorithms that arrange elements in a specific order, such as ascending or descending.
Comparison-based Types:
- Bubble Sort: Simple algorithm with O(n²) time complexity, stable sorting method.
- Selection Sort: In-place sorting with O(n²) time complexity, not stable.
- Insertion Sort: Adaptive with O(n²) time complexity, stable sorting method.
- Merge Sort: Efficient with O(n log n) time complexity, requires additional space, stable.
- Quick Sort: Average time complexity of O(n log n), but O(n²) in the worst case, in-place but not stable.
- Heap Sort: Time complexity of O(n log n), in-place but not stable.
Non-comparison-based Types:
- Counting Sort: O(n + k) complexity, assumes integer keys, stable.
- Radix Sort: O(nk) that processes individual digits, stable.
- Bucket Sort: O(n + k), distributes elements into buckets, stable.

Techniques used to find specific data within a data structure.
Linear Search: O(n) complexity; checks each element in sequence.
Binary Search: O(log n) complexity; effective on sorted data, halves the search space.
Depth-First Search (DFS): Explores deeply along one branch before backtracking, can use recursion or a stack.
Breadth-First Search (BFS): Explores all adjacent nodes at one level before going deeper, utilizes a queue.

Evaluates the efficiency of algorithms concerning time and space.
Big O Notation: Describes the upper limit of an algorithm's time complexity.
Common Complexities:
- O(1): Constant time; execution time does not change with input size.
- O(log n): Logarithmic time; efficient for large datasets.
- O(n): Linear time; time increases proportionally with input size.
- O(n log n): Linearithmic time; a typical complexity for efficient sorting algorithms.
- O(n²): Quadratic time; performance deteriorates rapidly with input size.
- O(2^n): Exponential time; increases extremely fast in relation to input size.
Space Complexity: Reflects the memory usage of an algorithm relative to input size.

Methods for organizing and storing data to allow efficient access and modification.
Arrays: Have fixed size with O(1) access time through indexed elements.
Linked Lists: Dynamic size enabled by nodes with data and pointers, O(n) access time.
Stacks: LIFO structure allowing O(1) time complexity for push and pop operations.
Queues: FIFO structure allowing O(1) time complexity for enqueue and dequeue operations.
Trees: Hierarchical models, includes binary trees and binary search trees, with O(log n) search time.
Hash Tables: Store key-value pairs with average O(1) access time, manage collisions with chaining or open addressing.
Graphs: Comprise nodes and edges, can be represented with adjacency lists or matrices for various algorithms.

Specific algorithms designed for processing graph data structures.
Dijkstra's Algorithm: Identifies the shortest path from a single source to all nodes in a weighted graph.
Kruskal's Algorithm: Constructs a minimum spanning tree by sorting edges and adding them while avoiding cycles.
Prim's Algorithm: Builds a minimum spanning tree starting from a single node, adding the lowest-cost edge iteratively.
Floyd-Warshall Algorithm: Calculates shortest paths between all node pairs using dynamic programming.
Topological Sort: Arranges vertices in a directed acyclic graph (DAG) employing DFS or Kahn’s algorithm for ordering.