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,059.15 |
| International Tuition Fees (NZD) | $4,627.65 |
- Prerequisite
- COSC 241
- Recommended Preparation or Concurrent Study
- One MATH, STAT or COMO paper
- Schedule C
- Arts and Music, Commerce, Science
- Contact
- Computer Science Adviser
- More information link
- View more information about COSC 242
- 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
- Hashing
- Binary tres and binary search trees
- 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. - 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
