Accessibility Skip to Global Navigation Skip to Local Navigation Skip to Content Skip to Search Skip to Site Map Menu

COSC242 Algorithms and Data Structures

Programming in C; structured data types including hash tables, trees, and graphs; analysis of standard sorting and searching algorithms; greedy algorithms and dynamic programming.

This paper extends the variety of data types familiar from COSC 241 and looks more closely at the algorithms that operate on them. Among the new data types to be treated are balanced search trees and graphs. The performance of algorithms is a unifying theme throughout. Students taking this paper will be introduced to another programming language - all practical work will be done in C.

Paper title Algorithms and Data Structures
Paper code COSC242
Subject Computer Science
EFTS 0.1500
Points 18 points
Teaching period Second Semester
Domestic Tuition Fees (NZD) $1,018.05
International Tuition Fees (NZD) $4,320.00

^ Top of page

Prerequisite
COSC 241
Recommended Preparation or Concurrent Study
One MATH, STAT or COMO paper
Schedule C
Arts and Music, Commerce, Science
Teaching Arrangements
There are two lectures and two labs per week.
Textbooks
Recommended:
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein - 3rd edition, MIT Press/McGraw-Hill

For Reference:
The C Programming Language, by Kernighan and Ritchie.
The Unix Programming Environment, by Kernighan and Pike
Course outline
View the course outline for COSC 242
Graduate Attributes Emphasised
Lifelong learning, Scholarship, Communication, Critical thinking, Information literacy, Self-motivation.
View more information about Otago's graduate attributes
Learning Outcomes
This paper will enable students to:
  • Implement a range of data structures and algorithms using the C programming language
  • Classify familiar algorithms in terms of efficiency and present big-O calculations in a clear and logical manner
  • Use proof by contradiction and proof by induction to support efficiency calculations
  • Critically evaluate the factors that should be taken into account when deciding on the data structures and/or algorithms to use for a given purpose
  • Demonstrate understanding of a variety of algorithm designs for optimisation
  • Articulate the differences between complexity classes such as P and NP
Contact
willem@cs.otago.ac.nz
kaye@cs.otago.ac.nz
Teaching staff
Course Co-ordinator: Professor Michael Albert
Lecturer: To be advised
Professional Practice Fellow: Iain Hewson
Paper Structure
The main topics are:
  • Efficiency of algorithms
  • Using proof by contradiction, proof by induction and the iteration method to classify time complexity functions
  • Paradigms in algorithm design, such as divide-and-conquer, greedy strategies and dynamic programming
  • Analysis and comparison of mergesort, quicksort and linear sorts
  • Hashing
  • Self-balancing trees
  • Graph algorithms that extend depth-first and breadth-first traversals
  • P and NP
Assessment:
  • Programming Assignment 15%
  • Practical Tests (3) 3%, 8% and 8%
  • Other Lab Assessments 6%
  • Final Exam 60%

^ Top of page

Timetable

Second Semester

Location
Dunedin
Teaching method
This paper is taught On Campus
Learning management system
None

Computer Lab

Stream Days Times Weeks
Attend one stream from
Y1 Tuesday 09:00-10:50 28-34, 36-41
Y2 Tuesday 12:00-13:50 28-34, 36-41
Y3 Tuesday 14:00-15:50 28-34, 36-41
AND one stream from
Z1 Friday 09:00-10:50 28-34, 36-41
Z2 Friday 12:00-13:50 28-34, 36-41
Z3 Friday 14:00-15:50 28-34, 36-41

Lecture

Stream Days Times Weeks
Attend
L1 Monday 11:00-11:50 28-34, 36-41
Thursday 11:00-11:50 28-34, 36-41

Programming in C; structured data types including hash tables, trees, and graphs; analysis of standard sorting and searching algorithms; greedy algorithms and dynamic programming.

This paper extends the variety of data types familiar from COSC 241 and looks more closely at the algorithms that operate on them. Among the new data types to be treated are balanced search trees and graphs. The performance of algorithms is a unifying theme throughout. Students taking this paper will be introduced to another programming language - all practical work will be done in C.

Paper title Algorithms and Data Structures
Paper code COSC242
Subject Computer Science
EFTS 0.1500
Points 18 points
Teaching period Second Semester
Domestic Tuition Fees Tuition Fees for 2018 have not yet been set
International Tuition Fees Tuition Fees for international students are elsewhere on this website.

^ Top of page

Prerequisite
COSC 241
Recommended Preparation or Concurrent Study
One MATH, STAT or COMO paper
Schedule C
Arts and Music, Commerce, Science
Learning Outcomes
This paper will enable students to:
  • Implement a range of data structures and algorithms using the C programming language
  • Classify familiar algorithms in terms of efficiency and present big-O calculations in a clear and logical manner
  • Use proof by contradiction and proof by induction to support efficiency calculations
  • Critically evaluate the factors that should be taken into account when deciding on the data structures and/or algorithms to use for a given purpose
  • Demonstrate understanding of a variety of algorithm designs for optimisation
  • Articulate the differences between complexity classes such as P and NP
Contact
Computer Science Adviser
Teaching staff
Course Co-ordinator and Lecturer: Associate Professor Brendan McCane
Professional Practice Fellow: Iain Hewson
Paper Structure
The main topics are:
  • Efficiency of algorithms
  • Using proof by contradiction, proof by induction and the iteration method to classify time complexity functions
  • Paradigms in algorithm design, such as divide-and-conquer, greedy strategies and dynamic programming
  • Analysis and comparison of mergesort, quicksort and linear sorts
  • Hashing
  • Self-balancing trees
  • Graph algorithms that extend depth-first and breadth-first traversals
  • P and NP
Assessment:
  • Programming Assignment 15%
  • Practical Tests (3) 3%, 8% and 8%
  • Other Lab Assessments 6%
  • Final Exam 60%
Teaching Arrangements
There are two lectures and two labs per week.
Textbooks
Recommended:
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein - 3rd edition, MIT Press/McGraw-Hill

For Reference:
The C Programming Language, by Kernighan and Ritchie.
The Unix Programming Environment, by Kernighan and Pike
Course outline
View the course outline for COSC 242
Graduate Attributes Emphasised
Lifelong learning, Scholarship, Communication, Critical thinking, Information literacy, Self-motivation.
View more information about Otago's graduate attributes.

^ Top of page

Timetable

Second Semester

Location
Dunedin
Teaching method
This paper is taught On Campus
Learning management system
None

Computer Lab

Stream Days Times Weeks
Attend one stream from
Y1 Tuesday 09:00-10:50 28-34, 36-41
Y2 Tuesday 12:00-13:50 28-34, 36-41
Y3 Tuesday 14:00-15:50 28-34, 36-41
AND one stream from
Z1 Friday 09:00-10:50 28-34, 36-41
Z2 Friday 12:00-13:50 28-34, 36-41
Z3 Friday 14:00-15:50 28-34, 36-41

Lecture

Stream Days Times Weeks
Attend
L1 Monday 11:00-11:50 28-34, 36-41
Thursday 11:00-11:50 28-34, 36-41