A second course in computer science. Data structures and algorithms are studied through major programming projects in the C++ programming language. Topics include linked lists, trees, graphs, dynamic storage allocation, and recursion.Prerequisite: Comp 11 or consent of instructor.
An alternative title for the course is:
Data Abstractions Every Working Programmer Must Know: Their Use, Implementation, and Performance
Students will learn about the use and implementation of a variety of standard containers focusing on their various interfaces and on the performance of their various operations.Students will learn to solve real-world problems by making appropriate data structure choices, reason about implementation alternatives, and analyze the costs associated with those choices. Students will also learn to write, debug, and test larger programs in a systematic way.
There are 2 weekly lectures, a weekly lab, and programming assignments written in C++.
Topics include:
- An introduction to asymptotic analysis
- Dynamic memory management
- Recursion
- Abstract data types
- Lists including array lists and linked lists
- Stacks
- Queues
- Sets
- Trees, including binary search trees and balanced binary trees
- Heaps
- Hash tables
- Graphs
- Sorting
Should I take Comp 11 or Comp 15?
Many incoming students or others with some programming experience are curious about whether they should take Comp 11 or 15.
Comp 11 and Comp 15 both use C++. Comp 11 covers problem solving and
basic programming skills from scratch, no experience necessary.
You'll learn about values, variables, expressions, conditional
execution (if statements), functions, recursion, loops,
and arrays. Unlike most courses students have elsewhere, students
also learn about computer memory organization, pointers, and manual
allocation and deallocation of memory (dynamic arrays and linked
lists). All of this is done on our department servers, which run
Linux.
Comp 15 starts from there and adds the aforementioned data abstractions and investigates their performance and use in various programming projects.
Students with a strong background would be bored in Comp 11 for the first two thirds of the course. But then, you get to work on larger projects and use pointers, so most students with a high school background are challenged at the end.
If you don't know about pointers, memory allocation/deallocation, and Unix, then you'll have to learn those skills in Comp 15. It's doable, and we support students during the transition, but it will be substantially more work for the first 3–5 weeks while you catch up on those topics.
If you have a busy schedule and are settling in to college, then it might make sense to take the easier course, reinforce the skills you have and acquire a few more — take Comp 11 (but don't complain that you already know the material for the first part of the course). If you are up for a challenge and are willing to do extra work, or if you already know about pointers, then take Comp 15.
You can also give Comp 15 a try for a week and then switch to Comp 11 if there is space. But you won't be able to switch into Comp 15 after a week or so — too much extra work will have piled up by then.
Auditing
I'm not generally enthusiastic about auditors in computing classes. That said, students who wish to audit are welcome to attend lectures. We usually have plenty of space in the lecture hall. Auditors should not sign up for labs or submit homework, however. They may attend a lab if there is space, but only after all registered students are accommodated.Here's why:
Students usually choose to audit, because they don't feel they have time to engage in the class fully. Just as watching someone juggle doesn't help you learn to juggle, merely “sitting in” on a computing class typically has very little benefit to the student.
Even if they believe they will engage, it's typical for students to stop participating when there are other demands on their time. Because computing classes typically build skills, it is usually not possible to re-engage later — by then, they are too far behind.
On the other hand, auditing students that do engage consume resources that registered students could use. For example, if they submit homework, someone has to grade it and the course staff must be available to answer questions. Either we have to hire staff or registered students have longer waits for questions and assignment feedback.
For these reasons, I insist that auditors understand they attend on a space-available basis and that they do not submit homework. They are welcome to do the projects on their own, of course.