# CSCU9A3 - Data Structures, Objects and Algorithms

#### Credits

22 credits at SCQF level 8

#### Prerequisites

CSC9A2, MAT911 is strongly recommended

#### Instructors

Dr David Cairns (Coordinator), Rm 4B87, 01786 467445, dec@cs.stir.ac.uk
Dr John Woodward, Rm 4B99, 01786 467448, jrw@cs.stir.ac.uk

#### 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%

Failure to submit any single component will result in a no grade for the module. Assessed coursework submitted late will be accepted up to five days after the submission date (or expiry of any agreed extension) but the grade will be lowered by one grade point per day or part thereof. After five days the piece of work will be deemed a non-submission, and will result in a no grade for the module.

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 Repeat examination. Only students who obtain a grade 4A, 4B or 4C for the module, following the main examination, will be eligible for a Repeat examination. The grade awarded following a Repeat examination is capped at 3C.

#### 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

• Data Structures and Problem Solving Using Java: International Version, Mark A. Weiss (4e). ISBN-10: 0321546229, ISBN-13: 978-0321546227.
• Data Structures and Algorithms in Java, Robert Lafore (2e) ISBN-10: 0672324539 ISBN-13: 978-0672324536
• The New Boston Intro to Java
• The New Boston Intermediate Java.
© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159