c

Dive deep into Kadane’s algorithm​

I am writing this post as I could not find any reliable material that could clearly explain the intuition behind Kadane’s algorithm.

To start, here’s a (very) crisp explanation of Kadane’s algorithm from Wikipedia.

Kadane’s algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position i (call this B_i), what is the maximum subarray sum ending at position i+1 (equivalently, what is B_{i+1})? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position i+1 includes the maximum subarray sum ending at position i as a prefix, or it doesn’t (equivalently B_{i+1}=max(A_{i+1}, A_{i+1} + B_i), where A_{i+1} is the element at index i+1

Unfortunately, when you see this explanation, it is hard to convince yourself why the algorithm works, but once I prove it to you,​ then it’ll seem trivial. Here is my attempt to make this explanation more easy to digest.

Continue reading “Dive deep into Kadane’s algorithm​” →

Advertisement

Replacing characters in a file (C)

The lesser known topic when it comes to C is FILE I/O. Even I’ve learnt a great deal in the past few days than what I’d learnt during my C classes. Today I sat down to solve the problem I’ve been facing on how to replace characters of a file in C. I searched through ‘stack-overflow’, dream in code and googled for about a half an hour without avail, but in the end the faithful GNU GCC Reference Manual helped me. It is related to my steganography project, where I try to replace the last bit of a byte and hide information using that. Let’s get down to business.

Please note that I’m talking in the context of replacing characters in a file. For example, say you want to replace all the ‘a’ characters with ‘b’.

These are the key points that led to my downfall: (even though I wiggled my way out of it!)
  • Opening a file for I/O – You need to open a file with “r+” if you are dealing with ASCII files and “rb+” if you are dealing with Binary files. The most common mistake one does when opening a file to read/write is that we forget and open the file using the “r” mode.
  • File pointer moves forward after every read or write. I had totally missed this point even though I knew it. I wasted about fifteen minutes on this!
  • Between a fgetc() and a fputc() call you need to call fflush() so that the changes you have made to take effect (in short it will transfer the buffer content to the file).

So with these things covered I’ll write an example which will help you understand the problem and the solution.

#include <stdio.h>

void read_file(FILE *fp)
{
    char c;
    fseek(fp,0,SEEK_SET)
    while(1)
    {
        c = (char) getc(fp);
        if(c == EOF)
            break;
        else
            printf("%c",c);
    }
    printf("\n\n");
}

void replace(FILE *fp, char find_c, char replace_c)
{
    char c;
    fseek(fp,0,SEEK_SET);
    while(1)
    {
        c = (char) getc(fp);
        if(c == EOF)
            break;
        else if(c == find_c)
        {
            printf("*");
            if(fseek(fp,-1,SEEK_CUR) != 0)
            {
                printf("Function: replace() :: Error: fseek() not working.\n");
                return -1;
            }
            if(fputc((int)replace_c,fp) == EOF)
            {
                printf("Function: replace() :: Error: fputc() not working.\n");
                return -1;
            }
            if(fflush(fp) == EOF)
            {
                printf("Function: replace() :: Error: fflush() not working.\n");
            }
        }
    }
    printf("\n\n");
}

int main()
{
    char find_c = 'l';
    char replace_c = 'm';
    FILE *fp;  

    printf("Before Replacement:\n");
    fp = fopen("message.txt","r");
    if(fp == NULL)
    {
        printf("Function: main() :: Error: fopen() not working for \"r\" mode.\n");
        return -1;
    }
    read_file(fp);
    fclose(fp);

    printf("During Replacement:\n");
    fp = fopen("message.txt","r+");
    if(fp == NULL)
    {
        printf("Function: main() :: Error: fopen() not working for \"r+\" mode.\n");
        return -1;
    }
    replace(fp,find_c,replace_c);
    fclose(fp);

    printf("After Replacement:\n");
    fp = fopen("message.txt","r");
    if(fp == NULL)
    {
        printf("Function: main() :: Error: fopen() not working for \"r\" mode.\n");
        return -1;
    }
    read_file(fp);
    fclose(fp);
    return 0;
}

One more thing I want to tell you is to have a copy of GCC Reference Manual with you, it really helps you a lot!