COMP3821: Extended Algorithms and Programming Techniques (UNSW)

Implementation and explanation of algorithms from the COMP3821 course at UNSW. All the implementations are written in Python 3+ with explanations in comments. This repository is intended for me to study algorithms by implementing them in code. Also included are various algorithms not strictly taught in the course but are related to the programming techniques taught.

Divide and Conquer

Core Algorithms

• Binary search
• Merge sort
• Karatsuba multiplication
• Fast Fourier transform
• Polynomial multiplication

Other Algorithms

• Closest pair of points

Problem Solving

• Peak finding (modified binary search)
• Median of two sorted arrays (modified binary search)
• Inversion counting (modified merge sort)
• Buy and sell stocks (modified merge sort)

Greedy Method

Core Algorithms

• Dijkstra’s shortest path algorithm
• Huffman encoding
• Huffman encoding visualisation

Dynamic Programming

• Notes on dynamic programming (optimal substructure and proof techniques)

Core Algorithms

• Weighted activity selection
• Longest increasing subsequence
• Minimal coin change
• Matrix chain multiplication

Other Algorithms

• Fibonacci series

Linear Programming

• Notes on linear programming (canonical form)

Intractability

• Notes on intractability (complexity classes and reductions)