Power Series Evaluation

Power series evaluation in O(lg(n)):[n is the number of terms]

We'll try to evaluate the following power series in logarithmic time w.r.t. the number of terms n.

n-1                                  xn-1 - 1
∑ xi = 1 + x + x2 + ..... + xn-1 = ———————————
i=0                                    x - 1

Well well... I may be asked, "dude, why do you want to do this in O(lg(n)) when there's already we have a O(1) solution for your problem?". Answer is simple, "I'm trying it from a programming perspective and the O(1) can get sometimes impossible when n keeps going up i.e. like 10¹⁰⁰⁰ and you are asked to return the answer w.r.t. some %m [modulus m] (meaning the final result will not reach m). This method will be suitable for this case only. Because, calculating {(x^n-1-1)/(x-1)}%m is not a very easy task and sometimes, it is not directly possible.

This series can be evaluated by binary splitting and recursively solving those building up the answer.
Let n = 6
We have, 1 + x + x² + x³ + x⁴ + x⁵
⇒ (1 + x + x²) + x³(1 + x + x²)
⇒ (1 + x + x²)(1 + x³)

So, when n is even, f(x, n) = (1 + x^n/2)f(x, n/2)

Now, what if n is odd, Let n = 7
We have, 1 + x + x² + x³ + x⁴ + x⁵ + x⁶
⇒ (1 + x + x²) + x³(1 + x + x²) + x⁶
⇒ (1 + x + x²)(1 + x³) + x⁶

So, when n is odd, f(x, n) = (1 + x^n/2)f(x, n/2) + x^n-1

So, by combining the above 2 equations, we get the final solution:
f(x, n) = (1 + x^n/2)f(x, n/2) + (n%2)x^n-1

By some clever observation, the need for -1 and %2 operation on n can be eliminated. So, the only thing we need to do is the /2 operation on n, which is easy even when n is a big integer.

Here is a python module that shows only the recursive part, no trick applied.

import math

def evaluate(x, n):
    if(n==0):
        return 0
    if(n==1):
        return 1
    ret = 0
    if(n%2==1):
        ret = ret + int(math.pow(x, n-1))
    n = n/2
    return ret + evaluate(x, n)*(1 + int(math.pow(x, n)))

If this is to be done with C/C++, some biginteger division algorithm should be implemented.

Easy, eh? Check different types of series here

Gauss–Jordan Elimination

Gauss–Jordan Elimination in C++

This is my first attempt to solve linear systems with unique solutions in O(N²).

Algorithm:
1. Read augmented matrix for the system.
2. Perform Gaussian Elimination to get the matrix in row echelon form.
3. Transform the matrix to reduced row echelon form.
4. Write results.

Preview:

[click for a clear view]

My C++ solution (change MAX to desired size, it is the maximum limit of how many equations it can handle, change the macro DEBUG to "if(1)" if you want to see the intermediate steps):

#include <iostream>
#include <cstdlib>
#include <cassert>
#include <algorithm>
using namespace std;

#define DEBUG if(0)
#define MAX 5

struct MAT {
    int R[MAX+1];
} M[MAX];

int N;

int gcd(int a, int b) {
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

bool comp(MAT A, MAT B) {
    for(int k=0; k<N; k++) {
        if(A.R[k] > B.R[k]) return true;
        if(A.R[k] < B.R[k]) return false;
    }
    return true;
}

void print(void) {
    int i, j;
    cout << "..." << endl;
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) cout << M[i].R[j] << '\t';
        cout << M[i].R[j] << endl;
    }
    cout << "..." << endl;
}

void modify(MAT &A, MAT B, int a, int b) {
    for(int r=0; r<=N; r++) A.R[r] = a*B.R[r] - b*A.R[r];
}

void eliminate(void) {
    int i, g, k;
    for(i=0; i<N-1; i++) {
        if(!M[i].R[i]) {
            sort(&M[i], M+N, comp);
            assert(M[i].R[i]);
        }
        for(k=i+1; k<N; k++) {
            g = gcd(abs(M[i].R[i]), abs(M[k].R[i]));
            modify(M[k], M[i], M[k].R[i]/g, M[i].R[i]/g);
        }
        DEBUG print();
    }
}

void reduce(void) {
    int i, g, k;
    for(i=N-1; i; i--) {
        for(k=i-1; k>=0; k--) {
            g = gcd(abs(M[i].R[i]), abs(M[k].R[i]));
            modify(M[k], M[i], M[k].R[i]/g, M[i].R[i]/g);
        }
        DEBUG print();
    }
}

void printsol(void) {
    double h, l;
    cout << "Solve for " << N << " variables:" << endl;
    for(int i=0; i<N; i++) {
        assert(M[i].R[i]);
        h = M[i].R[i];
        l = M[i].R[N];
        cout << 'x' << i+1 << " = " << l/h << endl;
    }
    cout << "..." << endl;
}

int main(void) {
    int i, j, g;
    while(cin >> N) {
        if(!N) break;
        memset(M, 0, sizeof(M));
        for(i=0; i<N; i++) {
            for(j=0; j<N; j++) cin >> M[i].R[j];
            cin >> M[i].R[j];
            for(j=g=0; j<=N; j++) g = gcd(abs(M[i].R[j]), g);
            for(j=0; j<=N; j++) M[i].R[j] /= g;
        }
        eliminate();
        reduce();
        printsol();
    }
    return 0;
}

However, I'm trying to do it in a more efficient way. I'll post that when I'm done.

CSE 102: Attacking Recursion

Some general approach for solving recursive problems:

[this article is dedicated for CSE-DU 15th batch students only]
After reading this, try this

#1: Forget about what you need to do, just think about what the last step will do, which means, when you want to stop and the relation between this step and the previous step or the next step. Then just keep calling again and again thinking that, the function I'm calling will solve the problem anyhow, which I will combine with current step to produce current result and return that.

Example: Think about computing n! recursively. I don't still know what and how my function will do this. But nothing to worry about, I know that 0! = 1! = 1. And I also know that, n! = n(n-1)!. So I will think like that, "I will get n! from this function, if some one gives me (n-1)!, then I'll multiply it with n and produce results". And, "this function" is the function for computing n!, so why don't I use again to get (n-1)! ?

int factorial(int n) {
    // I know this, so I don't want to go my functions any further...
    if(n==0) return 1;
    // don't bother what to do, just reuse the function...
    else return n*factorial(n-1);
}

#2: What ever you can do with loops, can be done with recursions as well. A simple technique for converting recursions and loops is shown below:

Forward:

for loop:

for(int i = 0; i < n; i++) {
    // do whatever needed
}

Equivalent recursion:

void FOR(int i, int n) {
    if(i==n) return; // terminates
    // do whatever needed
    FOR(i+1, n); // go to next step
}

Backward:

for loop:

for(int i = n-1; i >= 0; i -= 1) {
    // do whatever needed
}

Equivalent recursion:

void ROF(int i, int n) {
    if(i==n) return; // terminates
    ROF(i+1, n); // keep going to the last
    // do whatever needed when returning from prev steps
}

#3: Use the advantage of call stack. When you call functions recursively, it stays in the memory as the following picture demonstrates.

int f(int n) {
    if(n==0) return 1;
    return n*f(n-1);
}

You know about stack, in a stack, you cannot remove any item unless it is the topmost. So you can consider the calling of a recursive function as a stack, where, you can't remove the memory used by f(n=3) before removing f(n=2) and so so... So, you can easily see that, the functions will hold all their variables and values until it is released. This actually serves the purpose of using an array.

These techniques will be used in almost all problems when writing recursive solution.

Drawing Regular n-gon

How to draw a regular pentagon with just ruler and compass?

How about a regular hexagon?

Underlying theorem:
Primes of the form 2²ⁿ + 1 are known as Fermat primes.

A regular n-gon is constructible using straightedge (ruler) and compass if and only if n = 2ⁱ · m where m is a product of any number of distinct Fermat Prime and i is any natural number, including zero.


Only five Fermat primes are known: 3, 5, 17, 257, and 65,537.

Related study: Compass and straightedge constructions.

CSE-102 Practice Recursions

Recursions are fun

[this article is dedicated for CSE-DU 15^th batch students only]
As the exam is knocking at the door, you may like to try out some simple problems to practice recursions. Most of these were supplied by MJ mam last year, Try to solve all of them without using any global variables. If you need any solution, leave a comment with your mail ID or mail me to zobayer1[at]gmail[dot]com, I'll send the solution.

Before looking at the problems, you may like to read this post about how to attack recursive problems.

Problem 1:

You will be given an array of integers, write a recursive solution to print it in reverse order.

Input:
5
69 87 45 21 47
Output:
47 21 45 87 69

Problem 2:

Write a recursive function to print an array in the following manner.
[0] [n-1]
[1] [n-2]
.........
.........
[(n-1)/2] [n/2]

Input:
5
1 5 7 8 9
Output:
1 9
5 8
7 7

Problem 3:

Write a recursive program to remove all odd integers from an array. You must not use any extra array or print anything in the function. Just read input, call the recursive function, then print the array in main().

Input:
6
1 54 88 6 55 7
Output:
54 88 6

Problem 4:

Write a recursive solution to print the polynomial series for any input n:
1 + x + x² + ................. + x^n-1

Input:
5
Output:
1 + x + x^2 + x^3 + x^4

Problem 5:

Write a recursive solution to evaluate the previous polynomial for any given x and n.
Like, when x=2 and n=5, we have 1 + x + x² + ................. + x^n-1 = 31

Input:
2 5
Output:
31

Problem 6:

Write a recursive program to compute n!

Input:
5
Output:
120

Problem 7:

Write a recursive program to compute n^th fibonacci number. 1^st and 2^nd fibonacci numbers are 1, 1.

Input:
6
Output:
8

Problem 8:

Write a recursive program to determine whether a given integer is prime or not.

Input:
49
999983
1
Output:
not prime
prime
not prime

Problem 9:

Write a recursive function that finds the gcd of two non-negative integers.

Input:
25 8895
Output:
5

Problem 10:

Write a recursive solution to compute lcm of two integers.

Input:
23 488
Output:
11224

Problem 11:

Suppose you are given an array of integers in an arbitrary order. Write a recursive solution to find the maximum element from the array.

Input:
5
7 4 9 6 2
Output:
9

Problem 12:

Write a recursive solution to find the second maximum number from a given set of integers.

Input:
5
5 8 7 9 3
Output:
8

Problem 13:

Implement linear search recursively, i.e. given an array of integers, find a specific value from it.
Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.

Input:
5
2 9 4 7 6
2
5 9
Output:
not found
1

Problem 14:

Implement binary search recursively, i.e. given an array of sorted integers, find a query integer from it.
Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.

Input:
5
1 2 3 4 5
2
3 -5
Output:
2
not found

Problem 15:

Write a recursive solution to get the reverse of a given integer. Function must return an int

Input:
123405
Output:
504321

Problem 16:

Read a string from keyboard and print it in reversed order. You must not use any array to store the characters. Write a recursive solutions to solve this problem.

Input:
helloo
Output:
oolleh

Problem 17:

Write a recursive program that determines whether a given sentence is palindromic or not just considering the alpha-numeric characters ('a'-'z'), ('A'-'Z'), ('0'-'9').

Input:
madam, i'm adam
hulala
Output:
palindromic
not palindromic

Problem 18:

Implement strcat(), stracpy(), strcmp() and strlen() recursively.

Input:
test on your own
Output:
test on your own

Problem 19:

If you already solved the problem for finding the n^th fibonacci number, then you must have a clear vision on how the program flow works. So now, in this problem, print the values of your fibonacci function in pre-order, in-order and post-order traversal. For example, when n = 5, your program calls 3 and 4 from it, from the call of 3, your program calls 1 and 2 again....... here is the picture:

Input:
5
Output:
Inorder: 1 3 2 5 2 4 1 3 2
Preorder: 5 3 1 2 4 2 3 1 2
Postorder: 1 2 3 2 1 2 3 4 5

Problem 20:

All of you have seen the tower of Hanoi. You have 3 pillars 'a', 'b' and 'c', and you need transfer all disks from one pillar to another. Conditions are, only one disk at a time is movable, and you can never place a larger disk over a smaller one. Write a recursive solution to print the moves that simulates the task.

Input:
3
Output:
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

Good Luck!!!