Course Outline

Description

How do we organize data to solve complex problems efficiently? This course studies the fundamental structures and algorithms that form the cornerstone of computational problem-solving. Building upon the programming foundations established in CS1, we will explore how algorithmic thinking and sophisticated data organization enables us to tackle increasingly challenging computational problems.

In this course, you will analyze how fast algorithms run and how much memory they use. These are skills you need to write programs that actually work on real data. You will implement classic data structures like arrays, lists, hash tables, trees, graphs, and stacks, and figure out when to use each one. The exercises we study will teach you to pick the right algorithmic approach for different problems.

We balances theory with hands-on implementation using the Racket language. You’ll get better at programming while learning to recognize elegant solutions. This course is a prerequisite for Artificial Intelligence.

Learning Outcomes

1. Use complexity analysis to evaluate and compare different algorithmic solutions.
2. Implement fundamental data structures including arrays, lists, hash tables, trees, graphs, and stacks to organize and manipulate data efficiently.
3. Apply appropriate data structures and algorithms to solve computational problems based on their specific requirements and constraints.
4. Design solutions using algorithmic paradigms such as recursion, greedy algorithms, and dynamic programming.
5. Evaluate the trade-offs between different data structures and algorithms through theoretical analysis and practical implementation.

Readings

• Bhargava, Aditya Y. Grokking Algorithms, 2nd ed. Manning, 2024.

Evaluation

• Midterm and Final Examination: Both tests will cover everything we’ve discussed in class and read about. You’ll see conceptual questions, complexity analysis problems, and algorithm design challenges.

• Engagement: Your engagement grade comes from completing exercises on time, active participation, and showing up regularly. The exercises are based on our readings, and are listed on the class schedule.

External Links

1. Class Schedule: Current schedule of readings and exercises
2. Electronic Whiteboard: For information sharing during class
3. Etherpad: For code sharing during class
4. DrRacket: Our development environment, to be installed on your machine
5. How to Design Programs (Prologue): Quickly get some experience with Racket
6. Simply Scheme: Introducing Computer Science: Learning Scheme step-by-step
7. The Structure and Interpretation of Computer Programs: Learning Scheme in large chunks

Racket

We use Racket because its clean presentation lets you focus on algorithms instead of fighting with syntax. More importantly, functional programming forces you to think recursively, which is exactly how many of the most powerful algorithms work. Tree traversals, graph searches, divide-and-conquer algorithms: they all become clearer when you’re not constantly mutating variables and tracking state.

Racket stands in the tradition of languages like Lisp and Scheme: languages created to explore the deepest ideas of computer science, not just to follow industry trends. Dijkstra once said that Lisp has been called “the most intelligent way to misuse a computer,” and he meant it as a compliment because “it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts.” That’s what we’re after here. Using Racket will change how you think about algorithmic problems, often revealing solutions that mirror the logical structure of the problems themselves.

1. Download Racket from here. There are versions for all modern Macs, Linux machines, and Windows. The file name will look something like:

   • racket-8.x-aarch64-macosx-cs.dmg on an Apple Silicon Mac
   • racket-8.x-x86_64-macosx-cs.dmg on an Intel Mac
   • racket-8.x-x86_64-win32-cs.exe on a PC
   • racket-8.x-x86_64-linux-cs.sh on Linux

2. Install Racket: On a Mac, open the .dmg file and drag the Racket folder to Applications. On a PC, run the .exe installer and follow the prompts. On Linux, open a terminal and run: sh racket-8.x-x86_64-linux-cs.sh.

3. Start DrRacket: On a Mac: this is in the Racket folder of your Applications list. If your computer complains that DrRacket is not from a “trusted developer,” go into the Finder, then Applications, right-click DrRacket, and click “Open” to bypass this. You only need to do this once. On a PC: this is in the Racket folder of your Applications list. On Linux: after installation, you can usually start DrRacket from your Applications menu. If not, open a terminal and run: drracket &

Lab computers in Dickinson have DrRacket pre-installed, if you prefer not to install it on your personal machine. You can also use them as a backup if your installation runs into problems.

Course Policies

1. Outline: This outline is subject to arbitrary change. I shall announce any changes in class; if you are not present, you are still responsible for finding out what I announce.
2. Late exercises: Exercises will not be accepted late without an acceptable medical or compassionate reason. All exercises are due at the beginning of class for which they are assigned.
3. Attendance: Come to class. Three unexcused absences might mean a marginal pass; four could mean a failure, even if your other work is fine. Excused absences don’t count.
4. Laptops and Cell Phones: Don’t use mobile technology in class unless I specifically permit it. Take notes with pencil and paper (unless you have special accommodations).
5. AI Tools: Don’t use ChatGPT or similar tools for assignments unless I explicitly allow it. If I do allow it, you must cite exactly how you used it according to Chicago style.
6. Office hours: Office hours are first-come-first-serve, unless you have an appointment. If you want to schedule something, email me a few times that work for you.
7. College Policies: Be familiar with the college rules on class attendance, as well as academic and artistic ethics.
8. Grading: If you opt for a letter-grade, your mark in the course will be translated according to the following scale: A+ (90–100), A (85–89), A– (80–84), B+ (77–79), B (73–76), B– (70–72), C+ (67–69), C (63–66), C– (60–62), D (50–59), F (0–49). If you do not opt for a letter-grade, the scale is as follows: Pass (65–100), Marginal Pass (50–62), Fail (0-49).

A Note about AI within Computer Science

Artificial intelligence can generate code, but it cannot decide what problems are worth solving, nor judge whether a solution is effective, ethical, or just. Computer science is less about mastering tools than about cultivating the habits of mind that let us interpret, understand, and evaluate. It asks how abstractions shape systems, how systems shape society, and how we might imagine technology serving human flourishing rather than undermining it. To study CS is therefore not only to learn how machines work, but to engage in broader questions about seeing clearly, reasoning correctly, and imagining responsibly in a world increasingly shaped by computation.

A Note on Liberal Arts Learning

An overarching objective of this course is to help you develop as a student of the liberal arts. True students of the liberal arts are able to reflect on the context in which they live, and reason about what it means to live a meaningful and happy life. Thus, they are able to be more than just children of their own time. But this means we must be willing to put our ideas to the test, see our own errors, and develop intellectual courage and humility. It also helps not to take ourselves too seriously.