VCE Algorithmics

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.pdf
• 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 §

• ADTs

• ADT Signatures

  • Lists
  • Arrays
  • Dictionaries
  • Stacks
  • Queues
  • Sets
  • Priority Queues

• Graphs

  • Graph Types
  • Graph Traversal
  • Graph Definitions
  • Negative Weight Cycles

• Pseudocode

• Graph Algorithms

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

• Loop Invariants

• Iteration

• Recursion

  • Page Rank Algorithm

Unit 4 §

• Complexity Analysis

  • Big-O Notation
  • Time Complexity
  • Space Complexity

• Complexity Theory

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

• Recurrence Relations

• Master Theorem

• Binary Search

• Algorithm Design Patterns

  • Greedy Algorithms
  • Greedy Arguments
  • Brute-force (Exhaustive)
  • Decrease-and-Conquer
  • Divide-and-Conquer
  • Dynamic Programming
  • Backtracking

• Merge Sort

• Quick Sort

• Heuristics

  • 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

• History of AI

  • Strong AI vs Weak AI

• Turing Test

• Chinese Room Argument

• Machine Learning

• Support Vector Machines

• Training Neural Networks

• Neural Networks

• Ethics of AI