Modules | CSCU9A3 | Syllabus CSCU9A3 | Syllabus Updated 1/09/17 13:25
CSCU9A3 - Data Structures & Algorithms Autumn 2016
Data Structures & Algorithms Autumn 2016

Organisation

Organisation

Syllabus

#### Lecturer

Dr David Cairns (Coordinator), Rm 4B87 dec@cs.stir.ac.uk

#### Credits

20 credits at SCQF level 8

#### Prerequisites

CSCU9A2, MATU9D1 is strongly recommended

#### Learning Outcomes

The emphasis of this module is on learning how to build larger pieces of software out of components (i.e. objects and modularization), and using this knowledge as a learning platform for fundamental data structures and algorithms. By the end of the module students will:

• Develop skill in using objects and modularization to build larger pieces of software.
• Develop a firm grasp of fundamental data structures and algorithms, comprising
• how they work;
• their benefits and consequences.
• Understand recursion as well as divide & conquer as two in a larger set of tools.
• Be introduced to algorithmic analysis as a way to assess efficiency.
• Improve their skills in computational thinking.

In order to complete the module, you should be able to demonstrate the ability to apply related theory and techniques to unseen problems without reference to notes, to work independently and under a time constraint.

#### Contents

Modularizing software using OO approach

• Quick Java review;
• Classes and their instantiations;
• Use of classes and objects;
• Separation between a value and a reference in memory.

Data Structures

• Abstract Data Types;
• Lists, stacks, queues;
• Hash tables (maps/sets), heaps (priority queues).

Recursion, Trees

• Recursion introduced in the context of pre-, in-, and post-order traversals of trees,
• Comparing/contrasting recursive vs. iterative approaches.

Algorithms

• Searches: quick review
• Sorts: merge-sort, quick-sort, heap-sort

• How algorithmic qualities emerge naturally from some data structures
• Binary search trees,
• Introduction to graph representations,
• ‘Visitation’, i.e., breadth-first search and depth-first search.

Algorithms in the ‘Real World’

#### Assessment

• Checkpoints 15%
• Assignment 45%
• Examination 40%

#### Module requirements

In assessing a student's grade for the module, the Examiners require that a student must:

Submit the assessed coursework
Non-submission of the assessed coursework will result in the award of Fail for the module as a whole, due to failure to comply with published requirements. Assessed coursework submitted late will be accepted up to seven calendar days after the submission date (or expiry of any agreed extension) but the mark will be lowered by 3 points per day or part thereof. After seven days the piece of work will be deemed a non-submission, and will result in the award of Fail for the module as a whole. This rule (regarding coursework) may be relaxed for students who can show good cause for failure to submit. "Good cause" may include illness (for which a medical certificate or other evidence will be required).
Attend the examination
If a student is unable to attend the Main examination, he/she must apply to the Student Programmes Office for a Deferred examination. If a Deferred examination is not granted, then the Examiners may allow a Resit examination. A student who attends neither the main exam nor the Resit/Deferred exam will be awarded Fail for the module as a whole.
Students who obtain an overall Fail for the module, or a mark in the range 0-39, following the main examination will be eligible for a Resit examination. The overall mark awarded following a Resit examination is calculated from the original checkpoint and assignment achievements together with the better of the original and new exam marks, and is capped at 40.

#### Discretionary repeat assessments

In exceptional circumstances, a student who has not met all the module requirements, following the Main examination period, may be permitted a discretionary repeat. This may be a repeat class test. Repeats are not permitted for laboratory checkpoints or group work. The mark following any repeat assessment is capped at 40. If you are granted a discretionary repeat assessment but do not attempt it, you will be awarded grade X for the module.

In deciding whether to grant a discretionary repeat, the Examiners will consider your record of attendance and engagement in the module. Students with a poor attendance record will not normally be permitted a discretionary repeat.

#### Expectations on the Student

This is a module in Computing Science fundamentals. As such, it covers a lot of material. While much of the material will be delivered via lectures, practical sessions and tutorials, the onus will be on the student to use the additional materials to fill in the gaps. Success will largely be determined by the student willingness to attend, engage, and work.

Attendance at practicals and tutorials are strongly encouraged, without which success in exams and the corresponding assignment will be difficult. Students are free to decide their own level of engagement. Clearly, decisions have benefits and consequences.

#### Textbooks

Required:

• Data Structures and Algorithms in Java: International Student Version (5e), Michael T. Goodrich, Roberto Tamassia. ISBN-10: 0470398809, ISBN-13: 978-0470398807