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):

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:

Compiling and running stuff on the Lab PCs:


Lab-1


Lab-2


Lab-3

  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


Lab-6



Homeworks

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


HW-1


HW-2


HW-3

Problem-1

Problem-2

** 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


HW-6