Course CL102 Foundations of Dynamic Data Structures and Algorithms in C (5 days)
Overview and Intended Delegates
The course emphasises the implementation of disciplined and well structured code and the design of modules with clean interfaces. The course provides and intensive overview of a wide variety of important data structures and algorithms. Topics include:
- Linked lists - singly linked, doubly linked and applications
- Binary trees and self-balancing binary trees (AVL, red-black, threaded)
- Stacks and Queues
- Indexing and hash tables
- Heaps and priority queues
- Graphs and graph algorithms
- VTables and interfaces
The course uses the GNU gcc compiler and associated tools such as make and gdb. As well as command line approaches use of the Eclipse IDE for C application development is also covered
The course will also cover important topics such as circular buffers, Finite State Machines and Hierarchical Finite State machines and how to apply them in practice.
Course Content
- Intensive overview of essential C concepts and idioms
- Data types, data structures, pointers and arrays
- Using pointers to search collections of data
- Arrays and buffers
- Circular buffers
- Polygonal buffers
- I/O vectors
- Linked Lists in depth
- Singly linked and doubly linked lists
- Using lists to implements FIFO queues and LIFO queues (stacks)
- Using lists of linked lists
- Using linked list nodes containing void * pointers to implement heterogeneous collections of data
- Using linked lists to implement resizeable arrays
- Implementing simple memory management schemes using linked lists
- Binary trees, their uses and their relations
- Basic binary trees
- Self-balancing binary trees (AVL, Red-Black, Splay)
- Heaps and their uses
- Huffman encoding
- Priority queues
- Error detection
- CRC checksums (16 bit and 32 bit)
- Finite State Machines (FSMs)
- Event driven programming
- Basic FSMs
- Pattern matching
- Parsing
- State driven hardware and communication protocols
- Implementing FSMs using switch statements
- Implementing FSMs using a table driven approach
- Limitations of FSMs
- Extended FSMs and hierarchical FSMs
- Extending FSMs by adding variables and conditional transitions
- Nesting state machines (push down automata)
- Statecharts and Hierarchical FSMs
- Hierachical FSMs and extended FSMs (simple statecharts)
- Orthogonal statecharts and concurrency
- Active objects - linking multi-tasking, message passing and event driven programming
- Pattern Matching, Searching and Sorting
- Sorting algorithms - insertion sort, quicksort, merge sort, radix sort, binary search
- Regular expressions and pattern matching - Boyer-Moore algorithm
- Graphs, graph algorithms and graph searching
- Patricia and Radix Trees and Tries
- Overview of further Advanced Topics
- Data Compression
- Data Encryption
- Geometric algorithms