Course Details

1. Discuss computability issues and need for axiomatic models of computations. Introduce the notion of an algorithm noting the existence of unsolvable problems.
2. Discuss the notion of time and space complexity and classify functions by their growth rates.
3. Analyze the running time of various algorithms; employ in particular, the Master Theorem for solving recurrences.
4. Describe and use general techniques, such as the Divide and Conquer and the Dynamic Programming paradigms, for designing correct and effective algorithms
5. Develop, evaluate and reason about the correctness and performance, of sorting algorithms (Insertion Sort, Merge Sort, Heapsort and Quick Sort), write programs to implement these and prove lower bounds for sorting by comparison keys.
6. Analyze graph traversing algorithms (BFS/DFS), compare Kruskall’s and Prim’s method for finding minimal spanning trees and explain Dijkstra’s Single Source Shortest-path algorithm. Discuss the Maximum flow problem and Ford-Fulkerson algorithm.
7. Explain the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction. Compare a range of computational problems according to their classification. Consider approximation algorithms for solving hard problems.

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.

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. (3ed Edition) The MIT Press, 2009

• Levitin A, The Design and Analysis of Algorithms, Pearson International 2e, 2007

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.