# 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 COSC242 Computer Science 0.1500 18 points Second Semester \$1,038.45 \$4,492.80
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
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
Lifelong learning, Scholarship, Communication, Critical thinking, Information literacy, Self-motivation.

## 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