COMP 2009 Data Structures and Algorithms

Credit Points 10

Legacy Code 300103

Coordinator Dongmo Zhang Opens in new window

Description This unit introduces students to fundamental data structures and algorithms used in computing. The material covered forms the basis for further studies in programming and software engineering in later units and for further training in programming skills. The unit focuses on the ideas of data abstraction and algorithm efficiency. The issues of computational complexity of algorithms are addressed throughout the semester. The topics covered include the fundamental abstract data types (lists, stacks, queues, trees, hash tables, graphs), recursion, complexity of algorithms, sorting and searching algorithms, binary search trees and graphs.

School Computer, Data & Math Sciences

Student Contribution Band HECS Band 2 10cp

Check your HECS Band contribution amount via the Fees page.

Level Undergraduate Level 2 subject

Pre-requisite(s) COMP 2014 OR
COMP 2015 OR
COMP 2016 OR
ENGR 1045

Learning Outcomes

On successful completion of this subject, students should be able to:
  1. Select appropriate data structures to solve moderately complex programming problems.
  2. Discuss time and space tradeoffs among different data structures that could be used to represent specific information.
  3. Perform time-complexity analysis against multiple implementations of various abstract data types.
  4. Write programs that use the fundamental abstract data types: linked list, stack, queue, hash table, binary search tree, heap, graph.
  5. Select efficient sorting and searching algorithms to solve moderately complex programming problems.

Subject Content

- Basic concepts: abstract data types, Big-O concept and Complexity analysis.
- Stacks and queues: ADT specification, implementation strategies and applications.
- variations of linked lists: Doubly linked lists and circular lists.
- recursion: recursive functions and divide-and-conquer approach.
- trees: Binary trees, Binary search trees, AVL trees, and heaps.
- Graphs: Adjacency matrix and Adjacency list implementations, depth-first search, breadth-first search, and minimum spanning tree algorithms.
- Searching: Sequential search, Binary search and hashing.
- Elementary sorting algorithms: insertion sort, selection sort, and bubble sort.
- advanced sorting algorithms: quick sort, heap sort, and shell sort.

Assessment

The following table summarises the standard assessment tasks for this subject. Please note this is a guide only. Assessment tasks are regularly updated, where there is a difference your Learning Guide takes precedence.

Item Length Percent Threshold Individual/Group Task
Practicals: A total of 12 face-to-face practical sessions: 10 sessions for programming and 2 sessions for assignment demonstration 2 hours (each practical) 14 N Individual
Quiz : 6 x online Quizzes 30 minutes each 6 N Individual
Applied Project: Two assignments with comprehensive algorithm and data structure design, implementation and complexity analysis tasks Around 600-800 lines of code and up to 4 A4 pages of algorithm description and analysis for each assignment 30 N Individual
Final Exam: Open book exam Two-hour 50 N Individual

Prescribed Texts

  • Malik, D.S. (2010). Data Structures Using C++ . (2nd ed.). Cengage Learning/Course Technology

Teaching Periods

2022 Semester 1

Penrith (Kingswood)

Day

Subject Contact Dongmo Zhang Opens in new window

View timetable Opens in new window

Parramatta - Victoria Rd

Day

Subject Contact Dongmo Zhang Opens in new window

View timetable Opens in new window