Bỏ qua

Hướng dẫn tự học cấu trúc dữ liệu và giải thuật

Hướng dẫn này sẽ tập trung vào việc giúp bạn hiểu về cấu trúc dữ liệu và thuật toán. Về phần áp dụng thì bạn lên LeetCode, Hackerrank hoặc bất cứ nền tảng nào. Bạn cũng có thể sử dụng Algorithms Visualizer để có thể xem cách thuật toán vận hành.

Kiến thức nền tảng

Toán rời rạc

Đọc hết trong cuốn Giáo trình toán rời rạc - Tổ hợp và đồ thị. Một số các chủ đề có thể kể đến

  • Các quy tắc đếm cơ bản
  • Xác suất
  • Hoán vị & Tổ hợp
  • Lý thuyết đồ thị

Đại cương

Được trích dẫn từ series Algorithms Design Techniques trên Viblo.

  1. Cùng ôn lại các khái niệm về Cấu trúc dữ liệu, Giải thuật, Độ phức tạp thuật toán.
  2. Tìm hiểu về giải thuật Đệ Quy
  3. Tìm hiểu về giải thuật Chia để Trị (Divide and Conquer)

Muốn "cưỡi ngựa xem hoa" một chút, đọc 8 kiểu cấu trúc dữ liệu mà mọi lập trình viên cần phải biết

Lập trình "cơ bản"

Bạn có thể viết bằng mã giả (pseudocode) hoặc một ngôn ngữ bất kì, thường là Java hoặc Python.

Tài nguyên khác

Phần lớn các bài viết được dẫn nguồn tới Viblo, và đây là một số nguồn bằng Tiếng Việt khác

Cấu trúc dữ liệu

Arrays và Linked Lists

Stacks và Queues

Cây

Hash Tables và Sets:

Trích từ kho video của ông Dev:

Đồ thị

Giải thuật

Thuật toán sắp xếp

Ta sẽ tập trung học sắp xếp dựa trên so sánh (Comparison-based sorting. Bao gồm: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort) và sắp xếp không dựa trên so sánh (Non-comparison based sorting. Bao gồm Counting Sort, Radix Sort).

Đọc thêm:

Thuật toán tìm kiếm

  • Linear Search
  • Binary Search
  • Interpolation Search
  • Các thuật toán tìm kiếm nâng cao (Ternary Search, Exponential Search)

Advanced Graph Algorithms:

  • Topological Sort
  • Strongly Connected Components (Tarjan's algorithm)
  • Maximum Flow (Ford-Fulkerson algorithm)

Dynamic Programming:

  • Memoization and tabulation
  • Solving problems using dynamic programming (Knapsack problem, Longest Common Subsequence, Matrix Chain Multiplication)

  • Backtracking:

  • Solving constraint satisfaction problems (N-Queens, Sudoku, Subset Sum)

  • Pruning the search space

  • Greedy Algorithms:

  • Activity Selection Problem, Huffman Coding, Fractional Knapsack Problem