Thuật toán Ứng dụng — DP, String, Big Data & hơn nữa

Bạn sẽ học được gì

Sau khoá học, bạn sẽ:

• Apply dynamic programming, greedy và backtracking vào bài toán tối ưu thực tế

• Implement string matching (KMP, Rabin-Karp, suffix structures) cho search và bioinformatics

• Design thuật toán big-data/streaming (external sort, sketch, sampling) khi dữ liệu vượt RAM

• Explain thuật toán phân tán, spatial index và cryptographic hash trong hệ thống production

Chương trình

Nội dung khoá học

7 module · 66 bài. Mỗi bài 18-25 phút đọc kỹ — không xem video, không hype.

1. 01

   Quyết định dưới constraint — DP, Greedy, Backtracking

   10 bài · ~210 phút

   • 01Module 1 — Quyết định dưới constraint: tổng quan10p
   • 02Dynamic Programming — framework 5 bước để giải quyết bài toán tối ưu20p
   • 03DP 1D — Climbing Stairs, House Robber, Kadane, Coin Change22p
   • 04DP hai chiều — LCS và Edit Distance: bảng dp[i][j] và truy vết22p
   • 05Bài toán cái túi — 0/1 Knapsack, Unbounded và tối ưu không gian20p
   • 06Greedy — Tham lam có chứng minh: Interval Scheduling và Huffman22p
   • 07Backtracking và cắt tỉa — Permutations, N-Queens, pruning21p
   • 08Mini-challenge — Edit Distance: khoảng cách sửa giữa 2 chuỗi30p
   • 09Case Study: LCS trong git diff & Huffman trong gzip28p
   • 10Module 1 — Tổng kết & cheat sheet15p
2. 02

   Pattern matching & String

   9 bài · ~175 phút

   • 01Module 2 — Pattern matching & String: tổng quan8p
   • 02Naive string matching — vì sao O(n·m) chậm16p
   • 03KMP — failure function & matching O(n+m)23p
   • 04Rabin-Karp — rolling hash cho đa mẫu20p
   • 05Z-function — z-array và ứng dụng18p
   • 06Aho-Corasick — automaton so khớp đa mẫu22p
   • 07Mini-challenge — tự viết grep bằng KMP30p
   • 08Case study — Lucene index & ClamAV signature26p
   • 09Module 2 — Tổng kết & cheat sheet12p
3. 03

   Big data & streaming — Khi RAM không đủ

   9 bài · ~174 phút

   • 01Module 3 — Big data & streaming: tổng quan8p
   • 02External merge sort — sắp xếp vượt RAM20p
   • 03Reservoir sampling — mẫu ngẫu nhiên từ stream18p
   • 04HyperLogLog — đếm distinct xấp xỉ22p
   • 05Count-Min Sketch — đếm tần suất xấp xỉ20p
   • 06Sliding window — thống kê trên cửa sổ trượt20p
   • 07Mini-challenge — top-K phần tử trên stream30p
   • 08Case study — Redis HLL & Kafka offset24p
   • 09Module 3 — Tổng kết & cheat sheet12p
4. 04

   Thuật toán phân tán

   10 bài · ~199 phút

   • 01Module 4 — Thuật toán phân tán: tổng quan8p
   • 02Consistent hashing — thêm/bớt node ít xáo trộn22p
   • 03Quorum — nhất quán đọc/ghi với R+W>N18p
   • 04Merkle tree — phát hiện khác biệt hiệu quả20p
   • 05Vector clock — thứ tự nhân quả sự kiện20p
   • 06Gossip protocol — lan truyền trạng thái18p
   • 07Raft — đồng thuận leader & log replication25p
   • 08Mini-challenge — consistent hashing ring có virtual node30p
   • 09Case study — Cassandra ring & etcd Raft26p
   • 10Module 4 — Tổng kết & cheat sheet12p
5. 05

   Geometry & Spatial

   10 bài · ~194 phút

   • 01Module 5 — Geometry & Spatial: tổng quan8p
   • 02Sweep line — quét đường tìm giao điểm20p
   • 03Convex hull — bao lồi (Graham / Andrew)20p
   • 04Quadtree — chia không gian 2D đệ quy20p
   • 05R-tree — index hình chữ nhật bao (MBR)22p
   • 06Geohash — mã hoá toạ độ thành chuỗi18p
   • 07H3 & S2 — lưới phân cấp toàn cầu20p
   • 08Mini-challenge — tìm điểm lân cận (geohash)30p
   • 09Case study — PostGIS GiST & Uber H324p
   • 10Module 5 — Tổng kết & cheat sheet12p
6. 06

   Search engine algorithms

   9 bài · ~182 phút

   • 01Module 6 — Search engine: tổng quan8p
   • 02Inverted index — nền tảng full-text search20p
   • 03TF-IDF — chấm điểm liên quan cổ điển18p
   • 04BM25 — chấm điểm chuẩn công nghiệp20p
   • 05PageRank — xếp hạng theo liên kết22p
   • 06HNSW — vector search xấp xỉ (ANN)24p
   • 07Mini-challenge — mini search engine32p
   • 08Case study — Elasticsearch & pgvector26p
   • 09Module 6 — Tổng kết & cheat sheet12p
7. 07

   Cryptographic & integrity algorithms

   9 bài · ~174 phút

   • 01Module 7 — Cryptographic & integrity: tổng quan8p
   • 02Cryptographic hash — preimage & collision18p
   • 03SHA-256 internals — Merkle-Damgård22p
   • 04HMAC — xác thực message bằng hash18p
   • 05Merkle proof — chứng minh thành viên O(log n)20p
   • 06Hash chain — log append-only chống sửa18p
   • 07Mini-challenge — Merkle tree + proof32p
   • 08Case study — Git objects & Bitcoin header26p
   • 09Module 7 — Tổng kết & cheat sheet12p