This course provides an intensive treatment of most of the key elements of algorithms and data-structures, beginning with the fundamentals of searching, sorting, lists, stacks, and queues, but quickly building to cover more advanced topics, including trees, graphs, and algorithmic strategies. It also covers the analysis of the performance and tractability of algorithms and will build on the concept of Abstract Data Types. A key focus of the course is on effective implementation and good design principles.

Topics covered include the following.

• Analysis of complexity: performance of algorithms, time and space tradeoff, worst case and average case performance, Big O notation, recurrence relationships, analysis of complexity of iterative and recursive algorithms.
• Complexity theory: tractable and intractable algorithmic complexity, travelling salesman problem, Hamiltonian circuit, 3-colour problem, SAT, cliques, determinism and non-determinism, P, NP, and NP-Complete classes of algorithm.
• Simple searching algorithms: linear search; binary search (iterative and recursive)
• Simple sorting algorithms: bubblesort, selection sort, Quicksort, worst case and average case complexity.
• Containers, dictionaries, Abstract Data Types (ADTs), lists, stacks, and queues, ADT specification, array and linked-list implementations; hashing.
• Trees: types of trees, tree terminology (level, height, external and internal nodes, skinny, fat, complete, left-complete, perfect, multi-way, d-ary), binary trees, binary tree operations, binary tree representation, binary search trees, binary search tree implementation, depth-first traversals, expression trees, pre-order, in-order, post-order traversal, fixed-length codes, variable length codes, optimal code trees, Huffman's algorithm and implementation, height-balanced trees, balance factor, AVL Trees, RR, RL, LR, LL rotations, Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring.
• Priority queues, binary heaps, array implementation, heapsort.
• Graphs, types of graphs (directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, non-simple, implicit, explicit, embedded, topological), adjacency list representation, adjacency matrix representation, depth-first traversal, breadth-first traversal, finding paths, topological sorting, minimum spanning trees, Prim's algorithm, Kruskal's algorithm, shortest-path algorithms, Dijkstra's algorithm, Floyd-Warshall's all-pairs algorithm.
• Algorithmic strategies: brute-force (Grenander's problem), divide-and-conquer (Quicksort, mergesort, Grenander's problem), greedy algorithms (Prim's algorithm, Dijkstra's algorithm, Huffman's algorithm, knapsack problem), dynamic programing (Fibonnaci number).
• Combinatorial search: exhaustive search and backtracking, pruning, generic algorithm implementation, enumeration of subsets, permutations, all paths in a graph, branch-and-bound.

Back to Top