Course Webpage

Lab Location: 210 WVH

Notes on the labs (Lab0, Lab1, Lab2, Lab3, Lab4, Lab5, Lab6, Lab7, Lab8, Lab9, Lab10, Lab11)

You can find notes, help etc. on the homeworks below (HW1, HW2, HW3, HW4, HW5, HW6)

Lab-0

Some text-editors which can be used (this is by no means an exhaustive list, only some of the ones I know; you are free to use whatever you are comfortable with):

• Notepad++ (Download): will work with MS Windows
• Vim (Download): will work with Linux, Windows, Mac
• Emacs: works with Linux, Windows (through Cygwin), Mac
• Eclipse (Download): technically, its an Interactive Development Environment (IDE), which is more than just a text-editor. It works on Linux, Windows, Mac. You need to install the CDT plugin, if you download the base Eclipse OR download this directly.
• Textpad (Download): works with Windows

Here is another great resource: codepad.org. You can compile, run and share your code online, in a number of languages.

Setting up GCC/G++ compiler on your machine:

• Fedora
  • Execute g++ on the Terminal, if it's not present, you should see a "Command Not Found" error message.
  • Install g++ using the following command on the Terminal: yum install gcc-c++
• Ubuntu
  • Execute g++ on the Terminal, if it's not present, you should see a "Command Not Found" error message.
  • Install g++ using the following command on the Terminal: sudo apt-get install g++
• MS Windows
  • There is a free IDE for C/C++, Dev-C++, which can be downloaded from here. Its semantics are similar to GCC.
  • Install Cygwin, following the instructions here
• Mac
  • Download and install Xcode from here.

Compiling and running stuff on the Lab PCs:

• You'll need to login using your myNEU IDs, since you don't have the CCIS accounts. Use NUNET\your_myneu_id for the ID
• The Dev-C++ installed on the machines is NOT working because the no-mingw version has been installed (which means that it doesn't have the compiler built-in)
• We can use the "MinGW Shell" which can be found under Start>All Programs>Shells>MinGW. You can create your programs separately and compile them with g++.
• Create the source file in your favourite text editor and place it in c:\MinGW\msys\1.0\home\<your_myneu_id>\
• Compile your file from the MinGW shell using the following command: g++ file_name.cpp -o output
• Run your program using the following command: ./output

Lab-1

• Don't forget to send the file Lab1_firstname_lastname.cpp to cs1500hw@gmail.com
• For calculating the monthly payment, include the adjusted annual property tax and insurance costs

Lab-2

• Use loop iteration to find the GCD
• Reference

Lab-3

• Refer to Bézout's Identity and the Extended Euclidean Algorithm

1. Values of arguments are local to that function call frame and are NOT preserved across function calls (the function might be called from within itself). Whatever values you pass in to the function are COPIED into the argument variables. The only invariant is what is done to the values -- which means that the same instruction/code/logic is executed but for a different set of values. For example: If you have a function like foo(int a, int b) and you call this function twice from somewhere,
   foo(2,3); // 'a' gets the value 2, 'b' gets the value 3
   foo(4,5); // 'a' gets the value 4, 'b' gets the value 5
2. It is required that the function be implemented recursively using the Euclid's Algorithm
3. There are some fundamental premises on which the Euclid's Algorithm is based.
   1. Any two integers, 'a' and 'b', can be written as: a=bq+r, such that q=⌊(a/b)⌋, r=(a mod b) and 0 < r ≤ b
   2. GCD(a,b) = GCD(b,r) [NOTE that both the parameters (b, r) are smaller than the corresponding previous two parameters (a, b) ]
   3. GCD(a, b) = b, if (a mod b) = 0
4. So, taking all the points of #2 under consideration, it can bee seen that if you recursively call GCD(a, b) for smaller numbers, eventually you'll reach a stage when (a mod b) becomes 0 and then the GCD of the current value of parameters (which is equal to the GCD of the original two numbers acc. to rule #3.2) will be the "current" value of 'b' (rule #3.3).
5. Finding the GCD(a,b) using this algorithm is part-1 of the problem. The other thing that needs to be calculated is the two numbers 'm' and 'n', such that GCD(a,b) = ma + nb (There is an identity which says that you can always find two such integers.) The calculation for 'm' and 'n' can be clubbed in together into the same function that you write for GCD(a,b).
6. As is mentioned in the SLIDES, m_(a,b) = n_(b,r) and n_(a,b) = m_(b,r) - q*n_(b,r). You can also see why this is true from the explanation given on the Wikipedia link for Extended Euclidean Algorithm.
   1. For the base case when 'a' is a multiple of 'b', it is easy to see that m=0 and n=1 (rule #3.3).
7. If the function GCD (b,r) was somehow able to return three values to its caller, the caller would be able to calculate it's own set of 'm' and 'n' based on the rules specified in #6. So, my pseudo code might look something like:
   GCD(a, b)
{
    q := ⌊a/b⌋
    r := a mod b
    if r=0, then
        return m as 0, n as 1 and gcd as b
    else
        Extract the values of m', n' and gcd from GCD(b,r)
        // Calculate the new values of m and n from the ones returned above
        m := n'
        n := m' - q*n'
        return m, n and gcd
    endif
}

8. In C++, functions can return only ONE object/value. So, in order to make it return more than one value, you can use some workarounds like, returning an array or packing the three values into one object (may be in a struct OR single integer value and do some simple algebra as suggested on the Lab3 webpage).

Lab-5

• This is a pretty straight-forward implementation of Quicksort. Note that the kernel of the program is the partition function. If partition works correctly, the rest of the code will work fine.

Lab-6

• The aim is twofold: a) given a sequence of 0s and 1s, find the equivalent integer and floating-point number and, b) give an integer or a floating-point number, find the sequence of 0s and 1s that make the number
• Some rules of Boolean algebra that will help you in this lab:
      x & 1 = x
      x & 0 = 0
      x | 1 = 1
      x | 0 = x
  where, & and | are the Boolean AND and OR operations.
• For part (a) of the problem, if you could write out the bit-sequence in the memory of the variable, reading out the variable later will give you number directly
• For part (b), read the bits from the memory of the variable and store them in an array of characters (containing '0' and '1') or integers (containing 0 and 1)

Homeworks

Send in the pseudocode and source code for your homework to cs1500hw@gmail.com

HW-1

• Solving a linear system of equations: IIT-M: Mathematics-2, Linear System of Equations
• General test cases: Unique solution, Parallel Lines, Overlapping lines, Lines parallel to the axes
• Sample test cases: 2x - y = -1, 5x - 3y = 6 (Unique solution); x + y/2 = 3, 10x + 5y = 7 (Parallel Lines); x + y/3 = 4, 3x + y = 12 (Overlapping lines); 5x = 4, x - 6y = 12 (Lines parallel to the axes)

HW-2

• Gradient Descent - Reference

HW-3

Problem-1

• For calculating the determinant of a square matrix, you could use the Cofactors/Minors formula (reference).
• Sample approach:
      Submatrix(Matrix, Size, r, c)
    {
        N := Create new 2D matrix of (Size-1)x(Size-1)
        Copy the values from Matrix into N except for those in rth row and cth column
        return N
    }

    Determinant(Matrix, Size)
    {
        if Size = 2, then
            return determinant of 2x2 Matrix
        else
            i := 0, d := 0
            for j=0 to Size, do
                tempMatrix := SubMatrix(Matrix, Size, i, j)
                minor := Determinant(tempMatrix, Size-1)
                delete tempMatrix
                cofactor := (-1)i+j * minor
                d := d + cofactor
            endfor
            return d
        endif
    }

• In order to dynamically create 2D arrays, you will need to use the C++ "new" operator
• The way to return 2D arrays from a function is by using "double" pointers (written as **). Refer to this

Problem-2

• You are supposed to use vectors ("vector" is a built-in datatype of the STL** in C++) instead of arrays for problem-2. In that case, you will not have to worry about dynamic allocation of memory for storage since it handles all of that automatically (unlike in C, where you'd have to create a linked list manually).
• Vectors are like arrays but with the added advantage of not having to worry about dynamic memory allocation or pre-defining the size of the vector at compile time. So, you can declare a vector of whatever datatype you want, and keep adding/deleting objects of that datatype to/from that vector. Example:
     My_Data_Type an_object;
   My_Data_Type another_object;
   vector list_of_objects; // notice that you didn't specify the size
   list_of_objects.insert(an_object);
   list_of_objects[1] = another_object;

• Refer to this for more examples and usage
• I would suggest a vector of struct objects. The struct could contain a string and a count. This way you'd be able to get a fast look-up for a word and it's frequency. My algorithm might look something like:
     0. Create a vector of mystructs.
   1. Keep reading the file while it is not the end
      2. Create a temporary mystruct object
      3. Put the word in the string member of the temporary object created in #2
      4. Calculate the hash of the word
      5. If there's already an object at the index (=hash) position of the vector, then
         5.1. Increase the frequency count
   6. Otherwise, add the object at the index
   7. End of loop

** STL is the Standard Template Library. It is NOT a part of the C++ programming language standard, per se. This is an extra library, which some people made _using_ the C++ programming language standards, to avoid having to write some of the common tasks, manually, each time. Having said that, it is a perfect example of how some things become so popular/widespread that people think that they were always/is a part of the original standard. And just FYI, printf(), cout, cin are also not part of the C/C++ standards; these are also part of the extra "Standard" C/C++ libraries.

You can imagine how having to write out each and every line for even a small task can get tedious with C/C++ -- especially when you get stuck with low level primitive operations that these languages support.

You can refer to "The C Programming Language" (by Kernighan and Ritchie) and "The C++ Programming Language" (by Stroustrup) to know about what's part of the language and what are the extra libraries (these guys are the creators of the respective languages).

HW-5

• For reading through the data, there can be many approaches. I'll just put down two of them:
  1. Pre-process the input file and replace all the commas with spaces and then read-in the numbers normally.
  2. 
     for each line, L, in the file, do
  pos := 0 // Start from the beginning of the line
  while pos < length(L), do
    buff := read_till_next_comma(pos, L) // Returns a string starting from the 'pos' position till the next comma in L
    M[i][j] := atoi(buff) // Convert the buff to number and save it.
    pos := pos + length(buff) // Increase the position
  done
done


HW-6

• Sample test code:
    mstring x;
  x.copy ("abcdefghijklmn",0, 10);
  mstring y("cs1500");
  x.append(" "); x.append (y);
  mstring z = x.substr(8, 13);
  ...
  cout << z;