Algorithms and Complexity

Efficiency, analysis and order. Solving recurrences. Heaps and priority queues, the heapsort algorithm, hashing, union and find. Elementary graph algorithms: breadth first search, depth first search, connected components. The divide and conquer technique: merge sort, quick sort, the master theorem. Greedy algorithms: the maximum independent set problem in interval graphs - the activity selection problem, minimum cost spanning trees - Prim’s and Kruskal’s algorithms, shortest paths in graphs, the fractional knapsack problem. Dynamic programming technique: shortest paths - the Bellman – Ford algorithm, the 0-1 knapsack problem, the longest common subsequence. The backtracking technique: the n-queens problem, the travelling salesperson problem. Decision problems, the classes P and NP, NP-complete and NP-hard problems, reductions.