Module: Computer Programming 3 (Data Struct. & Alg.)

Module Specifications..

Current Academic Year 2022 - 2023

Please note that this information is subject to change.

Module Title	Computer Programming 3 (Data Struct. & Alg.)
Module Code	CA268
School	School of Computing
Module Co-ordinator	Semester 1: Hossein Javidnia Semester 2: Hossein Javidnia Autumn: Hossein Javidnia
Module Teachers	Hossein Javidnia
NFQ level	8	Credit Rating	5
Pre-requisite	None
Co-requisite	None
Compatibles	None
Incompatibles	None

Description

The module aims to give students an understanding of basic data structures and algorithms, most especially with respect to managing collections of data such as sets, sequences, and maps. Students will learn how to specify collections using abstract data types (ADTs), how to implement them using a variety of techniques such as linked lists and search trees, and how to package them using object-oriented programming methods. Students will learn a range of fundamental algorithms including searching and sorting, and how to assess their computational cost. Students will also develop practical skills in implementing and testing algorithms on computers.

Learning Outcomes

1. Use iterative and recursive techniques to design and implement elementary algorithms.
2. Describe a variety of basic ADTs including sets, sequences, stacks, queues, graphs, trees and maps.
3. Implement the above ADTs using arrays, linked lists, search trees, and hash tables
4. Use object-oriented techniques such as interfaces, inheritance, and generics to package ADTs appropriately.
5. Analyse the time and space complexity of elementary algorithms, and justify the complexity of the above ADT implementations.
6. Incorporate ADTs and associated implementations appropriately into program solutions.
7. Describe and use a variety of searching and sorting algorithms.

Workload	Full-time hours per semester
*Type*	*Hours*	*Description*
Lecture	24	Theory, practice and examples
Laboratory	20	Completion of problem sets
Directed learning	30	Completion of problem sets
Independent Study	76	Review of lecture material, background reading and independent practice
Total Workload: 150

All module information is indicative and subject to change. For further information,students are advised to refer to the University's Marks and Standards and Programme Specific Regulations at: http://www.dcu.ie/registry/examinations/index.shtml

Indicative Content and Learning Activities

Object-oriented programming
Review of OO Concepts: classes and methods, inheritance, abstract base classes/interfaces

Algorithms
Designing algorithms using iteration and recursion. Basic algorithmic complexity, big-O notation, time vs space complexity, comparison of algorithms

Abstract Data Types
The notion of abstract data type (ADT). Sets, lists, sequences, maps, iterators, generators, stacks, queues as ADTs. Implementing and using them via the built-in collections.

Basic Data Structures
Linked lists, doubly-linked lists, binary search trees, balanced search trees, tree traversal; comparison of time complexities.

Hash Tables
Hash tables, implementation in arrays, collision resolution (e.g. chaining), extensible hash tables. Directory structures.

Searching and Sorting
Bubble sort, insertion sort, selection sort, quicksort, merge sort, radix sort, binary search, string search (Knuth-Pratt-Morris).

Graph Structures and Algorithms
Representation (adjacency matrix vs adjacency list). Graph colouring. Searching strategies (DFS vs BFS), Dijkstra’s Algorithm, Spanning Tree Algorithms (Kruskal, Prim).

Assessment Breakdown
Continuous Assessment	30%	Examination Weight	70%

Course Work Breakdown
Type	Description	% of total	Assessment Date
Laboratory Portfolio	Laboratory exercises	15%	Every Week
Assignment	A set of problems that students work on in their own time	15%	Every Week

Reassessment Requirement Type
Resit arrangements are explained by the following categories; 1 = A resit is available for all components of the module 2 = No resit is available for 100% continuous assessment module 3 = No resit is available for the continuous assessment component
This module is category 1

Indicative Reading List

Brad Miller and David Ranum: 2014, Problem Solving with Algorithms and Data Structures, Franklin, 978-1590282571
M Goodrich: 2013, Data Structures and Algorithms in Python, Wiley, 978-1118290279

Other Resources

None

Array

Programme or List of Programmes

CASE

BSc in Computer Applications (Sft.Eng.)

COMSCI

BSc in Computer Science

BSc in Data Science

ECSA

Study Abroad (Engineering & Computing)

ECSAO

Study Abroad (Engineering & Computing)

Timetable this semester: Timetable for CA268

Archives: