Quick links
MISSING LINKCourse schedule

COMP15 Data Structures
Spring 20XX


Nearly any ad-hoc technique, even trial and error, can be used to write a 50 line, bug-riddled, throw-away program. Software-based products are complex systems, beginning in size at several hundred thousand lines of code and increasing in complexity to several million lines of code. Given the level of investment and commitment needed to build such large systems, a vendor expects to sell and maintain a product for many years, if not decades. Ad-hoc techniques cannot be successfully applied to systems of practical scale and longevity.

This course is your first step toward large-scale system development. Large-scale software systems are composed of interacting modules -- components -- that implement a desired behavior. You will learn to design, build, test and reuse software modules. Later courses, such as COMP180 Software Engineering, address requirements analysis, "design in the large," integration, and other methods needed for large-scale software development.

Data structures and good algorithmic design underlie correct and efficient implementations. Data structures are part of the body of knowledge that every software engineer must know and be ready to apply. Through the study of data structures, and most importantly, by completing projects implementing and using the most common data structures, you will refine your software development skills.

It's time to start thinking and working like a professional software engineer!

Course information at a glance

Instructor Paul Drongowski
Office hours: T 3:00-4:30, W 10:30-12:00
Lectures Section 01: M,W 1:30-2:20, Th 3:00-3:50, G block, H-111
Section 02: T,Th,F 1:30-2:20, H block, H-108
Other teaching responsibilities COMP150-PAT: T,Th 5:30-6:45, M+ block, H-106
Teaching assistants
Required textbook Nyhoff: ADTs, Data Structures and Problem Solving with C++, Second edition, L. Nyhoff, Pearson Prentice Hall, 2005.
Recommended books Practical Debugging in C++, A.R. Ford and T.J. Teorey, Prentice Hall, 2002.

Practical C++ Programming, Steve Oualline, Second edition, O'Reilly & Associates, 2003.

C++ Pocket Reference, K. Loudon, O'Reilly & Associates, 2003.
Schedule MISSING LINKLecture topics, readings, key dates
Laboratories MISSING LINKLab and account information


The primary textbook for this course is ADTs, Data Structures and Problem Solving with C++ by Larry Nyhoff. The assigned readings provide an essential knowledge base. The lectures cover some aspects of topics in the text and generally add enrichment material. You are responsible for material from both the text and class lectures.

As a further reference, expecially when working in the lab, I would recommend the C++ Pocket Reference from O'Reilly & Associates. The C++ Pocket Reference is inexpensive ($10) and is a better resource than the C++ "reference cards" that are available from Barnes and Noble or Borders.

Prior experience is required

This course is not an introduction to programming. We assume that you can competently write a 50 to 100 line program in a higher level, block-structured programming language like Java, C or C++. At a minimum, this means an understanding of and an ability to apply:

We expect that you have written programs using keyboard input, screen output and file I/O, and can apply concepts from your earlier experience.

COMP10 Computer Science Primer does not provide sufficient background or programming experience for this course. Experience equivalent to COMP11 Introduction to Computer Science is required.

Mathematics required for this course include high school algebra, set theory, coordinate geometry and descriptive statistics. Many data structures and algorithms are based upon concepts in discrete mathematics:

and operations research: You'll get a very brief introduction to some of these concepts. Be prepared to make connections between data structures and other courses, including MATH22 Discrete Mathematics, COMP160 Algorithms and, of course, COMP180 Software Engineering.

If you have doubts or questions, please speak with me or take COMP11 Introduction to Computer Science. Our class will have students with a wide range of experience and different "entry points." We hope to accommodate everyone with the required base competence in programming.


The projects are the most important part of this course! Software engineering is an activity and software engineers are hired to produce high-quality software, not to theorize. There are two overarching principles for our work:

We build on and reuse our own software modules. In some cases, completion of later assignments will depend on results produced by earlier assignments. Dependencies will be explicitly stated, so you will know which assignments depend upon others.

Every software engineer should know and be able to apply at least a little practical knowledge from several areas:

The assignments in this course will draw from these areas.

There is scientific evidence that active application of class knowledge is essential to learning. Recent research on brain structure and learning shows that learning causes physical changes in the brain. The most effective way to learn is to (iteratively) complete full learning cycles:

Retention is enhanced when the cycle is completed in earnest. Ever take a course, pass the exam, and realize two months later that "nothing stuck?" Chances are that you missed one or more steps in the learning cycle. Cramming is not an effective learning strategy.

Research also shows that learning is not instantaneous. It takes 20-30 minutes of concentrated effort to develop potential new neural synapses where connections can be made. Effort and commitment are essential to learning and they must come from within. Learning is most effective when you actually enjoy the activity or subject matter in which you are engaged. This is why the expression, "Do what you enjoy and success will follow," is so true. Enjoyment does not preclude hard work -- think about fun activities that you willingly pour in effort. An activity must be intrinsicly important to you in order to motivate a high level of effort. Look for the fun aspect of every problem! It may also help you to decide what you want to do with your life. (But, please realize that there is more to computer science than just programming, too.)


Evaluation is an assessment of personal progress toward a learning goal. If you are obsessed with your GPA, please stop that behavior right now -- you are hurting yourself. Studies have shown that an obsession with grades (or "rewards") actually demotivates students in the long run.

Evaluations in this course are based upon the quality of results. Software development projects require and expect on-time, high quality results. Development processes are assessed and tuned for quality. Code reviews and other quality-oriented practices are the norm. Criteria to be considered include:

The phrase "convincing argument" is one that you will hear quite often during your career. It is your job to give a lucid argument (in the sense of logic, not a raised voice) that your solution is correct and appropriate. Time and again, you will be called upon to give a convincing argument at a code review in order to have your solution accepted by your peers. Development projects generally do not allow code to be "checked in" until it passes a formal code review.

Contrary to "conventional wisdom," we are educators, not gatekeepers for the corporate world. Having been a campus recruiter, I can assure you that GPA is a weak factor in interview and hiring decisions. (GPA is also a very weak indicator of future success in the real world and is not even considered beyond entry-level positions.) Here are some suggestions to apply now:

Recruiters like students who are enthusiastic about their work, who know what kind of technology and problems that they enjoy the most, and who have completed projects of significant substance and weight.

The following table summarizes the relative weights of projects, quizzes, and exams.

Projects #1 to #5, #7 and #8 5% per project, 35% total
Project #6 10%
Quiz #1 5%
Quiz #2 5%
Midterm examination 20%
Final examination 25%

Project #6 is larger in scope and requires more effort than projects #1 to #5, #7 and #8. Quizzes are scheduled before key DROP dates to help you assess your progress.

Quotas are not used when assigning letter grades (e.g., 10% A's, 30% B's, etc.) Grade quotas have negative, undesirable effects:

Having to reduce academic assessment to one of five letters is bad enough; we don't need to make this practice more stressful or unproductive.

Late submissions

The score for any late assignment will be reduced by 10% for each 48 hour period by which submission is delayed. For example, if the maximum score for an assignment is 100 points, then there will be a 10 point reduction for each 48 hour delay in submission. Please also be aware that some assignments will use the code developed in other assignments. In those cases, you have an added incentive to complete your work on time.

In case of severe illness or emergency, you may request an extension if you have a note from health services, a doctor, or a dean confirming your situation. If you miss an examination or quiz due to an emergency or severe illness, please contact me immediately. You must still obtain a confirmatory note from health services, a doctor or a dean. No other grounds for extension will be considered. The class schedule has been designed to accommodate religious holidays.

Checking scores and resolving issues

Within two to three weeks from the start of the semester, you will have access to our records of all your scores via the World Wide Web. Please check these records every week to make sure that you have received your proper credit. It usually takes about one week for scores to be posted. You will then have two additional weeks to check the recording of your scores. Any correction of a recorded score must be made within three weeks of submitting the assignment, quiz or examination. Thus, after you submit a project, you will not be able to review your score for revision, even if it is wrong.

If you detect an error in a score, you should contact the person responsible for recording that score. For projects, the person to contact is the responsible teaching assistant (TA.) For exams, the contact is your instructor. If an issue surrounding a score cannot be resolved by the TA, only then should you discuss the issue with me.

Correcting errors in not the same as groveling. Decorum, please!

Professional ethics

Yes, ethics are important. Customers, managers and team members will rely on you to meet your commitments. You want to be perceived as a person of integrity as trust is essential for future promotion. Would you trust a liar or a cheat with the company's business?

The Association for Computing Machinery (ACM) is the society for computing professionals. The ACM publishes two codes of ethics:

Corporations require their employees to complete annual ethics training. I have yet to encounter a code of ethics that says "Go ahead, cheat" or "Prevaricate."

Copying software (either binary or source code) in the real world puts your employer at risk for a lawsuit. Even open source software, such as that governed by the GPL, has legal restrictions and requirements. Improper use of open source code may force your employer to put its own source code into public release, thereby losing any competitive advantage or trade secret protection. Needless to say, if you're the culprit, you won't be employed.

The Tufts University policy on Academic Integrity has additional information, advice and suggestions. It treats both the ethics of academic work and the ethics and appropriate use of electronic resources. Of course, we are expected to comply with these policies. Violations of these policies, especially cheating and illicit use of computing resources, will not be tolerated. All examinations and quizzes are closed book and no electronic devices may be used.

Here are a few general guidelines regarding ethical academic work.

If you have further questions, or are concerned that you are considering an ethically ambiguous course of action, please speak with me before the situation becomes a problem.

Getting help

Your first and best resources for help are the teaching assistants. When you seek their advice and help, please come prepared. Bring a fresh listing of your program. Please make your program as readable and understandable as possible -- the quality of the advice that you receive is directly proportional to the quality of the input and questions that you bring. A teaching assistant has the right to refuse to help if a program is unreadable or just plain garbled in some way.

Class time is a great time to raise questions. Real engineers discuss problems over coffee in small groups. Let's use class time that way -- it will help you and will make life even more fun for me! Of course, I will hold office hours. I also believe in "managing by walking around," and if I'm in the lab, my time is up for grabs! Please respect the fact that I have other teaching responsibilities and generally need one hour+ to get my head together before a lecture. That's why I have listed my other lecture times in the table on "Basic course information."

User consultants are provided by Academic Computer Services in public user areas like Eaton Hall. Their responsibilities are limited to answering general usage questions, minding computer equipment, etc. They cannot help you with the assignments or C++ programming.

Reference information

The table below has links to reference information that you will find useful. This material complements the textbooks, lectures, etc. and in some cases, is necessary to the successful completion of projects.

Reference information
Emacs and UNIX GNU Emacs reference card
UNIX help pages (Edinburgh)
C++ tutorials Tutorials @ CProgramming.com
A Quick Introduction to C++ (HTML) (PDF) (PostScript)
C++ vs. Java Comparison of C++ vs. Java
C++ Standard streams reference
File streams reference
Using assert
Standard C library reference Hexadecimal and bit twiddling
Programming utilities Compiling C++ programs
Using make to build programs
The GNU gdb debugger
PostScript PostScript reference

Copyright © 2004-2013 Paul J. Drongowski