CPTR 318
Data Structures and Algorithms
Remarks on Assignments

Home Code CPTR 318

  1. Unless otherwise specified, your solutions to all programming problems must be expressed in C++. You may develop on the platform of your choice, but your submissions will be checked under Microsoft's Visual Studio 2017 C++ compiler. If you are using macOS or Linux, a current version of GCC or Clang should work equally well for the kinds of programs we write for this course—be sure to compile with the ‑std=c++14 switch.

  2. Submitting code that won't compile is a very bad thing. If you cannot complete a feature, document the missing functionality and provide at least a method or function stub. From wikipedia (http://en.wikipedia.org/wiki/Method_stub):

    A Stub is a routine that doesn't actually do anything other than declare itself and the parameters it accepts and returns something that is usually the values expected in one of the 'happy scenarios' for the caller. Stubs are used commonly as placeholders for implementation of a known interface, where the interface is finalized/known but the implementation is not yet known/finalized. The stub contains just enough code to allow it to be compiled and linked with the rest of the program.

    Help is readily available for resolving compiler errors. The CPTR 124 tutors (see the posted schedule) probably can help you diagnose most of the compiler errors. Since we will encounter more esoteric issues than CPTR 124 students, the CPTR 124 tutors may not be able to resolve all problems. If they cannot help you or you need help with compiler errors at other times, send me the offending source code and I'll help you resolve the problem.

  3. Run-time errors such as program exceptions (Windows) and segmentation faults (Mac and Linux), are bad. While you genuinely may believe the problem lies in the compiler, your operating system, or your hardware, the problem almost certainly is somewhere in your code. The problem most likely involves an out-of-bounds array access or pointer misuse. Using vectors, smart pointers, and other features of modern C++ can alleviate many of the issues that have plagued C++ developers for years. If you cannot quickly locate the offending code, use a debugger. If you do not know how to use a debugger, see me and I'll show you how. The CPTR 124 tutors can assist as well.

  4. For your safety, build your code with the highest warning levels provided by your compiler (/W4 for Visual C++, -Wall for GCC and Clang). The warnings are generated for a reason. Do not be satisfied until your code compiles cleanly (no warnings and no errors) under the strictest scrutiny.

    You should examine any compiler warnings very carefully because often they infer subtle bugs in your code. For example, consider

    /***************************** * sort(v) * Sorts vector v into * ascending order. *****************************/ void sort(vector<int>& v) { for (int i = 0; i < v.size() - 1; i++) // The rest of the details are omitted ... }
    The comparison of i to v.size() yields a warning about comparison of an int to an unsigned. This is because i's declared type is int, but v.size returns an unsigned value (technically a vector::size_type). Often this warning may be ignored without harm, but what if in this case v's size is zero (that is, the vector v is empty)? The expression v.size() - 1 evaluates to 4,294,967,295, not –1! The condition of the for is initially true when you would expect it to be false. Take warnings seriously, and do not be content until your code compiles without any warnings.

  5. Unlike some other programming languages that you may have used, the C++ run-time environment does not perform automatic garbage collection. Any memory allocated with new eventually should be freed up with a corresponding delete. You should be vigilant to prevent memory leaks but also be careful when deallocating memory—common mistakes include attempts to reclaim space not allocated with new, freeing live memory that will be used later, and attempting to delete the same memory more than once. While each of these memory deallocation problems may appear trivial on the surface, you must remain vigilant because even experienced developers can be plagued by memory management issues when implementing complex data structures. Using vectors, smart pointers, and other features of modern C++ eliminates many of these memory management concerns.

  6. Unless otherwise specified, do not include any I/O (couts or cins) within code implementing collections such as lists, trees, etc.). Clients of your code are responsible for I/O. You are welcome to add debugging statements during development, but please remove them when you submit you code. Any stray output from your implementation code may interfere with a testing framework used to evaluate your code for correctness and completeness.

  7. If you are using Visual Studio, during development you should build your projects in Debug mode. Under Debug mode the compiler instruments your executable with extra information available during run time. This enables you to use the debugger to track down errors in your code, and it injects run-time error checking for things like using uninitialized variables, accessing a collection outside of its bounds, or attempting to use an invalidated iterator.

    Debug builds do pay a significant cost in terms of execution speed, so when it is time to process a large data set rebuild your project in Release mode. You will not be able to use the debugger and the Debug-mode run-time checks will not apply, so lurking errors may cause your program to crash without much helpful information. In return, your program will run much, much faster.

  8. You are refining your skills with the possibility of becoming a professional software developer. With that in mind, the quality of the source code you submit should be a step above the code you wrote in CPTR 124 and CPTR 215. Hopefully by now you have developed the habit of choosing descriptive variable and function names. Really long Java- or C#-like identifiers are neither necessary nor welcome, but using, for example, a local variable named i as something more than a for loop control variable or a nondescript parameter is sketchy. Please be consistent with your spacing and indentation. Pick a style (K&R, ANSI, GNU, etc.) and use it throughout your program. Your IDE (if any) may be able to assist you in consistent formatting. Be consistent with how you name variables, constants, types, functions, etc. You should be using comments to clarify code that is not obvious. Functions should be documented sufficiently; consider:

    /***************************** * div(m, n) * Returns m divided by n *****************************/ int div(int m, int n) { return m/n; }

    Really? What if n is zero? Where applicable, your function comment should include the function's behavior under exceptional circumstances. A better description for the particular function above would be

    /***************************** * div(m, n) * Returns m divided by n. * The function's behavior is * undefined when n is zero. *****************************/ int div(int m, int n) { return m/n; }

    Please do your best to limit the length of each line of your source code to 80 characters or less.

    In short: The appearance of your submitted code should be of high quality, something that you would be proud to include in a publication.

  9. All programming assignments receive a score of 0–10. Points generally are awarded as follows:

    Points Qualification
    0 Program does not compile or fails to address the assigned problem.
    1–7 Program compiles without errors and addresses various aspects of the assigned problem but contains logic errors (including mismanaging memory or flirting with C++ undefined behavior) or is functionally incomplete. Points are based on the severity of the problems.
    8 Program compiles, behaves correctly in most situations, but it exhibits some incorrect behavior in rare circumstances and/or is inefficient performing some activities.
    9 Program compiles, behaves correctly in all situations, and performs efficiently in all situations.
    10 Program compiles, behaves correctly in all situations, performs efficiently in all situations, uses consistent style and good naming practices, and is well commented.

    Compiler warnings will not affect the assignment's grade; however, review the remarks above about the dangers of ignoring compiler warnings.

  10. Assignments must be submitted by the specified due date and time. An assignment submitted within 24 hours after the due date will receive a one point penalty. An assignment submitted 24–48 hours after the due date will receive one-half credit. Assignments submitted more than 48 hours after the due date receive 0 credit.

    Note: No assignments will be accepted after the due date of the final assignment.

  11. The first six lines of every source file you submit should consist of comments like the following:

    // Name: Rick Halterman // Assignment number: 4 // Assignment: Binary space partitioning trees // File name: bsp.cpp // Date last modified: March 14, 2017 // Honor statement: I have neither given nor received any unauthorized help on this assignment.

    Including your name reassures me that the code I am grading actually is the person's code that I think it is. It also ensures that you will get the proper credit you're due. The honor statement reminds you that, unless specified otherwise, each assignment represents an individual effort and copying others' code is forbidden.

  12. All electronic submissions should go to http://eclass.e.southern.edu/. Submit them to the CPTR 318 section. Unless instructed otherwise, submit only the source files (.cpp) to eclass. I usually do not need an archive of all your development files.