VCE Algorithmics (HESS)

Here lies all the notes I’ve taken for VCE 3/4 Algorithmics (HESS). Some of the information may be outdated, or no longer relevant, but I’m pretty sure I’ve covered almost everything.

Some useful sources you might like:

• Alexandria Repo TextBook
• Virtual Textbook (this one’s really good)
• Divide and Conquer Algorithms:

Note: In most of the coding snippets for some algorithms, I’ve used a python library known as NetworkX. It makes coding graph and graph algorithms much simpler, though in the actual exam, each graph operation would have to be explicitly shown. I’ve also used matplotlib for displaying (drawing) the graphs.

---

Unit 3 §

• Abstract Data Type

• ADT Signatures

  • List
  • Array
  • Dictionary
  • Stack
  • Queues
  • Set - CS
  • Priority Queues

• Graph

  • Graph Types
  • Graph Traversal
  • Graph Terms
  • Negative Weight Cycle

• Pseudocode

• Algorithms By Input

  • Breadth First Search Algorithm
  • Depth First Search Algorithm
  • Best First Search Algorithm
  • Prim’s Algorithm
  • Kruskal’s Algorithm
  • Dijkstra’s Algorithm
  • Bellman-Ford Algorithm
  • Floyd-Warshall’s Algorithm
  • Transitive Closure Algorithm
  • A-star Algorithm

• Loop Invariant

• Iteration

• Recursion - CS

  • Page Rank Algorithm

Unit 4 §

• Complexity Analysis

  • Big-O Notation
  • Time Complexity
  • Space Complexity

• Complexity Theory

  • P-Class
  • NP-Class
  • NP-Complete
  • NP-Hard
  • Computational Limits

• Recurrence Relations

• Master Theorem

• Binary Search Algorithm

• Algorithms By Design Paradigm

  • Greedy Algorithm
  • Greedy Argument
  • Brute-force (Exhaustive)
  • Decrease-and-Conquer
  • Divide-and-Conquer
  • Dynamic Programming
  • Backtracking

• Merge Sort

• Quick Sort

• Heuristic

  • Hill Climbing
  • A-star Algorithm
  • Simulated Annealing

• Travelling Salesman Problem (TSP)

• N-Queens Problem

• Knapsack Problem

• Graph Colouring Problem

• History of Computer Science

• Entscheidungsproblem

• Hilbert’s Program

• Gödel’s Incompleteness Theorem

• Church-Turing Thesis

• Turing Machine

• Computability

• AI

• Timeline of AI

  • Strong AI vs Weak AI

• Turing Test

• Chinese Room Argument

• Machine Learning

• Support Vector Machines

• Training Neural Networks

• Neural Network

• Ethics of AI