COSC262-20S1 (C) Semester One 2020

Algorithms

15 points

Details:
Start Date: Monday, 17 February 2020
End Date: Sunday, 21 June 2020
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Friday, 28 February 2020
  • Without academic penalty (including no fee refund): Friday, 29 May 2020

Description

This course teaches a range of fundamental algorithms and analyses their complexity.

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.

A selection of topics from the following (non-exclusive) list is covered:
• Introduction to algorithmic thinking and design
• Analysis of algorithms (proof techniques, asymptotic notation)
• Divide & conquer: recursive design techniques and solving recurrences
• Greedy algorithms: Coin changing, Interval scheduling, Fractional knapsack, Huffman codes
• Dynamic programming: Top-down approach, Bottom-up enumeration, Optimal substructure, Optimal coin changing, Minimum cost path in grid, Multi-stage graphs, Unbounded knapsack, 0/1 knapsack, Edit distance, Longest common subsequence, Dynamic time warping
• Computational geometry: Convex hulls (properties, Gift-wrap algorithm, Graham-scan algorithm), Plane-sweep algorithms (closest pair, line intersections), Range search methods (kD trees, Quadtrees)
• Graphs: Topological ordering, Minimum spanning trees, Single-source and All-pair shortest paths
• Backtracking: combinatorial search and generation
• String matching: Rabin-Karp algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm.

Learning Outcomes

  • After successful completion of this course, students will be able to:
  • Understand and describe the behaviour of algorithms.
  • Reason informally about the correctness of programs.
  • Analyse the complexity of algorithms.
  • Implement algorithms given their high level descriptions.
  • Implement both top-down and bottom-up dynamic programming techniques.
  • Develop and implement divide and conquer algorithms.
  • Comfortably implement recursive algorithms.
  • Implement a range of classical graph algorithms.
  • Implement a range of classical computational geometry algorithms.
  • Appreciate the merits of standard string matching algorithms.

Pre-requisites

(1) COSC121; (2) COSC122; RP: MATH120

Restrictions

COSC202, COSC229, COSC329

Recommended Preparation

Timetable 2020

Students must attend one activity from each section.

Lecture A
Activity Day Time Location Weeks
01 Wednesday 16:00 - 17:00 - (25/3, 22/4-27/5)
A1 Lecture Theatre (19/2-18/3)
17 Feb - 29 Mar
20 Apr - 31 May
Lecture B
Activity Day Time Location Weeks
01 Tuesday 10:00 - 11:00 - (24/3, 21/4-26/5)
C1 Lecture Theatre (18/2-17/3)
17 Feb - 29 Mar
20 Apr - 31 May
Lecture C
Activity Day Time Location Weeks
01 Monday 12:00 - 13:00 - (23/3, 20/4, 4/5-25/5)
K1 Lecture Theatre (17/2-16/3)
17 Feb - 29 Mar
20 Apr - 26 Apr
4 May - 31 May
Computer Lab A
Activity Day Time Location Weeks
01 Monday 10:00 - 12:00 - (23/3, 20/4, 4/5-25/5)
Jack Erskine 131 Lab 1 (17/2-16/3)
17 Feb - 29 Mar
20 Apr - 26 Apr
4 May - 31 May
02 Monday 16:00 - 18:00 - (23/3, 20/4, 4/5-25/5)
Jack Erskine 131 Lab 1 (17/2-16/3)
17 Feb - 29 Mar
20 Apr - 26 Apr
4 May - 31 May
03 Wednesday 10:00 - 12:00 - (25/3, 22/4-27/5)
Jack Erskine 131 Lab 1 (19/2-18/3)
17 Feb - 29 Mar
20 Apr - 31 May
04 Wednesday 12:00 - 14:00 - (25/3, 22/4-27/5)
Jack Erskine 131 Lab 1 (19/2-18/3)
17 Feb - 29 Mar
20 Apr - 31 May
05 Tuesday 16:00 - 18:00 - (24/3, 21/4-26/5)
Jack Erskine 131 Lab 1 (18/2-17/3)
17 Feb - 29 Mar
20 Apr - 31 May
06 Thursday 11:00 - 13:00 - (23/4-28/5)
Jack Erskine 131 Lab 1 (20/2-19/3)
17 Feb - 22 Mar
20 Apr - 31 May
07 Thursday 13:00 - 15:00 - (23/4-28/5)
Jack Erskine 136 Lab 4 (20/2-19/3)
17 Feb - 22 Mar
20 Apr - 31 May

Examination and Formal Tests

Test A
Activity Day Time Location Weeks
01 Tuesday 09:00 - 21:00 27 Apr - 3 May
Test B
Activity Day Time Location Weeks
01 Monday 09:00 - 21:00 18 May - 24 May

Timetable Note

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.

Course Coordinator / Lecturer

Richard Lobb

Lecturer

Kourosh Neshatian

Assessment

Assessment Due Date Percentage  Description
Weekly online quizzes Weekly quizzes totalling 20% of the course.
Assignment one super-quiz
Lab test
Assignment two super-quiz
Final Exam


Updated Semester One 2020 assessment deadlines and details will be available once finalised.

Textbooks / Resources

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.

Notes

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).

Additional Course Outline Information

Grade moderation

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.

Students may apply for special consideration if their performance in an assessment is affected by extenuating circumstances beyond their control.

Applications for special consideration should be submitted via the Examinations Office website within five days of the assessment.

Where an extension may be granted for an assessment, this will be decided by direct application to the Department and an application to the Examinations Office may not be required.

Special consideration is not available for items worth less than 10% of the course.

Students prevented by extenuating circumstances from completing the course after the final date for withdrawing, may apply for special consideration for late discontinuation of the course. Applications must be submitted to the Examinations Office within five days of the end of the main examination period for the semester.

Indicative Fees

Domestic fee $867.00

International fee $4,250.00

* Fees include New Zealand GST and do not include any programme level discount or additional course related expenses.

For further information see Computer Science and Software Engineering.

All COSC262 Occurrences

  • COSC262-20S1 (C) Semester One 2020