Design and Analysis of Algorithms

Course Introduction

The "Design and Analysis of Algorithms" (DAA) course develops the ability to create efficient algorithms to solve computational problems. It focuses on understanding how algorithms work, how to measure their efficiency, and how to design them for various problem types.

Key concepts include:

Time complexity and space complexity (Big O, Big Θ, Big Ω)
Algorithm design paradigms: Divide-and-Conquer, Greedy, Dynamic Programming, Backtracking
Graph and network algorithms
Optimization problems (Knapsack, TSP)
Theoretical foundations like NP-completeness and undecidability

Data Structures

Basic Structures

Arrays: Fixed-size collections, fast access using indices. Example: storing student marks.

Stacks: LIFO structure, supports push/pop operations. Example: Undo operations in text editors.

Queues: FIFO structure, used in scheduling and buffering. Example: Print queue.

Linked Lists: Dynamic memory allocation, easy insertion/deletion. Types: singly, doubly, circular.

Intermediate Structures

Trees: Hierarchical structure, useful for searching and sorting. Example: Binary Search Tree (BST)

Graphs: Represent networks. Types: Directed, Undirected, Weighted, Unweighted.

Heaps: Complete binary tree for priority queues. Example: Min Heap for minimum extraction.

Advanced Structures

Tries: Efficient string storage for prefix search. Example: Auto-complete in search engines.

Fenwick Trees / BIT: Range queries in O(log n) time.

Segment Trees: Range queries and updates, useful for interval problems.

Skip Lists: Probabilistic data structure for fast insertion/search in sorted lists.

Algorithms

Sorting & Searching

Bubble Sort: Repeatedly swap adjacent elements. Complexity: O(n²)

Pseudocode:

for i = 0 to n-1:
    for j = 0 to n-i-1:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])

Merge Sort: Divide-and-conquer algorithm, complexity: O(n log n)

function mergeSort(arr):
    if length(arr) <= 1:
        return arr
    mid = length(arr)/2
    left = mergeSort(arr[0:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

Graph Algorithms

Dijkstra's algorithm: Shortest path in weighted graph (no negative weights)
Bellman-Ford algorithm: Shortest path (supports negative weights)
Prim & Kruskal: Minimum Spanning Tree (MST)
Floyd-Warshall: All pairs shortest path

Dynamic Programming

Solve complex problems by breaking into smaller overlapping subproblems and storing results. Example: Fibonacci, Longest Common Subsequence, 0/1 Knapsack.

Recursion & Backtracking

Solve problems incrementally and backtrack if constraints fail. Example: N-Queens, Sudoku solver.

String Matching

Naive, KMP, Rabin-Karp, Boyer-Moore algorithms for pattern search in strings. Important in search engines.

Optimization Problems

Knapsack, Traveling Salesperson Problem (TSP), Huffman Coding. Applied in resource allocation, logistics, and compression.

Undecidability & Complexity

Halting Problem, P vs NP, NP-Complete problems. Understand the limits of computation.

Course Learning Reflections

Sorting, searching, and pathfinding are fundamental problem types. Recursion, backtracking, greedy, and dynamic programming offer powerful methods to solve them efficiently.

Understanding time complexity (speed) and space complexity (memory usage) is essential. Orders of growth (O(1), O(log n), O(n), O(n log n), O(n²)) help classify algorithms and choose the best approach.