Gwybodaeth Modiwlau
Module Identifier
CS21120
Module Title
Program Design, Data Structures and Algorithms
Academic Year
2016/2017
Co-ordinator
Semester
Semester 1
Mutually Exclusive
Pre-Requisite
Other Staff
Course Delivery
| Delivery Type | Delivery length / details |
|---|---|
| Lecture | 30 x 1 Hour Lectures |
| Tutorial | 10 x 1 Hour Tutorials |
| Workshop | 10 x 1 Hour Workshops |
Assessment
| Assessment Type | Assessment length / details | Proportion |
|---|---|---|
| Semester Exam | 2 Hours Written Exam Written examination | 50% |
| Semester Assessment | Programming Assignment | 50% |
| Supplementary Exam | 2 Hours Ailsefyll Asesiad Students must resit failed examination and/or resubmission of failed/non-submitted coursework components or ones of equivalent value. | 50% |
| Supplementary Assessment | Ailsefyll Arholiad Students must resit failed examination and/or resubmission of failed/non-submitted | 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. Module Overview - 1 Lecture
An overview of the method of teaching and assessment, and a road-map of the topics to be covered and their relationships. Some basic concepts are introduced.
2. Java Programming - 5 Lectures
A recap of basic Java concepts (file, types, statements, loops, conditionals, classes and objects), compilation, debugging, JUnit testing, generics. Refresher on Graphical User Interfaces. Threads and synchronization issues.
3. Programme design, abstract data types, stacks, queues and priority queues - 5 Lectures.
Explanation of design issues such as object-orientation and how Abstract Data Types support good programme design, how they are implemented in Java with interfaces, examples of a Stacks, Queues and Priority Queues and their different implementations.
4. Design patterns and frameworks - 5 Lectures
An introduction to object-oriented design patterns and frameworks. Support for reuse. General concepts, representation and examples. How patterns may be implemented in Java.
5. Design Paradigms for Algorithm - 3 Lectures
An overview will be given on the different design paradigms for algorithms; for example, recursive algorithms, divide and conquer, dynamic programming and greedy algorithms.
6. Storing and Retrieving Data by Key - 6 Lectures
The Map ADT will be introduced and the problem will be used to motivate the discussion of a wide variety of different implementation techniques. The features of some typical solutions will be related to the dimensions of the problem such as the volume of data to be handled, volatility and the operations required. Internal Storage: linear and binary searching. Linked representations; an introduction to hashing, binary search trees, AVL trees and heaps.
7. Representing Complex Relationships: Graphs - 3 Lectures
Some examples of greedy algorithms. Terminology and implementation considerations. A look at some graph-related problems such as: finding a route (shortest paths); planning a communications network (minimum spanning trees).
8. Revision and assignment preparation - 2 Lectures
1 lecture will be devoted to describing the assignment and providing guidance on its completion, and 1 lecture will be used as a revision session before the exam.
An overview of the method of teaching and assessment, and a road-map of the topics to be covered and their relationships. Some basic concepts are introduced.
2. Java Programming - 5 Lectures
A recap of basic Java concepts (file, types, statements, loops, conditionals, classes and objects), compilation, debugging, JUnit testing, generics. Refresher on Graphical User Interfaces. Threads and synchronization issues.
3. Programme design, abstract data types, stacks, queues and priority queues - 5 Lectures.
Explanation of design issues such as object-orientation and how Abstract Data Types support good programme design, how they are implemented in Java with interfaces, examples of a Stacks, Queues and Priority Queues and their different implementations.
4. Design patterns and frameworks - 5 Lectures
An introduction to object-oriented design patterns and frameworks. Support for reuse. General concepts, representation and examples. How patterns may be implemented in Java.
5. Design Paradigms for Algorithm - 3 Lectures
An overview will be given on the different design paradigms for algorithms; for example, recursive algorithms, divide and conquer, dynamic programming and greedy algorithms.
6. Storing and Retrieving Data by Key - 6 Lectures
The Map ADT will be introduced and the problem will be used to motivate the discussion of a wide variety of different implementation techniques. The features of some typical solutions will be related to the dimensions of the problem such as the volume of data to be handled, volatility and the operations required. Internal Storage: linear and binary searching. Linked representations; an introduction to hashing, binary search trees, AVL trees and heaps.
7. Representing Complex Relationships: Graphs - 3 Lectures
Some examples of greedy algorithms. Terminology and implementation considerations. A look at some graph-related problems such as: finding a route (shortest paths); planning a communications network (minimum spanning trees).
8. Revision and assignment preparation - 2 Lectures
1 lecture will be devoted to describing the assignment and providing guidance on its completion, and 1 lecture will be used as a revision session before the exam.
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