CODE 
ICS2212 

TITLE 
Data Structures and Algorithms 2 

LEVEL 
02  Years 2, 3 in Modular Undergraduate Course 

ECTS CREDITS 
4 

DEPARTMENT 
Artificial Intelligence 

DESCRIPTION 
This unit presents a mode advanced and computer theoretic treatment of data structures and algorithms and introduces the student to the theory of NPCompleteness. The units starts with a description of computable and noncomputable problems and then proceeds to the definition and discussion of the classes P, NP, and NPComplete. The notion of polynomialtime Turing Reduction is used to explain how a problem can be reduced to another.
The unit covers approximation algorithms, the greedy and the dynamic programming algorithmic paradigms, as well as algorithms for MST, Huffman Coding, and Graph Traversals.
Studyunit Aims:
The aim of the studyunit is to expose the students to the: i) Computable vs Noncomputable problems. ii) Greedy Algorithms and Dynamic Programming. iii) The Theory of NPCompleteness. iv) MST Algorithms (with proofs).
Learning Outcomes:
1. Knowledge & Understanding:
By the end of the studyunit the student will be able to explain NPCompleteness, the Classes P, NP, and NPC, the greedy algorithm and dynamic programming paradigms, identify the difference between computable and noncomputable 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 NPHard problems cannot be approximated.
2. Skills:
By the end of the studyunit 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 9780262033848
Computers and Intractability: A Guide to the Theory of NPCompleteness Michael R. Garey, David S. Johnson Freeman, Jan 1975. ISBN 9780716710455. Class notes and slides.


RULES/CONDITIONS 
Before TAKING THIS STUDYUNIT YOU MUST TAKE CIS1017 OR TAKE CIS1117 

STUDYUNIT TYPE 
Lecture and Independent Study 

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

Yes 
75% 


LECTURER/S 
John M. Abela (Coord.) Kristian Guillaumier


The University makes every effort to ensure that the published Courses Plans, Programmes of Study and StudyUnit information are complete and uptodate 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 studyunit description above applies to the academic year 2017/8, if studyunit is available during this academic year, and may be subject to change in subsequent years.

18 January 2018
https://www.um.edu.mt/ict/studyunit