CSD201 - Cấu trúc dữ liệu và giải thuật
CSD201 - Cấu trúc dữ liệu và giải thuật (Data Structures and Algorithms) là môn học 3 tín chỉ của Đại học FPT, học sau PRO192, gắn kết cấu trúc dữ liệu với thuật toán thao tác trên nó và với phân tích độ phức tạp, cài đặt toàn bộ bằng Java theo giáo trình Data Structures and Algorithms in Java của Goodrich, Tamassia và Goldwasser. Nội dung môn học bao quát trọn bộ chương trình 60 buổi theo tám chuẩn đầu ra CLO1 đến CLO8: danh sách (mảng và hạn chế của mảng, danh sách liên kết đơn với các thao tác thêm đầu - thêm cuối - chèn trước - chèn sau - chèn theo vị trí - tìm kiếm - sửa - xoá - đảo ngược - sắp xếp, danh sách liên kết đôi, danh sách liên kết vòng, so sánh với ArrayList và LinkedList của thư viện Java); ngăn xếp và hàng đợi (định nghĩa và các thao tác cơ bản, ứng dụng của ngăn xếp, hàng đợi, hàng đợi hai đầu deque, hàng đợi ưu tiên và lý do cần nó, cài đặt bằng Java); đệ quy (ý tưởng đệ quy, hàm giai thừa, tìm kiếm nhị phân đệ quy, duyệt hệ thống tệp, phân tích thuật toán đệ quy, đệ quy tuyến tính - đệ quy nhị phân - đệ quy bội, thiết kế thuật toán đệ quy, khử đệ quy đuôi, so sánh đệ quy với lặp); cây (cây tổng quát và các tính chất, kiểu dữ liệu trừu tượng cây, cây nhị phân và tính chất, cách cài đặt cây, bốn phép duyệt cây, cây tìm kiếm nhị phân với tìm kiếm - chèn - xoá và phân tích độ phức tạp, cây cân bằng và cây AVL với các phép quay, heap và ứng dụng); đồ thị (đồ thị vô hướng và có hướng, đỉnh - cạnh - kề - liên thuộc, ba cách biểu diễn bằng danh sách cạnh - danh sách kề - ma trận kề, duyệt theo chiều sâu và chiều rộng, bài toán đường đi ngắn nhất và thuật toán Dijkstra, cây khung nhỏ nhất với thuật toán Prim-Jarník và Kruskal, chu trình và đường đi Euler cùng điều kiện tồn tại, chu trình Hamilton và thuật toán quay lui, tô màu đồ thị); sắp xếp (sắp xếp chọn, sắp xếp chèn, sắp xếp nổi bọt, sắp xếp nhanh, sắp xếp trộn, sắp xếp vun đống, sắp xếp theo cơ số và sắp xếp theo thùng, so sánh các thuật toán sắp xếp về độ phức tạp và tính ổn định); băm (khái niệm băm, hàm băm và bảng băm, các loại hàm băm chia dư và gấp, va chạm và xử lý va chạm bằng địa chỉ mở với dò tuyến tính và dò bậc hai, bằng nối chuỗi riêng và nối chuỗi hợp nhất, hệ số tải và tái băm, hàm băm hoàn hảo và băm mở rộng); cùng xử lý văn bản (bài toán so khớp mẫu, thuật toán vét cạn, thuật toán Knuth-Morris-Pratt, nén văn bản với mã Huffman, thuật toán LZW và mã hoá độ dài loạt).