ATLAS 2270 Spring 2025 Exam 1 Study Guide

First: don't panic! Some of you have told me that you're afraid of the exams. Yes, exams are about assessment, but for me they're also foils to help you learn the topic at hand. So I want to make this as helpful as possible. Five years from now it probably won't matter what specific grade you got on this exam, but it will probably matter that you understand how to build things with data structures and algorithms.

Second: this is a study guide and shouldn't be considered a comprehensive replacement for all the material from class. I'll try to box things up with a nice bow on top, but this is still just a summary.

Topics and question types

There are three main topics to this first exam:

References which we covered with the Linked Lists homework.
Recursion which we covered with the Binary Search Tree homework.
Complexity which cross-cuts everything throughout the course.

And some general kinds of questions I've been known to ask:

Execution: "Here's a problem, please write a solution in code or pseudocode."
Debugging: "Here's a passage of code but it has a bug. Find and fix the bug."
Comprehension: "Here's some code and some inputs. What are the outputs?"
Complexity: "Here's an algorithm. What is its complexity?"

Starting with Complexity

Since complexity (big oh notation, algorithm analysis) is something that cross cuts everything in the course, I'll address this first.

Computational complexity is used to describe how much time or space (memory) is used by an algorithm depending on its input size n. There are several common runtime complexities:

O(1) is constant time and means the algorithm's time is not bounded by the input size n.
O(log n) is logarithmic time and is commonly associated with algorithms that repeatedly subdivide their work, such as by cutting the search space in half on every iteration.
O(n) is linear time and means that some amount of work is performed for every item in the input, such as examining every number in a list to compute a sum total.
O(n log n) is log linear time and often means we are performing an O(log n) operation inside an O(n) loop.
O(n^2) is quadratic time and like above often means we're nesting operations. In the case of quadratic time, we're doing an O(n) thing inside an O(n) loop.

In lectures I had that weird series of phone book examples. You could go through those to make a punchlist for your cheat sheet.

A few words of advise about complexity, and where "trick" questions might come up.

If you see a loop, ask yourself how many times it will run:

const sum = (data: number[]) => {
  let total = 0;
  for (let i = 0; i < 1000; i++) {
    total = total + data[i];
  }
};

What is the complexity here? We're sort of looping through a list of numbers, right? So you might be tempted to say this is O(n) because we're looping and accessing elements of data. But look at which values i takes on. It runs from 0 up to 1000, and it doesn't matter what the length of the data is. The runtime complexity of this code is O(1) because it does not grow with the input size. This is a trick question, and I've been on the receiving end of job interview questions like this.

(There is also a bug in this code that isn't really related to complexity. I'll return to that.)

The heuristics to keep in mind for complexity:

Constant time operations do a fixed or limited amount of work. Examples are things like removing the first item from a linked list.
Logarithmic time operations iteratively chop out a fraction of the search space. Examples are everywhere with binary search trees: every time you follow a child link, you're culling the seach space by a factor of two.
Linear time operations typically touch every item in the input list, for example if you're calculating a sum or average, or if you're looking for an item in an unsorted list.

The log linear and quadratic operations are often (but not always!) the result of nesting one algorithm into another. For example, inserting a single item into a Binary Search Tree is O(log n), and iterating through every item in a linked list is O(n). But inserting every item from a linked list into a BST will be O(n log n) because the BST insert is nested inside a linked list scan: O(n) * O(log n) gives you O(n log n).

References & Linked Lists

Linked lists are built from nodes that include (a) some data value, and (b) a reference to the next node in the list. The last node's reference is empty to indicate it is the end of the list.

References are simple variables that simply refer to something else. You can use a reference to read or write the thing that it references. You can also change the reference itself, which just changes what it refers to and doesn't modify the thing that it was referring to. For example:

// declare and initialize two variables to object references
let personA = { name: "Jack", age: 19 };
let personB = { name: "Diane", age: 18 };

// At this point, personA and personB are both references to
// the objects you see above. Objects in Javascript (and many
// other languages) are handled by reference.

// Change the referenced object's name from Jack to John
personA.name = "John";

// Create a new reference to the Diane object.
personC = personB;

// Update the personB reference itself to something new. This
// does not change the value that personB used to point to.
personB = { name: "Jill", age: 20 };

// Print the names and ages of everybody:
console.log(personA); // prints {name: 'John', age: 19}
console.log(personB); // prints {name: 'Jill', age: 20}
console.log(personC); // prints {name: 'Diane', age: 18}

Iterating a linked list

The general form for scanning the contents of a linked list myList is thus:

let cursor = myList;
while (cursor != null) {
  // 1. Do something with the current data, such as counting
  // the number of values in the list:
  count++;
  // 2. Increment the cursor to reference the next value
  cursor = cursor.next;
}

The while loop will continue iterating as long as cursor != null.

The "do something" step can involve lots of things, and it all depends on what you're trying to do. See if you can write code to do these things:

Scan a list to count the number of odd values.
Scan a list to count the number of zeros.
Scan a list and return the first node whose value is less than three.
Scan a list and set the prev and cursor references to nodes that appear at offset - 1 and offset, respectively.

If you can write those in either pseudocode or actual code syntax, you're good to go for the exam.

Complexity of linked list operations

Go thru the slides and be sure you know the complexity of the following operations, and why:

Append a value to the end: O(n)
Insert a value at an arbitrary offset: O(n)
Remove a value from an arbitrary offset: O(n)
Remove a value from the beginning of the list: O(1)

Recursion and Binary Search Trees

A recursive function is one that calls itself. For example, a linked list size function could be written with recursion:

const linkedListSize = (list: LinkedList) => {
  if (list != null) {
    return 1 + linkedListSize(list.next);
  } else {
    return 0;
  }
};

Binary trees are structures where each node contains a data value, and two references to other binary tree nodes called left and right.

Binary search trees include rules (invariants) that the values down the left path are strictly smaller than the parent; all other values are found down the right path.

Algorithms that read or write binary search tree data can use this data ordering to efficiently find the correct location. For example, if we are looking for the value 5, and the node we are looking at has the value 9... which path should we look?

Here's a recursive function for checking to see if a BST contains a given value:

const bstContainsValue = (bst: BinarySearchTree, value: number) => {
  if (bst == null) {
    // if we get here, it means the value is not in the tree
    return false;
  }
  if (bst.data == value) {
    // if we get here, we've found it!
    return true;
  }
  if (value < bst.data) {
    // if the value is in the tree it will be down the left side.
    return bstContainsValue(bst.left, value);
  } else {
    // otherwise, it will be down the right side.
    return bstContainsValue(bst.right, value);
  }
};

See if you can write recursive functions to do various things with binary search trees and linked lists:

Count the number of values greater than 10
Find the node (if any) whose value is 10
Find the smallest value in a BST
Find the average value in a BST
Remove all the odd values from a BST
Re-write the linked list 'contains' function to be recursive

Complexity of BST operations

Like Linked Lists you'll need to understand the runtime complexity of the main BST operations, along with why:

Insert: O(log n)
Find: O(log n)
Remove: O(log n)

Debugging Questions

I will ask some questions about code that has bugs, and you'll need to spot the bug and possibly fix it.

Spot the bugs

Earlier in this study guide I showed this code:

const sum = (data: number[]) => {
  let total = 0;
  for (let i = 0; i < 1000; i++) {
    total = total + data[i];
  }
};

There is a bunch wrong with this (so much that I wouldn't actually ask a question with it). What bugs can you spot?

Spoilers:

We're iterating from 0 to 1000, not from 0 to data.length, so this won't compute the sum of the list if it has more than a thousand items.
Since we're unconditionally iterating from 0 to 1000, if the list actually has less than 1000 items, it will read values that don't actually exist in the list.
The function doesn't actually return anything!

Fix the code

Say your peer shows you their code that isn't working:

const removeAt = (list: LinkedList, offset: number): void => {
  let cursor = list;
  let count = 0;
  while (list != null) {
    if (count === offset - 1) {
      cursor.next = cursor.next.next;
    }
    count++;
    cursor = cursor.next;
  }
};

There are a couple things that could be wrong with this, so you can pick whichever you see first. First, describe in plain language what the problem is and propose a solution either in plain language or in code.

Comprehension

Some questions will simply be "here is some code, what does it do?" and you'll need to translate from code or pseudocode into English. Something like this:

const doSomething(list: LinkedList, a: number, b: number) => {
    let cursor = list;
    while (cursor != null) {
        if (cursor.data < a) {
            cursor.data = a;
        }
        if (cursor.data > b) {
            cursor.data = b;
        }
        cursor = cursor.next;
    }
}

Read the code, become one with it. Do you see what it does? I will probably also ask about the complexity of these functions as a separate follow-on question.