WGU · C949v5

Data Structures & Algorithms — Study Guide

Every topic on the assessment blueprint, explained with worked examples — plus an interactive trace tool for the pseudocode-reading skill the course flags as hardest.

Explains Algorithms

29%

Introduction to Algorithms Ch. 1

An algorithm is a finite, well-defined sequence of steps that takes some input and produces a correct output. Judge algorithms on correctness — does it always produce the right answer — and efficiency — how much time and memory it uses as input grows.

Tip
Review the website links in Chapter 1. Conceptual questions on the exam draw from those linked readings, not just the textbook prose.

Classes Ch. 20

A class is a blueprint for objects; it bundles data (attributes) with the behavior (methods) that acts on that data. An object is one instance of a class.

Encapsulation

Bundling data and methods together, controlling access with private/public visibility.

Constructor

Special method that runs when an object is created — sets initial attribute values.

Instance vs. class variables

Instance variables belong to one object; class (static) variables are shared across all instances.

this / self

Reference inside a method to the specific object the method was called on.

Recursive Algorithms Ch. 11, 21

A recursive algorithm calls itself on a smaller version of the same problem. Every correct recursive function needs two parts:

Base case

The smallest version of the problem, solved directly — this stops the recursion.

Recursive case

Reduces the problem and calls the function again, moving closer to the base case.

function factorial(n):
    if n == 0: return 1              // base case
    else: return n * factorial(n-1)  // recursive case

Each call is pushed onto the call stack; once the base case hits, calls resolve ("unwind") in reverse order. A function that never reaches its base case causes infinite recursion and a stack overflow.

Linear & Binary Search

Linear Search 11.1

Checks each element in order until it finds the target or reaches the end. Works on sorted or unsorted data.

Best O(1) Worst O(n)

Binary Search 11.2

Requires sorted data. Compares target to the middle element and discards the half that can't contain it — repeat.

Worst O(log n)

Trace: searching for 7 in [1,3,5,7,9,11,13] → mid=7, match on the first comparison. Searching for 9: mid=7, 9>7 → search right half [9,11,13]; mid=11, 9<11 → search left half [9]; mid=9 → match.

Sorting Algorithms Ch. 11

You need to both explain how each sort works and recognize it from pseudocode.

Algorithm	How it works	Recognize it by	Worst case
Bubble Sort	Repeatedly compares adjacent pairs, swapping if out of order — largest values "bubble" to the end each pass.	Nested loop with an adjacent swap: arr[i], arr[i+1]	O(n²)
Selection Sort	Each pass finds the min (or max) of the unsorted portion and swaps it into place at the front.	Tracks a "min index" while scanning; one swap per outer pass	O(n²)
Insertion Sort	Builds the sorted list one element at a time, shifting larger elements right to insert in place.	Shifting elements right inside a while loop — like sorting a hand of cards	O(n²)
Quick Sort	Picks a pivot, partitions so smaller values are left and larger are right, recursively sorts each side.	Keywords "pivot" and/or "partition" / "split"	O(n²) (avg O(n log n))
Merge Sort	Recursively splits the array in half until pieces have one element, then merges sorted halves.	Recursive halving, followed by a merge comparing two sorted lists	O(n log n)
Heap Sort	Builds a max-heap, then repeatedly removes the root (largest) and re-heapifies.	References to a heap / heapify operation	O(n log n)
Bucket Sort	Distributes values into "buckets" by range, sorts each bucket, then concatenates.	Keyword "bucket"; grouping by range before sorting	varies
Radix Sort	Sorts digit by digit, least significant to most significant, using a stable sort each pass.	Sorting passes keyed on individual digits, not whole-value comparisons	O(nk)

Watch Each Algorithm — Animated, Same Input Array

Every panel below sorts the same starting array [64, 34, 25, 12, 22, 11, 90, 45, 5, 77] so you can compare how each algorithm moves through it. Amber = comparing · Coral = swapping/writing · Green = settled into final position.

Playback speed 1×

Big O — Time Complexity & Efficiency 11.7

Big O describes how running time (or memory) grows as input size n grows — usually the worst case. Constants and lower-order terms are ignored; what matters is growth rate at scale.

Illustrative bar heights (not to scale) — operation counts shown for n = 16.

Big O	Name	Example
O(1)	Constant	Array index access; average-case hash table lookup.
O(log n)	Logarithmic	Binary search.
O(n)	Linear	Linear search; a single pass over a list.
O(n log n)	Linearithmic	Merge sort, heap sort.
O(n²)	Quadratic	Bubble, selection, insertion sort (nested loops over n).

Best case = fewest steps for some input (insertion sort on an already-sorted list: O(n)). Worst case = most steps possible (insertion sort on reverse-sorted data: O(n²)). Average case = expected performance across all inputs. Quicksort's O(n²) above is worst case only — in practice, with good pivot choices, it usually runs closer to O(n log n).

Worst-case complexities to memorize

Selection Sort O(n²)

Insertion Sort O(n²)

Bubble Sort O(n²)

Quick Sort O(n²) worst / O(n log n) average

Merge Sort O(n log n)

Heap Sort O(n log n)

Radix Sort O(nk) — k = digits in the largest number

Trace Practice — Nested Loop Walkthrough

Tip
You'll need to read pseudocode cold. Practice writing out steps by hand — one misstep gives you the wrong answer choice. This is the hardest section on the exam.

Step through the trace

i–

j–

Output: (none yet)

Determines Data Structure Impact

31%

Core Structures

Array 1.1

Fixed-size, contiguous memory, zero-based index.

Read by index O(1) · Insert/delete mid O(n)

Linked List Ch. 2

Nodes chained via next (and prev, if doubly linked) pointers.

Insert/delete at known node O(1) · Traverse to find O(n)

Stack Ch. 3

LIFO. push() adds to top; pop() removes top; peek() reads top.

All ops O(1)

Queue Ch. 3

FIFO. enqueue() adds to rear; dequeue() removes from front.

list.pop(0) is O(n) — use deque instead

Deque Ch. 3

"Double-ended queue" — append/appendleft/pop/popleft at both ends.

All ops O(1)

Hash Table Ch. 4

Maps keys to indices via a hash function. Collisions resolved by chaining or open addressing.

Avg insert/search/delete O(1)

Tree Ch. 4

Hierarchical nodes with one root. A leaf has no children. Height = longest root-to-leaf path.

Heap Ch. 7

Complete binary tree. Max-heap: parent ≥ children. Min-heap: parent ≤ children. Backs priority queues.

Insert/remove O(log n)

Set Ch. 8

Unordered, unique elements. Supports union, intersection, difference.

Graph Ch. 9

Vertices connected by edges. Represented via adjacency list (sparse-friendly) or adjacency matrix (fast lookup).

.pop() by Structure

Tip
Per the pre-assessment, this competency leans heavily on basic stack/queue/dictionary functions — especially .pop() and .push().

Structure	What .pop() does
Stack	Removes and returns the most recently added (top/last) element — LIFO.
Queue	Removes and returns the front (oldest) element — FIFO. On a plain Python list: `pop(0)`. With `collections.deque`: `popleft()`.
Priority Queue	Removes and returns the highest-priority element. Python's `heapq.heappop()` returns the smallest value by default (min-heap).

Tree Traversal 5.7

Order of visiting every node in a binary tree — example tree: root 5, left child 3, right child 8.

Traversal	Order	Result on example
Inorder	Left → Node → Right	3, 5, 8 (sorted order for a BST)
Preorder	Node → Left → Right	5, 3, 8
Postorder	Left → Right → Node	3, 8, 5

Hashing 4.1

Hashing

Running a key through a hash function to produce an integer, mapped to an array index.

Chaining

Collision handling — each slot holds a small list of all pairs that hashed there.

Hash key

The resulting index/value produced by hashing a key.

Modulo operator

index = hash(key) % table_size. If table_size=10 and hash(key)=47, then 47 % 10 = 7 → stored at index 7.

Design of Data Structures

ADT characteristics 1.5, 1.6 — an Abstract Data Type defines what operations a structure supports, not how they're implemented. A Stack ADT guarantees push/pop/peek behavior whether it's built on an array or a linked list underneath.

Tip
Know how each structure compares, inserts, and deletes elements — which support indexing, and which have hierarchy vs. a flat layout.

Linear structures

Array, Linked List, Doubly Linked List, Queue, Stack — flat, sequential.

Hierarchical structures

Binary Tree, Heap — parent/child relationships, height and depth matter.

Graph structures

Vertices + edges, optionally weighted/directed — no single "flat" order.

Applies Algorithms

40%

Programming Basics

Variable declaration — dynamic vs. static 18.3

Static languages (Java, C++) require a fixed type up front: int x = 10;. Dynamic languages (Python) infer type at runtime and allow reassignment to a different type entirely.

Assignment operators 13.1

=	Assign — `x = 5`
+=	Add & assign — `x = x + 5`
-=	Subtract & assign
*=	Multiply & assign
/=	Divide & assign
%=	Modulo & assign

Order of operations / precedence 13, 15

Highest → lowest: parentheses → exponentiation → × / % → + − → comparisons → NOT → AND → OR. Ties resolve left to right.
2 + 3 * 4 → multiplication first → 2 + 12 = 14, not 20.

Loops Ch. 17

for — bounded iteration over a known range or collection.

while — repeats while a condition holds; count not known in advance.

do-while — condition checked after the body runs; executes at least once.

Conditionals / branching Ch. 15

if / else if / else chains branch on Boolean expressions; switch/case branches on discrete values of one variable. Only one branch executes per pass.

List, Stack & Deque Operations

Method	Effect
append(x)	Add to the end O(1) amortized.
insert(i, x)	Insert at index i, shifting right O(n).
remove(x)	Remove first occurrence of x O(n).
pop()	Remove & return last element O(1).
pop(i)	Remove & return element at index i O(n).
index(x)	Return index of first occurrence O(n).

Stack 3.1 — push(x)/pop()/peek(), all O(1). Deque 3.8 — append(x)/appendleft(x)/pop()/popleft(), all O(1) at both ends.

Identify Sorting Algorithms From Code

Bubble

Look for adjacent-element swaps that let the result "bubble" to the top.

Bucket

Look for values distributed into "buckets" sorted individually.

Merge

Look for something that continually splits a list in half.

Quicksort

Look for the keywords "pivot" and/or "split"/"partition".

Big-O primer video referenced in course materials: youtube.com/watch?v=__vX2sjlpXU

Reference — Abstract Data Types

List & Array

Function: ordered collection, same or mixed types.

Distinctions: ordered, indexable.

Underlying: dynamic array.

Syntax: [] creates a list · append() adds to end · pop() removes & returns last.

Tuple

Function: ordered collection, same or mixed types.

Distinctions: immutable.

Underlying: dynamic array.

Syntax: () creates a tuple · indexing/slicing to access.

Stack

Function: LIFO collection.

Distinctions: add/remove from the top only.

Underlying: dynamic array or linked list.

Syntax: append() adds to top · pop() removes & returns last.

Queue

Function: FIFO collection.

Distinctions: add at rear, remove from front.

Underlying: linked list.

Syntax: append() adds to rear · pop(0) removes & returns first.

Deque

Function: add/remove from both ends.

Distinctions: "double-ended queue".

Underlying: linked list.

Syntax: append()/appendleft()/pop()/popleft().

Bag

Function: unordered collection, duplicates allowed.

Distinctions: order not preserved.

Underlying: hash table.

Syntax: add() · remove().

Set

Function: unordered, unique elements.

Distinctions: no duplicates.

Underlying: hash table.

Syntax: set() · add() · remove().

Priority Queue

Function: elements dequeued by priority.

Distinctions: ordered by priority, not insertion order.

Underlying: heap.

Syntax: heapq module · heappush() · heappop().

Dictionary (Map)

Function: key-value pairs.

Distinctions: keys unique.

Underlying: hash table.

Syntax: {} creates a dict · keys() · values() · items().

Reference — Data Types

Type	Description	Java	Python
Boolean	Two possible values.	boolean x = true;	x = True
Byte	8-bit signed two's complement integer.	byte x = 10;	n/a — use int
Int	32-bit signed two's complement integer.	int x = 10;	x = 10
Char	Single Unicode character.	char x = 'a';	x = 'a'
Float	Single-precision 32-bit floating point.	float x = 3.14f;	x = 3.14
Double	Double-precision 64-bit floating point.	double x = 3.14;	x = 3.14
String	Sequence of characters.	String x = "Hello";	x = "Hello"

Reference — Core Concepts

Assignment vs. comparison

= assigns a value; == compares two values. x = 5 vs. if (x == 5):

Garbage collection

Automatic reclaiming of memory no longer used. Java's JVM and Python's interpreter both handle this automatically.

Reference count

How many times an object is referenced. In Python, when an object's reference count hits zero, the garbage collector deletes it.

Memory allocation (linked vs. sequential)

Linked allocation: memory reserved in linked nodes, each pointing to the next (linked lists). Sequential allocation: memory reserved contiguously (arrays).

Pointer

A variable storing another variable's memory address. C++: int *ptr.

Null

Represents the absence of a value. In Java, null can be assigned to reference types.

Object constructor

Special method that initializes a new object; shares the class's name in Java and runs automatically on new.