memset( ) function in C++

Today I learnt that I always misinterpreted the working of memset( ) in C++.
I generally use memset( ) to set integer arrays as either 0 or infinity (some very large integer), but sometimes I need to set it to other values as well.

Consider an array :
int a[100];

My understanding was that calling memset(a,127,sizeof(a)); would set all elements in the array as 127.

However, this is not how memset( ) works.

memset( ) writes byte-wise on the memory.
Calling memset(a,127,sizeof(a)) sets every byte, in every integer, as 127.

So, the actual value that will be assigned to each integer in the array a[ ] would be a much larger integer value.

From cplusplus.com :

void * memset ( void * ptr, int value, size_t num );

Sets the first num bytes of the block of memory pointed by ptr to the specified value (interpreted as an unsigned char).

Efficient Doubly Linked Lists

Every node in a Doubly Linked List consists of two pointers - one pointing towards the next node and another pointing towards the previous node.

 ...  A       B         C         D         E  ...
          –>  next –>  next  –>  next  –>
          <–  prev <–  prev  <–  prev  <–

We can reduce the memory of this list by using an XOR Linked List, represented as follows:

 ...  A        B         C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

As you can see in the figure above, every node stores the XOR of the address of its previous node and the address of its next node, i.e.

link(B) =  address(A) ⊕ address(C)

To traverse the list, we need to XOR the current link with the address of the previous node (explained below)

 i.e.  addr(D) = link(C) ⊕ addr(B)
    where
          link(C) = addr(B)⊕addr(D)
     so  
          addr(D) = addr(B)⊕addr(D) ⊕ addr(B)           
      
          addr(D) = addr(B)⊕addr(B) ⊕ addr(D) 
    since 
           X⊕X = 0                 
           => addr(D) = 0 ⊕ addr(D)
    since
           X⊕0 = x
           => addr(D) = addr(D)
    The XOR operation cancels addr(B) appearing twice in the equation and all we are left with is the addr(D).

Note:

This method might create some problems in deletion of nodes or in certain other operations, and the code might become slightly difficult to understand, initially.

The method is elegant, nonetheless.

( Source: Wikipedia! :) )

Conversion of a fraction to its lowest form

Doing this is really simple.
Consider a fraction represented as (numerator) / (denominator). To reduce it to its lowest form, divide both - numerator and denominator - by the GCD (Greatest Common Divisor) of the numerator and the denominator.

To find the GCD, Euclid's algorithm works really fast.

Here's the pseudo-code to find the GCD:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod t
       a := t
    return a

A non-intuitive example of independent random variables

Consider the variables x,y and z which are related as follows:

->      z = x (XOR) y

Are 'x' and 'z' dependent or independent ?

                                                                (  x and y can take the values [0,1]

 XOR stands for the eXclusive-OR operator.  )

For all possible ordered pairs (x,y), we get a corresponding z.

  x   y       z
( 0 , 0 ) -> 0
( 0 , 1 ) -> 1
( 1 , 0 ) -> 1
( 1 , 1 ) -> 0                     ... (A)

We obtain a certain value of z according to the values of x and y.
So, it might seem intuitive that x and z, or y and z, are DEPENDENT, i.e., z changes when either x or y change.

Now, consider the ordered pairs (x,z).
We have,
(0,0) , (0,1) , (1,1) and (1,0)                  ... (from A)

These are all the possible ordered pairs of (x,z) just like (x,y), and each of them occurs with equal probability.

This means that just like all ordered pairs (x,y), which were independent, all the ordered pairs (x,z) are also independent , and not dependent, unlike what intuition suggests.

Note : The word 'independent' might be deceptive, as such, but what we are looking at here is the Mathematical meaning of it and its usage in proofs et al.

Reincarnation

    It all began in 2007 when I started learning Java in 9th Grade. I had no prior knowledge of programming and I did not know what to expect. However, I was really curious to know what programming was used for and what I could do using Java.

    The next two years passed in a flash. By mid-2009, I had learnt the basics of Java and made a little project - a Billing System for a Vehicle Rental Agency. I was obsessed with programming. My friend +Anirban and I used to sit together in our Computer Lab, competing as to who would finish the day's assignment first. Those were the most enjoyable couple of hours in the whole day and that phase is the most memorable one in my life. I absolutely loved it.

    I did not write code a single time between then and 2012.

In December 2012, I got to know about Google Code Jam from my friend Aaryaman ( +adyaman ) (ironically nicknamed Jam). I immediately asked +Aditya Sarode (my first friend in Engineering College) if he would be interested to join in. +Aditya had learnt C++ in school and was logically very sound. He agreed, and we started solving some problems at Codechef, a couple of days before Code Jam. I had lost touch with Java but I was slowly catching up, so I was optimistic about making it past the Qualifying Round, at least. Meanwhile, +Aditya taught me File Handling in C++ and we discussed the differences between C++ and Java.

    Then came Google Code Jam. I woke up at 5 a.m. to read the problems and start solving as soon as possible.

There was an easy problem on Palindromes [ Fair and Square: https://code.google.com/codejam/contest/2270488/dashboard#s=p2 ] whose Small Input I solved quickly. There were 2 large inputs in that Question (instead of the usual 1 large input), which looked required some analysis. +Aditya solved Tic-Tac-Toe-Tomek (both small and large) and we had crossed the Qualification threshold. All this was done by 6pm. 

[ Some extra info: We had a Chemistry Exam that day in which I flunked and had to write 4 assignments to cover up. ]

+Anirban had been solving too and he helped us with 1 of the large inputs of Fair and Square. Later in the night, we solved Lawnmower, which was rather easy, but required some thought.

At the end of the Qualification Round, all 3 of us had more than 35 points and had qualified for Round 1.

    Google Code Jam was the event that gave a new birth to programming in my life. That day onward, I started learning various data structures and algorithms, and also started learning Python, C++ ( since C++ is one of the most popular languages in Competitive Programming and Python is now widely used for a variety of applications).

That's how the journey began.