Tiểu Luận Bài tập lớn phân tích và thiết kế thuật toán

BÀI TẬP LỚN
PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN

Mục lục
1. Bài 1: Sách MIT, Problem 5.2 Câu a,b,c,d. 3
1.1. Phát biểu bài toán. 3
1.2. Lời giải 3
a. Giả code của thuật toán RANDOM-SEARCH 3
b. Tính kì vọng của số lần thử nếu như tồn tại đúng một chỉ số i mà A = x. 3
c. Tính kì vọng của số lần thử nếu như tồn tại k ≥ 1 chỉ số i mà A = x. 4
d. Tính kì vọng của số lần thử nếu như không tồn tại chỉ số i mà A = x. 4
2. Bài 2: Sách MIT, Problem 15-1. 5
2.1. Phát biểu bài toán. 5
2.2. Lời giải 6
a. Thuật toán Bitonic. 6
b. Bài toán đơn giản với 7 điểm 6
c. Đánh giá thuật toán. 9
3. Bài 3: Câu a&d. 10
3.1. Phát biểu bài toán. 10
3.2. Lời giải 10
a. Kì vọng số lượng ô còn trống là bao nhiêu. 10
d. Xác suất để tồn tại một ô có chứa ít nhất 2 lá thăm của khách hàng VIP. 11
4. Bài 4: Thuật toán sắp xếp Bucket Sort 11
4.1. Phát biểu bài toán. 11
4.2. Lời giải 11
a. Thuật toán sắp xếp Bucket Sort 11
b. Điều kiện để Bucket Sort đạt thời gian thực hiện là O(n). 12