CSD201 - Phần 5: Đồ thị

CSD201 - Phần 1: Danh sách và danh sách liên kết

Ứng với CLO1, buổi 1-4. Tương ứng Chương 3 của Goodrich ấn bản 6. Phần mảng nêu cách dùng mảng làm danh sách cùng hai hạn chế cốt lõi là kích thước cố định và chi phí dịch chuyển phần tử khi chèn hoặc xoá ở giữa. Phần danh sách liên kết đơn trình bày cấu trúc nút gồm dữ liệu và con trỏ tới nút kế, cùng bộ thao tác đầy đủ: thêm vào đầu, thêm vào cuối, chèn trước hoặc sau một nút, chèn theo vị trí, tìm kiếm, sửa, xoá, đảo ngược danh sách và sắp xếp. Phần danh sách liên kết đôi bổ sung con trỏ lùi để duyệt được hai chiều và xoá một nút mà không cần biết nút trước nó. Phần danh sách liên kết vòng cho nút cuối trỏ về nút đầu cùng các thao tác tương ứng. Khép lại bằng lý do thư viện Java cung cấp cả ArrayList lẫn LinkedList và tiêu chí chọn giữa hai lớp này.

CSD201 - Phần 2: Ngăn xếp, hàng đợi và hàng đợi ưu tiên

Ứng với CLO2, buổi 5-10. Tương ứng Chương 6 và Chương 9 của Goodrich ấn bản 6. Phần ngăn xếp định nghĩa cấu trúc vào sau ra trước cùng ba thao tác chính đẩy vào, lấy ra và xem đỉnh, kèm các ứng dụng kinh điển như kiểm tra dấu ngoặc cân đối, chuyển biểu thức trung tố sang hậu tố, tính giá trị biểu thức hậu tố, quay lui và mô phỏng lời gọi hàm. Phần hàng đợi định nghĩa cấu trúc vào trước ra trước cùng các thao tác thêm vào cuối và lấy ra ở đầu, các ứng dụng như hàng đợi tác vụ và duyệt theo chiều rộng, cùng hàng đợi hai đầu deque cho phép thêm và xoá ở cả hai phía. Phần hàng đợi ưu tiên giải thích vì sao cần một hàng đợi mà phần tử ra trước là phần tử có độ ưu tiên cao nhất chứ không phải phần tử vào trước. Cả ba cấu trúc đều được cài đặt bằng Java trên nền mảng và trên nền danh sách liên kết.

CSD201 - Phần 3: Đệ quy

Ứng với CLO3, buổi 11-14. Tương ứng Chương 5 của Goodrich ấn bản 6. Phần ý tưởng nêu hai thành phần bắt buộc của mọi thuật toán đệ quy là trường hợp cơ sở để dừng và bước đệ quy thu nhỏ bài toán, cùng ba ví dụ dẫn nhập là hàm giai thừa, tìm kiếm nhị phân và duyệt hệ thống tệp. Phần phân tích hướng dẫn cách lần theo một hàm đệ quy để xác định kết quả mà không cần chạy chương trình, và cách ước lượng độ phức tạp qua số lời gọi. Phần phân loại phân biệt đệ quy tuyến tính với một lời gọi, đệ quy nhị phân với hai lời gọi như dãy Fibonacci, và đệ quy bội với nhiều nhánh, kèm ví dụ và so sánh. Phần thiết kế đưa ra quy trình xây dựng một thuật toán đệ quy từ bài toán thực tế. Khép lại bằng kỹ thuật khử đệ quy đuôi và bảng so sánh ưu nhược điểm giữa đệ quy và lặp.

CSD201 - Phần 4: Cây, cây tìm kiếm nhị phân, AVL và heap

Ứng với CLO4, buổi 15-28, là phần dài nhất của môn. Tương ứng Chương 8 và Chương 11 của Goodrich ấn bản 6. Phần cây tổng quát định nghĩa cây, gốc, cha, con, lá, độ sâu, chiều cao cùng kiểu dữ liệu trừu tượng cây. Phần cây nhị phân trình bày tính chất về số nút và chiều cao, các cách cài đặt, và bốn phép duyệt trước - giữa - sau - theo mức. Phần cây tìm kiếm nhị phân là trọng tâm: tính chất thứ tự, thao tác tìm kiếm, chèn, xoá với ba trường hợp nút lá, nút một con và nút hai con, tìm phần tử nhỏ nhất và lớn nhất, đếm số nút và tính chiều cao, cùng độ phức tạp của từng thao tác và lý do cây suy biến làm hỏng hiệu năng. Phần cây cân bằng giới thiệu cây AVL với hệ số cân bằng và bốn phép quay khi chèn hoặc xoá. Khép lại bằng heap, tính chất heap và ứng dụng làm hàng đợi ưu tiên.