The aim of this subject is to give the student the necessary skills and knowledge to allow the student to design, implement and test data structures and algorithms written in the C language.
Abstract Data Typing
C structs, Use of header files, Header guards, Modularity, Cohesion, Coupling, Information hiding, Global and shared variables, ADT implementation using header files
Linked List, Stack and Queue Containers
Self-referential classes. Fundamentals of linked lists. Stack implementation using a linked list. Stack examples: infix to postfix translation, Evaluation of Expressions. Queue implementation using linked lists. Priority Queues using Heaps. Array implementation of a Heap. Heap enqueue and dequeue
Trees and Tables
Fundamental properties of Trees. Binary Search Tree: implementations, searching, insertion, deletion by copying, deletion by merging, Recursion, Run Time Stack operation, traversals: breadth first, Preorder, Inorder, Postorder. Balanced Trees. AVL tree: rotations, local re-balancing. Problem Solving using Trees. Hash tables. Hashing functions
Algorithms and Asymptotic Notation
Upper bound - Big Oh, Lower Bound – Omega. Sorts and Searches: Sequential Search, Binary Search, Bubble sort, Selection Sort, Insertion sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort.
| Module Content & Assessment | |
|---|---|
| Assessment Breakdown | % |
| Other Assessment(s) | 40 |
| Formal Examination | 60 |