Package 2 · Design an Algorithm (Thiết kế thuật toán)
Thuộc Curriculum Computer Science.
Tôi nghĩ ra được cách giải và kiểm tra nó trên giấy, trước khi viết dòng code đầu tiên.
Thuật toán đúng thôi chưa đủ, nó còn phải trả giá được. Chạy tay trên giấy và hỏi nó lớn lên thế nào theo dữ liệu là hai thói quen tách người thiết kế lời giải khỏi người chỉ gõ code.
| Module | 4 |
| Unit | 13 |
| Mastery level | 2 tới 12 |
| Lớp (VN) | 2 tới 12 |
| Key concept chính | Systems (Hệ thống) · Development (Phát triển) |
Module trong package
| Module | Nội dung | Unit |
|---|---|---|
| 2.1 · Steps that work (Các bước chạy được) | Thuật toán là dãy bước không mơ hồ | 3 |
| 2.2 · Choose a strategy (Chọn cách tiếp cận) | Nhiều cách đúng, khác nhau ở cái giá | 4 |
| 2.3 · Cost of a solution (Cái giá của lời giải) | Nhanh chậm, tốn ít tốn nhiều | 3 |
| 2.4 · Will it always work (Nó có luôn đúng không) | Trường hợp biên và trường hợp xấu nhất | 3 |
Toàn bộ unit
| Unit | Mastery level (B21) | Lớp (VN) | Key concept |
|---|---|---|---|
| 2.1.1 Unambiguous instructions (Chỉ dẫn không mơ hồ) | 2-6 | 2-7 | Communication |
| 2.1.2 Order, choice, repetition (Tuần tự, rẽ nhánh, lặp) | 4-9 | 4-10 | Systems |
| 2.1.3 Trace it by hand (Chạy tay từng bước) | 5-10 | 6-11 | Systems |
| 2.2.1 More than one right answer (Không chỉ một cách đúng) | 5-10 | 6-11 | Development |
| 2.2.2 Search and sort (Tìm kiếm và sắp xếp) | 7-11 | 8-12 | Patterns |
| 2.2.3 Divide and conquer (Chia để trị) | 9-12 | 10-12 | Systems · Patterns |
| 2.2.4 Recursion (Đệ quy) | 9-12 | 10-12 | Patterns · Models |
| 2.3.1 Count the steps (Đếm số bước) | 8-12 | 9-12 | Relationships |
| 2.3.2 How it grows with input (Nó lớn lên thế nào theo dữ liệu) | 9-12 | 10-12 | Relationships · Patterns |
| 2.3.3 Time against memory (Đánh đổi thời gian và bộ nhớ) | 10-12 | 11-12 | Development |
| 2.4.1 The empty and the huge case (Trường hợp rỗng và trường hợp khổng lồ) | 7-12 | 8-12 | Evidence |
| 2.4.2 Worst case, not lucky case (Trường hợp xấu nhất, không phải may mắn) | 9-12 | 10-12 | Evidence |
| 2.4.3 Argue that it terminates (Lập luận rằng nó dừng) | 10-12 | 11-12 | Systems |
Chỗ hay bị bỏ qua
Unit 2.1.3 rẻ tiền và bị bỏ nhiều nhất. Chạy tay thuật toán trên giấy với một bộ dữ liệu nhỏ bắt được phần lớn lỗi logic trước khi learner ngồi vào máy, và tiết kiệm hàng giờ gỡ lỗi. Learner bỏ qua bước này vì nó chậm, rồi mất nhiều thời gian hơn ở Package 4.
Unit 2.3.2 là chỗ nhiều learner giỏi code vẫn hụt. Một chương trình chạy tốt với 100 phần tử và treo cứng với 100 nghìn phần tử không phải chương trình chậm, nó là chương trình sai về mặt độ phức tạp. Nhận ra khác biệt này là bước sang tư duy kỹ sư.