University of Cincinnati Logo
 

20-CS-122 - Computer Science II
Electrical Engineering and Computer Science

FAQ

Why can't I run the Java code posted on your web page?
Whoops, Strings strings[count]; is not ANSI standard C++!?
Your solution to HW1 does not match the assignment, what's the deal?
What does clock() do?
Can you remind me, which are the important unix commands?
Just what is the this pointer?
Can the Min Cost Network problem be solved by removing largest cables first?
What is this "main (int argc, char **argv)" anyway?
Can we eliminate an argument by using a static variable?
Does trading an if for a virtual call save time?
 
   Why can't I run the Java code posted on your web page?
The reason might be because you need to grant permission to the applet to do so. In this case create a java policy file with the following content:
     grant {
        permission java.security.AllPermission;
     };
Name it .java.policy in unix (I do not know what to call it in Windows) and put it in your home directory (I do not know what is considered a home directory in Windows).
   Whoops, Strings strings[count]; is not ANSI standard C++!?
Use
    Strings *strings = new Strings[count];
instead. Do you have any idea what the following does?
    Strings **strings = new Strings*[count];
I thought so. But this is really what we should be worried about in this example.
   Your solution to HW1 does not match the assignment, what's the deal?
Do you really need the exact solution? If so check readfile1.cc.
   What does clock() do?
When you do this
    clock_t time_1 = clock();
you create a variable called time_1 of type clock_t with a value that is returned by the function clock(). That value is the number of milliseconds that have elapsed since January 1, 1970. If you do the following
    ...
    clock_t time_1 = clock();
    // your code goes here
    clock_t time_2 = clock();
    cout << (time_2 - time_1) << "\n";
    ...
you will output the number of milliseconds it took your code to execute.
   Can you remind me, which are the important unix commands?
The following assumes you have installed KDE.

    open a terminal     Menu->System->terminal (or something similar)
    ls     Show the contents of the current directory
    cd     Change the current directory to be your home directory
    cd blah     Change directory to blah - only works if blah exists as a subdirectory in current directory
    kate     A nice text editor - watch-for/choose-which directory files are saved in!
    rm blah     Remove (delete) a file named blah from current directory
    make blah     Compile a C++ file named blah.cc. The result is the executable blah in the current directory.
    mv blah blam     Rename file blah in the current directory to blam

A common question is why do I always need to do ./blah to run blah instead of just blah? The reason is probably because you have not set your PATH variable in .bash_profile. Another problem is attempting to run an existing command but getting a message saying the command does not exist. Such messages are common when trying to run unix commands that are in directory /sbin or /usr/sbin. These problems can be fixed by editing the PATH variable in .bash_profile as follows:

    export PATH=".:/sbin:/usr/sbin:$PATH"
   Just what is the this pointer?
This question arises because students attempt to answer it by looking at the documentation of Visual Studio. Unfortunately, the VStudio description of the this pointer is poor. Before describing the this pointer recall that the creation of many different objects of a class is possible (actually encouraged), but all objects of the same class have access to the same methods. Suppose an object invokes one of its methods but the method requires using the object that invoked it for some reason (such as returning the object or handing the object off to another method or function). How is the method going to be written to do something like this if the same method must apply to any object of the class? The answer is it should be written to make use of the this pointer. The this pointer in a class method is not hidden any more than cout is hidden. It is not a parameter any more than cout is a paramter. Nor is it invisible. The this pointer, when accessed within a method, is merely a pointer to the object that is invoking the method. This is alternatively called a self-reference. The following is a code snippet illustrating what is said above.
    #include <iostream>
    using namespace std;

    class B;

    class A {
       public:
       int encode(B*);
    };

    class B {
       friend ostream &operator<<(ostream&, B*);
       friend class A;
       int number;
     public:
       B (int);
       void mash (A*);
    };

    A::encode(B *b) {  return b→number - 1; }

    B::B (int n) { number = n; }
    void B::mash (A *a) { number = a→encode(this); }

    ostream&operator<<(ostream&out, B*b) {
       out << b→number;
       return out;
    }

    int main() {
       B *b = new B(10);
       b→mash(new A());
       cout << b << "\n";
    }
In the above code, class A objects are intended to provide some service to class B objects through the method encode which takes a B object as argument. A class B object can be encoded by invoking method mash of class B. The mash method takes an A object as argument (actually a pointer to an A object) and applies that object's encode method to the B object requesting the service (that is, the one from which the mash method was invoked). The encode method of class A knows which B object requested the service because this was passed to encode during execution of mash. The following does the same thing without the this pointer
    #include <iostream>
    using namespace std;

    class B;

    class A {
     public:
       int encode(B*);
    };

    class B {
       friend ostream &operator<<(ostream&, B*);
       friend class A;
       int number;
     public:
       B (int);
       void putNumber(int);
     };

     int A::encode(B *b) {  return b→number - 1; }

     B::B (int n) { number = n; }
     void B::putNumber (int n) { number = n; }

     ostream&operator<<(ostream&out, B*b) {
        out << b→number;
        return out;
     }

     int main() {
        B *b = new B(10);
        b→putNumber((new A())→encode(b));
        cout << b << "\n";
     }
This is NOT considered a good solution because data in class B is forced to become more publicly available and we want to keep data as private as possible. When putNumber is added to class B anyone then suddenly has the ability to change the number in objects of class B!!! Why bother with object oriented programming, then? Don't do it.

 
   Can the Min Cost Network problem be solved by removing largest cables first?

Answer: Yes

Method:

input: A collection of cable costs between pairs of cities
output: A network of cables of minimum cost

    1. Order the cables by decreasing cost.
    2. Let N represent the network of cables to be
       output and make it empty.
       Let P represent the original network of cables.
    3. Repeat the following until all the cables are
       considered.
    3a.   Choose the next cable c in the ordered list.
    3b.   Check whether removing c from P results
          in P becoming disconnected.
    3c.   If P remains connected, remove c from
          P and continue the loop.
    3d.   Otherwise, include c in N.
    4. Return N.
   What is this "main (int argc, char **argv)" anyway?
Answer: In
  int main (int argc, char **argv) {
     ...
  }
the variable argc holds the number of strings on the command line, including the command itself. For example, the value of argc in "command 1 2 3" is 4. The variable argv is an array of strings, each element of which points to a command line string token, starting with the command itself. For example, given command line "find eat food.bananas", argv[0] is "find", argv[1] is "eat", and argv[2] is "food.bananas".

To transform one of the argv strings to a number use atoi, atoi, or atof. For example:

   int main (int argc, char **argv) {
      ...
      char command[128];
      strcpy (command,argv[0]);
      int x = atoi(argv[1]);
      long y = atol(argv[2]);
      double z = atof(argv[3]); 
      ...
   }
in which case "find 1 200000 3.4" results in
command same as "find"
x with value 1
y with value 200000
z with value 3.4
   Can we eliminate an argument by using a static variable?
The following code is a tail recursive solution to the problem of finding the factorial of a positive integer. The factorial function in this example uses two arguments including acc which holds the accumulated intermediate value of the solution. By using a static variable, as in the second section of code below, the accumulator can be eliminated. The neatness of the result may be debated.
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
	 
    typedef unsigned long ulong;

    ulong factorial (int n, ulong acc) {
       if (n <= 0) return acc;
       return factorial (n-1, acc*n);
    }

    int main (int argc, char **argv) {
       if (argc != 2) {
          cout << "Usage: " << argv[0] << 
                        " <positive-integer>\n";
          exit (0);
       }
       int n = atoi(argv[1]);
       cout << n << "! = " << 
            factorial(n, 1) << "\n";
    }
This section of code uses a static variable to eliminate the need for the acc argument.
    #include <stdlib.h>
    #include <iostream>
    using namespace std;

    typedef unsigned long ulong;

    ulong factorial (int n) {
       static ulong acc = 1;
       if (n <= 0) return acc;
       acc *= n;
       return factorial (n-1);
    }

    int main (int argc, char **argv) {
       if (argc != 2) {
          cout << "Usage: " << argv[0] << 
                        " <positive-integer>\n";
          exit (0);
       }
       int n = atoi(argv[1]);
       cout << n << "! = " << 
            factorial(n) << "\n";
    }

Here is a similar result for Fibonacci code. The first section has two accumulators and the second two static variables.

    #include <stdlib.h>
    #include <iostream>
    using namespace std;

    typedef unsigned long ulong;

    ulong fib (int n, ulong x, ulong y) {
       if (n <= 1) return x;
       return fib(n-1, x+y, x);
    }

    int main (int argc, char **argv) {
       if (argc != 2) {
          cout << "Usage: " << argv[0] << 
                        " <positive-integer>\n";
          exit (0);
       }
       int n = atoi(argv[1]);
       cout << "fib(" << n << ") = " << 
                      fib(n, 1, 1) << "\n";
    }

Here is the section using the static variables.

    #include <stdlib.h>
    #include <iostream>
    using namespace std;

    typedef unsigned long ulong;

    ulong fib (int n) {
       static ulong x = 1, y = 1;
       if (n <= 1) return x;
       ulong t = x;
       x += y;
       y = t;
       return fib(n-1);
    }

    int main (int argc, char **argv) {
       if (argc != 2) {
          cout << "Usage: " << argv[0] << 
                        " <positive-integer>\n";
          exit (0);
       }
       int n = atoi(argv[1]);
       cout << "fib(" << n << ") = " << 
            fib(n) << "\n";
    }
   Does trading an "if" for a virtual call save time?
This question arose one year when looking at spiffy "if-less" code for the topological sort problem. We compare running times for two pieces of code. Here is the first piece (uses an "if"):
    class A {
       bool a;
     public:
       A () { a = true; }
       void f () { if (a) return; }
    };

    int main () {
       A a;
       for (long i=0 ; i < 1000000000 ; i++) a.f();
    }
Here is the second (uses virtual call):
    class A {
     public:
       virtual void f () { }
    };

    class B : public A {
       bool a;
     public:
       B () { a = true; }
    };

    int main () {
       B b;
       for (long i=0 ; i < 1000000000 ; i++) 
          ((A)b).f();
    }
Results:
Compiled without optimization (g++ file.c -o file):
     First       Second
     ------      ------
     31 sec      61 sec
Compiled with optimization (g++ -O3 file.c -o file):
     First       Second
     ------      ------
     4.442s      4.444s
Using a 450MHz Intel PIII. Conclusion: No apparent penalty for the virtual functions with -O3.
ERC
MainStreet
Paul Erdos
NIT
Ladies on Campus
Oscar Robinson