Programming meets Mathematics

One of the most discussed examples in Computer Science classes is the palindrome. Wikipedia defines palindrome as a word, phrase, number, or other sequence of units that can be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers.

According to one article, palindromes were discovered as early as the 79AD where the latin phrase “Sator Arepo Tenet Opera Rotas” was found as a graffito at Herculaneum. However, it was found out that palindromes of considerable complexity were explored in the ancient Sanskrit poetry.

Palindromes are usually discussed in computer science classes because it poses a rather easy problem for students to tinker with. The most common example of a problem involving palindromes is checking whether a given string is a palindrome or not. Here are 3 different ways to check if a string is a palindrome(NOTE: The methods posted assumes that the string be a one-word string and does not include punctuation and word dividers.)

Code #1

public boolean isPalindrome(String word){

    boolean isPal = true;

    for(int i=0; i<Math.floor(word.length()/2); i++){

        if(word.charAt(i) != word.charAt(word.length()-1-i)){

            isPal = false;

            break;

        }

    }

    return isPal;

}

Explanation:

The method loops until the middle of the string and compares the character found at the value of i and compares it to the character with the same index if the string is reversed. If all characters are equal, then the string is said to be a palindrome

Code #2

public boolean isPalindrome(String word){

    boolean isPal = true;

    String rev = “”;

    for(int i=0; i<word.length(); i++){

        rev = word.charAt(word.length()-1-i) + “”;

    }

    if(!word.equals(rev))

        isPal = false;

    return isPal;

}

Explanation:

The method reverses the string and stores it in another variable. The method then compare the original string and the reversed string. If the two string are equal, then the string is said to be a palindrome.

Code #3

public boolean isPalindrome(String word){

    boolean isPal = true;

    Stack<Character> stack = new Stack<Character>();

    for(int i=0; i<Math.floor(word.length()/2); i++)

        stack.push(word.charAt(i));

    for(int i=Math.ceiling(word.length()/2); i<word.length(); i++){

        if(word.charAt(i) stack.pop()){

            isPal = false;

            break;

        }

    }

    return isPal;

}

Explanation:

The method uses a stack, a Last In First Out data structure, and stores all the characters until the middle of the string. The method then pop each character from the stack and compare it to the character corresponding to it on the 2nd half of the string.

DISCLAIMER: I didn’t test if the Java codes are working. It may cause some syntax errors but the algorithm will definitely work.

jafetsanchez:

“If you want to be a good programmer, you just program every day for two years.

If you want to be a world class programmer, you just program every day for 10 years, or take the “Analysis of Algorithms” class and program for two years.”

By Prof. Erik Demaine at M.I.T.

ramiismail:

Best code comments ever encountered

// 
// Dear maintainer:
// 
// Once you are done trying to 'optimize' this routine,
// and have realized what a terrible mistake that was,
// please increment the following counter as a warning
// to the next guy:
// 
// total_hours_wasted_here = 39
// 

LOL. This is funny. :))

hellolixian:

• Mathematical Induction

We can easily verify this for n = 1, so we make the inductive assumption that it holds for n and prove that it holds for n + 1.

• Bounding the Terms

          A good upper bound on a series by bounding each term of the series, and it often suffices to use the largest term to bound the others.

• Splitting Summations

          Express the series as the sum of two or more series by partitioning the range of the index and then to bound each of the resulting series.  Generally, this technique applies when each term in a summation is independent of n.

• Approximation by Integrals

joethought:

Skipping past relevant theory into a programming dive means we need to define data structures needed to define a graph.

They consist of: 

1. Adjacency matrix - an NxN boolean matrix; A[i][j] =1 if an edge between i and j
2. Adjacency list - An array of linked list nodes, one for each node. Each array element will depict a vertex node of the graph. However, this node will also be a linked list head element. The linked list will comprise of one element per adjacent node of the vertex we’ve been talking about.

Both have obvious advantages and disadvantages. But I am picking up lists because I like pointers. :-)

Other things needed to depict a graph and make life simple.

A degree table - A degree of a vertex is how many outgoing edges exists for it. A degree table can be an array of MAX_VERTICES, one per vertex, the value being an integer which shows its degree.

integers for nvertices, nedges - for number of vertices and edges in the graph, respectively.

#define MAX_VERTICES 20


//adjacency list - node structure
typedef struct {
    int y;
    int weight;
    struct edgenode *next;
} edgenode;

//graph structure
typedef struct {
    edgnode *edges[MAX_VERTICES];
    int degree [MAX_VERTICES];
    int nvertices;
    int nedges;

} graph;

Good read

I am bored today and I’m thinking of writing bash scripts. Any ideas of what to do?

Submit any programming problem and/or solutions and we’ll try to analyze them. We’ll look for areas on how we can solve the problem or improve the solution. Also, I’m thinking of featuring one simple programming project per week that appear to be useful for a lot of people. I’ll be doing a lot of research for this.

Cheers everyone! :D