Data Structures and Algorithms with C

Course Map

This page puts every chapter of the course on one map. Each chapter is a node, and an arrow shows which idea from an earlier topic the next one relies on. Read it before the course starts to see where the topics are heading, or during the course to see where you are.

Basic SortingAlgorithmsIntroduction andAlgorithmAnalysisArrays andStructuresRecursion,Binary SearchandBacktrackingAdvanced SortingAlgorithmsLinkedListsStacksTreesPolynomials andSparseMatricesHashTablesQueuesSearchTreesSets andUnion-FindThe List ADT andGeneralizedListsStack andQueueApplicationsGraphsPriority Queuesand HeapsThreadedBinary TreesMinimumSpanningTreesShortest Pathsand ActivityNetworks
Figure 1: The course map. Each arrow points from a topic to one that builds on it. The paths that leave arrays and recursion split into linear structures, trees, graphs, and sorting.

Figure 1 shows the connections between the topics. Each node is a chapter, and an arrow indicates which idea of the earlier topic the later one relies on. Only the closest connections are drawn on the map; every chapter that a given chapter depends on is listed in Table 1.

Table 1: The connections on the map.
Topic (chapter)Builds onConnection
Introduction and Algorithm Analysis (1)—The system life cycle, expressing an abstract data type with a C header file, and asymptotic analysis.
Arrays and Structures (2)Introduction and Algorithm AnalysisThe array ADT and the relation between arrays and pointers; dynamic arrays with malloc, and structures.
Recursion, Binary Search and Backtracking (3)Introduction and Algorithm Analysis, Arrays and StructuresTracing recursion with stack frames; binary search in a sorted array, Hanoi, and permutations.
Linked Lists (4)Arrays and StructuresNodes built with malloc and free where an array falls short.
Polynomials and Sparse Matrices (5)Arrays and Structures, Linked ListsTwo representations of the same ADT: coefficient and term arrays, and linked lists; sparse matrices.
Stacks (6)Arrays and Structures, Recursion, Binary Search and Backtracking, Linked ListsThe LIFO structure: push and pop with an array and a struct; the call stack is the stack of recursion.
Queues (7)StacksThe FIFO structure: the drifting problem of the linear queue is solved with the circular queue.
Stack and Queue Applications (8)Stacks, QueuesBacktracking in a maze, converting an infix expression to postfix, and evaluating it.
The List ADT and Generalized Lists (9)Linked Lists, Polynomials and Sparse MatricesThe contract of the list ADT; multivariate polynomials lead to the generalized list.
Trees (10)Recursion, Binary Search and Backtracking, Linked ListsBinary trees, array and linked representations; traversals are written recursively.
Search Trees (11)Recursion, Binary Search and Backtracking, TreesAn ordering condition on the tree: insertion and search are the tree counterpart of binary search.
Threaded Binary Trees (12)Trees, Search TreesThe n+1 null pointers become threads: inorder traversal without a stack.
Priority Queues and Heaps (13)Queues, TreesThe priority form of the queue; the heap, by storing a complete binary tree in an array.
Hash Tables (14)Arrays and Structures, Linked ListsFrom direct addressing to hashing; open addressing uses an array, chaining uses linked lists.
Graphs (15)Linked Lists, Queues, Priority Queues and HeapsThe adjacency list is a linked list; BFS traverses with a queue and DFS with a stack.
Sets and Union-Find (16)TreesDisjoint sets are stored as trees with a parent array; weighted union and path compression.
Minimum Spanning Trees (17)Priority Queues and Heaps, Graphs, Sets and Union-FindThe greedy spanning tree: Kruskal uses union-find, Prim uses a heap.
Shortest Paths and Activity Networks (18)Priority Queues and Heaps, GraphsDijkstra, Bellman-Ford, and Floyd-Warshall; topological order and the critical path in AOV and AOE networks.
Basic Sorting Algorithms (19)Introduction and Algorithm Analysis, Arrays and StructuresThe first example, selection sort, is generalized: insertion sort and bubble sort, stability.
Advanced Sorting Algorithms (20)Recursion, Binary Search and Backtracking, Priority Queues and Heaps, Basic Sorting AlgorithmsQuicksort and merge sort through divide and conquer; heap sort and radix sort.

The backbone of the map can be read as array and pointer → linked structure → tree → graph. Every topic is carried from the abstract data type to a working C implementation, and its two tools are the array and the linked list built on malloc and free. Stacks and queues are written with both implementations and come together in the applications. Recursion leads to trees; heaps and disjoint sets are the array forms of trees. Graphs use all of these structures together: a heap and union-find for spanning trees, a priority queue for shortest paths. Sorting starts with selection sort in the first chapter and rests on divide and conquer and the heap in the last chapter.

Course page: Data Structures and Algorithms with C · Glossary · © Sercan Külcü. All rights reserved.