DCU Home | Our Courses | Loop | Registry | Library | Search DCU

Module Specifications..

Current Academic Year 2020 - 2021

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-ordinatorSemester 1: Charles Daly
Semester 2: Charles Daly
Autumn: Charles Daly
Module TeachersCharles Daly
Dimitar Shteliyanov Shterionov
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
Lecture24Theory, practice and examples
Laboratory20Completion of problem sets
Directed learning30Completion of problem sets
Independent Study76Review 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 Assessment30% Examination Weight70%
Course Work Breakdown
TypeDescription% of totalAssessment Date
Laboratory PortfolioLaboratory exercises15%Every Week
AssignmentA set of problems that students work on in their own time15%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
CASEBSc in Computer Applications (Sft.Eng.)
DSBSc in Data Science
ECSAStudy Abroad (Engineering & Computing)
ECSAOStudy Abroad (Engineering & Computing)
Timetable this semester: Timetable for CA268
Archives:

My DCU | Loop | Disclaimer | Privacy Statement