ECE 250: Algorithms and Data Structures

Sources and References

Equivalent UW courses — CS 240 (Data Structures and Data Management), CS 341 (Algorithm Design and Analysis) Primary textbook — Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Addison Wesley, 2014 Supplementary references — Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), MIT Press, 2022

Equivalent UW Courses

ECE 250 compresses the content of the two-course CS sequence CS 240 + CS 341 into a single term aimed at second-year computer and electrical engineers. CS 240 covers the data-structure half (ADTs, hashing, trees, sorting), while CS 341 covers the algorithm-design half (divide-and-conquer, greedy, dynamic programming, graph algorithms, NP-completeness). ECE 250 visits essentially all of these topics but with less time per item and with a strong C++ implementation emphasis; the CS antirequisites list (CS 234/240/341) confirms this overlap explicitly. A student who does well in ECE 250 has seen most of CS 240 and a solid slice of CS 341, though without the same mathematical depth.

What This Course Adds Beyond the Equivalents

ECE 250 is taught in C++ with explicit memory management, so students get more low-level implementation practice — pointers, manual allocation, templates, and performance tuning — than CS 240/341 typically require. The lab component centres on building working data structures and measuring them, an engineering angle that the CS versions treat more lightly. What ECE 250 omits or reduces relative to the CS pair is mathematical rigour: CS 341 spends much more time on formal analysis, amortized arguments, lower bounds, linear programming, and reductions. Advanced randomized algorithms, approximation algorithms, and the theoretical treatment of NP-completeness in CS 341 are touched only briefly in ECE 250.

Topic Summary

Asymptotic and Algorithm Analysis

Big-O, big-Omega, and big-Theta notation; worst-case, average-case, and amortized analysis; recurrence relations and the master theorem. Used as the common language for comparing algorithm efficiency throughout the rest of the course.

Elementary Data Structures

Arrays, linked lists, stacks, queues, and deques as abstract data types and as concrete implementations. The distinction between interface and implementation is introduced here and reused for every later structure.

Hashing

Hash functions, collision resolution via chaining and open addressing (linear probing, double hashing), and load-factor analysis. Expected \( O(1) \) operations under uniform hashing justify why hash tables dominate dictionary implementations in practice.

Search Trees, Balanced BSTs, B-Trees

Binary search trees and the rotations needed to keep them balanced (AVL, red-black), plus B-trees for disk-resident data. Balanced-BST operations run in \( O(\log n) \), and B-trees minimize block reads for large external datasets.

Heaps and Priority Queues

Binary heaps as an implicit array layout, with \( O(\log n) \) insert and extract-min. Priority queues power Dijkstra, Prim, and event-driven simulation, and are the basis for heapsort.

Sorting Algorithms

Comparison sorts (insertion, merge, quicksort, heapsort) and non-comparison sorts (counting, radix, bucket). The \( \Omega(n \log n) \) comparison lower bound and the stability/in-place trade-offs motivate why different sorts are chosen in different settings.

Algorithmic Paradigms

Divide-and-conquer, greedy, dynamic programming, and backtracking, illustrated through classic examples such as matrix-chain multiplication, longest common subsequence, and knapsack. The paradigms give students a vocabulary for recognising which technique fits a new problem.

Graphs

Representations (adjacency matrix and list), traversal (BFS, DFS), shortest paths (Dijkstra, Bellman-Ford), minimum spanning trees (Kruskal, Prim), and topological sort. Graphs tie together most of the earlier structures (queues, heaps, union-find) and underlie routing, scheduling, and dependency analysis.

NP-Completeness

Polynomial-time reductions, the classes P and NP, and canonical NP-complete problems (SAT, vertex cover, Hamiltonian cycle). The goal is to recognise when a problem is unlikely to admit an efficient exact algorithm so that heuristics or approximations can be used instead.