University of Malta
 

Study-Unit Description
UOM Main Page
 
 
 
Apply - Admissions 2016
Newspoint
Campus Map button
Facebook
Twitter


CODE ICS2210

 
TITLE Data Structures and Algorithms 2

 
LEVEL 02 - Years 2, 3 in Modular Undergraduate Course

 
ECTS CREDITS 5

 
DEPARTMENT Artificial Intelligence

 
DESCRIPTION This unit presents a more advanced and computer theoretic treatment of data structures and algorithms and introduces the student to the theory of NP-Completeness. The units starts with a description of computable and non-computable problems and then proceeds to the definition and discussion of the classes P, NP, and NP-Complete. The notion of polynomial-time Turing Reduction is used to explain how a problem can be reduced to another.

The unit also covers approximation algorithms, the greedy and the dynamic programming algorithmic paradigms, as well as algorithms for MST, Huffman Coding, and Graph Traversals.

Study-unit Aims:

The aim of the study-unit is to expose the students to:
i) Computable vs Non-computable problems;
ii) Greedy Algorithms and Dynamic Programming;
iii) The Theory of NP-Completeness;
iv) MST Algorithms (with proofs);
v) Approximation Algorithms.

Learning Outcomes:

1. Knowledge & Understanding:

By the end of the study-unit the student will be able to explain NP-Completeness, the Classes P, NP, and NPC, the greedy algorithm and dynamic programming paradigms, identify the difference between computable and non-computable problems, as well as explain why reducing a known NPC problem to another problem makes the target problem also in NPC. Finally the student will identify and explain why certain NP-Hard problems cannot be approximated.

2. Skills:

By the end of the study-unit the student will be able to:
i) Distinguish between NP and NPC problems;
ii) Show that a problem is in NPC by reducing another NPC problem to it;
iii) Use MST algorithms to find approximations to Euclidean TSP;
iv) Solve certain problems using a greedy or dynamic programming approach.

Main Text/s and any supplementary readings:

Introduction to Algorithms
Clifford Stein, Thomas H Cormen, Ronald L Rivest, Charles E Leiserson
MIT Press, July,2009. 3rd Edition,ISBN 978-0262033848

Computers and Intractability: A Guide to the Theory of NP-Completeness
Michael R. Garey, David S. Johnson
Freeman, Jan 1975. ISBN 978-0716710455.

Class notes and slides.

 
RULES/CONDITIONS Before TAKING THIS STUDY-UNIT YOU MUST TAKE CSA1017 OR TAKE ICS1018

 
STUDY-UNIT TYPE Lecture and Independent Study

 
METHOD OF ASSESSMENT
Assessment Component/s Resit Availability Weighting
Project Yes 30%
Examination (2 Hours) Yes 70%

 
LECTURER/S John M. Abela
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 study-unit description above applies to the academic year 2017/8, if study-unit is available during this academic year, and may be subject to change in subsequent years.
Calendar
Notices
Study-unit Registration Forms 2017/8

Register

For Undergraduate (Day) and Postgraduate students.

 

Academic Advisors 2017/8

AA1

Academic Advisors for ICT 1st year students (Intake 2017/8), NOW available

Faculty of ICT Timetables

Timetables

ICT Timetables are available from Here.

Health and Safety Regulations for Labs Form

The Faculty of ICT Health and Safety Regulations for Laboratories form can be found here

 HealthAndSafety

 
 

Log In back to UoM Homepage