Data Structure and Algorithm Design

Course content summary

Xingang (Ian) Fang

Outline

  • Overview

  • Learning outcomes and assessments

  • Math and analysis

  • Problem classification

  • Algorithmic paradigms

  • Other Algorithm Categories

  • Advanced data structures and algorithms

  • Well-known problems

  • Misc. relationships and comparisons

Overview

  • This document is a summary of the topics covered in the course.

  • This is a systematic high-level overview. Fragmented details are not included!

Learning outcomes and assessments

  • Know the fundamentals of advanced data structures, and algorithm paradigms: TF, MC, MA, FIB

    • Definitions

    • Limitations

    • Pros and cons

  • Which data structure, ADT or algorithm to choose: MC, MA

    • Some are required

    • Some are better than others

    • Some depends

    • Analysis based on time/space complexity

  • How algorithm/data structure works on paper: MC, MA, FIB, SA

  • How to implement a data structure, ADT or algorithm (not much in this course due to the complexity of implementations). MC, MA, coding

Math and analysis

  • Math tools are mostly employed in algorithm analysis

  • Basic math tools

    • Exponential and logarithmic functions

    • Proof techniques: 4 types

  • Solve recurrence relations

    • substitution method

    • recursion tree method

    • master method

  • Combinatorics and counting

  • Probability

    • Classical probability

    • Ratio of two counting results

Combinatorics

  • Types

    • Arrangement/Permutation

    • Selection/Combination

    • Partition/Distribution

  • Principles

    • sum - exclusive events, a or b

    • product - independent events, a and b

    • division - correct overcounting

    • inclusion-exclusion - correct overcounting

    • pigeonhole - at least one

Combinatorics Examples

  • Greasy spoon problem

  • Anagrams

    • permutations with duplicates

    • correct overcounting caused by identical items

  • Play cards

  • Distribution

    • star and bars method

Problem classification

  • Help to understand the nature of the problem and thus the best approach to solve it

  • By the goal

    • Enumeration - find all qualifying solutions

    • Search - find one

    • Optimization - find the best

    • Decision - answer yes or no

    • Counting - report how many qualifying solutions

    • Evaluation - calculate the value, usually math problems

  • Relationships

    • These are goals (requested outputs), not algorithmic paradigms.

    • Enumerating all solutions can answer search, decision, counting, or optimization questions, but may do more work than necessary.

    • Search asks for a witness; decision asks only whether one exists.

    • Interactive reference: Connecting Problem Types to Algorithm Paradigms

Algorithmic paradigms

  • Frameworks to design algorithms

  • Not all algorithms fit into a single or any paradigm

  • Brute-force

  • Backtracking (brute-force with pruning on unfeasible partial solutions)

  • Branch and bound (use bounds to prune partial candidates that cannot improve the best known solution; commonly used for exact optimization)

  • Divide and conquer (solve subproblems and combine their results; suited to independent subproblems)

  • Greedy (make locally best choices; exact only when a greedy-choice argument applies, otherwise may be heuristic or approximate)

  • Dynamic programming (reuse results for overlapping subproblems; can compute an optimum, count, yes/no answer, or other value)

Brute-force

  • Find one or all feasible solutions

  • No heuristics

  • No pruning, only check feasibility of complete solutions

  • Usually exponential or factorial time complexity

Backtracking

  • Find one or all feasible solutions

  • With pruning, check feasibility of partial solutions to avoid unnecessary exploration

  • Share the same recursive code structure as brute-force with extra feasibility check to return early

  • May also be iterative using a stack

Divide and conquer

  • Divide the problem into subproblems, solve them individually, and combine the results

  • Suited to problems whose subproblems can be solved independently; repeated subproblems may be recomputed

  • Recursive structure

  • Master method to solve time complexity

Greedy

  • Make a locally best choice at each step

  • Gives an exact optimum when the greedy-choice property is established; otherwise it may be a heuristic or approximation

  • Choices are not revised later

  • Runtime depends on the problem and implementation; it is not inherently linear

  • Employs a priority queue or a sorted list to get the best option

Dynamic programming

  • Compute a result from overlapping subproblems without necessarily listing every feasible solution

  • Characteristics

    • Overlapping subproblems

    • Many DP optimization problems have optimal substructure: an optimal solution can be constructed from optimal solutions to subproblems

    • Depending on the recurrence, DP can compute an optimum, count, Boolean answer, or other value

  • Tabulation (bottom-up) or memoization (top-down)

  • Multi-dimensional array to store intermediate results

Other Algorithm Categories

  • By data structure

    • Graph algorithms

  • By technique used in the algorithm

    • Randomized algorithms

      • random number generator

      • Monte Carlo

      • Las Vegas

      • genetic algorithm

Advanced Data Structures and Algorithms

  • Self-balancing trees

    • AVL tree

    • B-tree

  • Graph algorithms

AVL tree

  • A self-balancing binary search tree

  • Height-balanced

    • Balance factor: 0, -1, 1

    • Rebalance after insertion/deletion

  • Types of imbalance and rotation to rebalance

    • RL - right-left double rotation

    • RR - left rotation

    • LL - right rotation

    • LR - left-right double rotation

  • Time complexity, tree height \(\Theta(\log n)\)

B-tree

  • A self-balancing tree

  • Degree

    • order of a B-tree

    • max degree \(m\)

    • min degree \(\lceil m/2 \rceil\) (only root can have less when the tree is height 1)

  • Self-balancing

    • Rebalance after insertion/deletion

    • Split, merge

    • Borrow from siblings

  • Variations

    • B+ tree: only leaf nodes store data, leaves are linked, great for indexing

    • B* tree (FYI)

Graph

  • Minimum spanning tree (MST)

    • Prim’s algorithm

      • greedy

      • priority queue

      • grow the tree from a single vertex

    • Kruskal’s algorithm

      • greedy

      • disjoint set and sorted edges

      • grow the forest (trees) from edges and let them connect

  • Shortest path

    • single source: Dijkstra’s algorithm

    • all pairs: Floyd-Warshall algorithm

Genetic algorithm

  • a meta-heuristic randomized algorithm

  • an evolutionary algorithm

  • an approximate algorithm

  • solves optimization problems

  • inspired by natural selection

  • familiar with the framework and techniques

    • repeat until stopping criteria

      • selection

      • crossover

      • mutation

      • evaluation

Well-known problems

  • Traveling salesman problem (TSP): GA

  • Bin packing problem: Greedy

  • Graph MST and shortest path (mentioned already)

  • Huffman coding: Greedy, full binary tree

  • Chain matrix multiplication: Dynamic programming

  • Max sum subarray: Divide and conquer; dynamic programming

  • Longest common subsequence: Dynamic programming

Misc. relationships and comparisons

  • Brute-force vs backtracking: with/without pruning

  • Greedy vs backtracking: never look back vs look back on rejection

  • Divide and conquer vs dynamic programming: consider/ignore overlapping subproblems

  • Online vs offline algorithms: with/without future information

  • Online vs offline bin packing: pre-sorting