COMP15 Data Structures
Spring 20XX

Introduction

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

Textbook

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:

• Primitive datatypes (integer, floating point, character)
• Arrays containing primitive datatypes
• Strings
• Control structures (if-then-else, switch, while-do, for)
• Structured programming
• Functions and parameter passing
• Recursion
• Keyboard input and screen output
• File input and output

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:

• Logic and set theory (sets, bit sets)
• Number theory (hash functions, pseudo-random number generation)
• Graph theory (trees, directed and undirected graphs)

• Networks (flow, product delivery, routing)
• Queueing systems (queues, networks of queues/servers)
• Simulation (queues)

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.

Projects

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 programs to understand and solve problems. Engineers routinely build and experiment with models in order to find and understand solutions to problems. Software engineers and other kinds of computer scientists are no different.
• We use what we build. Quality, reusability and maintainability improve when developers are forced to "eat what they cook." Software is not "throw-away" and sometimes early design decisions or laziness come back to haunt us.

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

• Simple parsing in order to post-process output from other programs, to handle command line arguments, to interpret user input, etc.
• Computer graphics to effectively present information, and
• Simulation to analyze real-world problems (traffic, assembly lines, people-flow through amusement park rides, etc.), networks, and other complex systems.

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:

• Concrete experience: Reading, listening to a lecture, studying example program code and other sensory experiences.
• Reflective observation: Setting aside time and really thinking about -- integrating -- what you've read, heard or observed.
• Abstract hypothesis: Applying new information and techniques through problem solving and developing a plan of action.
• Active testing: Putting the solution and plan into action by writing, testing, and debugging a program.

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

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:

• Is the program correct?
• Was the program delivered (submitted) on schedule?
• Is the solution and program clear, straightforward, readable and understandable? Is the program properly indented?
• Do the comments adequately describe the approach?
• Is behavior partitioned in order to hide design decisions and improve maintainability?
• Does the program detect and handle error conditions appropriately?
• How thorough are the test cases? Do they test all of the "corner" cases and conditions?

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:

• Build a portfolio of your work. Employers are mainly concerned with what you have done and can do.
• Develop interpersonal skills to help you work with customers and to become a good team member.
• Develop writing and speaking skills to communicate effectively with customers, team members, and management.
• Live and work to a high standard of professional ethics.

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

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:

• Less experienced students become discouraged because they believe that the A's will go solely to the more experienced students.
• Quotas discourage cooperation. (All cooperation must adhere to University and professional standards of ethics and academic integrity.)

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:

• ACM Code of Ethics and Professional Standards
• Software Engineering Code of Ethics and Professional Practice

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.

• It's OK to discuss the readings, lectures and assignment hand-outs and web pages.
• It's OK to read example code.
• You are encouraged to help each other to learn Emacs, UNIX/Linux, Secure Shell (ssh), the Ghostscript previewer and other development tools.
• Never copy code, documentation, test data or test results.
• Never provide code, documentation, test data or test results to any other student.
• Do not plagiarize the work of others and submit it as your own work.
• Protect your directories and files. Set your file permissions so that only you can read and write your files (e.g., chmod 0600 file.) Put the shell command umask 077 into the .cshrc file in your home directory. This sets the file creation mask to automatically restrict file access when a file is created. Periodically check your directory and file permissions using ls -l.
• Guard your hardcopy and removable storage media. Do not leave listings, ZIP disks, Jump Drives, etc. where they can be easily stolen or copied.

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.