Algorithms and Data Structures
Trees:
Terminology.
The ADT Binary Tree:
Operations of the ADT Binary Tree. Traversals of a binary tree. Representations of a binary tree.
Review of the ADT Binary Search Tree
Treesort.
General Trees.
Balanced Search Trees: 2-3 trees. 2-3-4 trees. Red-black trees. AVL trees. B-tree.
Priority queues and Heaps:
The ADT Priority Queue:
Heaps. A heap implementation of the ADT Priority Queue. Heapsort.
Hashing:
Hash functions. Resolving collisions. The efficiency of hashing. What constitutes a good hash function? Table traversal: an inefficient operation under hashing.
Graphs:
Terminology.
Graph Traversals:
Depth-first search. Breadth-first search.
Applications of Graphs:
Topological sorting. Spanning trees. Minimum spanning trees. Shortest paths. Circuits. Some difficult problems.
Path-finding algorithms used in computer games.
Final Marks:
Overall - 48%
Grade - C
Pass
Final Marks:
Overall - 48%
Grade - C
Pass
