|
| 1.
| [Basic algorithm design technique]
Understand basic techniques for designing algorithms, including the techniques of recursion, divide-and-conquer, and greedy. |
| 2.
| [Advanced algorithm design technique]
Understand advanced techniques for designing algorithms, including dynamic programming, network flow and problem reduction. |
| 3.
| [Correctness and time complexity]
Understand the techniques of proof by contradiction, mathematical induction and recurrence relation, and apply them to prove the correctness and to analyze the running time of algorithms. |
| 4.
| [Intractability]
Understand the mathematical criterion for deciding whether an algorithm is efficient, and know many practically important problems that do not admit any efficient algorithms. |
| 5.
| [Program solving]
Able to apply the algorithm design techniques to design efficient algorithms for different kinds of problems |
Mapping from Course Learning Outcomes to Programme Learning Outcomes
| | PLO a | PLO b | PLO c | PLO d | PLO e | PLO f | PLO g | PLO h | PLO i | PLO j |
| CLO 1 | T,P | | | | | | | | | |
| CLO 2 | T,P | | | | | | | | | |
| CLO 3 | T,P | | T,P | | | | | | | |
| CLO 4 | T,P | | T,P | | | | | | | |
| CLO 5 | | | T,P | | | | | | | |
T - Teach, P - Practice
For BEng(CompSc) Programme Learning Outcomes, please refer to
here.
|
| Syllabus |
|
Calendar Entry:
The course introduces various algorithm design techniques, including divide and conquer, greedy, and dynamic programming, and studies selected topics on graph algorithms. These techniques can be used to design better algorithms in various areas of computer science. The course also gives an overview of NP-complete problems.
|
|
Detailed Description:
| Basic algorithm design technique |
Mapped to CLOs
|
| Divide and Conquer | 1, 3, 5 |
| Greedy algorithms | 1, 3, 5 |
| Graph algorithms | 1, 3, 5 |
| Advanced algorithm design technique |
Mapped to CLOs
|
| Dynamic programming | 2, 3, 5 |
| Network flow | 2, 3, 5 |
| Intractability |
Mapped to CLOs
|
| Problem reduction and NP-completeness | 2, 3, 4, 5 |
| Approximation Algorithms | 3, 4, 5 |
|
|
Assessment:
Continuous Assessment:
50%
Written Examination:
50%
|
| Teaching Plan |
|
Please refer to the corresponding Moodle course.
|
| Moodle Course(s) |
|
|
