Course CL102
Foundations of Dynamic Data Structures and Algorithms in C
Foundations of Dynamic Data Structures and Algorithms in C
Duration: 5 Days
Intended Audience
Attendees should have some experience of C programming and a basic understanding of arrays, pointers and data structures.
Course Overview
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
Lab exercises are used to consolidate key concepts.
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
Course Benefits
Students completing this course will considerably improve the discipline and rigour with which they design and write embedded systems applications in C, possibly, learn more about algorithms and data structures (e.g. refreshing topics rushed over in University computer science courses), reinvigorate their passion for programming.
You'll be able to implement classical data structures such as circular buffers, linked lists, and trees -- and you'll know when it's appropriate to use them.
You'll be exposed to a variety of advanced programming idioms and algorithms with their associated data structures, for tasks such as indexing, data compression and error detection.
You'll learn to write event driven programs, to implement Finite State Machines, and to design hierarchical state machines using statecharts.
You'll learn how complex algorithms and data structures are applied and used (some of the examples will be taken from the Linux Kernel source code).
Course Contents
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
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)
Implementing simple memory management schemes
Implementing simple flash memory file systems
State Machines and Statecharts
- 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
- 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
Advanced Topics
- Data Compression
- Data Encryption
- Geometric algorithms