Comp 15:
Data Structures

FAQ

Welcome to the FAQ page! Type in any keyword to begin

The FAQ page has questions from previous semesters that can help you if you are stuck, or have a general question. Spec specific questions will still be answered over Piazza. Questions are asked by students or written by TAs and answered by the teaching staff.

You can only search by one word at a time.

Keyword Question Answer
Null character When compiling, I get “warning: null character ignored”. What does this mean? You have NUL characters ('\0') in your source code. Usually that's hard to do. I can think of a couple ways this can happen, one of which is a big problem.

It's possible you actually have some NUL characters in your source code. That can happen through copy/paste (boo, hiss!), through a deliberate effort to put them there (unlikely if you're surprised and/or unhappy about it), or because you were editing a file over a flakey internet and they got inserted by a noisy connection (very unlikely in modern times).

If this is the case, which, alas, I expect is unlikely, then open the file in an editor and remove them. Some editors may not show them, which makes it hard, but the error messages are telling you exactly where they are, e. g., on line 85, columns 1, 2, 3, 4. NUL characters will show up as ^@ in Emacs and some other editors, because Ctrl-@ is a way to type them.
My fear is that you may have destroyed your .cpp file by storing compiler or linker output there. This can happen if you separate the -o flag from the it's other half --- the file name for the output.
clang++ -Wall -Wextra -o foo foo.cpp
will compile and link the file foo.cpp and save output into foo (-o foo)
clang++ -Wall -Wextra -o foo.cpp foo.cpp
will compile and link the file foo.cpp and store the resulting executable file back in foo.cpp. This will destroy the contents of foo.cpp and replace it with binary data. If this happened to you, then the file is lost. You may be able to recover an earlier version by looking for editor backup files (files that end in ~ for Emacs and some other editors). If you have the file in an editor somewhere, then you can re-save what you have, and you may not have lost much if anything. If you've been storing your files on the department servers, then log in, go to the directory in question, and then "cd .snapshot" which will show you the available back-ups of the directory.

The backup system takes a snapshot of files about every 4 hours or so. Find the most recent backup that isn't binary junk (look the files from newest to oldest), and then copy that backed up file out to the directory. You will have lost work, but hopefully not too much.

Otherwise, you may have to start over. The good news (if there is any) is that writing stuff the second time is much easier, since you solved all the problems already very recently.
Compiling, Throw, Error Throw is giving an error when compiling. make sure you
#include <stdexcept>
Quota, Disk space I am out of disk space, or i have reached my quota limit. What does this mean, and what should I do? Disk quota exceeded means you don't have any more space on your account. You need to delete unneeded files to free up space If you want to know how much space you're using, use the "quota" command.
vm-hw03{kdesti01}58: quota

Disk quotas for user kdesti01 (uid 38393):

Filesystem space quota limit grace files quota limit grace

vs-home:/tufts_ugrad 1920M 2765M 3072M 33589 270k 300k
The space column says how much space you're using. The limit column is a hard upper limit on your disk usage. Try to exceed this limit causes "fatal error: error in backend: IO failure on output stream: Disk quota exceeded". If you just want to find and get rid of large files, the command:
find . -maxdepth 1 ! -path . ! -path ./.snapshot -exec du -sh {} \; | sort -h
will output the size of the files and folders in the current directory (sorted from smallest to biggest)
228K ./simulation
332K ./.kde
344K ./.nv
368K ./.npm
420K ./transcript
692K ./.gstreamer-0.10
744K ./comp11
4.1M ./goto
4.2M ./comp111
8.0M ./.debug 12M ./bin
14M ./.cache
17M ./comp122
21M ./comp15
28M ./PersonalProjects
32M ./Documents
38M ./.vscode-cpptools
70M ./.local
88M ./comp40
93M ./.mozilla
95M ./TAcomp15
153M ./.config
270M ./Desktop
1000M ./.vscode-server
You can then narrow down which files/folders take up a lot of space in your directory. If you absolutely can't figure out what's taking up space, shoot an email to quota@eecs.tufts.edu and ask them if they can increase your disk quota (you have to give them a number) and tell them why. In a pinch, often you can delete .o files from previous semesters / old folders, which can free a significiant amount of space without you "losing" anything, because you can always recompile if you want.
Valgrind, Memory, Grading I have lost points due to valgrind errors.

How are we graded based on memory leaks and memory errors?
Pay attention to the "definitely lost" and "indirectly lost" sections of valgrind.


Also, we use different tests than you do. When you guys run valgrind, you are running it on the tests you came up with, meaning you probably missed some important edge cases. We are working on making it more accessible for you guys to see exactly which tests fail valgrind.

You lose points based on the number of memory errors and leaks.
More errors and more leaks -> more points lost

Exact grading will be determined after you submit your assignment by the teaching staff, so there is no "10% of grade is valgrind" pre-determineded on memory leaks and memory errors
Submit, Missing files I am trying to submit but get a message saying I am missing files. Why? You have to spell the file name correctly, including case. In a pinch, you can create a file with the correct name and then submit with your (incorrectly named) file as an extra file. It's best to name the file correctly and give yourself time at the deadline to account for glitches.

If we are requiring you to submit a file, that means we expect the file, and if you don't have it, something is wrong.
Submit, Late, Token, Late Token, Feedback If we submit a hw assignment after the deadline (not using late tokens), could we still get some feedback for our own learning purposes even though we will receive a 0 as a grade? We do not take late submissions at all. You are welcome to bring your submission to office hours and discuss it with one of us.
There is no reason not to submit what you have by the deadline. Why take a 0 over some other non-0 score? If you have worked hard and made some progress, we will give you some credit for it.
Please submit your work, even if it isn't perfect. That's how you will get feedback!
Late Token How are late tokens applied in the system? (asking y/n) You need to say "y" to use a late token. Otherwise, you cannot submit your homework. If you say "n", your submission will not go through
Style, README I'm aware that we should keep lines under 80 columns. Does this apply to the README file as well?

I am wondering because I'd like to include the command to compile the program without splitting it up into different lines.
Yes! README must be under 80 lines.
Style, Testing Do we need to write function contracts for unit test code? Yes.
Since this is code you submit, it must follow all the same rules as other function contracts.
Throw, Exception, Error, Abort What do "throw" errors look like in the terminal? If a program crashes with an unhandled exception, then it prints a message like that "terminate" message and, if the it's one of the C++ exceptions, it prints the exception's message (it's "what()"). If that is the string you want in the message, then that's good!

Example:
terminate called after throwing an instance of 'std::runtime_error'
    what(): <error message>
Aborted (core dumped)
const How do we know when to use the const keyword? Should I include one in my copy constructor? "const" is used to indicate that something will not be (must not be) changed. It can get a bit murky, but the idea is fairly simple:
x = y;
You expect the above line to change x, but not y. The assignment operator for whatever the type of x and y are should not modify the right hand side object.

The copy constructor is similar: you expect it to initialize the new object, but not to change the existing object
DogHouse fluffy(snoopy);
// same as DogHouse fluffy = snoopy;
should not change snoopy.

While you can just abide by that rule, writing const for the parameter is a written promise to the caller/client that you won't change the parameter, and the compiler will make sure you keep your promise.
So, I would write const on the copy constructor's parameter.

String to int, Exception, Throw How to convert an integer into a string?

When throwing an exception, I need to print an integer as a string.
Use
to_string()
to convert an integer into a string
This will let you concatenate a string to a string representation of an integer in the exception messages.

See cplusplus.com for details on to_string if you need more information. It is available in C++ 2011.
Exceptions, Valgrind, Memory, Possibly Lost Is it normal to have possibly lost memory when you throw an exception? I only seem to be losing memory when I throw exceptions and am not sure why. Yes, this is normal.

Why: When you raise an exception, it immediately leaves the current scope and goes up the call stack looking for a catch. Unless or until if finds one, it keeps leaving functions. If the program terminates, destructors will not have been run, and you not have recycled all memory. This makes sense, because the existence of an exception renders it questionable whether it is safe to run the destructors.
Testing, Unit test, submission Do we need to submit our test files? Yes. You are graded on your test files as provided, as well as the testing description in your README.
README What do I do if I'm not provided a README? If for some reason there is no README provided on any homework or project, then you must make one and fill it out.
Empty Character, Null Character General question: When we have data that is not accessible to the user, but is data that we have allocated, what do we store in it?

As a specific question to Array List containing characters, when capacity is greater than the number of characters actually stored in the CharArrayList, what represents the empty space? Do we use '\0' for it?
No. When we have data allocated, that is not going to be read before its set again, we don't care about its "perceived value".

As in, until the memory is actually initialized with some value you care about, it can be pretty much anything. They are just addresses in memory, so they could hold all sorts of wacky values.

In fact, it's kind of a fun experiment to allocate an array of some size, say 100 integers, and then print out the values of them. You might be surprised by the result!

To answer the specific question, we do not change the values in our CharArrayList to the null character, because we will never read them until after they are set again (and therefore do not have used value), and we keep track of that using the "num items" and "capacity" private data memebers.
.h, .cpp, functions, definitions For certain functions, can I write helpers in my .cpp files without defining them in my .h file? For member functions, you MUST put them in the .h file!
If they are not member functions, then just declare them in the .cpp file.

In fact, it is normal to put the keyword "static" before functions that are purely local to the .cpp file. That actively hides them from other files. This is very important to do in large systems where someone might accidentally use the same name as one of your functions.


Because we are not writing such large things, we won't require "static," but you can do it if you like.
shrink (specific to ArrayList/LinkedList), testing, private functions Since we cannot add any public functions, I was wondering how we can test our shrink function (or any other general private function) since currently there is no public function that returns the capacity. This is a very good question.

Some functions may be hard to test, and, of course, Comp 15 does not require that students do anything that is impossible.
You have to decide what, if anything, you can do in these cases. Since you implemented the functions, only you know the details about what constitutes a good test (exactly what boundary conditions there are, if any, what values might be problematic, etc.).
If it helps, you may temporarily create a public test function in order to test some function. If you do that, you must
Make it private after your tests and before you submit, and

Document that you did this in your testing documentation (in your README and/or test file). You could say, "to test the X function, I created a test_X function and temporarily made it public and then called it with arguments Y and Z. This verifies ..." Also leave the test code in place that called the public function, but obviously you will need to comment it out, or the program won't compile and link after the function is made private.
Style, Testing Do the test functions need to be under 30 lines or are they an exception? I find that some of my test functions for functions that are a little more complex can get a bit long. Test files still need to adhere to the style guide! Try to modularize your code. Use helper functions to break down the complexity.
Style Between the { and } for int main, can there only be 30 lines of testing code? Yes. "All code you write" includes main.cpp. Because you expect humans to read it, it must adhere to the guidelines for readability.
Type Why do you need to add typename before the function signature? So that the compiler knows what you mean to make.
Template Should I write Typedef char E or T? Parameter names are your choice. Template parameters are like function parameters: From C++'s point of view the names don't matter. You pick.

You have to be consistent within a single template, but you don't have to use the same name everywhere. However, if all your templates are being used for a common purpose, then it does make sense to use the same name throughout your definitions.
Logistics, VSCode, Authentication, Halligan When I try to save my code on VSCode, I get the following message: Error: all configured authentication methods failed. No new edits show up when I compile and run my code. I used atom last semester and never ran into this issue. Did you change your halligan/cs login password? I had this issue until updated my VSCode sftp configurations.
Assignment Operator, Pointer, Reference For the assignment operator, it says to "return a reference to the lhs". Using the example of the LinkedList class, does this mean that the operator should return a LinkedList or LinkedList pointer? It returns a reference to a LinkedList, which is neither an object itself nor a pointer.

It is a reference to the object that the assignment operator was called on.
More info about what references are: https://www.geeksforgeeks.org/references-in-c/

More in depth answer --
C++ references and pointers are different, though references can be implemented using pointers behind the scenes with the compiler doing all the addressing and dereferencing automatically.
They are different, however, for very practical reasons: the compiler is free to eliminate any pointers involved in the use of references if it can, but it cannot, in general, eliminate pointers created by the programmer.
A reference is a programmer-declared alias, in which a variable refers directly to the memory associated with another variable. (That sounds like a pointer, but compilers can be very tricky and can even avoid creating variables sometimes.) A pointer variable is a location in memory (a variable) that can contain the address (pointer value) of some location in memory. Pointer values stored in pointer variables are programmer manipulable (you can pass them around, store them in other places, return from functions).

The comp15 page has an explanation of pointers and references that may be helpful. On the website under References -> Pointers.
Readme, Algorithms Is the algorithm overview section of the README relevant for this assignment? Should we write pseudocode for particularly ticky functions or skip this all together? If you have any tricky algorithms, then definitely put a pseudocode description in the README.

If you are unsure about what to write, think about what algorithms are relevant to this assignment. If you can think of anything relevant, you should describe them here.
Destructor, clear, modularity How to avoid calling the destructor twice?
In my clear function, I call a helper function that deletes all nodes in order to clear the LinkedList in the same way a destructor would. Unfortunately, when the LinkedList then goes out of scope, the destructor is called again, resulting in a valgrind double free error because the program is trying to clear memory that has already been cleared.
Is there a way to bypass the calling the destructor on an empty LinkedList, for example?
The clear function should delete all the nodes like a destructor would, and writing a helper function to use in both the clear function and the destructor is a good example of modularity. However, there is no way to circumvent calling the destructor; it's an essential part of how a class functions. But, both clear() and the destructor should work on an empty list, so could you potentially add a condition to your helper function in the case of an empty list, which would prevent trying to free an empty list?
Iterators, Polymorphism Since we're already using templates doesn't it make sense to get even more "polymorphic" and use iterators as well? No :-) Actually, it's not a bad idea, and good for you for investigating, but...
This is not a "C++ course," that is, C++ is not the primary object of study. Data structures are. So, while there is necessarily a lot of C++-specific stuff in the course, we just can't do a complete tour of C++ features, even extremely useful and common ones. I already feel that the first part of the course is rather thick with C++ stuff like assignment operator overloading and copy constructors, but nothing will work if you don't do those.
Iterators are great, and in a professional setting you should use them, but I am prioritizing other things. Others could make perfectly sensible other choices.
I would still do interfaces with abstract classes before iterators, in fact, and we may talk about that --- we did in the spring as a kind of additional topic. I might suggest "concepts," too, but I haven't really caught up on everything (I think they are for bounded quantification of generic types, and that can get much better error messages.)
Anyway, there are lots of good things, and we can't cover them all, so we pick.
(In fact, modern C++ should use smart pointers, but we don't teach that, because (a) they're hard to see the value of until you know the underlying stuff and what can go wrong, and (b) we want students to be ready for Comp 40, which assumes students are very comfortable with raw pointers and can move easily to C.)
Logistics, Back up, Save Whats the best way to go about backing up our code? Copying all of the files into a back-up directory using the cp command? If we should use the cp command, should any options be used? Sure, using cp is one way to copy files. The regular cp command copies files one by one. So for example
cp /somedirectory/somefile ./
will make a copy of somefile located in the directory /somedirectory into your current folder.
cp /somedirectory/ * ./
will copy all of the files in /somedirectory into the current directory.
However, if you want to copy an entire directory, which is what I'm guessing you want to do, you would do
cp -r /somedirectory /path/where/you/want/the/copy
In fact, cp does a lot of other things. Try this out:
man cp
That will open the manual page for the program cp! It has lots of other options that can be useful to you. In fact, most commands you are used to running like ls, cd, mkdir, touch, cat etc. have man pages. Just type man in front of your favorite command to see all that you can do.
In fact learning to read and understand man pages will benefit you greatly! I learned this the hard way, and sort of forced myself to take the time to read the documentation, and it really has payed off!


Also,
If you're working directly on halligan, the halligan server automatically backs up all of your files. It saves versions every 4 hours (for the past 24 hours), every day (for 6 days before that), and every week (for the 3 weeks before that).
You can access those backups by going to the .snapshot directory in your home directory.
cd ~/.snapshot
There, you can browse through the various backups and copy the files you need back to your working directory.
Exception, Abort, What After an exception is called, I get the message I'm supposed to get but there is also an 'Abort'. Is that normal? If that looks like what you're getting:
terminate called after throwing an instance of 'std::runtime_error'
    what(): <error message>
Aborted (core dumped)
Then that's totally fine. Different systems have different ways of displaying exceptions. The output on my mac is slightly different from the ones on the halligan, and that's all right. They are all standard library's way of displaying and formatting an uncaught exception.
In real life, people who are using your code are probably going to
try{} catch{}
your exception (which is where the name "uncaught exceptions" comes from) so they know when they're doing something wrong without crashing the application. And your exception message is going to be passed onto the code that "catches" your error, without the "abort" or any of the formatting added.
Overload I have always wondered why when we are overloading the "=" operator, there is the address operand & yet the address operand never appears when overloading "==" or "<" or even ">" operators.
For this answer, we have a student answer, and an added follow up response. This is a good discussion, so the whole thing is left here.

Student answer:

For overloading the "=":
If X=Y , "=" is an assignment operation that maps the value of Y to X. Returning a reference allows transitivity.

If you know about relations you know "=" is the most trivial example of an equivalence relation. "=" allows chaining so X=Y and Y=Z we can just write X=Y=Z. operator= actually assigns something to the object. So if I say X=Y=Z=5 this is X = (Y = (Z = 5) ). 5 is assigned to Z then return Z then Z is assigned to Y return Y then assign Y to X. So to do a chain you must return a reference to the LHS of the = each time. Hence we return *this not this.

For overloading comparison operators like "==":
You don't need to return a reference to any object you just compare and return a bool result.



Follow up by instructor:


Excellent student answer!

Emphasize: in a typical assignment overload, the & symbol appears in 3 places. In one of those places, it's the "address of" operator: (this != &rhs) (or similar). In this case, you are taking the address of rhs and seeing if this contains that address --- if so, then you are assigning an object to itself, and maybe there isn't much to do in that case.

In the function header, & is used in the parameter and return declarations to indicate those are references: it's an indicator of a reference (the function takes and returns a reference to an instance of the class). While under the covers they may be (and often are) implemented with pointer values, they are not a case where the programmer is explicitly taking the address of anything.

The student answer gets at exactly why the assignment returns a reference: You want to be able to chain assignments (C++ allows that, and if your assignment doesn't, then clients will be frustrated and confused). If it weren't a reference, then there could be an extra copy where you assign an object, the make a copy of the assigned object to return, and then each = in the chain would create a copy that was immediately destroyed after the assignment. So, a reference wins. Note the object whose reference you return is guaranteed to exist after the overload function runs, because it was already there: there had to be something for this to point to. The argument is passed by (const) reference to avoid making a copy.

You can pass references to <, >, ==, but there is really no point in returning a reference to a boolean, and if you did, what reference would you return? You cannot return a reference to a local variable on the stack (or you don't want to). So, booleans are cheap to copy and you don't actually have an existing boolean variable to return a reference to. You can pass the arguments by reference for these, and that's the normal procedure. Again, it avoids making extra copies just to compare things.
Template Error Compiling error after adding templates that say, "expected a qualified name after 'typename',"
and "warning: declaration does not declare anything."
In this case, you cannot write "typename," you have to write "class" (or "class", "struct", or "union", but we don't use unions in Comp 15).
Illegal Instruction When I try to test my assignment operator, the terminal says "illegal instruction" but when I put a print statement at the end of the assignment operator function it prints exactly what I want it do, so it seems like it's working, but once it runs in the test file it returns the "illegal instruction." "Illegal Instruction" errors are often caused when a the code reaches the end of a function but doesn't return anything when the function is supposed to return something. You may remember also that assignment operators are not like constructors, they must return the object its working on, namely with "return *this;"

One thing to look out for is when you compile, if there are warnings that say "function may reach end of non-void function," that usually indicates a return call is missing.
Destructor Is it possible to call a destructor within class functions? Say, in the assignment operator function, it is possible to call a destructor then return a new list? You should not call the destructor directly, but you can make a separate function and have the destructor and other functions call it.
Template How do I write an assignment operator using templating?

Can you use a LinkedList as an example?
LinkedList<E>& LinkedList<E>::operator= (const LinkedList<E> &other)


Logic: When you make a templated class, say List, there is no thing of type List. It has to be List <...something...> to fill in the template. If you know the type, you can write List<int> or List<SpaceStation>. If you are writing another template, then the type of the list may depend on the template type parameter(s).
Late token, Submission, Resubmit I submitted using a late token, but now want to submit again, right after my last submission. It is still within the 24 hour window provided by the first late token.

Will it require a second late token to submit again?
No, it would not cost an additional late token to submit.

From the course administration page, "Each token grants you a 1-day (24 hours) extension, no questions asked. You don't have to do anything to use a token. We'll check when your work comes in and deduct the appropriate tokens from your bank."


However, if your homework has already been graded since your last submission, we will not grade the new submission. From the course website, "If you intend to use tokens, you must not submit until you are ready for your code to be graded. We may start grading submissions any time after the deadline. We will grade the most recent submission as of the time we grade your assignment. But, if you submit something before the deadline as a hedge, we may grade that. If you submit again a day later, for example, intending to use a token, we will not grade the new assignment.
Segfault, Seg fault, Undefined behavior, Reference implementation, demo program The reference implementation segfaults / has undefined behavior / ect on a non valid input (described as non valid by the spec). As described by the spec, if explictly we say that you can always assume a valid input, then there is no problem if the reference/demo or your code has undefined behavior on a non valid input.
Warnings, Grading, Compiling, Late token I get warnings when I compile. How will this affect my score? Warnings will lose you some points, but often help identify sources of bigger problems in your code. Try to resolve all warnings before your final submission. However, if you do submit code that compiles with warnings, only a few points would be lost - it would not be advised for you to use a late token to resolve warnings, if your program otherwise works correctly.
Queue, invariant, data structure, index For my implementation, I would like to use a QUEUE data structure, that allows me to remove from an index that is not the first in queue. Is this allowed? No, queue data structures follow the first in, first out invariant -> you cannot remove elements from the middle of a queue. This would break the invariant of a queue.
README, input, output, testing, files Do I need to submit my input and output files used in testing, and describe them in the README? Yes. We need to view your testing files in order to give you credit for them. Please also include a brief description of each test file in your README.
Word count, VSCode, line wrap, grading, style, line length, WC When I run the
wc -L *
command to check for line length, it says that some of my files have line lengths over 80. I also keep losing points for this in the homeworks.

However, since the first assignment, I have kept all my lines below 65 in AtoVScode. I have line wrap set to 65 chars. I was wondering what is causing this discrepancy because I don't think that I can make my lines any shorter in VSCode otherwise my code would be unreadable.
Be careful! For example, setting your editor to wrap doesn't necessarily mean that the lines are less than 76 or 65 characters: it can mean that it wraps in your viewer if the line is longer.
Autograder, cout, cerr, redirect, input, output file, diff Does the autograder care whether we use cout or cerr?

I know that using > to redirect output into a file doesn't redirect cerr in unix, so I was wondering if the autograder requires output to go to cout so it can redirect it and run `diff` on the resulting file.
You must follow the specification in the assignment.

You may use cerr for debugging purposes, but then you should remove that output before you turn it in.


Redirection from the command line does not show up in the program in any way (that we can detect with Comp 15 programs), which is the beauty of shell I/O redirection.
The autograder actually captures both standard output and standard error output. If the assignment requires output to cerr, we can check it, and if it does not, then there may be (and usually is) a penalty for inappropriate output to cerr.
Again, this doesn't mean you should be shy about using cerr for debugging purposes!
Valgrind, blocks, memory, leak, error Just ran valgrind on my program, and noticed that it says there are over 90,000 bytes in 7 blocks use at exit, although it also says there are no bytes lost or errors detected. Is this a problem? It seems off to me, since 90,000 is a lot more than the usual 72,000. 90,000 is too many, something is up. Not sure what.
No errors is good, but that's a separate issue. Look at allocs vs frees. There should be 1 alloc and 0 frees (because our libraries do that --- it's where the 72,704 bytes come from).
You can rerun valgrind with --leak-check=full to see what else is going on.
README, purpose The README for (some homework) already has a program purpose written along with some file descriptions.


Should we leave these as they are or change them?
If they are true and complete, then you may leave them. If they are not, then please update them!
Exit
Exit failure,
exit()
What command should we use to quit our programs when an invalid filename is used?
Should we use
EXIT(exit_failure)?


Note: this only applies when the spec tells your program to quit on an invalid file name.
Depends on where the relevant code is. If you are in main, then just returning EXIT_FAILURE will do (that name is defined in cstdlib and is more of a C thing, but I think it's quite reasonable).
If you are in another function, then you may exit as you describe or return an error indication and let it bubble up to main or throw an exception that you catch in main. You should do whatever is cleanest for your implementation!
.h file, filename, functions, .cpp, structs, classes In the given (filename).h there were some functions both declared and implemented in the .h file, can I do this as well or is it considered bad style? Is it only allowed for constructors? It's customary to do that for structs, but classes should have a separate .cpp file.

Functions defined in a .h file should be quite brief (just a handful of lines), and there should not be many of them. If you create a struct and then find yourself wanting to write more or longer functions, consider changing that struct to a class instead.
Makefile, grading, Do we NEED a makefile for our submission to get credit? In short, yes.

It is a required file as part of your submission, so you should get it to work and make sure that your program compiles fully with no errors or warnings using your Makefile. You can refer to any of the labs that use Makefiles, as some of them have very detailed descriptions of what is going on at every step in the file!

Additionally, in testing, we will be using your Makefile to compile your submission for testing! So you do want to be sure you get it to work if you want to pass the autograder section!
IO, exception, abstraction I saw in the IO handout, open file (exit if fail) seems all handled in main, should we always do those in main? Or can the class we're calling handle it? Think about who the client is and what you can do to maintain abstraction barriers. Is the client concerned with I/O? What is the client specifying and what do you have that's hidden from them.
diff diff
Are there any readings on diff that could be useful for me?
Try the following command:
man diff
Will print to stdout the manual page for the diff utility. Otherwise, just google, "how to use diff linux"
Cout, streams, << I have some questions about cout, with some general confusion. Can you help me out? Many students think that cout is a command, a verb that tells the computer to do something. It is not. << is the verb that tells the computer to send the stuff on the right to the place on the left. cout is place you can << ("send", "print") things. If you have another place, like myOutputFileStream, then you can send stuff there by writing
myOutputFileStream << stuff_to_print;
cout is not special syntax: it's just a pre-defined global variable that contains an instance of an output stream class, and that instance is normally tied to the console. The << operator will work with ANY output stream!

There are several kinds of output stream. cout is an ostream. If you open a file, it will be an ofstream (output file stream). But a function that takes an ostream can also accept an ofstream.

Last note: always pass stream objects by reference (or by pointer, but reference is the C++ way).

A great resource is the comp 15 reference on streams. Link is here: File Input/Output
Big three, data structures, Do we have to build the Big Three for our data structures for this homework? Follow the instructions in the assignment: you only have to define them if they are necessary for your class implementation. Since you are designing the class, we cannot say definitively whether they are required.
File, open file, close file, open, close Is it bad form to open a file and have it open for a long time before closing or should we try to open a file right before we need it and close after we are done with it? There is nothing wrong with keeping the file open for the duration of your program's runtime. Just make sure every file gets closed when your class/program goes out of scope/ends.
Big 3 Do I need the Big 3 for this assignment? If your data members are all either simple things like integers that can be shallow copied or instances of classes that have all three, like the STL classes, then you won't need to implement them. Otherwise, yes!

A good tip, is that if there are any pointers in your class, then yes, you need the big 3.
Class, spec, name Does the name of my class need to match that in the spec? Yes, the TAs grading will want the same name for consistency, or the autograder will require the same class name.
More generally, when we name a class, the purpose of the class should be at least somewhat evident from its name.
Main, length, style main length
Is there a limit on how long our main functions should be?
According to our course coding standard and the style guide, all functions should be less than 30 lines in length. This includes the main function. We love to see a very short, modular main() in which you solely call other functions.
Output, IO, stream, open, close, file When you output to a file, is there a way to open the file and output to it bit by bit (adding to what was already there) instead of all at once? Every time I output to a file, I appear to output over what was previously there. Don't reopen the file everytime you output to it. Output data to the same ofstream. That'll automatically append data to the file.
Style, testing, lines, 30 line, length Style for testing files
Do the testing files have to adhere to the style guidelines, specifically the 30 line rule?
yes
It's especially important for testing code to have good style, so that it's easy to understand what's being tested.

One single exception, is a function whose purpose is only to call other functions. If your testing main calls 40 private test functions, then that is an acceptable length.

Make sure to follow the spec specific guidelines: There may be special instructions using the testing framework for a particular assignment.
Endl, style, \n std:: endl and "\n"
is using both bad style?
its fine.
If you asked someone with a lot of C++ experience, they'd probably tell you to prefer \n for performance reasons.
But nothing you do in Comp15 is so high-performance that you'd notice any difference.
ssh, VSCode Can't connect to SSH
My SSH connection worked perfectly for the labs and homeworks, but today it won't connect. I've tried several times and it doesn't give any error message, it just says it can't connect.
I use VSCode. I checked VSCode and my computer for updates but neither needed them. Has anyone had this happen and fixed it?
Go to Command Palette
(ctrl+shift+P)
and use Kill VS Code Server on Host, then reconnect.

The other way is to do it manually.
for x in {00..09}; do ssh YOURUTLN@vm$x.cs.tufts.edu "pkill node; pkill Microsoft; done
(there's 10 homework servers)
Grades, late work, bonus, extra credit, gradescope Does this class provide extra credit? there may be very small extra credit available for sections of an assignment, but overall no
Specific to BST: Min, max, INT_MIN, INT_MAX Why would we return a number like infinity, or a large number (portrayed as INT_MAX), when looking for the minimum, if there is none? Aren't we looking for a minimum When we are searching for a minimum that does not exist, we have a couple of options. We could throw an error.

Another choice is to indicate we had there is no minimum, by returning INT_MAX.

The client can easily check if the function (that returns an integer) is INT_MAX, which indicates that is the largest value possible, and finding the minimum failed because the data structure is empty.
30 line rule, style guide, function parameters Does the 30 line rule in the style guide apply to the function parameters? The limit only applies to what is contained between the function's brace { " }, so if there are 30 lines or under between the braces, you are fine. However, if you are nearing 30 lines, it is a good sign that there is usually a good way to make the function smaller and modular using helper functions.
Linker error, compiler, undefined reference to Linker error - "undefined reference to ... " You are calling a function as specified, but there isn't one available. It's possible your .cpp and .o files are out of sync (in which case the dependencies in the Makefile are incorrect). It's possible the link command doesn't include the .o file. It's possible the function specifications doesn't match --- it clearly matches a declaration, but the definition is missing.
Public function, helper function, I made a couple public helper functions for testing purposes, but we're not allowed to add public functions and I was told to make sure my tests weren't commented out when submitted.
Making the helper functions private or commenting them out will cause the tests that use them to crash.
What should I do with the helper functions - comment them out, make them private, or leave them public?
You can make private functions public, but then make them private again before submitting.
Strong data abstractions are important, and putting extra stuff in the (public) interface makes things less abstract and less modular. In particular, we WILL link our test code against your implementation, and the test code will not build if you change the interface.
You may comment them out if the produce compiler warning when made private. In your write up of your testing, simply describe how a grader can duplicate your tests. It's ok to say "make functions that begin with 'test_' public and link with my testing code in testBST.cpp"
Helper function, recursive The assignment asks for a function to be implemented recursively. My function calls a recursive helper function, but the exact function with the exact parameters specified in the spec does not. Is this okay? Yes, your functions can use a recursive helper function, rather than being recursive themselves. Often, the parameters in the public functions do not work well for recursion.

Make sure to read the spec for your specific assignment, because there should be more details for this requirement.
Debugging, commenting, style Debugging statements in functions.
In some functions, I included print statements in them to debug while working on them. Should I leave them in (commented out) when submitting to demonstrate the debugging process or just get rid of them?
"Commented-out code should not be submitted! It's great to test out multiple potential solutions to a problem, but by the time you submit, you should have chosen the code that works the best and deleted anything you decided not to use. The occasional exception to this rule is unit testing code that is meant to crash your program." - Style guide


We are interested in your solution and how you (purposely) tested your solution. We don't expect to see everything you did to debug. Testing and debugging can be intertwined, of course, but our main interest in this regard is how you checked that things worked, and not so much all that happened when things didn't work.

If you put print statements in as part of you testing strategy, and they aren't too distracting, you can leave them commented out and describe the strategy in your README (and explain their presence). But, even then, I would probably delete them and just say you put print statements in functions to ensure (whatever you want to test) But they should part of a coherent testing strategy, not just normal debugging.

We mostly want your algorithm to stand out clearly in the implementation, and lots of extraneous debug statements can be distracting.
File headers, purpose, Should we modify the file headers for the provided files to match update with our names, date and purpose?

Should we use the provided file purpose?

Should we also write function contracts for every function?
Yes, you need to modify the file headers.

You can modify the purpose of the file provided, to match your needs.

Ask on piazza if you need to write function contracts for PROVIDED functions (functions given in the starter code), but you need to write for every function you write.
Testing, submission Is there some other way besides comparing to the reference and using the driver that we can/should do for testing? Can I make a new file that tests each function separately or is that not necessary for this assignment? Of course you can, and you SHOULD make a separate test file.
We said you can't change the hw4 program, so that you can compare your implementation to ours.

You will naturally want to test your implementation incrementally --- because you know by now it will save you a ton of time.

We also asked you to show us your testing code, so you need to put it somewhere.

Just as with previous assignments, you should write a test program as you describe.
Design grade, gradescope, project, phase Hi! I went to a TA to talk about my design implementation for a project, but my grade in gradescope isn't there. When should I expect it to be up? You won't see the grade until we release all of them.

If you went, and you still recieve a zero, post privately on Piazza with the TA who helped you, so we can get your grade in.
Public, testing, unit testing, style, commenting Can I temporarily implement a public function as a means of testing? If so, do I comment it out so graders can see what tools i used to test? Yes. They must be private or commented out when you submit your program, but do leave them visible and documented so we can assess our testing.
Makefile, main, compile I am trying to write a makefile with two mains.
So I'm writing a test file for my (...) function in its own file, so it has it's own main function. Should these files be included in the makefile? I'm just wondering because it feels weird if the makefile has two main functions.
Makefiles can have any number of targets. That's ok.
The first one is special, because if you type "make" it will build the first target. But it's quite common to have others.
make testFunctionABC
make testFunction123
make
are all fine things to type. As a rule, you should make the first rule build whatever the assignment asks for.
Cin, Reading, file Is there a way to see what the first character of a cin is before reading it in?

For context, I'm trying to either getline() or read from the standard input stream (cin >>) depending on what the first char of input is without actually doing those actions.
std::cin::peek
check the c++ reference for more information... although you shouldn't need it for any assignment.
Quota, vscode, cache VSCode server too large, cache large. What do I do to free up space on my student account? I usually just delete the vscode folder and let it reinstall itself the next time I connect to halligan.
rm -rf ~/.vscode-server
Check out this for more information on how to limit the space used by the VScode server
https://github.com/microsoft/vscode/issues/22557

Also,
/comp/15/bin/free_space.sh
will remove browser caches
Function, class, .h, .cpp, organize, #include, include How do I use a function not included in a class, in another file? Review: How to organize programs with separate components
It is important to know that C++ allows functions to be in a class or not. main, for example, is never in a class, and the functions you write for the first part of Comp 11 are all outside of any class.
This is true for separate program components (called modules), too. To make a separate program module you:
Make a .h file with declarations necessary to use the module. The .h file can contain class definition(s) and/or function headers for top-level functions.

Put the definitions of the functions in a .cpp file. If they are in a class, then you put ClassName:: in front of them, if not, then you don't put anything in front of the function names.

#include the .h file in the implementation .cpp file AND in any client files. Never #include .cpp files!

Compile all .cpp files to .o files

Link together the .o files necessary for any particular program
If, style Can I do nothing inside of an if statement?

Example : if (condition) {} else { ... }
if (test) {
// do nothing
} else {
// do something
}
is equivalent to -------
if (not test) {
// do something
}
The latter is preferred.

However, the most important thing is readability. If something is more readable, or if saying "not test" doesn't really make sense, then you can use the style that makes the most sense.
Redirect, stream, stderr, stdout, cerr, cout, Is there a way to redirect the output of the standard error stream into a file, similar to how you redirect the standard output streaming using command_to_run > file_name ? Yes. First, this is the reason that cerr and cout are different streams --- so that you can separate error messages from normal programming output automatically!
You can send both cout and cerr to the same file in the tcsh (the shell that student accounts get by default) like this:
command_you_want_to_run >& cout+cerr_output_file
&
is like > except that it grabs both cout and cerr.
Redirecting just cerr is actually strangely difficult in tcsh, so post on piazza if you need help with that.
Helper function, private, .h, static My helper function does not need access to class components, and is only used in one file. Should I include the function in the .h for the class? Because they are not something for the client nor something C++ needs for the class, they should not go in the .h file.

You can make functions like this static (defined in the .cpp file). A static function is a function that is exactly as you described. You can do
static bool got_int(string s, int *resultp) {
char extra;
return sscanf(s.c_str(), " %d %c", resultp, &extra) == 1;
}

Make sure to define the static functions BEFORE you define the functions that call them.
Std::_bad_alloc, memory What is the std::bad_alloc exception message? Bad alloc is what happens when std::new can't allocate any new memory
an educated guess: you're infinite looping somewhere in your run function, allocating memory somehow (making a string?, pushing something onto the stack? etc), and eventually run out of memory.

No assignment in comp15 needs more memory than default, so try to see where you are allocating with the keyword "new".
Tab, style Is there an easy way to find tab characters in my files?
/comp/15/bin/has_tabs filename
will tell you whether there are any tabs in the file at all, but not where they are.

grep -P '\t' filename
will print the whole line(s) out whenever there is a tab

You can also change your tab setting in your editor and see what moves.
Piazza I have a question for Piazza. Should I post it as public to all students, or private to instructors? Please make generic questions public. That way, other students can read the answers.
Line length, 80 characters, style I have over 80 characters on some of my lines. How can I find what files and what lines are over 80 character long. The grep Unix command is pretty useful:
grep -n ".\{79\}" <filename>
This will print the lines that have lines over 79 characters the -n flag also tells you what line number they"re at.
DFS, depth first search, graph Why would DFS produce more than one valid path? Any correct path is valid. The difference in output is caused by a difference in vertex order; either your implementation populates vertices in a different order than the reference, or your dfs algorithm explores neighboring vertices in a different order than the reference.
Vector, compiler warning, int, size_t, unsigned int, size() Why can't I compare the size of a vector with a normal int? I get a warning that comes up saying I have a comparison of different integers of different signs in my for loop.

I tried to google it, and I found I can't just compare a vector size to a normal integer (int i = 0 for example). Why is this?

I think I have to use size_t somewhere, but I don't really understand why/how I'm doing that.
tldr; Since negative numbers aren't useful for indexing into arrays, unsigned int values are used to index into an array.
-----------
The
size()
function of a vector returns a size_t value.
std::size_t
is a type used for expressing the sizes of things.

A key feature of sizes is that, while they are integers, they cannot be negative, so a size_t is an unsigned integer of some kind ("unsigned" in C++ means values will always be >= 0). C++ is warning you about comparing signed and unsigned values, because it's usually a case where the programmer messed up, and strange things can happen. For example,
for (size_t i = 10; i >= 0; --i)
cout << "i is " << i << endl;
is an infinite loop, because i can never be negative!


Moral: Always use unsigned integers, and specifically size_t's for iterating over collections.


If you want some more (a little Comp 40 preview!):
An int in C++ on our system is 4 bytes. There are 32 bits in 4 bytes, which can encode 4,294,967,296 distinct values. Integers may be positive or negative, so some of the values will be for negative values and others for positive values (and 0). One bit can be used as the sign. Thus, an integer may be any value in the range:
-2,147,483,648 through 2,148,483,647
That's −2^31 through 2^31 −1 (0 takes up one of the non-negative values)


In C++, negative numbers cannot be used to index into an array. Consequently, using a standard signed integer is inefficient; it cannot use half of its domain. An unsigned integer uses all 32 bits to represent a number (and can therefore only represent positive numbers). An unsigned long integer can use 64 bits! The number of bits in a size_t is implementation dependent, but if you use variables of type size_t, then you be sure you'll be able to represent the size (and index where appropriate) of any C++ collection.
getline, IO, file, reading, >>, I'm having trouble using getline vs. >> Any tips? I encourage students to look up things they are using. This is a key professional skill. For example, good getline documentation can be had here:

http://www.cplusplus.com/reference/string/string/getline/

getline reads a line of text into a single string. That line ends at the next '\n' or at the end of file, whichever comes first, and '\n' is not included in the string (if it was there at all). Here is exactly what it says:
Extracts characters from is and stores them into str until the delimitation character delim is found (or the newline character, '\n', for (2)).

The extraction also stops if the end of file is reached in is or if some other error occurs during the input operation.

If the delimiter is found, it is extracted and discarded (i.e. it is not stored and the next input operation will begin after it).

Note that any content in str before the call is replaced by the newly extracted sequence.

Each extracted character is appended to the string as if its member push_back was called.
>> on the other had extracts things from the stream based on the type of the variable designated to receive the variable. This one is trickier to look up, because sometimes it's in the stream class, sometimes it's in the target variable's class, and sometimes it's an external function. In the case of strings (http://www.cplusplus.com/reference/string/string/), it's a non-member function overloaded by the string library (http://www.cplusplus.com/reference/string/string/operator%3E%3E/)


Unfortunatly, the documentation appeals to operator>> on c-strings, to which it does not link, but the documentation covers you:
Notice that the istream extraction operations use whitespaces as separators; Therefore, this operation will only extract what can be considered a word from the stream. To extract entire lines of text, see the string overload of global function getline.
so, it stops at the next (whitespace) delimiter.
A line that contains "pony frog\n" will give back "pony" using >> but "pony frog" using getline.
Logistics
Windows
Atom
carriage
Text editor/line ending errors
(A common problem if you can't figure out why tests you made aren't working.)
Unix (including MacOS) and Linux use 1 character, LF to signal an end of line; Windows machines use the 2-character sequence CRLF ("\r\n") for end of line.
If you have a text file already saved in Windows format, you can run the dos2unix program on the server (type "man dos2unix" to see how to use it).

In Atom, You can ctrl+shift+p and enter "line endings" to convert and also change the atom config to apply the change to all files.
Late tokens, homework, submissions How do I see how many tokens I have left? Type
use comp15
and then
prolog hw4
(Or whatever the last assignment was). This will show you the logging of your last submission, and in this is a summary of your past token usage.
Time complexity, Dijkstra's algorithm, graphs Dijkstra time complexity? It is true that that in a graph with V vertices and E edges, E∈O(V2), but not every edge is used. In a connected graph, every vertex is visited exactly once by Dijkstra's algorithm. This means the number of edges actually traversed when running Dijkstra's algorithm is O(V).

Over the course of the algorithm, V vertices are inserted into the min-heap (each insertion takes O(lgV) time), and there are E extractions from the min-heap (each extraction also takes O(lgV) time. Thus, the runtime of the algorithm is O((V+E)lgV), which expands to Θ(VlgV+ElgV). Since at most V edges prompt an extraction, E∉O(V2)
Also, consider this: it is impossible for every edge in a fully connected graph to result in a path to a given vertex that is shorter than every other previous path. If this were the case, that would imply that every path was the shortest path, which is never the case.
-------
Follow up Question: I still don't get it. If you have a DAG or just a directed graph the number of edges still converges to O(V^2)?
-------
If you have O(|V|^2) edges, then there is nothing you can do. As I said in the video, most graphs do not have that many edges: completely connected graphs are rare in practice, and sparse graphs are the norm, at least for many applications.
I think the example I used in the video was a road map where vertices are road intersections. There is no road from every intersection to every other intersection. In fact, a typical intersection will have <= 4 neighbors. You can pretty much assume that an intersection will have some constant bounded number of intersections. I saw some estimates online that there are ~300,000 intersections with traffic signals in the US, but none of them have anything like 300,000 roads coming into them!

So, the priority queue model does assume that you are not going to have O(|V|^2) edges --- in fact, must less, like O(|V|), is common.
Folder, halligan, deleted, back up, snapshot Just deleted everything in my comp15 folder - how do I get it back? It was backed up before that.
cd home
ls -la
cd .snapshot
ls
cd (enter the most recent snapshot)
cp -r (the files/folders you want back) ~/
&&, &, strict boolean operators, lazy Strict Boolen operators (and vs && vs &)
(There are two replies for this one)
Zach and I were both answering this, and we had overlapping, but not identical, information in the explanation and gave the same suggestion :-)
-------
tl;dr Don't use the bitwise operator for boolean purposes. If you want to force evaluation, either

●Assign the two items to variables and then put the variables in the boolean expression

●Make a function that does the and/or operation, which will force all arguments to be evaluated.

Here is more:
The English/symbol operator name split is not related to when things are evaluated (strictness).

We usually use the terms "strict" and "lazy" with regard to function arguments (though nearly all mainstream programming languages are strict).

For boolean operators, the term we use is "short-circuit." A short-circuit operator produces result as soon as the answer is known, and does not evaluate the second operand when it isn't necessary. Thus, short-circuit operators are not just boolean operations, but are also control flow operators.
For example,
orders_verified() and launch_missiles
won't launch missiles if orders have not been verified. Whew! You can think of logical and/or as being built from if statements (really conditional expressions).
The English names are just more readable names for the operators. For example, for each row, the operator name on the left is exactly equivalent to the symbol(s) on the right. The named version and the symbol version have exactly the same control flow properties.

Logical
and &&
or ||
not !
Bitwise
bitand &
bitor |
compl ~

The bitwise operators are not the same as the boolean operators. If you JUST have true boolean values, then they will work the same, BUT C++ inherits C's history of punning on booleans. That is, 0 is considered false and ANY integral non-zero value is considered true. There are functions that are used in a boolean context that will return non-zero true values that are not true (which is convertible with 1).

Suppose is_frob(a) returns a true value of 5, and is_frob(b) also returns a true value, but the integer is actually 10.

Then, is_frob(a) and is_frob(b) which is the same as the old-fashioned is_frob(a) && is_frob(b) will be true. But, is_frob(a) bitand is_frob(b) which is the same as is_frob(a) & is_frob(b) will be 0, which is considered false.

This is why I adopted the policy in Comp 15 of using the English ones: it's very easy to type & when you mean && and not notice the difference, and it will often work. Except sometimes. And then the bug is very hard to figure out. You are not likely to type bitand when you mean and.

So, DO use the names rather than the symbols, because they are easier to read AND less likely to lead to mysterious bugs. DO use boolean operators when you are doing boolean operations, and use bitwise operators only for actual bit manipulations. This more clearly communicates your intentions to the reader. (If you use bitwise operators to enforce strictness, then you'll need a 2 or 3 line comment explaining why you're doing it, and even then, you've sent the reader down a little detour. You can assign values to variables and then put a brief comment that your forcing the evaluation of all boolean expressions --- but the fact that we're doing boolean manipulations is clear.

-Mark

-------

Generally, try to avoid writing (non-short-circuited) boolean expressions that rely on the evaluation order of each expression. The evaluation order for non-short-circuited boolean operations is not guaranteed, so the side effects you intend to induce may not behave as expected.

I would recommend you evaluate each expression and store the resulting boolean in a variable. This will guarantee the expressions are evaluated in the order you intend. Then, just compare the booleans using the standard and keyword.

Technically speaking, use of "&" operator is appropriate for your case (but it still not preferred). Bjarne Stroustrup (the inventor of C++) really loved his ampersands; there are seven different use cases for the "&" character in C++, each with distinct behaviors. This invariably leads to confounding errors when we try to debug code that looks perfect, but is sneakily interpreting our ampersands in a way other than we intended. The not, and, and or keywords are included in C++ for good reason; to avoid all this unnecessary confusion. Thus, we explicitly forbid the "&&" boolean operator in COMP 15. --Zach