Dr David Cairns (Coordinator), Rm 4B87
20 credits at SCQF level 8
CSCU9A2, MATU9D1 is strongly recommended
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
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.
- Abstract Data Types;
- Lists, stacks, queues;
- Hash tables (maps/sets), heaps (priority queues).
- Recursion introduced in the context of pre-, in-, and post-order traversals of trees,
- Comparing/contrasting recursive vs. iterative approaches.
- Searches: quick review
- Sorts: merge-sort, quick-sort, heap-sort
Advanced Algorithms and Data Structures
- 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’
- Checkpoints 15%
- Assignment 45%
- Examination 40%
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.
- Data Structures and Algorithms in Java: International Student Version (5e),
Michael T. Goodrich, Roberto Tamassia. ISBN-10: 0470398809,
Recommended reading includes:
- Data Structures and Problem Solving Using Java: International Version, Mark A. Weiss (4e).
- Data Structures and Algorithms in Java, Robert Lafore (2e)
- The New Boston Intro to Java
- The New Boston Intermediate Java.