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