Trontor/ALDS

2018 Semester 2, Algorithms and Data Structures, Notes + Programs

You can find the subject notes in the file notes.md

This is just a collection of notes, coding snippets and algorithm definitions collated from The University of Melbourne's: Algorithms and Data Structures course held in Semester 2 of 2018.

Please feel free to branch or fork this repo!

Table of Contents

• L02 - Algorithms
  • Example: Fibonacci Numbers
  • Memoization
  • Complexity Analysis: General Method
• L03 - Complexity Analysis
  • Big-O Definition
  • Big-O Arithmetic
  • Big-O Hierarchy
  • Big Omega Ω (Lower Bound)
  • Big Theta Ө (Growth Rate)
• L04 - Data Structures 101
  • Abstract Data Types vs. Data Structures
  • Data Structures and Searching
  • malloc()
• L05 - Data Structures, The Basics
  • Linked Lists
    • Search Operations
    • The Node
    • Traversing the List
    • Inserting into the List
    • Deleting from the List
  • Arrays vs Linked Lists
• L06 - Binary Search Trees
  • Types
  • Best Case Run Time
  • Worst Case Run Time
• L07 - AVL Trees
  • General Procedure
  • Rotation
• L07/L08 - Deletion in BST
  • Tree Traversal
  • In-order Traversal
  • Deleting an Item
    • Node With Two Children
  • Deletion Complexity Analysis
    • Worst Case:
    • Average Case:
• L09 - Multi-File Programming
  • Header Files
  • Include
  • Makefiles
• L09/10 - Distribution Counting
  • Definition
  • Steps
  • Stable Sort?
  • Complexity and Example
    • Task
    • Count
    • Cumulative Count
    • Redistribution
• L10/11 - Hash tables
  • Complexity
  • Hash Function
  • Modulus and Prime Utilisation
  • Hash Function for Strings
  • Collisions
    • Chaining
    • Open Addressing
• L11/12 - Selection/Insertion Sort
  • Selection Sort
  • Insertion Sort
• L12 - Quicksort
  • Quicksort: Basic idea
• L13 - Mergesort
  • Procedure
  • Merging
  • Recurrence Relation
  • Bottom Up Mergesort
• L14 - Master Theorem
  • Divide and Sorting Algorithms
  • Relationship Between a, b, d
• L14/L15 - Priority Queues/Heaps
  • Priority Queues
  • Implementations
  • Heap
  • Deleting The Max (Downheaping)
  • Downheaping
  • Upheaping
  • Complexity Comparison
  • Heapsort
• L16 - Introduction to Graphs
  • What is a graph?
  • Types of Graphs
    • Undirected Graphs
    • Directed Graphs
  • Reachability
    • Bipartite Graph
    • Completed Graph
  • Trees
  • Representing Graph Vertices
  • Array Representation
  • Adjacency List
  • Size Comparison
• L17 - Traversing Trees and Graphs
  • Traversal
  • Graph Traversal vs Tree Traversal
  • Tree Traversal (BST, DFS, traversal DFS)
    • Depth First Search
    • Breadth First Search
  • Assumptions
  • Traversing an Unconnected Graph (DFS)
    • Graph DFS Analysis
  • Breadth First Search
  • Weighted Graphs
• L18 - Shortest Paths
  • Dijkstra’s Algorithm
  • Code using a Priority Queue
  • Dijkstra's Algorithm Complexity Analysis
  • Limitations
  • Single Source vs All Pairs
    • Using Dijkstra’s multiple times:
• L19 - All Pairs (Floyd-Warshall)
  • Transitive Closure
  • Warshall Algorithm
  • Warshall Algorithm Analysis
  • Floyd-Warshall Algorithm
  • Notes on the Floyd-Warshall Algorithm
  • Big Assumptions
    • Johnson's Algorithm
• L20 - Kruskal's Algorithm for MST
  • Greedy Algorithms
  • Spanning Tree
  • Minimum Spanning Trees
  • Why minimum spanning trees?
  • Kruskal's Algorithm
  • Kruskal's Algorithm Analysis
  • Union-Find/Disjoint-Set Data Structure
    • What is a disjoint set?
    • Union-Find Algorithms
    • Array-based Union Find
  • Application to Kruskal's Algorithm
• L21 - Prim's Algorithm
• L22 - Topological Sorting (Toposort)
  • What is toposort?
  • Topological Sorting Algorithm Overview
  • Toposort Example
  • Toposort Assumptions