5024.17 - Algorithms and Data Structures
Course number
5024.17
Title
Algorithms and Data Structures
ECTS
7.5
Prerequisites
Discrete Mathematics; Linear algebra for Software Engineers; Introductory Programming in Java, C or C++
Purpose
- To introduce the notation, terminology, and techniques underpinning the study of algorithms
- To introduce the standard algorithmic design paradigms employed in the development of efficient algorithmic solutions
- To introduce the mathematical tools needed for the analysis of algorithms in terms of the use of formal models of Time and Space
Content
Introduction
o Definition of an algorithm, counting elementary operations during execution, worst-case analysis of running time and storage requirements - on several examples of simple algorithms
o Design of pseudo code algorithms
Complexity Issues
o Asymptotics and "order of" notation for complexity
o Comparison of polynomial time and exponential time complexities and examples of algorithms with such complexities
o Brief introduction of the notion of computable and non-computable functions
Review of Graphs structures and their representation
o Directed and Undirected graphs; Trees; representation by adjacency matrices and incidence lists, graph and tree traversals
Algorithm Design Techniques
o Review of the standard algorithm design paradigms commonly used in Computer Science together with typical example problems solved by these
o Overview: why a range of design methods is needed
o Divide-and-Conquer algorithms: general overview of approach; run-time analysis of simple Divide-and-Conquer methods via solution of recurrence relations
o Dynamic Programming: differences from Divide-and-Conquer; general overview; necessity for iterative implementation
o Greedy Method: concept of optimisation problem and the distinction between 'exact' and 'approximate' solution algorithms
Learning and teaching approaches
Lectures, theoretical and computer-based exercises, and tutorials
Learning outcomes
By the end of the course the student is expected to be able to:
- describe standard algorithms such as sorting algorithms, search algorithms, string matching algorithms, graph traversal algorithms;
- apply these algorithms or a given pseudo code algorithm in order to solve a given problem;
- carry out simple asymptotic analyses of algorithms involving sequence, selection, and iteration, and identify and compare simple properties of these algorithms;
- describe the algorithm design principles of divide-and-conquer, greedy method, and dynamic programming and distinguish the differences between these principles;
- apply the studied algorithms that illustrate these design principles;
- apply the studied design principles to produce algorithmic solutions to a given problem;
- explain and illustrate the distinction between different classes of problems, in particular, polynomial time and exponential time solvable problems.
Assessment method
one or two assessments will be given during the lectures
o 0% contribution to the final marks but we strongly recommend you to pass these assignments although it is not a necessary condition to get the permission for the examination
4-hour written examination (paper and pen based)
o course related materials are NOT allowed
o 100% contribution to the final marks
Examination
External
Marking scale
7-
Bibliography
Recommended Textbook:
Introduction to the Design and Analysis of Algorithms, Anany V. Levitin, Villanova University, 2011 (Third Edition), Addison-Wesley
Further Reading:
Introduction to ALGORITHMS, TH Cormen, CE Leiserson and RL Rivest, MIT Press/McGraw-Hill, 3rd Edition, 2009
Contact
Qin Xin