College of Engineering and Computer Science (CECS)
Research School of Computer Science
Lecturer: Dr Weifa Liang
Prerequisites6 units of 2000-level COMP courses or enrollment in BComptlSci., COMP2100 or or COMP2500; or COMP2300; and 6 units of 2000-level MATH courses or COMP2600.
This course deals with the study of algorithms for solving practical problems and the data structures used in the implementations of algorithms. Detailed analysis of the resource requirements of algorithms will be an important issue.
A large variety of algorithms are candidates for study. These include, but are not limited to, the following: greedy algorithms, dynamic programming, divide-and-conquer paradigm, basic graph algorithms like BFS and DFS trees, minimum spanning trees, single source shortest path algorithms, all pairs of shortest paths algorithms, advanced data structures such as hash tables, binary search trees, and red-black trees, etc. The mathematical tools used to study the resource usage of algorithms will be considered too.
A good knowledge of algorithms and algorithmic theory is essential for finding efficient solutions to real life problems, and for determining whether such a solution exists in the first place. This course aims to expose students to a variety of algorithms that have practical applications, while conducting detailed analysis of the resource requirements required by the algorithms.
Aims to give the students an exposure to a variety of algorithms that can be used for solving real life problems. This should help them acquire the necessary skills to recognize problem scenarios where such algorithms can be used, to modify an existing algorithm or develop a new one for new problems, and to show that the given problem does not lead itself to an efficient solution, if such be the case. It will also provide further experience in the development of efficient software for nontrivial purposes.
IdeasThis course will carry the main responsibility for:
TopicsThe topics covered could include the following:
SkillsWill acquire a good knowledge of a variety of algorithms that have real-life applications; will further develop skills in the analysis of algorithms; will get some hands-on experience in the design, analysis and implementation of algorithms for some nontrivial problems; will get an exposure to the theory of intractability; will get some experience in how one can go about showing that certain problems are intractable.
ObjectivesUpon completion of this course, the student will:
AssessmentThere will be four quizzes (Q), two assignments (A), one mid-semester exam (M), and one final exam (F). The overall assessment will be based on a 10:35:20:35 weighting for the quizzes, assignments, and the examinations. The final mark is calculated using the following formula:
Total = 0.1Q+0.35A+0.2M+0.35F,
subject to necessary adjustment during the School examination meeting. The departmental policy on plagiarism will be enforced.