Use the Tab and Up, Down arrow keys to select menu items.
This course teaches a range of fundamental algorithms and analyses their complexity.
Algorithms are fundamental to all branches of computer science. They play a key role in the development of efficient computer programs. This course aims to provide a good understanding of fundamental data structures and algorithm design methods used for solving a wide range of problems. The topics covered include:- Introduction to algorithmic thinking and design- Analysis of algorithms (proof techniques, asymptotic notation)- Divide & conquer: design techniques and solving recurrences- Backtracking: Combinatorial search and generation - Graphs: Minimum spanning trees, single-source and all-pair shortest paths, Maximum flow- Algorithms for linear time sorting and order statistics- Advanced data structures: Red-black trees- Computability: reductions, complexity classes, approximation algorithms- Computational Geometry: Convex Hulls (Properties, Gift-wrap algorithm, Graham-scan algorithm), Plane-sweep algorithms (Maximal set, closest pair, line intersections), Range search methods (kD trees, Quadtrees), Polygon triangulation (Ear-clipping algorithm, k-colourable graphs) - Pattern Matching: Knuth-Morris-Pratt Algorithm, Boyer-Moore Algorithm- Optimization Problems: Greedy algorithm (Interval scheduling, Fractional knapsack, Huffman codes), Dynamic programming (Bottom-up enumeration, Principle of optimality, Longest common subsequence, 0/1 Knapsack, Matrix chain product, multi-stage graphs)
Students will develop the necessary skills for designing and implementing efficient algorithms for a wide range of practical problems, and will be able to analyse and compare different algorithms used in an application domain.
(1) COSC121; (2) COSC122; RP: MATH120
COSC202, COSC229, COSC329
MATH120
Depending on final student numbers, some of the advertised lab/tutorial streams may not run. Final lab/tutorial options will be available for self-allocation closer to the start of the semester through My Timetable.
Ramakrishnan Mukundan
Kourosh Neshatian
No assignments will be accepted after the drop-dead date. The penalty for the late submission of an assignment will be an absolute deduction of 15% of the maximum possible mark.
Recommended Reading:• Steven S. Skiena, The Algorithm Design Manual, Springer, 2nd Ed., 2008.• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Ed., The MIT Press, 2009 • Goodrich and Tamassia, Data Structures and Algorithms in Python, John Wiley & Sons, 2013.
Course Information on Learn
There are several important documents available online about departmental regulations, policies and guidelines at the following site. We expect all students to be familiar with these. Notices about this class will be posted to the class forum in the Learn system.COSC students will also be made members of a class called “CSSE Notices”, where general notices will be posted that apply to all classes (such as information about building access or job opportunities).
The Computer Science department's grading policy states that in order to pass a course you must meet two requirements:1. You must achieve an average grade of at least 50% over all assessment items.2. You must achieve an average mark of at least 45% on invigilated assessment items.If you satisfy both these criteria, your grade will be determined by the following University- wide scale for converting marks to grades: an average mark of 50% is sufficient for a C- grade, an average mark of 55% earns a C grade, 60% earns a B- grade and so forth. However if you do not satisfy both the passing criteria you will be given either a D or E grade depending on marks. Marks are sometimes scaled to achieve consistency between courses from year to year. AegrotatsIf factors beyond your control (such as illness or family bereavement) prevent you from completing some item of course work (including laboratory sessions), or prevent you from giving your best, then you may be eligible for aegrotat, impaired performance consideration or an extension on the assessment. Details of these may be found in the University Calendar. Supporting evidence, such as a medical certificate, is normally required. If in doubt, talk to your lecturer.
Domestic fee $778.00
International fee $3,450.00
* All fees are inclusive of NZ GST or any equivalent overseas tax, and do not include any programme level discount or additional course-related expenses.
For further information see Computer Science and Software Engineering .