How to prepare for Lafayette CS 150

CS 150 Data Structures and Algorithms is the course that opens up the rest of the major. In the Lafayette catalog, CS 202, CS 203 and CS 205 all list it as a prerequisite, and most upper-level courses depend on those. That's why a little preparation here pays off for the next three years.

This guide doesn't cover any specific section, professor or assignment. Your syllabus decides the language and the schedule. The examples below are in Python because it's short to read, and the ideas carry over to whatever your section uses.

What the course asks of you

The catalog describes two things: object-oriented design, and data structures with the algorithms that store and find data. In practice, the step up from an intro course is that you stop writing code that just runs and start reasoning about what it does in memory and how long it takes.

Three self-checks

Try these on paper before reading the answers. If you get all three, you're in good shape. If one surprises you, that's what to review.

1. Do two names point to the same object?

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

a = Node(1)
b = Node(2, a)
c = b
c.value = 9

print(b.value)       # ?
print(b.next.value)  # ?

Answer: 9, then 1. The line c = b doesn't copy anything. It gives the same object a second name, so changing it through c also changes what b sees. This one idea is behind most linked list bugs. Get into the habit of drawing boxes and arrows.

2. Can you trace a recursive call?

def count(n):
    if n == 0:
        return 0
    return 1 + count(n - 1)

print(count(3))  # What's on the stack at the deepest point?

Answer: it prints 3, with four calls on the stack at the deepest point: count(3), count(2), count(1) and count(0). Nothing returns until the base case is reached. If you can write out the stack by hand, recursive tree code will feel much less like magic.

3. How does the work grow?

def has_duplicate(items):
    seen = []
    for x in items:
        if x in seen:
            return True
        seen.append(x)
    return False

Answer: O(n²) in the worst case. x in seen looks like one step, but it scans the whole list. Double the input and the work roughly quadruples. Using a set makes each lookup constant time on average, which makes the whole function O(n). Being able to see the hidden loop is a skill you'll use constantly.

A two-week plan

Days 1 to 3: classes and objects. Write a small class from scratch, such as a bank account or playlist, with methods that change its state. Then explain out loud the difference between a class and an object.

Days 4 to 6: arrays and loops. Reverse an array in place. Find the largest value without using a built-in function. Write nested loops that print a grid. These should stop feeling hard.

Days 7 to 9: references. Build a linked list by hand with three nodes. Print it, add to the front, then remove the middle one. Draw it after each step.

Days 10 to 12: recursion. Write factorial, then sum of a list, then reverse a string. Trace each one on paper before running it.

Days 13 and 14: read errors on purpose. Break your own code in small ways and read the message. Learn what a null reference or index error looks like, because you'll see them often.

Once the course starts

• Start assignments the day they're posted. The bugs in this course take time to find, and you can't rush thinking about pointers.
• Draw before you code. For any structure, sketch what happens to the arrows first, including the empty case and the one-item case.
• Test the edges. Empty list, one item, first position, last position. Most bugs are there.
• Use office hours early. They're free, and your professor knows the assignment. Follow your course's collaboration policy for any help you get, including from me.

After CS 150, the same ideas continue into CS 202 Analysis of Algorithms, where you'll prove what you practiced here.