Data Structure and Algorithms – An Overview

T. H. Cormen, Ed., Introduction to algorithms, 2nd. ed., 10th pr. Cambridge, Mass.: MIT Press [u.a.], 2007.

Data Structure and Algorithsm, Sixth Edition, GoodRich et al., Wiley

What is a data structure? https://www.ibm.com/think/topics/data-structure

What are algorithms?

An Algorithm is simply a specific, step-by-step set of instructions used to complete a task or solve a problem.

In the context of Computer Science (DSA), if a Data Structure is how you organize and store data (like a bookshelf), the Algorithm is the procedure you use to interact with that data (like the steps to find a specific book on that shelf).

An algorithm is like an recipe. With input, we have ingredients such as data in numbers, text or lists etc. We follow a sequence of well defined operations on that data such as cooking instructions (Process). Through those processes, we get output (the meal) like sorted list, specific value or yes/no etc.

Data Structures:

These are the containers used to store and organize data.
https://en.wikipedia.org/wiki/Data_structure

• Arrays: Fixed-size, contiguous memory locations.
• Linked List: Elements (nodes) are linked using pointers.
  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List
• Stacks: LIFO (Last In, First Out). Think of a stack of plates.
• Queue: FIFO (First In, First Out). Think of a line at a store.
  • Simple Queue
  • Circular Queue
  • Priority Queue: Elements are served based on priority, not arrival order.
    https://en.cppreference.com/w/cpp/container/priority_queue.html
  • Deque (Double-Ended Queue): Insert/delete from both ends.
    https://www.geeksforgeeks.org/dsa/deque-set-1-introduction-applications/

Non-Linear Data Structures:

Data elements are arranged hierarchically or interconnectedly.

• Trees: Hierarchical structure with a root node. https://www.w3schools.com/dsa/dsa_theory_trees.php
  • Binary Tree: Each node has at most 2 children.
  • Binary Search Tree (BST): Left child < Parent < Right child.
  • Balanced Trees: Self-adjusting to keep height low (AVL Tree, Red-Black Tree).
  • B-Tree / B+ Tree: Used in databases and file systems.
  • Trie (Prefix Tree): Used for autocomplete and spell checking.
  • Segment Tree / Fenwick Tree: Used for range queries.
    
• Heap: A special tree-based structure that satisfies the heap property. https://en.wikipedia.org/wiki/Heap_(data_structure)
  • Min-Heap: Parent is smaller than children.
  • Max-Heap: Parent is larger than children.
    
• Graph: Nodes (vertices) connected by edges. https://www.w3schools.com/dsa/dsa_theory_graphs.php
  • Directed vs. Undirected
  • Weighted vs. Unweighted
  • Cyclic vs. Acyclic
    
• Hash Table: Stores data in key-value pairs using a hash function. https://www.geeksforgeeks.org/dsa/hash-table-data-structure/
  • Includes: Hash Map, Hash Set.

Algorithms:

These are the procedures to process the data.

• Sorting Algorithms
  • Simple/Slow: Bubble Sort, Insertion Sort, Selection Sort.
  • Efficient/Fast: Merge Sort, Quick Sort, Heap Sort.
  • Non-Comparison: Radix Sort, Counting Sort, Bucket Sort.
• Searching Algorithms
  • Linear Search: Check every element one by one.
  • Binary Search: Divide and conquer on sorted data.
• Graph Algorithms
  • Traversal:
    • Breadth-First Search (BFS): Explore neighbor by neighbor (layer wise).
    • Depth-First Search (DFS): Go as deep as possible before backtracking.
  • Shortest Path:
    • Dijkstra’s Algorithm: Shortest path in weighted graphs (no negative weights).
    • Bellman-Ford Algorithm: Handles negative weights.
    • Floyd-Warshall Algorithm: All-pairs shortest path.
    • A* Search: Used in pathfinding (like video games/maps).
  • Minimum Spanning Tree (MST):
    • Kruskal’s Algorithm
    • Prim’s Algorithm
  • Others: Topological Sort, Flood Fill, Lee Algorithm.
• String Algorithms
  • KMP Algorithm (Knuth-Morris-Pratt): Fast pattern matching.
  • Rabin-Karp Algorithm: Rolling hash pattern matching.
  • Z Algorithm / Manacher’s Algorithm: Advanced string manipulation.
• Algorithm Paradigms (Strategies)
  These are “styles” of solving problems, not specific algorithms themselves.
  • Recursion: A function calling itself.
  • Divide and Conquer: Break a problem into smaller sub-problems (e.g., Merge Sort).
  • Dynamic Programming (DP): Solve complex problems by breaking them down and storing the results of sub-problems to avoid re-computation (e.g., Fibonacci, Knapsack Problem).
  • Greedy Algorithms: Make the locally optimal choice at each step (e.g., Huffman Coding).
  • Backtracking: Explore all possibilities and “backtrack” when a path fails (e.g., Sudoku solver, N-Queens problem).