Computer Science

ECM1414 - Data Structures and Algorithms (2019)

Back | Download as PDF
MODULE TITLEData Structures and Algorithms CREDIT VALUE15
MODULE CODEECM1414 MODULE CONVENERProf Ronaldo Menezes (Coordinator)
DURATION: TERM 1 2 3
DURATION: WEEKS 11
Number of Students Taking Module (anticipated) 73
DESCRIPTION - summary of the module content

According to an old formula, Algorithms + Data Structures = Programs. This remains as true today as when it was originally formulated by Niklaus Wirth in 1976, and encapsulates the truism that all computation consists of the manipulation of data by means of systematic procedures. But data comes in many different forms (e.g., numerical, alphabetical, graphical) and only by knowing how it is structured can we specify the procedures – algorithms – for manipulating it to produce desired outcomes.  Thus the study of data structures and algorithms constitutes an integrated topic, which forms the subject matter of this module. You will be introduced to some of the key concepts in the area, with plenty of examples to illustrate them, and will be given a chance to demonstrate your understanding by undertaking exercises. This module builds on the programming knowledge you have already acquired from ECM1408 (Programming for Science) and will make use of mathematical tools introduced in ECM1415 (Discrete Mathematics for Computer Science) to enable data structures and algorithms to be described precisely.

Prerequisite module: ECM1400, ECM1415 or equivalent

AIMS - intentions of the module

The aim of this module is to introduce you to the fundamental role played by data structures and algorithms in computer science. You will already have acquired some practical understanding of data structures and how they work from the programming module; now it is time to put this understanding on a more formal and theoretically-grounded footing by introducing a systematic framework for the description and manipulation of data structures. This will pave the way for a systematic study of algorithms, the abstract procedures that may be implemented in concrete form within computer programs. In particular, you will be introduced to the study of computational complexity, which provides measures of the efficiency of algorithms (in terms of memory utilisation and running time) and can also characterise the complexity of problems in terms of the optimum efficiency of algorithms for solving them.

INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)

On successful completion of this module, you should be able to:

 

Module Specific Skills and Knowledge:
1 demonstrate a familiarity with a range of fundamental data structures used in computing;
2 use the formalism of abstract data types to construct precise specifications of data structures and derive their properties;
3 describe the properties of algorithms, explaining clearly their relationship to programs and to heuristics;
4 give rigorous specifications of algorithms and construct solutions to algorithmic tasks using pseudocode;
5 show an awareness of the issues of termination and correctness, demonstrating these for some simple examples;
6 make use of recursion and iteration in constructing algorithms;
7 explain the meaning of computational complexity, distinguishing space and time complexity, and evaluating the complexity of a range of different algorithms;
8 display an awareness of the phenomenon of NP-completeness, giving examples of problems known to be NP-complete and explaining the significance of NP-completeness for practical computation.
Discipline Specific Skills and Knowledge:
9 demonstrate enhanced practical skills in programming and problem analysis as a result of the deeper theoretical understanding gained from this module.
10 describe computational phenomena using a range of key theoretical concepts.
Personal and Key Transferable / Employment Skills and Knowledge:
11 present and explain abstract ideas using a systematic approach.

SYLLABUS PLAN - summary of the structure and academic content of the module

- recapitulation of fundamental data structures used in computing: lists, stacks, queues, trees, graphs, digraphs;

- abstract data types: distinguished elements, operations and relations; models; morphisms;

- what an algorithm is;

- algorithms vs heuristics;

- specification and pseudocode;

- termination and correctness;

- iteration and recursion;

- space and time complexity (including recapitulation of logarithmic, polynomial and exponential functions, order notation);

- use of searching and sorting as running examples to illustrate the foregoing;

- NP-completeness and the travelling salesman problem.

LEARNING AND TEACHING
LEARNING ACTIVITIES AND TEACHING METHODS (given in hours of study time)
Scheduled Learning & Teaching Activities 32.00 Guided Independent Study 118.00 Placement / Study Abroad 0.00
DETAILS OF LEARNING ACTIVITIES AND TEACHING METHODS
Category Hours of study time Description
Scheduled learning and teaching 22 Lectures
Scheduled learning and teaching 10 Tutorials
Guided independent study 30 Coursework
Guided independent study 88 Private reading

 

ASSESSMENT
FORMATIVE ASSESSMENT - for feedback and development purposes; does not count towards module grade
Form of Assessment Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
In Class Test 1 hour All In class
       
       
       
       

 

SUMMATIVE ASSESSMENT (% of credit)
Coursework 20 Written Exams 80 Practical Exams 0
DETAILS OF SUMMATIVE ASSESSMENT
Form of Assessment % of Credit Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
Coursework 20 6 pages 1,2,7,8,10,11 Written feedback sheet
Examination 80 2 hours - Summer Exam Period All On request
         
         

 

DETAILS OF RE-ASSESSMENT (where required by referral or deferral)
Original Form of Assessment Form of Re-assessment ILOs Re-assessed Time Scale for Re-reassessment
All Written exam All August Ref/Def period
       
       

 

RE-ASSESSMENT NOTES

Referred and deferred assessment will normally be by examination. For referrals, only the examination will count, a mark of 40% being awarded if the examination is passed. For deferrals, candidates will be awarded the higher of the deferred examination mark or the deferred examination mark combined with the original coursework mark.

RESOURCES
INDICATIVE LEARNING RESOURCES - The following list is offered as an indication of the type & level of
information that you are expected to consult. Further guidance will be provided by the Module Convener

ELE – College to provide hyperlink to appropriate pages

Reading list for this module:

Type Author Title Edition Publisher Year ISBN Search
Set Cormen T, Leiserson C, Rivest R, Stein C Introduction to Algorithms 3rd Edition MIT Press 2009 [Library]
Set Aho, A., Ullman, J., Hopcroft, J. Data Structures and Algorithms Addison Weslett 1983 [Library]
CREDIT VALUE 15 ECTS VALUE 7.5
PRE-REQUISITE MODULES ECM1415, ECM1400
CO-REQUISITE MODULES
NQF LEVEL (FHEQ) 1 (NQF Level 4) AVAILABLE AS DISTANCE LEARNING No
ORIGIN DATE Tuesday 10 July 2018 LAST REVISION DATE Tuesday 10 July 2018
KEY WORDS SEARCH Data structures; algorithms; computational complexity.