50.004 Algorithms
Course Description
This course is an introduction to algorithms and algorithmic thinking. The course covers common algorithms, algorithmic paradigms, and data structures that can be used to solve computational problems. Emphasis is placed on understanding why algorithms work, and how to analyze the complexity of algorithms. Students will learn the underlying thought process on how to design their own algorithms, including how to use suitable data structures and techniques such as dynamic programming to design algorithms that are efficient.
Prerequisite
- 10.014 Computational Thinking for Design (For AY2020 and subsequent batches)
Learning Objectives
At the end of the term, students will be able to:
- Analyze the running times of algorithms.
- Demonstrate familiarity with major algorithms and data structures.
- Use suitable data structures in algorithms to solve computational problems.
- Identify major issues in the implementation of algorithms.
- Solve algorithmic issues in the design of information systems.
- Understand graphs as data structures, and implement graph traversals.
- Apply Bellman-Ford algorithm and Dijkstra’s algorithm to compute shortest paths in graphs.
- Design efficient algorithms using dynamic programming to solve computational problems.
- Analyze NP-complete problems and apply polynomial-time reductions to problems.
Measurable Outcomes
- Compute the asymptotic complexity of algorithms.
- Analyze and apply properties of data structures.
- Design algorithms that build upon basic operations on data structures.
- Apply and/or modify existing algorithms to solve computational problems.
- Compute hash tables and perform re-hashing.
- Implement graph-based algorithms on provided graphs.
- Design efficient algorithms using dynamic programming.
- Analyze NP-complete problems and apply polynomial-time reductions to problems.
Topics Covered
- Complexity, Asymptotic notation
- Document distance
- Peak finding, divide-and-conquer
- Sorting algorithms, master theorem
- Heaps, priority queues, analysis of heap algorithms
- Binary search trees (BSTs), BST operations, AVL trees
- Arrays vs linked lists, hashing, designing good hash functions, re-hashing
- Graphs as data structures, breadth-first search, depth-first search, topological sort
- Single source shortest path problem, Bellman-Ford algorithm, Dijkstra’s algorithm
- Dynamic Programming (DP), designing DP algorithms
- DP problems: rod-cutting problem, knapsack problem, text justification problem, matrix chain parenthesization
- P vs NP, decision problems, polynomial-time reduction, NP-hardness
- Examples of NP-complete problems (inc. multiple graph-related NP-complete problems)
- More graph-theoretic terminology, 3-SAT problem
Textbook(s) and/or Other Required Material
- Thomas H. Cormen et al., Introduction to Algorithms, 3rd ed. Cambridge, MA: The MIT Press, 2009.
- Bradley N. Miller and David L. Ranum, Problem Solving With Algorithms and Data Structures Using Python, 2nd ed. Portland, OR: Franklin, Beedle & Associates, 2011.
Course Instructor(s)
Prof Ernest Chong, Prof Soh De Wen, Prof Cyrille Jegourel, Prof Dileepa Fernando, Prof Pritee Agrawal