Module Catalogues, Xi'an Jiaotong-Liverpool University   
 
Module Code: IOT202TC
Module Title: Data Structure and Algorithms
Module Level: Level 2
Module Credits: 5.00
Academic Year: 2021/22
Semester: SEM1
Originating Department: School of Internet of Things
Pre-requisites: N/A
   
Aims
To introduce students to a wide variety of data structures and algorithms. To provide students with a coherent knowledge of techniques for implementing data structures and algorithms. To discuss the complexity, advantages and disadvantages of different data structures and algorithms. To introduce the main algorithms for fundamental tasks such as sorting and searching.
Learning outcomes 
A. To understand and to be able to apply a wide variety of data structures, together with their internal representation and algorithms;

B. To be able to make informed choices between alternative ways of implementation, justifying choices on grounds such as time and space complexity;


C. To be able to select, with justification, appropriate data structures to ensure efficient implementation of an algorithm.
Method of teaching and learning 
Students will be expected to attend two hours of formal lectures as well as to participate in one hour of supervised tutorials and practicals in a computer lab in a typical week. Lectures will introduce students to the academic content and practical skills which are the subject of the module, while tutorials and computer practicals will allow students to practice those skills. In addition, students will be expected to devote at least three hours of unsupervised time to solving continuous assessment tasks and private study. Private study will provide time for reflection and consideration of lecture material and background reading. Continuous assessment will be used to test to what extent practical skills have been learnt, in particular, assessment tasks will be solved individually and each solution comprises the resolution, using sound programming and software engineering techniques, of the given problems expressed in terms of a requirements statement.
Syllabus 
Week 1: Introduction to Data Structures Data Structures, Data Types, and Abstraction Data Types; Abstraction, Information Hiding, and Encapsulation; Efficiency; Static vs. Dynamic data structures.


Week 2: (Multi-dimensional) arrays and vectors Abstract Datatype definition; Java arrays of objects (declaration, initialisation, use, iteration through array elements, iterators), data representation of arrays and access to array elements; Abstract Datatype definition; Java vectors (declaration, initialisation, use); examples of vector use.


Week 3-4: Lists Abstract Datatype definition; Realisation of lists using arrays; Singly linked lists in Java (declaration, initialisation, use, iteration); data representation of singly linked lists; Doubly linked lists in Java (declaration, initialisation, use, iteration); data representation of doubly linked lists; variations of lists including circular lists, their implementation using references or arrays; examples of list use.


Week 5-6: Stacks, Heaps and Queues Abstract Datatype definitions; Realisation of stacks, heaps and queues using lists or arrays; priority queues and their implementation; examples of stack and queue use.


Week 8-9: Trees Abstract Datatype definition (trees, binary trees); Realisation of trees using references or arrays; tree traversal; (binary) search trees; AVL trees; splay trees; B-Trees.


Week 10-11: Sorting, Sets, and Selection and insertion sort; Merge sort; quick sort; bucket sort and radix sort; external sorting using B-Trees; comparison of sorting algorithms; Set Abstract Datatype definition; Union/Find Structures; Selection.


Week 12: Maps and Dictionaries Abstract Datatype definitions; Realisation; Hash tables; Graphs; extensions and applications of dictionaries.


Week 13: Choosing the right data structure Discussion of various criteria which can be used to determine the best data structure for a specific purpose.
Delivery Hours  
Lectures Seminars Tutorials Lab/Prcaticals Fieldwork / Placement Other(Private study) Total
Hours/Semester 39    7  6    98  150 

Assessment

Sequence Method % of Final Mark
1 Assessment 10.00
2 Assessment 10.00
3 Final Exam 80.00

Module Catalogue generated from SITS CUT-OFF: 6/7/2020 3:53:30 AM