School of Electronics and Computer Science:
COMP1009 Data Structures and Algorithms

Basic Information

School	Dept- Electronics & Computer Science
Known as	COMP1009.
Status	This syllabus is still provisional.
Session and Semester	Semester Two, 2011 - 2012
Credit	10 Credit Points
Unit Leader	Dr Adam Prugel-Bennett
Moderators	Dr Kirk Martinez
Study	25 hours
Assessment	Examination 85%, Tutorials 15%
Coursework	1 practical
Teaching	Lectures 20
Prerequisites and Exclusions	Prerequisites: (COMP1003 - Advanced Programming or COMP1005 - System Administration Tools and Techniques) and COMP1004 - Programming Principles.
Referral	On referral, this unit will be assessed 100% by examination.
Syllabus Approved

Description

Aims

• Examine the most important data structures in use in computers today
• Understand the algorithms that efficiently use those data structures
• Reinforce and extend the understanding and programming of Java

Learning Outcomes

Knowledge and Understanding

Having successfully completed the module, you will be able to demonstrate knowledge and understanding of:

• Knowledge of common data structures and algorithms
• Understanding of time complexity
• Understanding of how to code data structures using object oriented methods
• Knowledge of Java collection class

Intellectual Skills

Having successfully completed the module, you will be able to:

• To choose the most appropriate data structure for a particular problem
• Be familiar with a number of important computer algorithms using those structures
• Understand how to evaluate an algorithm for efficiency

Practical Skills

Having successfully completed the module, you will be able to:

• Have a greater confidence to write programs in Java
• Be able to code a simple data structure
• Be able to use data structures to build complex algorithms

General Transferable (key) Skills

Having successfully completed the module, you will be able to:

• Be able to solve problems algorithmically

Topics Covered

• Introduction
  • Data Objects, Data Structures, Complex Data Structures
• Simple Data Structures
  • List, Stack, Queue, Tree, Tree traversal
• Algorithm Analysis
  • The big O
• Sorting
  • Selection Sort, Insertion Sort, Shellsort, MergeSort, QuickSort, Bucket Sort, Radix sort, External sorting
• Searching
  • Sequential Search, Handling Failure, Binary Search, Binary Tree Search,
• Advanced Tree Structures
  • AVL Trees, Retaining Balance, Single Rotation, Double Rotation
  • Splay Trees, Red-black Trees, B-trees
• Hash tables
  • Terminology, Hash table size, Hash function collision resolution, Separate chaining, Open Addressing, Re-hashing
• Priority Queues (Heaps)
  • Terminology, Simple implementations, Binary heaps, Heap sort
• Graphs
  • Terminology, Adjacency Matrix and List, Connectivity, Shortest path algorithms, Unweighted graphs, Breadth first search, Weighted Graphs, Minimum Spanning Tree, Prim's algorithm

Resources

Core Resources

• Weiss MA, Data Structures and Algorithm Analysis in Java 2nd Edition, Addison-Wesley 2006. [Library] [Shops]

Background Resources

• Collins W Data Structures and the Java Collections Framework 2nd Edition, McGraw-Hill 2004. [Library] [Shops]
• Main M, Data Structures and Other Objects Using Java 3rd Edition, Addison Wesley 2005. [Library] [Shops]

Taught to

COMP1009

Pt I BSc Computer Science (Compulsory)
Pt I MEng Computer Science with Artificial Intelligence (Compulsory)
Pt I MEng Computer Science (Compulsory)
Pt I MEng Computer Science with Distributed Systems & Networks (Compulsory)
Pt I MEng Computer Science with Image and Multimedia Systems (Compulsory)
Pt I MEng Computer Science with Mobile and Secure Systems (Compulsory)
ECS Socrates Students (Optional)
Pt I BEng Software Engineering (Compulsory)
Non-existing cohort: "seMEng1" (Compulsory)

Students who are not registered on an ECS approved programme may take this module subject to meeting its pre-requisites and the availability of resources. To confirm this, please can you contact the module leader (as listed above) in the first instance. They will then refer you on to the appropriate director of studies for formal approval of your selection.

Change Log

2012-01-17 10:39:48.740 - apb
2011-04-04 18:59:37.070 - Roll script