Faculty of Science

Objectives

This course introduces students to advanced techniques for the design and analysis of algorithms, and explores a variety of applications. The class covers various topics, including: analysis (asymptotics, upper/lower bounds, best/average/worst case analysis, amortized analysis, complexity), basic techniques used to design algorithms (including divide & conquer, greedy, dynamic programming, heuristics, choosing appropriate data structures), and important classical algorithms (including sorting, string, matrix, and graph algorithms).

Contents

Concept and properties of algorithms, role of algorithms, problem-solving strategies, separation of behavior and implementation. Differences among best, expected, and worst case behaviours of an algorithm. Asymptotic analysis of upper and expected complexity bounds. Big O notation: formal definition and use. Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential. Empirical measurements of performance. Time and space trade-offs in algorithms.

Little o, big omega and big theta notation. Recurrence relations. Analysis of iterative and recursive algorithms. Some version of a Master Theorem

Brute-force algorithms. Greedy algorithms. Divide-and-conquer. Dynamic Programming

Implementation and use of: Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, and mode in a list, approximating the square root of a number, or finding the greatest common divisor.

Sequential and binary search algorithms. Worst case quadratic sorting algorithms (selection, insertion). Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort). Hash tables, including strategies for avoiding and resolving collisions. Binary search trees (Common operations on binary search trees such as select min, max, insert, delete, iterate over tree). Graphs and graph algorithms (Representations of graphs (e.g., adjacency list, adjacency matrix), Depth- and breadth-first traversals)

Heaps, graph algorithms (minimum spanning tree, single source shortest path, all pairs shortest path), string algorithms (longest common subsequence). Introduction to P/NP/NPC with examples

Review definitions of the classes P and NP; introduce P-space and EXP. NP-completeness (Cook’s theorem). Classic NP-complete problems. Reduction Techniques

Balanced trees (1-2 examples), graphs (topological sort, strongly connected components), advanced data structures (disjoint sets, mergeable heaps), network flows, linear programming, duality, simplex, ellipsoid, matchings, overview of techniques), approximation algorithms, amortized analysis, Geometric algorithms (e.g., points, line segments, polygons [properties, intersections], finding convex hull, spatial decomposition, collision detection, geometric search/proximity). Randomized algorithms. Online algorithms and competitive analysis

Critical path, work and span, naturally parallel algorithms, specific algorithms (e.g. mergesort, parallel prefix).