Available in 2021
Course code

COMP2230

Units

10 units

Level

2000 level

## Course handbook

### Description

This course introduces students to the notion of efficiency and computational complexity. The basic data structures encountered in first year, such as lists, trees and graphs, are reviewed in light of their efficiency and common usage scenario. Asymptotic measures of complexity are covered, and recurrence relations are introduced as an analytical tool. Problem-solving techniques such as the greedy strategy, divide-and-conquer, dynamic programming, and graph searching are covered. These techniques are illustrated upon optimization problems chosen for their practical relevance.

### Availability2021 Course Timetables

#### Callaghan

• Semester 2 - 2021

### Learning outcomes

On successful completion of the course students will be able to:

1. apply basic techniques to analyse the performance of algorithms

2. explain the most important algorithms used in various common computer science applications;

3. apply efficient algorithm design techniques and understand the limitations of algorithms.

### Content

1. Preliminaries (review of basic mathematical notions, data structures, induction, basic combinatorics).
2. Elementary algorithmics (worst-case vs. average case, basic examples, elementary operations).
3. Asymptotic Notation (big O, Omega and Theta).
4. Analysis of Algorithms (loops, recurrence relations).
5. Data structures (graphs, trees, heaps, disjoint sets).
6. Searching and sorting
7. Greedy algorithms.
8. Divide-and-Conquer.
9. Dynamic programming.
10. Text-serach Algorithms.
11. Introduction to the topics of computational complexity, heuristics, metaheuristics and approximation algorithms.

SENG1120

MATH1510

### Assessment items

Quiz: Test 1 Quiz

In Term Test: Midterm 1

Quiz: Test 2 Quiz

In Term Test: Midterm 2

Written Assignment: Assignment

Quiz: Test 3 Quiz

Formal Examination: Formal Examination *

* This assessment has a compulsory requirement.

### Compulsory Requirements

In order to pass this course, each student must complete ALL of the following compulsory requirements:

#### Course Assessment Requirements:

• Formal Examination: Minimum Grade / Mark Requirement - Students must obtain a specified minimum grade / mark in this assessment item to pass the course. - Students whose overall mark in the course is 50% or more, but who score less than 40% in the compulsory item and thus fail to demonstrate the required proficiency, will be awarded a Criterion Fail grade, which will show as FF on their formal transcript. However, students in this position who have scored at least 25% in the compulsory item will be allowed to undertake a supplementary 'capped' assessment in which they can score at most 50% of the possible mark for that item.

### Contact hours

#### Callaghan

##### Lecture

Face to Face On Campus 2 hour(s) per Week for Full Term

##### Tutorial

Face to Face On Campus 2 hour(s) per Week for Full Term

The University of Newcastle acknowledges the traditional custodians of the lands within our footprint areas: Awabakal, Darkinjung, Biripai, Worimi, Wonnarua, and Eora Nations. We also pay respect to the wisdom of our Elders past and present.