COMP2230
10 units
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.
Availability2024 Course Timetables
Callaghan
- Semester 2 - 2024
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
- Preliminaries (review of basic mathematical notions, data structures, induction, basic combinatorics).
- Elementary algorithmics (worst-case vs. average case, basic examples, elementary operations).
- Asymptotic Notation (big O, Omega and Theta).
- Analysis of Algorithms (loops, recurrence relations).
- Data structures (graphs, trees, heaps, disjoint sets).
- Searching and sorting
- Greedy algorithms.
- Divide-and-Conquer.
- Dynamic programming.
- Text-serach Algorithms.
- Introduction to the topics of computational complexity, heuristics, metaheuristics and approximation algorithms.
Assumed knowledge
SENG1120MATH1510
Assessment items
Quiz: Test 1 Quiz
In Term Test: Midterm Exam
Quiz: Test 2 Quiz
Written Assignment: Assignment 1
Quiz: Test 3 Quiz
Formal Examination: Formal Exam
Compulsory Requirement: Pass requirement - Must pass this assessment item to pass the course.
Written Assignment: Assignment 2
Compulsory Requirement: Pass requirement 40% - Must obtain 40% in this assessment item to pass the course.
Contact hours
Semester 2 - 2024 - Callaghan
Lecture-1
- Face to Face On Campus 2 hour(s) per week(s) for 13 week(s) starting in week 1
Tutorial-1
- Face to Face On Campus 2 hour(s) per week(s) for 13 week(s) starting in week 1
Course outline
Course outline not yet available.
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.