Module Information

Module Identifier
CS21120
Module Title
Program Design, Data Structures and Algorithms
Academic Year
2018/2019
Co-ordinator
Semester
Semester 1
Mutually Exclusive
Pre-Requisite
Other Staff

Course Delivery

Delivery Type Delivery length / details
Lecture 20 x 1 Hour Lectures
Tutorial 10 x 1 Hour Tutorials
Workshop 10 x 2 Hour Workshops
 

Assessment

Assessment Type Assessment length / details Proportion
Semester Exam 2 Hours   Written Exam  50%
Semester Assessment Programming Assignment  40%
Semester Assessment Worksheets in practicals  10%
Supplementary Exam 2 Hours   Resit Exam  Students must resit failed examinations.  50%
Supplementary Assessment Resubmission of failed component assignments Resit of failed components - 50 hours  50%

Learning Outcomes

On successful completion of this module students should be able to:

1. demonstrate their understanding of the principles of abstraction and encapsulation as they apply to the design of abstract data types and programs;
2. analyse and evaluate the time and space behaviour of algorithms and understand how this is expressed and determined;
3. recognise the importance of this analysis in the design of software;
4. describe some of the main approaches to algorithm design such as greedy algorithms, divide and conquer and dynamic programming;
5. demonstrate judgement in evaluating and choosing appropriate data structures and algorithms for a range of programming problems;
6. design and implement significant programs in Java.

Brief description

This module builds on the foundations of the first year modules on program design and provides a thorough grounding in the design of data structures and algorithms and gives further insight into object-oriented design.

Content

1. Introduction - 1 Lecture
Module road-map; Object-oriented design goals and principles; Abstract data types

2. Basic abstract data types - approx 3 Lectures.
Basic data structures; Stacks, Queues, Priority Queues and their implementations

3. Storing and Retrieving Data by Key - approx 5 Lectures
The Map abstract data type and related abstract data types; Implementations using basic data structures; Hashing; Binary search trees; Balanced binary search trees.

4. Representing Complex Relationships: Graphs - approx 4 Lectures
Introduction; Terminology; Implementation; Representation; Graph traversal; Problem modelling and solving using graphs, e. g., planning a communications network (minimum spanning trees), finding a route (shortest paths); Graph libraries

5. Design Paradigms for Algorithms - approx 4 Lectures
Introduction; Brute Force; Recursion; Greedy algorithms; Divide & Conquer; Dynamic programming

6. Design patterns and frameworks - approx 2 Lectures
Introduction to object-oriented design patterns; Implementation of patterns in Java

7. Revision - 1 Lecture

Aims

Minor changes to syllabus and format of workshops based on TuN feedback (implementation of action plan).

Module Skills

Skills Type Skills details
Application of Number Particularly in algorithm analysis.
Communication Written skills will be needed to complete supporting documents to accompany assessed coursework.
Improving own Learning and Performance Students are required to engage in self study. Completing the assignment requires improvements in programming skills. Both the assignment and the exam requires understanding challenging concepts.
Information Technology The whole module concerns this area.
Personal Development and Career planning Carefully time management will be needed as so to enable students to complete coursework etc. A frequent topic of interview questions for programmers.
Problem solving This is inherent in both the formative practical work and the assessed coursework.
Research skills The students wil need to search for and use relevant technical information while completing practical and assessed coursework.
Subject Specific Skills See module title and content.
Team work N/A

Notes

This module is at CQFW Level 5