algorithms_and_data_structures_ii

Go back to the main page

Table of contents

• Table of contents
• Algorithms and Data Structures II
• Topics covered
• Assessment
• Module specification
• Syllabus
• List of required reading
• Resources
  • Complementary learning
  • Mock exam
    • Solutions shared by students
  • Notes
  • Solutions to the textbook Introduction to Algorithms

---

Algorithms and Data Structures II

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.

Topics covered

• 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

Assessment

One two hour unseen written examination and coursework (Type I)

Module specification

• Module specification (September 2020)

Syllabus

• Syllabus PDF September 2020

List of required reading

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

Resources

Complementary learning

• Courses

  • Algorithmic Design and Techniques - edX platform, by UC San Diego
  • Data Structures Fundamentals - edX platform, by UC San Diego
  • Graph Algorithms - edX platform, by UC San Diego

• Websites

  • 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."

  • Skiena's Algorithms Lectures

  • 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

Mock exam

• Mock exam, 2020

Solutions shared by students

• Solutions to the mock exam are available in this Google Sheets document.

Notes

• student_notes/felipe_balbi/notes.pdf

Solutions to the textbook Introduction to Algorithms

• CLRS Solutions - Michelle Bodnar, Andrew Lohr