This module aims to provide you with detailed knowledge of several common algorithms and data structures. You will improve your understanding of searching and sorting and learn new algorithms to solve new problems. You will learn about a range of data structures such as trees, heaps, sets, maps, stacks, queues and graphs. You will learn how to evaluate and describe the performance of algorithms using big-O notation. You will learn: how to choose appropriate data structures for representing problems, how to define and implement algorithms for manipulating them, and how to analyse the correctness and efficiency of algorithms.
You will be expected to have mastered the material in Algorithms and Data Structures I before attempting this module.
- Dr. Alejandra Beghelli Zapata
- Complexity, growth of functions and big-O notation
- Stacks and queues
- Binary trees
- Heaps and priority queues
- Implicit array algorithms
- Recursion and Iteration
- Graphs and simple pathfinding
- Shortest-path algorithms
- Sets, maps and hash tables
- Collections
One two hour unseen written examination and coursework (Type I)
Book - Cormen, T.H., C.E. Leiserson, R.L. Rivest and C. Stein Introduction to algorithms. (MIT Press, 2009) 3rd edition [ISBN 9780262533058].
| Week | Topic | Section | Page number |
|---|---|---|---|
| 1 | RAM Model | 2.2 | pp. 23-4 |
| 2 | Worst and average case analysis | p. 27 | |
| 2 | Asymptotic notation | 3.1 | 43-52 |
| 4 | Recursive algorithm and analysis | 2.3, ch. 4 (except 4.6) | pp. 29-37, pp. 65-113 |
| 5 | Insertion Sort | 2.1, 2.2 | pp. 16-22, pp. 23-9 |
| 6 | QuickSort | Ch.7, 7.1, 7.2 | pp. 170-3, pp. 174-8 |
| 6 | MergeSort | 2.3.1, 2.3.2 | pp. 30-34, pp. 34-37 |
| 7 | Lower bounds for comparison sorts | Chapter 8, 8.1 | pp. 191-3 |
| 7 | Counting Sort | 8.2 | pp 194-6 |
| 8 | Radix Sort | 8.3 | pp. 197-9 |
| 8 | Bucket Sort | 8.4 | pp. 200- |
| 9 | Hashing | 11 | pp. 253-285 |
| 13 | Linked Lists | definition of DS, 10.2 | p.9, pp.236-41 |
| 14 | Stacks and Queues | 10.1 | pp 232-5 |
| 16 | Binary search trees | ch. 12, 12.1, 12.2, 12.3 | pp. 286-8, pp. 289-92, pp.294-8 |
| 17 | Heaps, Heapsort and priority queues | Chapter 6 | pp. 151-69 |
| 19 | Graph representation, MST and Dijsktra | Ch.22- 22.1, Ch. 23, Ch 24-Ch. 24.3 | pp. 579-92, pp. 624-42, pp.658-66 |
-
Courses
- Algorithmic Design and Techniques - edX platform, by UC San Diego
- Algorithms Specialization - Coursera. Offered by Stanford. Includes:
- Divide and Conquer, Sorting and Searching, and Randomized Algorithms
- Graph Search, Shortest Paths, and Data Structures
- Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
- Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
- Data Structures Fundamentals - edX platform, by UC San Diego
- Graph Algorithms - edX platform, by UC San Diego
-
Websites
-
⭐ Mathematics for Computer Science - "Proofs, Structures, Counting, Probability, Recurrences."
-
Algorithms in the "Real World" (2018) - Compression, error correcting codes, cryptography, parallel algorithms, locality and I/O efficient algorithms, indexing and searching, nearest neighbors, dimensionality reduction.
-
Comparison of Algorithms - See time complexity at a glance for various popular algorithms.
-
Dictionary of Algorithms and Data Structures - "This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions."
-
Introduction to algorithms (problem sets) - MIT OpenCourseWare.
-
Khan Academy - Algorithms - "We've partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn with a combination of articles, visualizations, quizzes, and coding challenges."
-
Readings from MIT OpenCourseWare (2015) on proofs, graph theory, recurrences, probability.
-
Visualizations
- HackerEarth - Visualize sorting algorithms, step by step.
- VisuAlgo - Visualising data structures and algorithms through animation.
-
-
Youtube
- Alejandra Beghelli's channel - Instructor for this module.
- Algorithm Design and Analysis (playlist) - UC Davis
- Algorithmic Lower Bounds: Fun with Hardness Proofs (playlist) - MIT OpenCourseWare - "[...] summarizing the prerequisite complexity theory and featuring two examples of hardness proofs in games."
- Algorithms Course - Graph Theory Tutorial from a Google Engineer - freeCodeCamp.org
- Algorithms for Big Data (playlist) - Harvard University
- Asymptotic Bounding 101: Big O, Big Omega, & Theta (Deeply Understanding Asymptotic Analysis) - Back To Back SWE
- Asymptotic Notation Recurrences Substitution Master Method - MIT OpenCourseWare
- Introduction to algorithms (playlist) - Abdul Bari
- Introduction to algorithms (playlist) - MIT OpenCourseWare
- Solutions to the mock exam are available in this Google Sheets document.
- CLRS Solutions - Michelle Bodnar, Andrew Lohr