Course Details
Course Information Package
Course Unit Title | ALGORITHMS AND COMPLEXITY | ||||||
Course Unit Code | ACSC401 | ||||||
Course Unit Details | |||||||
Number of ECTS credits allocated | 5 | ||||||
Learning Outcomes of the course unit | By the end of the course, the students should be able to:
| ||||||
Mode of Delivery | Face-to-face | ||||||
Prerequisites | AMAT181,ACSC191,ACSC288 | Co-requisites | NONE | ||||
Recommended optional program components | NONE | ||||||
Course Contents | Computability issues, need for axiomatic models of computations; unsolvable problems and computers limitation
Analysing Algorithms and Problems: Notion of an algorithm; Principles and Examples; Time and space complexity; Classifying functions by their growth rates; Brute force and greedy algorithms. Divide and Conquer paradigm; Master Theorem for solving recurrences.
Algorithms design - Sorting: Selection and Insertion Sort; Heapsort, Merge-sort, Quick-sort. Lower bounds for sorting by comparison keys.
Algorithms design - Arithmetic & Matrix Computations Divide and Conquer paradigm applied for integer and matrix multiplication. Dynamic Programming paradigm and examples (Matrix chain multiplication)
Searching: Balanced Binary Search Trees (Red-Black, AVL, B-Trees) and string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms)
Graphs and Trees: Terminology and graph representation. Graph traversing (Breath/Depth First Search). Kruskal’s and Prim’s algorithms for Minimal Spanning Trees. Dijkstra’s Single Source Shortest-path (SSSP) algorithm. Maximum flow problem and Ford-Fulkerson algorithm
Complexity theory: Classes P and NP, NP-Completeness and Reducibility. Approximation algorithms for finding near-optimal solutions in polynomial time for intractable problems. | ||||||
Recommended and/or required reading: | |||||||
Textbooks |
| ||||||
References |
| ||||||
Planned learning activities and teaching methods | For the delivery of the class material, power point presentations are primarily used, along with the whiteboard. The lecture notes, consisting of slides presented in class, and additional material, are made available to the students through the course website and are complementary of the course textbooks. The theoretical part of each lecture is accompanied with detailed solved examples on which emphasis is given in the class. The solutions to these exercises, as well as specimen solutions for all tests and assignments, are discussed with students. | ||||||
Assessment methods and criteria |
| ||||||
Language of instruction | English | ||||||
Work placement(s) | NO |