Module Code - Title:
CS4115
-
DATA STRUCTURES AND ALGORITHMS
Year Last Offered:
2023/4
Hours Per Week:
Grading Type:
N
Prerequisite Modules:
Rationale and Purpose of the Module:
To provide a uniform theoretical treatment of the data structures and algorithms used in systems and applications programming. This module includes a practical component to reinforce learning and to encourage students in the practical use of theoretical material.
Syllabus:
- Mathematics Review;
- Review of the ADTs, internals and usage of simple data structures and associated algorithms, in particular recursive algorithms;
- Linked Lists and Networks;
- Recursion, and the elimination of recursion from algorithms;
- Study of sorting algorithms: quicksort, heapsort, mergesort and bucket and radix sorting;
- Analysis of general divide-and-conquer algorithms;
- Searching: tree searching, AVL trees, splay trees;
- Graph algorithms: graph traversal and spanning forests, depth and breadth first search of graphs; connectivity; minimal spanning trees for weighted graphs; shortest path algorithms; networks.
Learning Outcomes:
Cognitive (Knowledge, Understanding, Application, Analysis, Evaluation, Synthesis)
Upon successful completion of the module the student will be able to:
1. Given a function or functions in pseudo-code, analyse their asymptotic running time;
2. Given an executable program in black-box form, determine its asymptotic running-time behaviour;
3. Given a fictitious customers requirements for data storage and their data retrieval patterns, propose appropriate data structures;
4. Identify appropriate sorting and searching algorithms for contrasting scenarios;
5. Understand the trade-offs of various graph representation schemes;
6. Formulate data access and optimisation problems as graph algorithms.
Affective (Attitudes and Values)
N/A
Psychomotor (Physical Skills)
N/A
How the Module will be Taught and what will be the Learning Experiences of the Students:
Research Findings Incorporated in to the Syllabus (If Relevant):
Prime Texts:
Jeffrey J. McConnell (2007)
Analysis of Algorithms (2nd edition)
, Jones and Bartlett
Anany V. Levitin (2006)
Introduction to the Design and Analysis of Algorithms (2nd edition)
, Addison Wesley
T. H. Cormen et. al. (2001)
Introduction to Algorithms (2nd edition)
, MIT Press
N. Wirth (1976)
Algorithms + Data Structures = Programs
, Prentice-Hall
Other Relevant Texts:
Programme(s) in which this Module is Offered:
Semester - Year to be First Offered:
Spring
-
08/09
Module Leader:
patrick.healy@ul.ie