Study-Unit Description

Study-Unit Description


CODE ICT1018

 
TITLE Data Structures and Algorithms

 
UM LEVEL 01 - Year 1 in Modular Undergraduate Course

 
MQF LEVEL 5

 
ECTS CREDITS 5

 
DEPARTMENT Faculty of Information and Communication Technology

 
DESCRIPTION This study-unit introduces the student to the concepts of algorithm and data-structure. Particular emphasis is placed on the time and space complexity of algorithms. The study-unit introduces the basic abstract data structures such as Stack, Queue, Linked List, ADT Table, Heap, Tree, and Graph. Trees, in particular, are treated in detail with coverage of binary trees, expression trees, binary search trees, AVL trees, and B-Trees. The study-unit also discusses various sorting, tree traversal, graph processing algorithms as well as a discussion of the Big O notation.

Study-Unit Aims:

The aim of the study-unit is to expose the students to the:

- Various abstract data structures;
- Various sorting, tree, and graph algorithms;
- Algorithmic paradigms - iteration vs recursion;
- Time and space complexity of algorithms and the Big O Notation;
- Development of problem-solving skills in programming.

Learning Outcomes:

1. Knowledge & Understanding:
By the end of the study-unit the student will be able to:

- Define and describe the time and space complexity of algorithms and explain how the Big O notation is used to determine both;
- List, describe, and compare the main abstract data types and also describe the various sorting, tree, and graph algorithms covered in class.

2. Skills:
By the end of the study-unit the student will be able to:

- Apply the Big O notation to determine the time and space complexity of segments of code;
- Comprehend why it is not feasible to implement algorithms with exponential time complexity;
- Implement the abstract data structures covered in class in a high level programming language;
- Code the sorting, tree, and graph algorithms covered in class.

Main Text/s and any supplementary readings:

Main Texts:
- Algorithms (4th Edition), Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, April 2011

Supplementary Text:
- Cormen, Rivest 2009. Introduction to Algorithms. MIT Press.

 
ADDITIONAL NOTES Pre-requisite Qualifications: Programming knowledge and skills

 
STUDY-UNIT TYPE Lecture and Independent Study

 
METHOD OF ASSESSMENT
Assessment Component/s Assessment Due Sept. Asst Session Weighting
Project SEM2 Yes 20%
Examination (2 Hours) SEM2 Yes 80%

 
LECTURER/S John M. Abela (Co-ord.)
Kristian Guillaumier

 

 
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints.
Units not attracting a sufficient number of registrations may be withdrawn without notice.
It should be noted that all the information in the description above applies to study-units available during the academic year 2023/4. It may be subject to change in subsequent years.

https://www.um.edu.mt/course/studyunit