Skip to content
academia.sh
tr
Log in

Course Intermediate

Algorithms

By the end of this course

Start course

01

Algorithm Analysis

Algorithm criteria, asymptotic notations, complexity classes, and cost calculation methods.

  1. 01 What Is an Algorithm The criteria for an algorithm, the distinction between correctness and termination, the model of computation, and why measuring running time is not enough.
  2. 02 Asymptotic Notation Definitions of big O, big omega, and big theta, elimination of constants, sum and product rules, and common misreadings.
  3. 03 Little o and Little omega Definitions of non-tight bounds, the limit criterion, the analogy between the five notations and comparison operators, and the limits of the ordering relation.
  4. 04 Reading Complexity Classes Constant, logarithmic, linear, linearithmic, polynomial, exponential, and factorial growth; scaling behavior and practical limits.
  5. 05 The Method for Computing Complexity Counting cost with loop and conditional rules, recurrence relations, the master theorem, and amortized analysis.
  6. 06 Time and Space Trade-off Space complexity, in-place operation, the cost of the recursion stack, memoization and precomputation patterns, and the limits of the trade-off.

02

Searching and Sorting

Linear and binary search, basic and advanced sorting algorithms, non-comparison methods, and selection criteria.

  1. 01 Linear Search Scanning unordered data, the expected comparison count for successful and unsuccessful search, the sentinel, and the justification of the linear lower bound.
  2. 02 Binary Search Halving in sorted data, boundary conditions justified by a loop invariant, variants that find the first position, and search over a monotone predicate.
  3. 03 Bubble, Selection, and Insertion Sort The definition of the sorting problem, the criteria of stability and in-place operation, the comparison and move costs of three quadratic algorithms, and the inversion count.
  4. 04 Merge Sort Stable sorting with divide and conquer, the correctness of the merge operation, the bottom-up variant, external sorting, and counting inversions.
  5. 05 Quicksort In-place sorting with partitioning, the effect of pivot choice on the average and worst case, three-way partitioning, and selecting the kth element.
  6. 06 Heap Sort A binary heap on an array, sift-down, linear-time heap construction, guaranteed in-place linearithmic sorting, and the top-k elements.
  7. 07 Non-Comparison Sorts The decision-tree lower bound for comparison-based sorting; the assumptions, costs, and limits of counting, bucket, and radix sort.
  8. 08 Choosing a Sorting Algorithm A decision table based on data characteristics, the use of stability in multi-key sorting, hybrid implementations, and cases where sorting is unnecessary.

03

Graph Algorithms

Shortest-path algorithms, heuristic search, minimum spanning tree, and network flow.

  1. 01 Dijkstra's Algorithm Single-source shortest path on a weighted graph, the relaxation operation, the justification for the greedy choice, a priority-queue implementation, and the non-negative weight restriction.
  2. 02 Bellman–Ford Algorithm Relaxation by iterating over all edges, induction on edge count, negative cycle detection, and the linear solution on a directed acyclic graph.
  3. 03 A* Search Target-directed search with a heuristic function, admissibility and consistency conditions, the relation to Dijkstra, and the gain in expanded vertex count.
  4. 04 Minimum Spanning Tree The cut property, Prim's and Kruskal's algorithms, the union-find structure, a comparison of the two approaches, and a clustering application.
  5. 05 Network Flow The definition of a flow network, the residual network and augmenting paths, the Ford–Fulkerson method with the Edmonds–Karp variant, the max-flow min-cut theorem, and a matching application.

04

Text Algorithms

Pattern-matching methods, preprocessing structures, and lossless compression.

  1. 01 Brute-Force Pattern Matching The definition of pattern matching in text, the sliding scan, character-comparison count, worst-case inputs, and behavior on real text.
  2. 02 Rabin–Karp Pattern matching with a rolling hash, constant-cost window updates, collision verification, worst case, and its advantage in multi-pattern search.
  3. 03 Knuth–Morris–Pratt The definition of the prefix function and its linear computation, search that never backtracks in the text, amortized cost analysis, and string periodicity.
  4. 04 Boyer–Moore Matching from the end, the bad-character and good-suffix rules, the Horspool simplification, sublinear behavior, and a measured comparison of four algorithms.
  5. 05 Suffix Arrays and Trees Structures that preprocess text, building a suffix array and querying it with binary search, the LCP array, comparison with the suffix tree, and applications.
  6. 06 Huffman Coding Variable-length prefix-free codes, greedy tree construction, the optimality argument, the entropy bound, and the method's limits.

Start typing to search.

↑↓ ↵ Esc navigate · open · close