Recitation 1

These notes were prepared by Petros Komodromos.

Topics

1. Course goals & content, references, recitations
2. Compilation 
3. Debugging  
4. Makefiles
5. Concurrent Versions System (CVS)  
6. Introduction to C++
7. Data Types
8. Variable Declarations and Definitions 
9. Operators
10. Expressions and Statements
11. Input/Output Operators
12. Preprocessor directives
13. Header files
14. Control Structures

1. Course Goals and Content

•  C++:
   Procedural and Object Oriented Programming
   Data structures
   Software design and implementation
   
• Algorithms:
   sorting (insertion, selection, mergesort, quicksort, shellsort, hashing)
   searching (linear search, binary search, binary search trees)
   
• Java®:
   Object Oriented Programming (OOP) using Java®, Java® application and applets,
   Graphical User Interfaces, Graphics using Java®
   
• Advanced  Topics:
   Geometric algorithms, Java®3D, Database design using  JDBC, etc.
   
• Term Project

Textbooks - References

• C++
  • C++ Primer. Lippman and Lajoie. 3rd edition (required).
  • C++ How to program. Deitel & Deitel. 3rd edition.
  • The C++ programming language. Bjarne Stroustrup. 3rd edition.
  • On to C++. H. Winston. 2nd edition.
  • Object Oriented Programming in C++. Johnsonbaugh & Kalin.
  • C++ FAQ. Cline/Lomow.
     
• Algorithms
  • Algorithms in C++. Sedgewick (required).
  • Algorithms, Data Structures and Problem Solving with C++. Weiss.
  • Introduction to Algorithms. Cormen, Leiserson, and Rivest.
     
• Java®
  • The Java® Tutorial. Mary Campione and Kathy Walrath (required).
  • Core Java®. Gary Cornell and Cay Horstmann. 2nd edition.
  • The Java® programming language. Ken Arnold and James Gosling. 2nd edition.
  • Java®: How to program. Deitel & Deitel. 2nd edition.

Problem Sets

You need to follow the instructions that are provided with each problem set, concerning what you must submit. In all problem sets you must both electronically turnin the source code files, and submit hardcopies of all completed, or modified, source code files. Sometimes you may also need to provide screen dumps of the window with the output results from the execution of your programs.

The problem statement and the provided source code files can be obtained using CVS, which is a version control system (covered later in this recitation). Whenever source code files are provided, the following naming convention is used:
For each question there is a ps<number_of_problem_set>_<number_of_question>.C which you may need to use, e.g. ps3_2.C for question 2 of problem set 3.
In some cases a makefile (named make<number_of_problem_set>) is provided, which you may use to compile and link your code.

Please comment your code to make it more readable whenever you think it would be helpful for someone else to understand what and how you do it (i.e. for the graders). Comments may be incorporated in your code by either enclosing them between /* and */, or, by putting them on the right side of two division symbols //.
It is also very useful for both yourselves, and the graders, to indent your code in order to emphasize loops and different parts of your code. You should indent your code so that different blocks start in different columns making it less obscure and difficult to understand.
Please, do not make any other changes to the provided code, except those that you are asked to make.

You can print a file in a compact form (saving some paper) using the following command so as to have the name of the file and the time and date printed on the hardcopy.
        athena% enscript   -2Gr    -P<printer name>   <filename>
Whenever necessary, you can dump an X window directly to a printer using the following command and clicking on the window you want to print.
        athena% xdpr  -P<printer name>

Homework that is turned in late will be penalized as follows:
 

• If turned in one day late i.e. by 2:30 p.m. on the day after the due date, the penalty is 10% of the overall score (i.e. 10 points off). You can turn in the problem set solution only once. The first hardcopy you will turn in will be the one to be graded, i.e. if you plan to submit it late you should not submit a solution on the due date, as well, but only the late one the day after the due date.
• If turned in more than one day late, the penalty is 100% i.e. no credit will be awarded. No exceptions!

Please, always staple your hardcopies together and write clearly on the first page your name and username. Also, type within a comment at the top of each file you submit the following information:

•  your first and last name
•  the problem set number, and
•  the question number

2. Compilation

After writing the source code of a program, e.g. using an editor such as emacs, you must compile it, which translates the source code into machine instructions. For the C++ programs you need to use the GNU g++ compiler. To be able to use this compiler, you need to add its locker using the following command (on the Athena prompt):
  
    % add -f gnu

You can customize your account, using a dotfile, so that it will automatically add the gnu locker at start-up. In the file .environment you need to add the following line:

       add -f gnu

The add command attaches the specified locker to your workstation and adds it to your path. Dotfiles, such as .environment and .cshrc.mine, can be used to set environment variables, shell aliases and attach lockers in order to get the desired working environment. In the .environment dotfile you may also put the following lines to avoid typing them every time you log in:

       add infoagents
       add  1.124
       setenv CVSROOT /afs/athena.mit.edu/course/1/1.124/src

You can check if you properly use the GNU compiler by giving the following commands:

    % which g++                    which should give you something like:
      /mit/gnu/arch/sun4x_55/bin/g++     or     /mit/gnu/arch/sgi_53/bin/g++

Then, you can use the GNU compiler to compile a C++ source code file. For example, to compile and link the source code file ps0_1.C, which is provided in PS0, you can use the following command:

     % g++  ps0_1 .C

Then, you can run the generated executable file, which is by default named a.out, by typing its name at the Athena prompt.
To give a specific name to the generated executable the -o option must be used:

     % g++  ps0_1 .C -o  ps0_1

Then, the generated executable file is named ps0_1

Sometimes, you may need to include an external library, e.g. the math library, using the -l option as follows, and the name of the external library (below the math library is included using m after -l) you want to include (in addition to including its header file in your files):

      %   g++    ps0_1 .C       -o  ps0_1     -lm

In some cases that you only need to compile a file without linking, i.e. to generate only the corresponding object file (machine language versions of the source code) and not the executable, you need to use the -c option. (In the following example a ps0_1.o will be generated)

     % g++  -c   ps0_1 .C

You also need to use the flags -ansi -pedantic to enforce the rules of ANSI Standard C++. In addition, it is useful to use the -Wall option to get all warnings, e.g.:

     % g++  -ansi -pedantic -Wall    ps0_1 .C     -o  ps0_1    -lm

It is more convenient to set an alias (e.g. c++), instead of typing all this every time. In particular you can add in your .cshrc.mine dotfile the following:

     alias   "c++"  "g++  -ansi   -pedantic   -Wall   -lm"
and then simply use the following command to compile and link a program:
     % c++   ps0_1 .C    -o  ps0_1

In addition, you can use makefiles to help you automate the compilation and linking of your programs. The following command creates the target_filename according to the instructions provided in the makefile make0a.

    % gmake -f makePS0a ps0_1

Eventually you must learn to use makefiles since they are extremely useful for the development of large programs with several different source code files.

Although you may work at any machine and using any compiler you want, you need to make sure that your code compiles properly using the GNU compiler on an Athena workstations. The graders will be using Athena workstations and the GNU compiler to check your solutions.

3. Debugging

Using a debugger can help you find logical and difficult to detect errors in your code much faster and easier. A debugger can be used to step through the program, line by line and examine the program variables while executing it. Therefore, you need to first correct all syntactical errors, using the messages from the compiler and then execute the program using the debugger to detect potential logical errors. Typically, you compile the program, identify errors using a debugger, correct it in emacs, compile and debug again, and repeat as often as necessary.

The debugger allows you to examine in detail what is happening during a program execution, or when it crashes due to a run-time error. In order to be able to use a debugger, such as gdb and ddd, you must first compile and link your code with the flag -g. e.g.:

       % g++   -g    ps0_1 .C    -o  ps0_1
 

• gdb debugger:
  
  The  g++   -g    ps0_1 .C    -o  ps0_1 command generates an executable filename that can be checked with gdb, e.g. using the following command for the program compiled above:

         % gdb   ps0_1

You can find more information about GDB at Debugging with GDB - The GNU Source-Level Debugger.
 

• ddd debugger:
  
  A user friendlier debugger, available on athena, is the Data Display Debugger (ddd), which uses the gdb for its operations. The ddd program is available in the outland locker. Since we also need the g++ compiler from the gnu locker for the compilation you need to type:
  
  % add outland
  % add gnu
  
  To invoke the ddd debugger with your executable program, e.g. for ps0_1, please, type:
  
  % ddd ps0_1 &

You can see that three windows pop up:

1. The main window, which has three main parts.
   • the top panel with the menu bar and the tool bar
   • the middle panel with your source code, which is a read only panel code here.
   • the bottom panel with the (gdb) prompt, which is the debugging console
      
2. Debugger command tool window, titled  ddd
3. A tip window, which often provides useful debugging tips. You can close this window.

In general, the debugging cycle involves stepping through your program carefully once it compiles and seems to run. In particular, step into each function that you wrote; step over, e.g. using the ’Next’ button, system functions. At each step, ’Print’ the variable value(s) computed and  check them for reasonableness. Keep going until you find logical errors. Then, make the proper correction, using the editor, recompile and do this again.

The execution of the program can be controlled from the ddd command tool which has the Run, Interrupt, Step, Next etc. buttons.
 

• To start debugging:
  • Find the first executable (non-declaration) line in the program
  • Place the cursor on that line (mouse click)
  • Then click on the ’Break’ button in the tool panel at the top of the main window. This will set a breakpoint at that line.  A breakpoint stops program execution. You should see a stop symbol at that   line.
  • Click on ’Run’ button in the ddd window.
  • This starts program execution, which will run until the next breakpoint  or the end. The program will run to the first breakpoint and halt.
     
•   To step through the program:

You can step through the program using the buttons on the ddd window. A green arrow will indicate the current program statement being executed in the source code panel.

• •  clicking on the ’Next’ button steps over function calls and goes to the next line of the current function
  • clicking on the ’Step’ button steps into any function call on the current line
  • clicking on 'Finish’ will finish executing the current function. You can use ’Finish’ to come out of any system source code (cout for example) you ’Step’ into
     

• Looking at variable values:

  • To examine normal variables you can:
  • move the mouse on top of a variable and a pop up box will show the variable’s value
  • click on the variable so that it becomes highlighted, and then click on the ’Print’ button in the toolbar. Then, the variable's value will appear in the console
     
• To examine arrays:
  • moving the cursor on top of an array, either the memory address of the first element is shown if values have not been set, or if values have been assigned to the array, the array values are shown
  • highlighting the array name the array name will appear in the text box present in the tool bar. If ’Print’ is clicked now, the memory address is printed in the console.
  • adding a * before the array name and clicking ’Print’ will print the value stored in the first element of the array. If you wish to see all the elements in the array, replace ’*arrayName’ by ’*arrayName@arraySize’ in the text box and then click ’Print’.
     
• To display a variable:

You can continuously see the values stored in a variable, by displaying it instead of printing it. The displayed variable will be shown in a new panel which will pop up above the source code panel. As you step through the program, any changes to the variable’s value will be shown there. You can display a variable by:

• highlighting a variable and clicking on the ’Display’ button on the tool bar. Its value is updated every time it changes.
• To undisplay a variable.

• Right click on the variable’s box and choose ’undisplay’.

• To display values of all local variables in the current function:
  • choose "Display local variables" from the ’Data’ tab in the menu bar of the main window.
     
• To display the arguments passed to the current function:
  • choose "Display function arguments"  from the ’Data’ tab in the menu bar of the main window.
     
• To input and output:
  • Input and output is done through the debug console.
  • cout line usually found before cin will display a prompt
  • stepping to a cin enter your input in the bottom window in the blank line at the bottom
     

• Resources:

  
  You can learn more about ddd from the DataDisplayDebugger web-page.
  
  
  You can look at the ddd manual as well.

4. Use of makefiles

In some cases a makefile (named make<number_of_problem>) will be provided, and you may use it to compile and link your code. Makefiles are used to automate the compilation and linking of programs. To compile and link a specific program, assuming that a proper makefile is available, the following command is used:
        % gmake -f make_file_name   <program_name>
You do not have to use the provided makefiles, but you can use instead your own makefiles, or any of the makefiles you have seen in the lectures or anywhere else. You need to turnin the makefile that you use to compile your files on athena (either the ones you got using CVS or your own) Learning to use makefiles will help you when you start writing and compiling larger programs with several files, which makes the use of makefiles necessary.

In problem set # 0, a simple makefile is provided for you, called makePS0a, which you may use to compile and link your code. There is also a more advanced makefile named makePS0b which you can use.

e.g.           athena%  gmake   -f makePS0a    ps0_1

Executing the above command creates the target filename ps0_1, according to the instructions provided in the makefile makePS0a.

5. Concurrent Version Control (CVS)

For the development of large software packages and programs it is useful to use a control system for modifications and revisions. Although it may not seem very useful for the development of small simple programs (like your first homework problems) it would be very useful for your project, and you will benefit from getting used to using it. Therefore, it would be beneficiary for you to get used to using such a revision control system as CVS (Concurrent Versions System). You may obtain more information on CVS from the man command (% man cvs) and from the following URLs:

• cvs - Concurrent Versions System
• Concurrent Versions System - Tutorials
• CVS Index
• Concurrent Versions System - The Open Standard for Version Control

The provided source code files are in the directory /mit/1.124/Problems/<Problem set number> from where you can copy them using CVS to your directory, and, make the necessary additions and/or modifications. To use CVS to check out the problem sets for the 1.124 you should first set the environment variable CVSROOT as below: (you can also put it in your .environment dotfile)
     % setenv CVSROOT /afs/athena.mit.edu/course/1/1.124/src
then you can use the command:
     % cvs co Problems/PS<Problem set number>
or, using the alias defined in 1.124/src/CVSROOT/modules
     % cvs co OOP_PS<Problem set number>

6. Introduction to C++

C++ is both a procedural oriented programming language and an object oriented programming (OOP) language, since it allows you to organize your program not only around functions (procedures), but also and most commonly used, around data.

A procedural language is based on a list of instructions (statements) organized in procedures (functions) and emphasizing the computations to be performed. Languages such as Fortran and C are procedural languages. C++ which is based on C, has many additional features that enable object oriented programming, where emphasis is given on the data and their behavior. Java® is a pure object oriented language.

The additional features and advantages of C++ are the following:

Classes allow the programmer to create her/his own data types extending the capabilities of the language according to the physical world problems. Classes are similar with the data structures in C, which are also available in C++. However, within a class both data variables and member functions that are used to work with the data variables can be provided.

  class Complex
    {
      public:
         double real;
        double imaginary;
   };

  main()
      {
         Complex x;
         x.real =15.5;
         x.imaginary = 2.5;
     }

There are many additional features, like inheritance and virtual functions, added to C++ which are related with the classes and provide simple ways to handle objects and develop programs in an object oriented programming style.

C++ allows reusability since a class which has been written, debugged and checked can be distributed to other programers and with minimal effort be incorporated in several programming packages.

C++ supports function overloading which allows the use of functions with the same name, as long as they have different signature. The signature of a function is considered its name and the number and type of its arguments. e.g.:

     int min(int x, int y) {      }
     double min(double x,  double y) {      }

In addition, virtual functions and polymorphism allows the dynamic binding on functions during run-time instead of static binding during compilation.

C++ allows operator overloading, i.e. to use operators with user defined data types according to a specified function associated with the specific operator. For example, we are able to add two complex numbers which are a user defined data type, as long as we provide the necessary functions for operator overloading.

   main()
         {
            Complex x,y,z;
             ........
             z = x + y ;
         }

In C++, there are two ways to comment, // (which comments everything until the end of line), and /*  */ (which comments everything between /* and */.

Two latest features of C++ are the templates and the exception handling. The templates allow us to parameterize the types within a function or a class providing a general definition that can be used for many different purposes. The exception handling mechanism provides a mechanism to respond to and handle run time errors (like division by zero, exhaustion of memory, etc.).

7. Data Types

• Boolean: bool
• Character and very small integers: char
• Integers: short int, int, long int     (short, int, long)
• Floating (single, double and extended precision): float, double, long double

The bool data type can be assigned the values true and false, which correspond to 1 and 0, respectively.
  
A char can be used both as a character and as an integer, depending on how it is used. Therefore, char, short, int, and long are all called integral data types.

There are also unsigned versions of integer types, which allow the increase of the range of the larger number that can be stored with them, by not using any bit for the sign: unsigned char, unsigned short int (unsigned short), unsigned int, unsigned long int (unsigned long).

The reason of using different data types is mainly for memory efficiency, since we can use the data type which correspond to our needs avoiding useless waste of memory. The proper data type must be selected and used based on the expected requirements during the program’s execution.

To refer to particular variables that correspond to a particular chunk of memory in C++ (and in any other programming language) we have to use identifiers (variable names). The variable names in C++ are case sensitive as they are in C, must begin with a letter or an underscore (_), and should not be a reserved keyword. You should use reasonable variable names that provide some meaning to the reader of your code.

Using the above keywords we can declare the data type of a variable giving to the compiler information about the necessary amount of memory required to store (i.e. the memory that is required to be allocated and reserved for) the variable and which is machine dependent, e.g.:

• int i, j ;
• double x,y,z;
• long int k;
• unsigned short int i;

The const type modifier (or qualifier) defines a variable as a symbolic constant and does not allow any change of its value. Therefore, a const variable must be initialized when defined, since any attempt to change its value results in a compile-time error.

       const int i=10;

Note the different meaning of the following declarations:

       const int *p: Pointer to a constant integer
       int *const p: Constant pointer to an integer
       const int *const p: Constant pointer to a constant integer

8. Variable Declarations and Definitions

Before using any variable we have to declare it, i.e. inform the C++ compiler what is the data type of the variable. Every variable has a certain data type that determines the storage requirements and the operations that can be performed on it. In C++, as in C, we can combine several separate variable declarations into one declaration, as long as each variable is of the same data type, e.g.:

           <data_type1>  <variable1_name>;
           <data_type2>  <variable2_name> = <initial_value>,  <variable3_name>;< /EM >

int a, b, c;
double x,y ;
float z ;

The above declarations are also definitions. A declaration simply informs the compiler that the variable exists, its data type and that it is defined somewhere else in the program. C++ allows to have many declarations of the same variable as long as they are consistent. The definition of a variable defines the variable’s name, its data type and may also initialize the variable. Defining a variable informs the compiler about the variable's data type so as to reserve the proper amount of memory to store values for that variable. The difference is that the definition reserves memory for the variable. Therefore, there must be only one definition of a variable in a program. A declaration is also a definition if it also sets aside memory at compile time.

For example, the following statement is a declaration because it informs the compiler that an external global variable will be used, but no memory is allocated for that variable. The memory is allocated at the definition of the variable.
        extern int x_limit ;                         // declaration

We can also initialize a variables in its definition, assigning an initial value and this is called initialization. When a value is assigned to an already defined variable this is called assignment :
      int a, b, c;                          // definitions
      double x = 3.4, y(4.);< /EM >        // definitions and  initializations
      float  z = 9.9;< /EM >                    // definition and initialization
      c = 10; < /EM >                            // assignment

9. Operators

You will often need to use operators which perform a specified action on their operands. Most operators are binary, i.e. they have two operands, e.g. a+b. The operators in C++ are the same as the ones used in C.

These are:

•  the arithmetic operators of C++ are the +, -, *, / and %
•  the assignment operator is the =
•  the shorthand (abbreviated) assignment operators: += ,  -= , *= and /=
•  the (unary) postfix and prefix increment/decrement operators ++ and --
•  the relational operators are: > , < , >= , and <=  (used to compare two expressions)
•  the equality operators are: == and !=   (used to check two expressions for equality)
•  the logical operators are the: && , || , and !

An assignment expression has the value that is assigned to the variable on the LHS, and, therefore, several variables can be assigned the same value in one statement,

e.g.:    x = y = z = 100;

The RHS of logical operators is executed only if its necessary for the decision that must be taken. e.g. if the LHS of a ‘logical and’ (&&) is false, there is no reason to examine its RHS.

In addition, in C++ it is allowed to create new definitions for operators applied to user defined data types.

  main()
    {
        Point x,y,z;
        ........
       z = x + y ;
   }

10. Expressions and Statements

Each C++ program must contain a function named main(), as in C. The execution of a C++ program begins from the first statement of main and finishes when the last statement of main is executed (e.g. when the last curly brace of main is reached).

An action in C++ is referred as an expression, while an expression terminated by a semicolon is called a statement. More than one statements enclosed in a pair of curly braces is called a compound statement.

Precedence and associativity: The sequence (order) with which individual components of an expression in C++ are executed is based as in C on the order of precedence. When the operators have the same precedence the associativity defines the order of execution. A table with the precedence and associativity of the C++ operators is provided. Similar tables you can find in any C++ textbook.

e.g.         a  =  b   +=    5    +      3      /      2     -     5     +     17    /     2    /     3
(order):     (8)      (7)        (4)           (1)          (5)         (6)          (2)       (3)

The following table provides the precedence and associativity of the C++ operators with the highest precedence being the operator :: having precedence level equal to 1.