CS4335Design and Analysis of Algorithms

这门课学什么

课程简介

This course aims to introduce the algorithms in various domains, and techniques for designing efficient algorithms. It trains students the ability to analyse algorithms and the skills to design solutions to problems.

校方 PDF 第 2 页 · Abstract

课程内容

Keyword Syllabus Algorithm analysis. Algorithm design: divide-and-conquer approach, greedy approach. Graph algorithms: graph searching, topological sort, minimum spanning tree, shortest paths, backtracking and its applications in games. String matching. Dynamic programming and longest common subsequence. Theory of NP-completeness. Turing machines and the halting problem. Introduction to computational complexity. Syllabus • 1. Algorithm analysis Review on program correctness and complexities, and the mathematical tools for analysis. • Graph algorithms Representation of graphs. Algorithms for graph searching. Topological sort. Minimum spanning trees. Greedy design approach. Shortest paths, transitive closure and their relations with matrix multiplication. Backtracking and applications in games. • String algorithms String matching. Longest common subsequence. Dynamic programming. • Theory of NP-completeness Problem reduction. P and NP. Some NP-complete problems. Approximation algorithms.

校方 PDF 第 4 页 · Keyword Syllabus; Syllabus

预期学习成果

查看校方学习成果与对应条件

Course Intended Learning Outcomes (CILOs)
               CILOs                                                Weighting (if DEC-A1        DEC-A2          DEC-A3
                                                                    app.)
1              Prove the correctness and analyse the running                          x         x
               time and performance of the major algorithms
               for those classic problems in various domains.
2              Apply algorithmic paradigms and methods by                             x         x
               using design techniques to solve problems.
3              Investigate the complexities of various problems                                 x
               in different domains.
4              Propose new solutions for problems through
               independent study.


A1: Attitude
Develop an attitude of discovery/innovation/creativity, as demonstrated by students possessing a strong sense of curiosity,
asking questions actively, challenging assumptions or engaging in inquiry together with teachers.

A2: Ability
Develop the ability/skill needed to discover/innovate/create, as demonstrated by students possessing critical thinking skills
to assess ideas, acquiring research skills, synthesizing knowledge across disciplines or applying academic knowledge to
real-life problems.

A3: Accomplishments
Demonstrate accomplishment of discovery/innovation/creativity through producing /constructing creative works/new
artefacts, effective solutions to real-life problems or new processes.

校方 PDF 第 2 页 · Course Intended Learning Outcomes (CILOs)

我能不能修这门课

先修、建议先备和并修要求分别查看；等同及互斥条件也会影响选课。and 表示同时满足，or 表示备选；组合条件按下方原文分组阅读。

先修条件

无（校方注明 Nil）

校方 PDF 第 1 页 · Prerequisites

建议先备知识

CS2468 Data Structures and Data Management or CS3334 Data Structures or EE2331 Data Structures and Algorithms, or equivalent

校方 PDF 第 1 页 · Precursors

并修要求

本页尚无已核实的这一项信息。

其他修读要求

本页尚无已核实的这一项信息。

等同课程及条件

无（校方注明 Nil）

校方 PDF 第 1 页 · Equivalent Courses

互斥课程及条件

无（校方注明 Nil）

校方 PDF 第 1 页 · Exclusive Courses

怎么考，怎样才算通过

考核方式

Continuous assessment: 30%; Examination: 70%; Examination duration: 2 hours

各项考核占多少分

考核项目	比重	生成式 AI 使用	备注与限制
AssignmentsCILO 1, 2, 3, 4	30%	原表未列明	原表未列明

查看校方原始考核表与使用要求

Assessment Tasks / Activities (ATs)


3      CS4335: Design and Analysis of Algorithms




                        ATs                   CILO No.       Weighting (%)       Remarks ("-" for    Allow Use of
                                                                                 nil entry)          GenAI?
1                       Assignments           1, 2, 3, 4     30                  -                   No

Continuous Assessment (%)
30

Examination (%)
70

Examination Duration (Hours)
2

Minimum Examination Passing Requirement (%)
30

Additional Information for ATs
For a student to pass the course, at least 30% of the maximum mark for the examination must be obtained.

通过条件

Minimum Examination Passing Requirement (%) 30 Additional Information for ATs For a student to pass the course, at least 30% of the maximum mark for the examination must be obtained.

校方 PDF 第 3 页 · Additional Information for ATs