CIS 2101 · 12 units

Watch the structure, not just the output.

The ADTs the course builds in C, from lists, stacks and queues to hash tables, heaps and graphs. Every question is a real program: after you mark it, step through the run and watch the structure change, drawn the way it is drawn on the board.

Units

In the order the course builds them.

12 units

U12 topics
Abstract Data Types
An ADT is a set of values and the operations on them, and nothing about how they're stored. Tell the ADT from the struct that implements it, and the operation from the code behind it.
Not started
U25 topics
ADT List
Initialize, insert, delete, member and locate, three ways: an array in its four versions, a singly linked list, and a cursor-based list living in a virtual heap. Then what each operation costs in each.
Not started
U34 topics
ADT Stack
Last in, first out: push, pop and top, with initStack, isEmpty and isFull. The same stack in an array, a linked list and a virtual heap — and why a stack can't be traversed.
Not started
U44 topics
ADT Queue
First in, first out: enqueue, dequeue and front. Front and rear pointers, the circular array with its two ways to tell full from empty, and the cursor-based queue.
Not started
U54 topics
ADT Set
No duplicates, no order. Union, intersection and difference on sorted arrays and linked lists, then the bit-vector and the computer word — one bit per element, worked with << >> & | ^ ~.
Not started
U65 topics
ADT Dictionary
Insert, delete and member in close to O(1). Open hashing chains synonyms in a list per bucket; closed hashing probes for the next free slot — with deleted marks, packing density and average search length.
Not started
U75 topics
ADT Tree
Root, parent, leaf, height and depth. The three traversals, the parent-pointer array and the list of children, binary and expression trees, and building a Huffman code.
Not started
U84 topics
Binary Search Tree
Smaller to the left, larger to the right. Insert and member down one path, delete with its three cases, what an AVL tree adds, and why halving beats scanning.
Not started
U94 topics
ADT Priority Queue
A partially ordered tree kept in an array: children at 2i + 1 and 2i + 2. Insert bubbles up, deleteMin and deleteMax sift down, and heapify builds one either by inserting or from the lowest parent up.
Not started
U102 topics
Heapsort
Heapify the array, then swap the root to the end and sift down, again and again — sorted without a second array. Trace it pass by pass.
Not started
U113 topics
Directed and Undirected Graphs
Vertices, edges, arcs, weights, degree and paths. The same graph as an adjacency matrix and as adjacency lists, directed and undirected.
Not started
U126 topics
Graph Algorithms
BFS and DFS orders, Dijkstra's single-source shortest paths, Floyd's all pairs, Warshall's reachability, and the minimum-cost spanning trees Prim's and Kruskal's build.
Not started

Watch the structure, not just the output.

Units

Abstract Data Types

ADT List

ADT Stack

ADT Queue

ADT Set

ADT Dictionary

ADT Tree

Binary Search Tree

ADT Priority Queue

Heapsort

Directed and Undirected Graphs

Graph Algorithms

Reference

C visualizer

C tracer