COMP90038 Algorithms and Complexity

👉Purpose

---

This repository contains tutorial slides and tutorial sample solutions of the subject COMP90038 Semester2 2020 given by Prof. Toby Murray and Dr. Casey Myers at the University of Melbourne. The repo also contains a list of useful resources about algorithms, data structures and Python etc.

🏃Author

---

The slides and materials are developed by Chuang Wang, the tutor for COMP90038 Semester2 2020.

📋Course Info

---

The aim of this subject is for students to develop familiarity and competence in assessing and designing computer programs for computational efficiency. Although computers manipulate data very quickly, to solve large-scale problems, we must design strategies so that the calculations combine effectively. Over the latter half of the 20th century, an elegant theory of computational efficiency developed. This subject introduces students to the fundamentals of this theory and to many of the classical algorithms and data structures that solve key computational questions. These questions include distance computations in networks, searching items in large collections, and sorting them in order.
Please check the handbook for more information about the subject.

📑Contents

---

Tutorial	Topic	Date
Tutorial 1	Introduction to Algorithms and Data Structures	11 Aug 2020 - 14 Aug 2020
Tutorial 2	Analysis of Algorithm Complexity	17 Aug 2020 - 21 Aug 2020
Tutorial 3	Brute Force and Recursion	24 Aug 2020 - 28 Aug 2020
Tutorial 4	Graphs and Graph Traversal Algorithms	31 Aug 2020 - 04 Sep 2020
Tutorial 5	Decrease and Conquer	07 Sep 2020 - 11 Sep 2020
Tutorial 6	Divide and Conquer	14 Sep 2020 - 18 Sep 2020
Tutorial 7	Trees, PriorityQueues, Heaps and Heapsort	21 Sep 2020 - 25 Sep 2020
Tutorial 8	AVL Tree and 2-3 Tree	28 Sep 2020 - 02 Oct 2020
Tutorial 9	Time/Space Tradeoffs and Hashing	12 Oct 2020 - 16 Oct 2020
Tutorial 10	Dynamic Programming	19 Oct 2020 - 23 Oct 2020
Tutorial 11		26 Oct 2020 - 30 Oct 2020

📁Resources

---

• Complexity

  • MIT Big-O notation notes
  • Big-O cheatsheet

• Brute Force and Recursion

  • Interview Question: Anagram Detection
  • Recursion Notes from Princeton University
  • Generate all permutation of a set in Python

• Graphs

  • Why does the time complexity of DFS and BFS depend on the way the graph is represented?
  • Animation of DFS
  • Animation of BFS
  • Complexity of factorial recursion function: O(N)
  • Complexity of powerset recursion function: O(N^2)

• Sorting Algorithms

  • 15 Sorting Algorithms in 6 Minutes
  • Insertion Sort vs. Selection Sort

• Trees

  • When to use Preorder, Postorder, and Inorder Binary Search Tree Traversal strategies
  • Red Black Tree
  • HashMap improvements in Java8.
    • souce code explanation
    • article
    • visualize performance

• Dynamic Programming

  • Algorithms by Jeff Erickson - Chapter 3
  • Exploring Fibonacci

📄Notes

---

Feedback and comments are more than welcome!
Please contact the author. Thanks a lot!

📧 Contact Info

---

• 📧: chuangw1@unimelb.edu.au
• LinkedIn

License

---