Week 5: String Algorithms, Approximation, Randomisation, Ethics
Week 5
The Tao of Programming
Strings
Strings
Pattern Matching
Pattern Matching
Analysis of Naive Pattern Matching
Boyer-Moore Algorithm
Knuth-Morris-Pratt Algorithm
Boyer-Moore vs KMP
Word Matching With Tries
Preprocessing Strings
Tries
Tries
Trie Operations
Word Matching With Tries
Word Matching with Tries
Compressed Tries
Pattern Matching With Suffix Tries
Text Compression
Text Compression
Huffman Code
Approximation
Approximation for Numerical Problems
Approximation for Problems in NP
Vertex Cover
Randomised Algorithms, Ethics, Course Review
Nerds You Should Know
Randomised Algorithms
Randomised Algorithms
Randomness
Sidetrack: Random Numbers
Randomised Algorithms
Analysis of Randomised Algorithms
Randomised Quicksort
Non-randomised Quicksort
Worst-case Running Time
Randomised Quicksort
Minimum Cut Problem
Contraction
Karger's Algorithm
Sidetrack: Maxflow and Mincut
Randomised Algorithms for NP-Problems
Simulation
Simulation
Example: Area inside a Curve
Summary
Algorithm and Data Ethics
Data Breaches
Data (Mis-)use
Costly Software Errors
Sidetrack: Year 2038 Problem
Programming Ethics
Moral Dilemmas
Course Review
Course Review
Assessment Summary
Final Exam
Revision Strategy
Supplementary Exam
Assessment
Summing Up …
So What Was the Real Point?
Finally …
Produced: 31 Jan 2025
![[index]](icon/up.gif){kind=icon}