ILTS Computer Science (205): Data Structures and Databases

Domain 3 tests selection and implementation of data structures plus relational database design and querying. Expect complexity comparisons, trace questions, and SQL interpretation.

Core rules

• Arrays give O(1) index access but O(n) insertion/deletion in the middle. Linked lists give O(1) insertion at a known node but O(n) search. Stacks are LIFO; queues are FIFO.
• Binary search trees give O(log n) search when balanced, O(n) when skewed. Hash tables average O(1) lookup but degrade to O(n) with many collisions.
• Relational tables have a primary key; a foreign key references another table's key. NULL means unknown, so use IS NULL, not = NULL.
• SQL logical order is FROM/JOIN, WHERE, GROUP BY, HAVING, SELECT, ORDER BY. WHERE filters rows before grouping; HAVING filters groups.
• Normalization reduces redundancy and update anomalies; indexes speed reads but add write and storage cost. Transactions aim for atomicity, consistency, isolation, durability.

Worked example

Tables: Student(id, name, advisor_id) and Advisor(id, name). To list students advised by Ng: SELECT s.name FROM Student s JOIN Advisor a ON s.advisor_id = a.id WHERE a.name = 'Ng';. The join matches each student to an advisor through the foreign key; the WHERE clause filters advisor rows. Selecting a.name instead of s.name would return the advisor's name, not the student's.

Traps

Calling a foreign key a primary key; using UNION when JOIN is needed; expecting hash tables to guarantee O(1) worst case; forgetting that a stack reverses order; and assuming more indexes always improve performance. Normalization is not the same as adding constraints.