Frequently Asked Questions

This page contains answers to some questions that students have already asked (in this case "frequently" means "one or more times"). It should be a good place to start looking for the answers to your questions.

If you have questions that aren't answered here, or if you don't understand the answer given here, please ask your question either in class, in my office hour, or by e-mail.

The questions are organized by topic, as follows.

  1. Examples and Assignments
    1. Assignment 1
    2. Assignment 2
    3. Assignment 3
    4. Assignment 4
    5. Assignment 5
    6. Assignment 6
  2. Compilers and Tools
    1. Compiler
    2. Editor
    3. Debugger
    4. CD Distribution
  3. C++ Language
  4. General questions

Examples and Assignments
  1. I tried to retrieve my assignment before it was marked, should I re-submit it?
    No. Retrieving your assignment does not change what you submitted.
  2. What are correctness demerits?
    Correctness demerits are points taken off for code that I consider to be incorrect in ways that can't be (or weren't) detected by testing. An example would be neglecting to delete something but removing all pointers to it (a memory leak). There is no reliable way for testing to detect this, but I consider that this code is wrong, not just bad style.
  3. How do I find out why I lost marks on an assignment?
    The report.txt file will tell you if it was for testing, correctness, or style. For testing the output.txt file will give you the expected and received output for each test case so you can see why you failed a particular one. For style and correctness, look in the returned copies of the files you submitted -- the TAs and I will add comments indicating things that are bad style or incorrect.

Assignment 1
  1. How do I implemnet a stack?
    Don't, use an STL stack. I'll talk more about it in class, but for now, you need to
    #include <stack>
    then you can declare a stack of int, for example, as follows
    stack<int> s;
    the operations on stacks are push(x), pop(), top(), and empty().
  2. Do we need to comment pre and post conditions?
    Yes. Even though they're given for you, it's good style to put them in.
  3. Do we have to use a stack?
    Yes. The purpose here is to learn something about stacks, so you have to use them.

  4. Part 1

    1. The question lists bases 10, 2, 7 and 16, will those be the only bases we need to deal with?
      No. The pre-condition in assign1_a.h says that the base is any number between 2 and 16.

  5. Part 2

    1. Will the expressions contain numbers greater than 9?
      Yes. I sugest you use atoi (declared in cstdlib) to convert to integer from a string. So, for example, if buf is a string that starts with a digit and x is and int, then
      x = atoi(buf.c_str());
      will assign the integer that starts at the start of buf to x.
    2. Should error checking be done for incorrect expressions?
      If you detect an error then given an appropriate message and exit, but don't go to any effort to detect errors.
    3. How do I work with strings?
      See the Dinkum C++ Library: string for more details, but here's a few useful string methods:
      MethodMeaningExample
      atReturns a reference to the character at the given position. s.at(i);
      operator[]Returns a reference to the character at the given position. s[i];
      operator+=Append.s += 'x';
      substrReturns a copy of a portion of the string. s.substr(start, len);
    4. How can I tell if a character is a digit?
      Use the isdigit function (declared in cctype).
    5. What should the program do in the case of division by 0?
      Print a reasonable error message and exit.
    6. Should we allow for spaces between any of the characters in the string?
      Yes, spaces can be anywhere except between digits in the same operand. You should just ignore them.
    7. Should we allow for there's more than one operator between a set of brackets, e.g., (1+2+3)?
      No. The definition of "fully parenthesized" says "every operator and its operands are contained within a matched pair of parentheses", which rules out these.

Assignment 2
  1. Where do I find out more about Iterators?
    The STL Programmer's Guide has a whole chapter on them. The following should cover the most common questions, however:
    1. Can I do pointer math on iterators (i.e., *(i + n) where i is an iterator and n is an int?
      No, not on this kind of iterator. You can only do i++ or ++i (this is an Input Iterator in the STL terminolgy).
    2. What's the difference between list::iterator and list::const_iterator?
      An iterator will allow you to change the value that it points at (i.e., it's like an ordinary pointer), whereas a const_iterator won't (i.e., it's like a const pointer). If you ask for an iterator to a const list then you'll get an error.
  2. How do I call the constructor?
    The Polynomial(int d, double *coefs) constructor is invoked when an object of type Polynomial is defined using the appropriate arguments. For example, 
      double co[] = { 1.2, 3.4, 5.6 };
  Polynomial p(2, co);
    constructs p to represent 5.6x2 + 3.4 x + 1.2.
  3. Should our constructor check that the given array is the right size?
    Do you know any way to check this? I don't.

Assignment 3
  1. What should reverse set err to if the list is empty?
    Ok.
  2. Should the index returned by find count from 0 or 1?
    0. The index of the first element in the list is 0.
  3. Are there any cases where reverse would set err to something other than Ok?
    No, it should always set it to Ok.
  4. In reverse, is is ok to just move the data, rather than changing the pointers around?
    Yes and no. Moving the data around does accomplish the job, so I won't consider it to be wrong, but it is less than ideal for two reasons:

Assignment 4

  1. Graph

    1. What is a graph?
      In the notes on recusion I give the definition: a Graph is a set of verticies (a.k.a. nodes) and edges, the edges being simply pairs of verticies. The Graph class assumes that the verticies are a the natural numbers less than numNodes.
    2. What is a set?
      Conceptually a set is a collection with no order and no duplicates (you should have learned this in discrete math, if not before). The STL set template implements a container with these properties and defines the usual set operations.
    3. I don't understand how areAdjacent works?
      The short answer is that you don't need to, you only need to know that it returns true if the given nodes are adjacent in the graph, or false if they are not. That said, it's a pretty simple function, so here's what it does: the nodes from and to are adjacent if and only if there is an edge between them. The Graph class simply stores the set of edges in the graph, so areAdjacent uses the find method to check if there is such an edge in edges. find returns end() if no such element is found. Note the set template uses the operator < to check for equality: a == b is defined as (!(a < b) && !(b < a)). Thus, looking at the definition of operator < for Edge, two edges are considered to be equal if they have the same start and end points.
    4. Is a node adjacent to itself?
      Not unless there is an edge from the node to itself. Of course this won't be very interesting, since clearly the node is already seen, so it doesn't make any sense to look further from it.
    5. My algorithm works, but it finds a rather inefficient route, is that acceptable?
      Yes. The simple backtracking algorithm will find if there is a route, but not the best route. It is possible to modify the algorithm to find the best route (try it on your own if you're ambitious, but it will require a modification of the interface, so don't submit it). You'll learn much better algorithms for doing this in a later course.
    6. Should the route include the source and destination nodes?
      It should include the destination, but not the source. The length of the route is the number of steps (edges) in the path. If the source and destination are the same, then the path is empty.
    7. Is the areAdjacent function symetric (i.e., will areAdjacent(i, j) == areAdjacent(j, i))?
      No. This class is for directed graphs. An edge from a to b doesn't mean there is an edge from b to a.
    8. If findPath is called with the same node for source and destination, what should it return?
      true. (Hint: what is the base case for the recursion.)
    9. What is the purpose of the graph methods markAsSeen() and isSeen()?
      As explained in class your algorithm needs to keep track of the nodes that you have visited in a search so as to not search from there again, so you should use these methods to do that. When you first visit node, n, call g.markAsSeen(n) then before visiting a node check that g.isSeen(n) is false.
    10. What if there are multiple paths?
      Just set route to the first one found.
    11. What does the weight represent?
      In this assignment it isn't used. Ignore it. In another application it might be used to represent the cost of a particuar step (length).
    12. Is it true that a node, i, cannot be adjacent to a node, j, such that j < i?
      No. There are no restrictions on edges based on node numbers.
    13. How do I move 'forward' or 'left' as in the algorithm presented in class?
      Since this is a generalized graph there is no notion of (compass) direction here so you have to check every node to see if it's adjacent. Remember that the nodes are represented simply by the integers between 0 and numNodes-1.
    14. I get a bunch of compile errors in graph.h using M$ Visual C++, what's wrong?
      There were some incompatibilty issues. Get the latest version of graph.h and assign4_a.h and be sure that your declaration matches the revised one.

  2. List Merge

    1. When I have two lists how do I know which one is *this and which one is r?
      As with any member method, this points to the object on which it was called, so, for example, in the call one.merge(two) this is a pointer to one and r is a reference to two.
    2. Can we assume that the lists are non-empty? No.

Assignment 5
  1. What should left() and right() return if the child doesn't exist?
    If the child doesn't exist then these should return any value greater than or equal to what is returned by size() for the same tree.
  2. What do you mean by the tree being "full" in the insert function?
    The number of nodes in the tree has reached the maximum specified in the constructor, so the insert cannot be completed.
  3. How can I determine if a node is a leaf?
    Think about the relationship between a leaf's index in the array and the number of nodes in the tree. Notice that in a complete tree the number of leaves is close to half the number of nodes. There is a fixed relationship that works well, what is it?
  4. Do we have to use recursion in this assignment?
    No.

Assignment 6
  1. What do we do with shorter?
    It's similar to taller in the insert - at each stage of the recursion it indicates if the height of the tree has been decreased by the operation. You need this to figure out when to rebalance.
  2. Can we use your rebalance functions?
    Yes, if they do the right thing. The trick is to know which one to call when.
  3. Help, I'm caught in a pointer tar-pit!
    You can always bring me your code for help, but here's a tip that might help to free you: consider how you might use avlRemove to help you in ways other than the straight forward recursion. If, in the case where the node to be removed has two children, you follow the process for removing from a binary search tree, then, after you've found the right-most child of the left sub-tree (or vice-versa) and copied it's value into the node that's being removed, you end up needing to delete a node from the sub-tree (i.e., the one that you've copied). You know that that node has at most one child, so can you think of a function that could do that for you (and look after the rebalancing).
  4. It looks to me like an AVLtree contains BinaryNodes, which don't have a balanceFactor. Shouldn't they be AVLnodes? How does this work?
    Notice that the BinaryTree only stores a pointer to the BinaryNode and that AVLnode inherits from ("is a") BinaryNode, so a pointer to an AVLnode can be used as a pointer to a BinaryNode, which is what is done in this case. In avlInsert you see that the nodes that are inserted into the tree are actaully AVLnodes.
  5. I don't understand the operations for AVLtrees.
    Here's an illustration of what's going on that a previous student found on the net.
  6. MS Visual C++ complains about the scope resolution operators (AVLtree<T>::) on rotateRight and rotateLeft, can I remove them?
    Yes. They're not needed by Cygwin.
  7. For the hash table, how do I check for empty places in the list?
    A list can't have an 'empty' place--when something is erased from the list it shrinks so that all places are full. The insert function is therefore easier than that in linearHash.h.

Compilers and Tools

 See also the Cygwin user's Guide and FAQ.

Compiler
  1. How do I get the Cygwin C++ compiler for Windows?
    The easiest way is to buy the distribution CD from the IEEE Student Branch ($5 for IEEE members, $10 for non). It contains the Cygwin (GNU) C++ compiler, the Insight debugger, the "Teaching Machine" and instructional videos. If you have a fast internet connection and don't want the videos etc., you can go to Cygwin's site and click on the "Install Now!" icon. Be sure to install at least the following packages:
  2. Do I need a compiler?
    Only if you want to test your programs on your own computer. You can write your programs without a compiler and bring them to the lab to test them.
    See also Can I access a C++ compiler from home without installing it on my computer?, Why do I need an editor?
  3. Can I access a C++ compiler from home without installing it on my computer?
    Yes, but it's not the same one as in the lab, so it may behave slightly differently. You can test your programs via modem by logging in to any of the Unix systems (tera, exa, pico etc.). The compiler commands are the same as I've demonstrated. You'll need to transfer your files to your directory on the server (e.g., using ftp), which is the same as the M: drive. Also note that files compiled using one Unix system will not necessarily run on another one--they're not all the same--and they certainly won't run on the Windows machines.
  4. I already have C++ compiler x, can I use it?
    Yes, but you should compile and run your test cases using the Cygwin/GNU compiler (g++) in the lab before you submit your assignments. If it works there, then it's ok. (Of course we may find test cases for which your program doesn't work on any compiler.)
  5. What are the commands that I need to compile my files.
    The most important command invokes the compiler: g++. The general form is:
    g++ options files
    where files is a list of one or more files that the compiler is to compile, and options is one or more of the following. (There are others, these are just the most relevant ones.)
    Option Meaning
    -Wall Give all warnings. You should always use this option and pay attention to the warnings--they usually mean that you've made a mistake.
    -o file Write the output to file. Normally this is used to specify the name of the executable. If you don't use this option the executable will be called a.exe.
    -g Produce debug information. This allows you to use a debugger to examine your program as it runs. I'll be demonstrating this in the lab.
    -c Only compile, do not link. Use this to produce an object file rather than an executable.
    For a program with only one implementation file, you can compile it using the following command line:
    g++ -Wall -o assign1 assign1.cpp
  6. What does this error message mean?
    Here are some of the most common error messages and their interpretation:
    parse error
    You're program contains something that isn't valid C++ code. Most often you've forgotten a semi-colon at the end of a statement (usually the one before the line that gives the first error). When you get parse errors, don't bother to try to understand the other error messages that follow it--since your code doesn't make sense, the compiler messages won't make sense.
    undefined reference to funName
    Your program uses a function funName that the linker cannot find. Usually this is caused by one of two things:
    • You've misspelled the name of a function. Check the spelling of funName carefully to be sure it matches the way the function declaration and definition have spelled it. Remember that capitalization counts.
    • You're trying to link and compile in one step without including all of the .cpp files needed. If funName is WinMain you don't have a main defined in your files.
    implicit declaration of function funName
    You're using a function that hasn't been declared in this scope. All functions should be declared before they are used. This also happens in you've misspelled funName.
    varName undeclared
    Your program uses a variable varName that is not declared in the scope in which it's used. You have to declare all variables before you use them. This also happens if you misspell a variable name (e.g., get the capitalization wrong). Another common case is varName is cout or cin, which means that you've left out
    #include <iostream>
    using namespace std;
    warning: assignment to `int' from `double'
    You have a statement of the form x = exp;, where x is an int and exp includes floating point math (i.e., non-integers). The value will be truncated (not rounded) to an integer. This is just a warning, so your program should still work, but you may not get the answers you expect. A "cast" can be used to stop the warning:
    x = int(exp);
    This says "treat exp as an int".
    file.h: No such file or directory
    The pre-processor cannot find file.h, which you have #included. This probably means that you either haven't got the assignn.h in the current directory (copy it from the web page) or you've misspelled a system header file name.
    g++: command not found
    The compiler is not installed correctly on your system or your PATH variable is not set correctly.
    g++: Compilation of header file requested
    You've asked the compiler to compile a header (.h) file. Only source (.cpp) or object (.o) should be given as files to compile in the g++ command.
    ... permission denied
    The compiler or linker was not allowed to open a file that it needed to. Most likely this means that you're over your disk quota. See out of disk space.
    0x00000000... cannot be used as a function
    This probably means that you've left out a * in an expression, for example:
    d = 0.5(G * time * time);
    should be written:
    d = 0.5*(G * time * time);
    In C++ multiplication is not assumed.
  7. How can I capture the error messages into a file?
    You can redirect the output messages from g++ (and other Cygwin tools) to a file using ">&". For example:
    g++ -Wall -o test5 -g test5.cpp assign5.cpp >& tmp.txt
    will put the messages in the file called tmp.txt.
  8. The compiler says "permission denied" or "not enough space left on disk", how can I fix that?
    You're probably using more disk space than your quota allows. To check this use the "Quota" program found in the same menu as the "Submit" program (i.e., Start -> Programs -> CCAE -> Quota). It'll tell you if you're using too much or not, and will also say what your quota is. If your quota is 5000 blocks (= 5 M bytes) then the CCAE staff will give you more if you ask for it. If you already have more that 5000 blocks then they may or may not give you more. Either way you should clean up your M: drive -- remove any files that you no longer need, particularly big ones. Some easy candidates for removal are: You should always back up your files on your own disk (floppy or otherwise).
  9. Can I run programs compiled in Cygwin from the Windows Explorer or DOS prompt?
    Yes, and no. By default, Cygwin g++ produces an executable that is a "console application" intended to be run from within the Cygwin environment called bash. If your environment is set up right then double-clicking on the executable in Windows Explorer will run the program in a shell, but the shell will disappear as soon as the program exits (if this doesn't work for you it probably means that the cygwin directory isn't in your path). If you really want to run this from a DOS prompt you can, for example as follows:
    bash -c M:/2420/hello
    assuming that hello.exe is in the 2420 folder of your M: drive. (This is not worth the bother.)

    If you'd like to make a Windows GUI application, you can do that, but it involves a whole bunch of stuff that is beyond the scope of this course. I'd suggest you start with using the Win32 API, and then you need to learn about what the Win32 API is (try Microsoft or any good book on Windows Programming).

  10. How do I compile a program with multiple implementation (.cpp) files using Cygwin?
    The simplest way is to compile them all together with one command line, so for example if your program is made up of testharness.cpp and assignment.cpp, then you could compile them as follows:
    g++ -Wall -o testharness testharness.cpp assignment.cpp
    If any of these were particularly large, or if there were several implementation files, then you might consider compiling and linking separately:
    g++ -Wall -c assignment.cpp
    g++ -Wall -c testharness.cpp
    g++ -o testharness testharness.o assignment.o
    However, if this is the case, I suggest you use a "make", which requires a Makefile.

Editor
  1. Why do I need a (text) editor?
    To write your programs. A C++ source file must contain only "printable" ASCII characters. Word processors include a lot of formatting information in the file, so they're not appropriate for editing source code. Windows comes with a simple editor called "Notepad", which should work for our purposes, but lacks a number of very useful features that are common in programming editors -- See also Are there alternatives to Notepad?
  2. Are there alternatives to Notepad?
    Yes, lots of them. If you like point and click style, then UltraEdit is pretty good (and cheap), or EditPlus also looks good. Also, if you don't mind the learning curve or already know vi, Vim is a free and improved (e.g., it does code highlighing in colour) version of the standard vi editor that is found on Unix systems. Vim is included on the course CD-ROM and is available on the systems in EN-3000.
  3. I can't read a file in the editor
    If a file appears as if it only has one, very long, line, then it's probably formatted for unix. You can convert it to dos format using the program unix2dos.bat in the Cygwin environment, as follows:
    unix2dos.bat file
    where file is the name of the file you want to convert.

    If a file appears as a bunch of odd characters then it's probably not a text file, so the editor will be of no help. It's likely an object or executable file, or in a word-processor format. Many word-processors can be made to save in text-only (sometimes called ASCII) formats. Look for an option like "file type" in the "Save As" option.

  4. I saved my file using notepad, but MS Visual C++ can't find it, or it appears as assign0.cpp.txt in the GNU environment?
    When you save in Notepad you have to change the "file type" selection to "all files", otherwise it tacks on the extension .txt onto the file name. You can rename a file in the GNU environment using the mv (move) command:
    mv oldfile newfile
     where oldfile is the old file name and newfile is the new file name.
    Better yet, don't use Notepad it's not really intended as a program editor. See Are there alternatives to notepad?.
  5. Can I get vi for windows?
    Yes, it's included on the distribution CD, or available from www.vim.org.
  6. How can I get help for Vim?
    The Vim documentation is online. Also check the Vim FAQ, and Vim HOWTO. Another possibly useful site is this Vi reference sheet.
See also Vim Installation problems.

Debugger
  1. Where can I get that GUI debugger that you use?
    It's included on the distribution CD, called gdb.

CD Distribution
  1. How do I install/use the CD?
    The file "Start Here.html" on the CD gives instructions. Point your browser at it and read what it says. The CD contains many things, not just one package to install. The Teaching Machine and the videos can be used directly from the CD. The GNU Distribution (Cygwin compiler and Vim editor) should be installed by following the instructions given.
  2. I installed Cygwin and, when I run it, it starts in some strange directory that I can't find.
    Cygwin will create a 'home' directory for each user who uses it in C:\cygwin\home\XXX, where XXX is the user's username. This directory is represented by the short form "~", and is analgous to your M: drive on the ENGRNT system. To change to another directory, say your 4892 folder on the C: drive, type cd c:/4892.
    If you'd like to change the Cygwin configuration on your own computer, edit the file C:\cygwin\etc\profile and change the line
    HOME="/home/$USER"
    so that the part after the "=" is whatever you'd like you home directory to be. I don't recommend, however, that you make C:\ or C:\cygwin you home directory.
  3. Is the compiler on the CD the same as the one available in the lab?
    Yes.
  4. I installed Vim but when I run it it doesn't have the menus or toolbar displayed. How can I get them to work?
    There are a few things that could be wrong, here's a few things to check:
    1. Did you to run the install program found in C:\vim\vim57 after extracting the zip files?
    2. Are you running a copy of the gvim executable to your desktop? If so, I suggest that you use a shortcut instead. Go to C:\vim\vim57, select the gvim executable, right click and select "create a shortcut", then move the shortcut to the desktop.
    3. If these don't help then you've probably made some incorrect selections during the install. The simple solution is to replace your C:\vim\_vimrc file with this file. See also Vim Help.
  5. How can I make the Teaching Machine look the same as when you use it in class?
    This file is the configuration I'm using. It's designed for at least 800x600 resolution.

C++ Language

 See also What does this error message mean?
  1. How can I recover once a user has input something invalid?
    This isn't really part of the course (at least not yet), but here is an example of how to handle it.

General Questions
  1. I have another textbook on Data Structures, is it ok?
    There are hundreds of books about programming in C++ in general and Data Structures in particular, some are good and some are not so good. While I don't require that you have any textbook, I do think it will be helpful for you to have some source(s) to turn to. There's little that fundamentally distinguishes Kruse and Ryba from other textbooks on data structures, so you'll probably be ok with another book (e.g., the one used in this course last year, or in CS 2711), but I'll as much as possible be using notation etc. consistent with Kruse and Ryba. For programming references, the key requirement you should look for is that it covers ANSI/ISO standard C++, which typically means it will be published after 1998. The 'trade' books (e.g., "C++ for Dummies" or "Teach Yourself C++ in ...") are reasonable language references, but won't, typically, cover the data structures, abstraction etc. that are the main emphasis of this course.
  2. Could you post all the notes now?
    That's a great theory, but it'd require that all the notes exist now. I'm updating them just ahead of the lectures so it's not possible to post them now. (BTW, call me a Sophist if you like, but I claim that this allows me to adapt the lectures to suit the progress, strengths and weaknesses of the class as they become apparent to me.)
  3. I'm lost, where can I get more help?
    Here are several sources of help:
    1. Me, in class. If you can ever formulate your mis-understanding as a question then ask it in class. I don't dismiss questions (unless they're off topic). My experience is that if one person in the class can think of a question to ask then many others will benefit from the response.
    2. Me in the lab or my office. If you are having difficulty even formulating the question you can always try me one-on-one. I'll do my best to explain it to you and I'm usually forthcomming with tips.
    3. The posted notes/examples. In particular the examples. Try reading them through and making sure you understand what every line is doing and why. They are fairly heavilly commented to help you understand. If you don't understand something, then ask me.
    4. The text book. Although I don't make explicit reference to it in class, we are following it and I think you'll find that the authors take a slightly different approach, which should be helpful. The relevant sections are indicated on the web page.
    5. Other books. Particularly if you struggle with the programming per se, then there are lots of 'trade' (i.e., less expensive) books available on programming in C++. Look for publication date after 2000 (when the language was standardized) and check that it covers classes and objects.
    6. Tutors. If you think you need more one-on-one help (and are willing to pay for it) there are lots of capable graduate or senior undergraduate students who may be willing to help you. Contact me and I'll provide a few names.
Back to 4892 homepage

Last modified: Sun 2003.07.27 at 10:34 NDT by Dennis Peters