Khóa học Cấu trúc dữ liệu và Giải thuật Toàn Diện

Khái niệm về giải thuật và tầm quan trọng trong lập trình

Định nghĩa và vai trò của cấu trúc dữ liệu trong lập trình

Các loại cấu trúc dữ liệu cơ bản

Các đặc điểm của một giải thuật tốt

Phân tích độ phức tạp của giải thuật

Khái niệm Big O, Big Theta, Big Omega.

Phân tích độ phức tạp thuật toán: thời gian & bộ nhớ.

Vòng lặp đơn: O(n), vòng lặp lồng nhau: O(n²).

Vòng lặp nhị phân: O(log n), so sánh hiệu quả.

Nhận dạng thuật toán linear, logarithmic, quadratic trong bài toán cơ bản.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Lũy thừa nhanh (Exponentiation).

Kiểm tra số nguyên tố nâng cao: Sieve of Eratosthenes, probabilistic tests.

Tính chất modulo và modulo lớn.

Ứng dụng số học nâng cao trong combinatorics.

Phân tích độ phức tạp các thuật toán số học nâng cao.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Số nguyên tố, phân tích số nguyên tố.

Chia lấy dư, đồng dư, các tính chất cơ bản.

UCLN, BCNN, thuật toán Euclid.

Quy tắc rút gọn trong số học.

Liên hệ số học cơ bản với tổ hợp và thuật toán.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Ôn lại kiến thức các buổi 1,2,3.

Chữa bài tập về nhà phần lý thuyết số.

Khái niệm nghịch đảo modulo.

Tính nghịch đảo modulo bằng thuật toán Euclid mở rộng.

Điều kiện tồn tại nghịch đảo modulo.

Ứng dụng nghịch đảo trong combinatorics và số học nâng cao.

Liên hệ với các bài toán modular arithmetic.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Khái niệm đệ quy, stack gọi hàm.

Các loại đệ quy: tuyến tính, phân nhánh, lồng nhau.

Thuật toán điển hình: giai thừa, Fibonacci, tổ hợp.

Phân tích độ phức tạp đệ quy.

Liên hệ đệ quy với cấu trúc dữ liệu stack.

Nhận biết dạng bài áp dụng đệ quy.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Ôn Big O, vòng lặp, đệ quy.

Ôn lý thuyết số: UCLN, BCNN, modulo, nghịch đảo modulo, số nguyên tố.

Nhận dạng thuật toán theo độ phức tạp.

Liên hệ số học với thuật toán tổ hợp và đệ quy.

Tổng hợp kiến thức phần 1 để chuẩn bị phần cấu trúc dữ liệu.

Chữa bài tập về nhà và sửa code cho học viên

Mảng 1 chiều: khai báo, truy cập, cập nhật giá trị.

Vector: cơ chế tự động mở rộng, push_back/pop_back, truy cập.

Set, Map, Pair: khái niệm, key-value, thao tác cơ bản.

Stack, Queue: LIFO/FIFO, push/pop, enqueue/dequeue.

Liên hệ các container với thuật toán xử lý dữ liệu.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Stack: cơ chế LIFO, push/pop, ứng dụng logic.

Queue: FIFO, enqueue/dequeue, hàng đợi chuẩn.

Deque: double-ended queue, thao tác hai đầu.

So sánh cơ chế Stack, Queue, Deque.

Liên hệ với các thuật toán BFS/DFS, đệ quy.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Set: tập hợp duy nhất, tìm kiếm nhanh.

Bitset: thao tác bit, set/reset, đếm bit.

Multiset, Multimap: lưu trữ nhiều giá trị trùng nhau.

Sort: cơ chế, comparator, sort chuẩn STL.

Liên hệ container với thuật toán tìm kiếm, sắp xếp.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Mảng 2 chiều: khai báo, truy cập, thao tác tổng hợp.

String: khái niệm, so sánh, nối, tách, tìm mẫu con, đếm ký tự.

Ôn container cơ bản: Stack, Queue, Vector, Set, Map.

So sánh cơ chế lưu trữ và thao tác.

Tổng hợp kiến thức cấu trúc tuyến tính.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Kiểm tra mức độ hiểu bài của học viên

Kèm lại cho những bạn yếu

Khái niệm tổ hợp, hoán vị, dãy nhị phân.

Thuật toán sinh tổ hợp, hoán vị tuần tự.

next_permutation: cơ chế hoạt động.

Phân loại bài toán áp dụng.

Liên hệ đệ quy với sinh tổ hợp.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Nguyên lý quay lui, thuật toán cơ bản.

Bài toán điển hình: Sudoku, N-Queen, tổ hợp chập k.

Nhánh cận (Branch and Bound) trong tối ưu hóa.

Cấu trúc dữ liệu hỗ trợ: Stack, recursive call.

Phân tích độ phức tạp thuật toán.

Mối liên hệ với lý thuyết tổ hợp.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Ôn tổ hợp, hoán vị, dãy nhị phân.

Ôn quay lui, nhánh cận.

Phân tích độ phức tạp thuật toán.

Liên hệ số học, đệ quy, quay lui.

Tổng hợp kiến thức phần thuật toán cơ bản.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Bubble Sort, Insertion Sort, Selection Sort: cơ chế, độ phức tạp.

Radix Sort: nguyên lý, sắp xếp theo chữ số.

Liên hệ sắp xếp với tìm kiếm.

Phân tích ưu nhược điểm từng thuật toán.

Khi nào nên chọn thuật toán nào.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Nguyên lý chia để trị, chọn pivot, partition.

Thuật toán đệ quy Quick Sort.

Phân tích độ phức tạp trung bình & worst-case.

So sánh với Merge Sort, Heap Sort.

Ứng dụng Quick Sort trong dữ liệu lớn.

Liên hệ với tìm kiếm nhị phân.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Merge Sort: chia để trị, gộp.

Heap Sort: xây dựng heap, cơ chế sắp xếp.

Phân tích độ phức tạp Merge, Heap.

So sánh Quick, Merge, Heap về ổn định và hiệu quả.

Liên hệ ứng dụng thực tế.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Ôn toàn bộ thuật toán sắp xếp.

Phân tích ưu nhược điểm từng thuật toán.

Nhận dạng thuật toán phù hợp với dữ liệu.

Liên hệ sắp xếp với tìm kiếm và container.

Tổng hợp kiến thức phần sắp xếp.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Linear Search, Binary Search.

Lower_bound, Upper_bound.

So sánh hiệu quả linear vs binary search.

Điều kiện áp dụng mỗi thuật toán.

Liên hệ tìm kiếm với sắp xếp, container.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Nguyên lý thuật toán tham lam.

Chọn bước tối ưu tại mỗi bước.

Bài toán điển hình: Activity Selection, đổi tiền.

Phân tích độ phức tạp.

Liên hệ với quay lui, DP.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Ôn thuật toán tìm kiếm và Greedy.

Tổng hợp lý thuyết & phân tích thuật toán.

Nhận dạng dạng bài áp dụng từng thuật toán.

Liên hệ Greedy với thuật toán trước.

Chuẩn bị kiến thức phần đồ thị.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Khái niệm đồ thị, đỉnh và cạnh.

Biểu diễn ma trận kề, danh sách kề, danh sách cạnh.

So sánh ưu nhược điểm các phương pháp lưu trữ.

Khái niệm đồ thị có hướng, vô hướng, trọng số.

Ứng dụng biểu diễn đồ thị trong thuật toán.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

DFS – Depth First Search: nguyên lý, đệ quy & stack.

BFS – Breadth First Search: nguyên lý, queue, duyệt theo lớp.

Duyệt thành phần liên thông.

Phân tích độ phức tạp O(V+E).

Liên hệ DFS & BFS với Topo Sort, kiểm tra bipartite.

Phân loại cạnh trong DFS: Tree, Back, Forward, Cross.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

BFS 0-K: ý tưởng và cơ chế tính khoảng cách.

Topo Sort: khái niệm, thuật toán DFS & Kahn.

Ứng dụng Topo Sort trong bài toán scheduling.

Đồ thị hai phía (Bipartite Graph): định nghĩa và kiểm tra 2-coloring.

Liên hệ với DFS/BFS và cấu trúc dữ liệu hỗ trợ.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Giới thiệu về cây cân bằng và tầm quan trọng

Cấu trúc và tính chất của cây AVL

Cấu trúc và tính chất của cây đỏ đen

DSU – Disjoint Set Union: khái niệm, parent & rank.

Thuật toán union-find, path compression.

Kruskal: xây dựng cây khung nhỏ nhất (MST).

Phân tích độ phức tạp Kruskal.

Liên hệ DSU với bài toán nhóm, kết nối.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Prim: ý tưởng, priority queue, xây dựng MST.

So sánh Kruskal và Prim.

Phân tích độ phức tạp.

Ứng dụng MST trong mạng lưới, kết nối tối ưu.

Liên hệ với DSU, đồ thị trọng số.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Khái niệm cầu (Bridge) và khớp (Articulation Point).

DFS-based algorithm để tìm bridge & articulation point.

Phân tích độ phức tạp O(V+E).

Ứng dụng: bảo vệ mạng, nối thông.

Liên hệ với DFS và thành phần liên thông.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Floyd-Warshall: tính tất cả cặp đường đi ngắn nhất.

Dijkstra: đường đi ngắn nhất từ 1 đỉnh, heap optimization.

Bellman-Ford: xử lý đồ thị có trọng số âm.

SPFA: cải tiến Bellman-Ford, cơ chế queue.

So sánh độ phức tạp, ưu nhược điểm từng thuật toán.

Tarjan: tìm SCC (Strongly Connected Components).

DFS-based algorithm, low-link value.

Ứng dụng Tarjan trong đồ thị có hướng.

LCA – Lowest Common Ancestor: khái niệm.

Phương pháp cơ bản tính LCA bằng DFS và parent array.

Thực hành chữa bài tập minh hoạ, chỉnh sửa code học viên

Ôn biểu diễn đồ thị, DFS, BFS.

Ôn Topo Sort, Bipartite, BFS 0-K.

Ôn MST: Kruskal, Prim, DSU.

Ôn Bridge & Articulation Point, Tarjan.

Ôn LCA cơ bản.

Tổng hợp kiến thức đồ thị để chuẩn bị phần kiểm tra định kỳ.

Kiểm tra mức độ hiểu bài của học viên

Kèm lại cho những bạn yếu

Khái niệm DP: subproblem & optimal substructure.

Memoization và Tabulation.

Phân loại DP: 1D, 2D.

Liên hệ DP với đệ quy.

Phân tích độ phức tạp DP cơ bản.

Coin Change: tối ưu số đồng tiền.

LIS – Longest Increasing Subsequence.

LCS – Longest Common Subsequence.

Phân tích độ phức tạp các bài toán.

Liên hệ với memoization và tabulation.

Knapsack: trạng thái & chuyển trạng thái.

DP mở rộng: bounded, unbounded knapsack.

Tối ưu hóa không gian cho knapsack.

Phân tích độ phức tạp.

Liên hệ với bài toán tổ hợp & đệ quy.

DP Bitmask: biểu diễn trạng thái bằng bitmask.

Bài toán TSP (Traveling Salesman Problem) cơ bản.

Cách cập nhật trạng thái và chuyển trạng thái.

Phân tích độ phức tạp O(2^n * n²).

Liên hệ với DP và combinatorics.

Ý tưởng Meet in the Middle: chia bài toán lớn thành 2 nửa.

Bài toán Subset Sum nâng cao.

Kỹ thuật generate & search kết hợp.

Phân tích độ phức tạp.

Liên hệ DP, combinatorics, backtracking.

Ôn DP cơ bản, Coin Change, LIS, LCS.

Ôn Knapsack & DP nâng cao.

Ôn DP Bitmask & TSP.

Ôn Meet in the Middle.

Phân tích các bài toán áp dụng.

Chuẩn bị kiến thức tối ưu DP nâng cao.

Divide & Conquer Optimization.

Convex Hull Trick (CHT) cho DP tuyến tính.

Khi nào áp dụng D&C optimization.

Khi nào áp dụng CHT, nguyên lý hoạt động.

Phân tích độ phức tạp & ví dụ lý thuyết.

Khái niệm Segment Tree: cây khoảng.

Cập nhật & truy vấn khoảng.

Lazy Propagation: cơ chế & ý nghĩa.

Phân tích độ phức tạp O(log n).

Liên hệ với bài toán phạm vi truy vấn.

Binary Indexed Tree (BIT) – cơ chế hoạt động.

Truy vấn prefix sum & update.

Phân tích độ phức tạp O(log n).

So sánh Segment Tree & BIT.

Liên hệ với bài toán cumulative sum.

Cây nhị phân cơ bản: traversal, height, balance.

AVL Tree: cân bằng, rotation.

Red-Black Tree: nguyên tắc, màu sắc, rotation.

Phân tích độ phức tạp tìm kiếm, chèn, xóa.

Liên hệ với container Set/Map.

Khái niệm LCA.

Binary Lifting: cơ chế, table chuẩn bị.

Truy vấn LCA giữa 2 đỉnh.

Phân tích độ phức tạp O(log n).

Liên hệ với cây nhị phân & đồ thị.

Ôn Segment Tree, Lazy Propagation.

Ôn Fenwick Tree (BIT).

Ôn AVL, Red-Black Tree, Binary Tree.

Ôn LCA & Binary Lifting.

Tổng hợp kiến thức, phân loại ứng dụng.

Chuẩn bị kiểm tra định kỳ cuối khóa.

Kiểm tra lý thuyết Segment Tree & BIT.

Kiểm tra AVL, Red-Black Tree.

Kiểm tra LCA & Binary Lifting.

Phân tích kết quả, tổng hợp kiến thức.

Tổng hợp kiến thức toàn khóa.

Ôn tập tư duy giải thuật, cấu trúc cơ bản, thuật toán.

Ôn tập đồ thị & DP.

Ôn tập cấu trúc nâng cao.

Định hướng luyện thi phỏng vấn, OLP, ICPC.

Hướng tự học, mở rộng kiến thức nâng cao.