This module considers various data structures such as lists, stacks, queues, trees and graphs and the abstract data types on which they are based. The module also discusses algorithms. It defines a scheme for quantifying algorithm efficiency, devoid of any computing system or language. Several approaches for algorithm design are studied such as recursion, divide and conquer, brute force and greedy strategies. Towards the end of the module the classification of algorithms and the problems they solve is explored. The module finally concludes by asking how future technological developments could change the way we perceive algorithms.
Main topics
Abstract data types: discussed in general.
Basic data Structures: lists, linkedlists, stacks, queues, implementation/applications of these.
Trees: general trees ordered trees, multiway trees, implementations of trees, tree traversal, path lengths.
Binary trees: internal and external nodes, binary tree depth, logs.
Binary tree applications: expression trees, binary search trees, heaps, Huffman data compression.
Graphs: undirected/directed, connected, weakly/strongly connected, complete), adjacency matrix/list, topological ordering, weighted graphs/networks, path lengths, Dijkstra’s Algorithm, depth/breadthfirst, traversals, minimum spanning trees, Prim’s Algorithm, Kruskal’s Algorithm.
Algorithm Efficiency: Big ‘Oh’, common time complexities, log time, binary search v linear search Recursion: why use it, the ground rules, Merge Sort in detail, Towers of Hanoi in detail.
Sorting: Bubble, Selection, Insertion, Shell, Bucket, Radix, Heap, Quick, external sorting.
Hashing: searching, hash function & table, collisions, separate chaining and open addressing.
Algorithm design strategies: brute force, greedy, divide and conquer, dynamic programming, incremental, probabilistic.
Algorithm and problem classification: polynomial and exponential time, reasonable and unreasonable algorithms, tractable and intractable problems, the future.
You should be clear that the Algorithms material in the module is NOT intended to be a review of a comprehensive range of specific algorithms. Nevertheless, a limited number of specific algorithms within the areas of searching and sorting will be examined.
