CSCI2520
Data structures
Programming foundations, abstract data types with stacks, queues and hashing, lists and recursion, complexity and sorting, trees and binary search trees, graphs, and heaps with greedy coding.
Your progress
0/ 14 sections marked complete
Next section: 0.1 Pointers, memory, and structs
Completion marks are saved in this browser.
This course in the web
In the CSCI2520 notes
- Theorem cards
- 34
- Definitions
- 47
- Counterexamples
- 0
- Concept lenses
- 0
- Histories of ideas
- 0
- Proof X-rays
- 0
No concept lens from this course is recorded in the web yet.
Counts cover the 14 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 34 · Definitions 47
No concept lens from this course is recorded in the web yet.
Counts cover the 14 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 0 · 1 section
Programming foundations
Language and memory tools used throughout the data-structure notes.
Theorems 2 · Definitions 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 0.1
Pointers, memory, and structs
Review the C language tools that the course uses to explain data-structure behavior: pointers, malloc, typedef, and struct layout.
Chapter 1 · 2 sections
ADT and operation semantics
From ADT contracts to stack/queue behavior and dictionary-style hashing operations.
Theorems 3 · Definitions 11
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
ADT operations: stack, queue, and function pointers
Build a precise ADT view of stacks, queues, and function-pointer-based operation dispatch in C data-structure implementations.
- 1.2
Hash tables and collision strategies
Use dictionary operations, hash functions, collisions, and chaining to understand why hash tables trade ordered structure for fast average-case access.
Chapter 2 · 1 section
Lists and recursion
Recursive list contracts, head-tail reasoning, and representation-aware operation cost.
Theorems 2 · Definitions 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Lists as recursive ADTs
Read lists as recursive head-tail ADTs, then compare iterative and recursive operation implementations.
Chapter 3 · 2 sections
Complexity and sorting
Asymptotic growth, cost comparison, and sorting-oriented complexity reasoning.
Theorems 5 · Definitions 8
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Complexity growth and algorithmic cost
Interpret asymptotic growth and compare algorithmic costs before implementing sorting or selection routines.
- 3.2
Selection, quickselect, and linear-time sorting
Separate selection from full sorting, then use quickselect, counting sort, and radix sort to understand when extra structure improves complexity.
Chapter 4 · 2 sections
Trees and BSTs
Binary tree traversal, reconstruction, and binary-search-tree operations.
Theorems 6 · Definitions 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Binary tree traversal and reconstruction
Read recursive binary-tree structure through preorder, inorder, and postorder traversal, then reconstruct trees from sufficient traversal information.
- 4.2
Binary search trees and core operations
Maintain the binary-search-tree ordering invariant through search, extrema, insertion, successor, and deletion operations, with costs measured by tree height.
Chapter 5 · 4 sections
Graphs
Graph representations and traversals, minimum spanning trees, shortest paths, and topological ordering.
Theorems 10 · Definitions 11
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Graph representations, DFS, and BFS
Compare adjacency matrices and lists, then trace DFS and BFS while maintaining correct frontier and visited-state invariants.
- 5.2
Minimum spanning trees: Prim and Kruskal
Construct minimum spanning trees with Prim's and Kruskal's greedy choices while distinguishing the MST objective from shortest paths.
- 5.3
Shortest paths and Dijkstra's algorithm
Use relaxation and settled-vertex reasoning to compute single-source shortest paths with Dijkstra's algorithm under nonnegative edge weights.
- 5.4
Topological sorting of DAGs
Order the vertices of a DAG with Kahn's indegree process and DFS finishing times, using both methods to expose directed cycles.
Chapter 6 · 2 sections
Heaps and greedy coding
Binary heaps, priority queues, Huffman coding, and heap-based multiway merging.
Theorems 6 · Definitions 7
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Binary heaps and priority queues
Represent a complete binary tree in an array and maintain min-heap order through priority-queue operations and bottom-up construction.
- 6.2
Huffman coding and heap applications
Build a prefix-free Huffman code by repeated minimum-frequency merges, then reuse the heap abstraction for efficient multiway merging.