Transition to the next class - Data Structures

This material is compiled with the help of many mentors over the years. Special thanks to Micheal Gardner for redoing the Cygwin installation instructions and his overall review of this document.

Overview

If you are continuing on your journey in Computer Science, here are some suggestions for you.

  • The next class in the sequence will introduce you to completely new concepts, building on the concepts learnt in this class.

  • Make sure you are very comfortable with the concepts we learnt here. Review labs and homeworks, make sure you can solve them pretty easily.

  • Install a working environment in C++, which is the language you will be using in the next class.

  • Review C++ syntax before you take your next class. Make sure you develop:

    • Skills to solve the CS-1 level problems in C++.
    • Skills to debug C++ programs.

    Students who wrote basic C++ programs over the break did well in Data Structures. It also helps solidify your algorithmic problem solving skills.

  • You can also review the first few labs in Data Structures if you wish and work on those in advance:

    http://www.cs.rpi.edu/academics/courses/fall15/csci1200/calendar.php

In this document, there are some suggestions to help you get ready for your next class.

Learning C++

You are not learning C++ from scratch. Many basic constructs are very similar in C++, but there are differences too. Here are some sources that were highly recommended:

Go through the tutorial and the videos. Make sure to write many programs.

Differences between Python and C++

Here are a few first things to notice between the two:

  • C++ is a compiled statically typed language. This means that variables need to be defined with a data type first, and the data type cannot be changed.
  • Programs cannot be run until compiled. If you have a syntax error, the compiler will not produce an executable until you resolve all syntax errors.
  • In C++, many new errors will be checked at compile time, like trying to add a string and an integer. As Python is dynamically typed, you are used to resolving such errors at run time. This means, you will spend more of your time in fixing compilation errors in C++ than in Python. Hence, learn to write programs in small steps, test and expand.
  • Syntax differences: each line in a program must end with a semicolon and each block must be delimited by curly brackets.
  • Be aware of the scope of local/global variables. Generally using our convention of passing variables to functions only as arguments and returning the result will help you a lot.
  • Strings and a single character are the same type of object in Python, but not in C++. Overall, make sure you understand each data type well first. Start with simple data types before you go into containers.
  • Many basic programming constructs are similar: variables, data types, operations, operator precedence, functions, loops, files, etc. You will find that for loops generally involve a single integer counter, no range function. Learn the basic snytax for these first.
  • Containers will be different. Instead of lists in Python that can be used for everything, you will need to learn about arrays, lists and vectors in C++. All containers we used had flexible length, while in C++, some will have predefined size.
  • You will see classes in C++ are very similar, but have a few new limitations like private attributes that can only be used within the class. This is actually a good thing, believe me.

For more in depth description of the differences see:

Setting up your C++ Working Environment

Your basic development environment in C++ consists of an editor for writing programs and a Terminal window for compiling and running your programs.

  • You must have a C++ compiler installed. In Windows, the compiler comes with Cygwin. In Macs, you must install the Command line tools (which we have already done for our class).

  • You must open a Terminal window: Terminal under Applications->Utilities in Macs (black box) and Cygwin under PCs. See more about Cygwin below.

  • Navigate the terminal to the folder in which you have your program. See basic terminal commands below.

  • You must use an editor to write your programs. Many choices exist. The choice of editor is not so important, but becoming proficient in using an editor is.

  • Example editors (Google the name for your operating system):

    • Emacs
    • Sublime
    • Notepad++
    • Vim

    Some of these already come with the Cygwin installation, see below.

Basic Terminal Operations

Basic terminal operations (Terminal in Macs and Cygwin in PCs) include:

  • Displaying the current working directory the terminal is pointing to:

    $ pwd
    
  • Listing the files in the current working directory for the terminal:

    $ ls
    $ ls p*   ##lists files that start with p
    $ ls Dropbox   ## lists files in the directory Dropbox
                 ## (assuming it is one level below it)
    
  • Changing the working directory to a directory on your file system (cd means change directory):

    $ cd directory_name
    $ cd directory1/directory2   ## if you want to change multiple
                               ## levels of directory in a single step
    $ cd ..  ## goes one level up in the dictionary hierarchy
    
  • Compile code:

    $ g++ programname -o outputname
    

    For example:

    $ g++ program.cc -o program
    

    This generates a new file called program in Macs and program.exe in PCs.

  • To run a program called program, use:

    $ ./program
    
  • Create a symbolic link (a shortcut) between two folders is very good way to simplify your life. Suppose you are at your own Desktop. I will create a shortcut to a directory on my dropbox on my own Desktop:

    $ pwd
    /Users/sibeladali/Desktop
    $ ln -s /Users/sibeladali/Dropbox/CSCI1100_Fall2014/ cs1
    

This tells me to create a symbolic link (ln -s) for directory /Users/sibeladali/Dropbox/CSCI1100_Fall2014/ and call it cs1. Now, I can simply write the following:

$ cd cs1

Installing Cygwin

If you are a Windows user, you should install Cygwin. Cygwin is a Unix-like command-line interference for someone who is using Windows. It’s important to learn how to navigate and use Cygwin to compile and run files because that is a very common way most developers work and it will be main method used in Data Structures.

  1. Visit www.cygwin.com/ and click the “Install Cygwin” link in the sidebar (both “Install Cygwin” and “Update Cygwin” take you to the same page) and download the setup file to somewhere where you can find it. You will most likely need the 64-bit version but please check your computer to make sure, and use setup-x86 for 32-bit systems or setup-x86_64 for 64-bit systems.

    You can check whether your machine is 64-bit or 32-bit by following the instructions here:

    http://windows.microsoft.com/en-us/windows7/find-out-32-or-64-bit

  2. Double click the setup file, click next and then dot the “Install From Internet” box, then click next again. Keep all settings for selecting Root Install Directory the same, then click next one more time.

  3. Make sure to set the local package directory to C:cygwin, then click next, and then next again. Here pick any mirror, and then click next again.

  4. There’s a ton of info on this page of packages to choose, do not get overwhelmed. Make sure to keep the “Curr” choice selected at the top bar.

  5. From this list we have two options: the g++/gcc compiler and the gdb debugger, or the clang++ compiler and the gdb debugger. The main difference between clang and g++ is that clang has better error messages, which is very useful for new C++ programmers. However, clang is still under heavy development and is sometimes less stable and portable to all OS and hardware. It should be noted that it is possible to compile all of Data Structures homeworks in g++ and clang.

    Choose g++ or clang, and follow the instructions below:

    If you chose G++:

    1. Go to the top left of the window to the Search bar and type in “g++” (do not press Enter, the search is automatic). The list will suddenly shorten so that the category “Devel” is left. Press the plus sign next to “Devel” to expand that category.

    2. Near the top of the list of compilers that have g++ in them, there is the compiler named “gcc-g++:GNU Compiler Collection (C++)”. Click the word “Skip” once to change it so that the package will install.

    3. gcc stands for GNU C compiler, with GNU standing for GNU’s not UNIX. g++ stands for GNU C++ compiler with the cc being replaced by ++ standing for C++.

    4. The command for g++ to compile C++ code in Cygwin is the phrase g++. Whenever you need compile code with g++, you must use the phrase:

      $g++ mycode.cpp -o myprogram
      

      with myprogram being the name of the compiled file. You can compile C code by using gcc instead of g++.

    If you chose Clang:

    1. Go to the top left of the window to the Search bar and type in “clang” (do not press Enter, the search is automatic). The list will suddenly shorten so that the category “Devel” is left. Press the plus sign next to “Devel” to expand that category.

    2. Near or at the top of the list of compilers that have clang in them, there is the compiler named “clang: C/C++/ObjC compiler frontend based on LLVM”. Click the word “Skip” once to change it so that the package will install.

    3. Clang stands for C Lang uage Compiler. It compiles languages such as C, C++, and Obj-C. We only care about C++ right now.

    4. The command for clang to compile C++ code in Cygwin is the phrase clang++. Whenever you need compile code with clang, you must use the phrase:

      $clang++ mycode.cpp -o myprogram
      

      with myprogram being the name of the compiled file. You can compile C code by using clang instead of clang++.

  6. Now, go back to the Search bar and type in “gdb”. The list of packages will change again and you will have lists with names such as “Database”, “Debug”, and “Devel”, click on the plus to expand “Devel”.

  7. Near the top of the list of programs with gdb in them, there is the program named “gdb: The GNU Debugger”. Click the word “Skip” once to change it so that the package will install.

  8. Then hit next and take a break. Your computer is going to download all the packages required and install them as well. This step can range from 20 seconds to 10 minutes so give it some time. Grab some coffee maybe.

  9. Click finish. You have finished installing Cygwin on your Windows machine. Proceed to another section to learn how to navigate around Cygwin with UNIX commands.

  10. Cygwin is now installed with the packages. If you ever need to uninstall or install new packages just re-run the setup.exe and modify as you need.

Using Cygwin

  • When you open a Cygwin window, it does not yet point to a valid location on your hard drive. The first thing you should do is to point it to your C drive with:

    $ cd c:
    
  • Next, you must point it to the root directory for all your files. In Windows, this is usually something like:

    $ cd c:/Users/your-user-name/
    

    Here you should be able to see folders like Desktop and Documents.

Integrated Development Environments (IDE)

As we used Wing for CS-1 as an integrated environment for Python, many IDEs exist for C++. Many general purpose IDEs work for C++ well:

Remember: IDEs are useful for debugging with a graphical user interface. But, it is likely that no one will be an expert in the specific IDE you use. Practice and learn its features before starting to use it in class assignments.

Final Note

Please feel free to send me other resources and corrections to this document by email.