CSCI-B 503 Algorithm Design and Analysis
3 credits
- Prerequisite(s): None
- Delivery: On-Campus
- Semesters offered: Fall, Spring (Check the schedule to confirm.)
- Equivalent(s): CSCI 58000 Algorithm Design Analysis & Implementation
Description
This course covers models, algorithms, recurrences, summations, and growth rates. Topics include probabilistic tools, upper and lower bounds, worst-case and average-case analysis, amortized analysis, and dynamization. Comparison-based algorithms include search, selection, sorting, and hashing. The course also covers information extraction algorithms for graphs and databases. Graphs algorithms include spanning trees, shortest paths, connectivity, depth-first search, and breadth-first search.
Topics
Introduction
- The role of algorithms in computing
- Insertion sort
- Analyzing algorithms
- Designing algorithms
Characterizing running times
- O-notation, Ω-notation, and Θ-notation
- Asymptotic notation: formal definitions
- Standard notations and common functions
Divide-and-conquer
- Multiplying square matrices
- Strassen’s algorithm for matrix multiplication
- Solving recurrences
Probabilistic analysis and randomized algorithms
Sorting and order statistics
- Heapsort
- Quicksort
- Linear time sorting
- Medians and order statistics
Data structures
- Arrays, matrices, stacks, and queues
- Linked lists
- Representing rooted trees
- Hash tables
- Binary search trees
- Red-black trees
- B-trees
- Disjoint sets
Dynamic programming
- Rod cutting
- Matrix-chain multiplication
- Longest common subsequence
- Optimal binary search trees
Greedy algorithms
- An activity-selection problem
- Elements of the greedy strategy
- Huffman codes
- Offline caching
Amortized analysis
Graph algorithms
- Representations of graphs
- Breadth-first search
- Depth-first search
- Topological sort
- Strongly connected components
- Minimum spanning trees: Kruskal and Prim algorithms
- Single-source shortest paths: Bellman-Ford, acyclic graphs, Dijkstra’s
- Difference constraints and shortest paths
- Proofs of shortest-paths properties
- All-pairs shortest paths: matrix multiplication, Floyd-Warshall, Johnson’s algorithm for sparse graphs
- Maximum flow
Selected topics
- Parallel algorithms
- Online algorithms
- Matrix operations
- Linear programming
- Polynomials and the FFT
- Number-theoretic algorithms
- String matching
- Machine-learning algorithms
- NP-completeness
- Approximation algorithms
Learning Outcomes
- Solve various problems, ranging from searching and sorting to graph traversal and network flow, by applying greedy, dynamic programming, and divide-and-conquer algorithm design techniques, among others. CS 1
- Analyze the performance of algorithms using asymptotic analysis and analyze the trade-offs between time and space complexity. CS 1
- Prove problems as NP-complete, evaluate the implications of NP-completeness on algorithm design and efficiency, and solve NP-complete problems efficiently using techniques such as approximation and randomization. CS 1
- Communicate effectively about algorithm design and analysis, including presenting and justifying algorithmic choices and writing clear and efficient code. CS 6
- Solve real-world problems, such as optimizing supply chains or forecasting financial markets, through algorithm design and analysis. CS 1
- Evaluate the implications of algorithmic decisions on society. CS 6
Policies and Procedures
Please be aware of the following linked policies and procedures. Note that in individual courses instructors will have stipulations specific to their course.