Finding all palindromes in a string (BTW Half Century)

#include
#include
#include
#include

void substring(char *stng, int from, int to){
char sstr[to-from+2];
for(int i=0; i<=(to-from+1); i++){ sstr[i] = stng[i+from]; } sstr[to-from+1] = '\0'; printf("%s\n", sstr); } void palin(char *string){ int len; len = strlen(string); for(int i=1; i=0;j--,k++){
if(string[j] == string[k]){
substring(string, j, k);
}
else
break;
}
}

for(int i=0; i=0; j--,k++){
if(string[j] == string[k]){
substring(string,j ,k);
}
else
break;
}
}
}
}

int main(){
char str[] = "ABRARBABACDDCABABRARBA";
//printf("Length = %d\n", strlen(str));
palin(str);

getch();
return 0;
}

Algorithm: to find the median of two sorted arrays

1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
4) Repeat the above process until size of both the subarrays
becomes 2.
5) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Example:

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}
For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

[15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:

m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become

[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
Implementation:

?
#include

int max(int, int); /* to get maximum of two integers */
int min(int, int); /* to get minimum of two integeres */
int median(int [], int); /* to get median of a single array */

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int m1; /* For median of ar1 */
int m2; /* For median of ar2 */

/* return -1 for invalid input */
if(n <= 0) return -1; if(n == 1) return (ar1[0] + ar2[0])/2; if (n == 2) return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2; m1 = median(ar1, n); /* get the median of the first array */ m2 = median(ar2, n); /* get the median of the second array */ /* If medians are equal then return either m1 or m2 */ if(m1 == m2) return m1; /* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */ if (m1 < m2) return getMedian(ar1 + n/2, ar2, n - n/2); /* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
return getMedian(ar2 + n/2, ar1, n - n/2);
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

/* Utility functions */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x > y? y : x;
}

/* Function to get median of a single array */
int median(int arr[], int n)
{
if(n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}
Time Complexity: O(logn)
Algorithmic Paradigm: Divide and Conquer

some some

The extern in a function's declaration is sometimes used to indicate that the function's
definition is in some other source file, but there is no difference between
extern int function_name();
and
int function_name();

Inline functions are similar to macros because they both are expanded at compile time, but the macros are expanded by the preprocessor, while inline functions are parsed by the compiler. There are several important differences:
Inline functions follow all the protocols of type safety enforced on normal functions.
Inline functions are specified using the same syntax as any other function except that they include the inline keyword in the function declaration.
Expressions passed as arguments to inline functions are evaluated once. In some cases, expressions passed as arguments to macros can be evaluated more than once.

run this code:

#include
/*
int foo(int a);
int foo2(int a, int b);
*/
int main(int a)
{
int (*fp)(int a);
a = foo();
a = foo2(1);
exit(0);
}
int foo(int a)
{
return(a);
}
int foo2(int a, int b)
{
return(a+b);
}

run this again by removing /* and */. Understand the difference.

Whats short-circuiting in C expressions?
What this means is that the right hand side of the expression is not evaluated if the left
hand side determines the outcome. That is if the left hand side is true for || or false for
&&, the right hand side is not evaluated.

i = i++ /// invalid

• auto - local variables.
• static - variables are defined in a nonvolatile region of memory such that they
retain their contents though out the program's execution.
• register - asks the compiler to devote a processor register to this variable in order
to speed the program's execution. The compiler may not comply and the variable
looses it contents and identity when the function it which it is defined terminates.
• extern - tells the compiler that the variable is defined in another module.

How can I convert numbers to strings (the opposite of atoi)?
Use sprintf()
Note!, since sprintf() is also a variable argument function, it fails badly if passed with
wrong arguments or if some of the arguments are missed causing segmentation faults.


http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

Brilliant example on dynamic programming

http://www.careercup.com/question?id=2445

Imagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;

white = 0 black = 1
1. construct a row and a col matrix to record the # of consecutive "1" from current node to left, and up, respectively.
e.g.:
Original (A):
11111
11101
10111
01011
row:
12345
12301
10123
01012
col:
11111
22202
30313
01024

int maxsize = 0;
for i=0; ifor j=0; j    if (A[i,j]==1){
	for (int k=min(i,j); k>maxsize; k--){ //min(i,j) is the maximum possible square size from i,j to 0,0 
	   if ((row[i,j] - row[i,j-k] == k) && 
	   (row[i-k,j] - row[i-k,j-k] == k) && 
	   (col[i,j] - col[i-k,j] == k) &&	
	   (col[i-k,j] - col[i-k,j-k] == k) &&
	   )
	   maxsize=k;
	   break;
	}
    }
}

some basics again

In Java, Objects are passed by reference, and primitives are passed by value.

This is half incorrect. Everyone can easily agree that primitives are passed by value; there's no such thing in Java as a pointer/reference to a primitive.

However, Objects are not passed by reference. A correct statement would be Object references are passed by value.

This may seem like splitting hairs, bit it is far from it. There is a world of difference in meaning. The following examples should help make the distinction.

refer : httx://javadude.com/articles/passbyvalue.htm

When the method or constructor is invoked , the values of the actual argument expressions initialize newly created parameter variables, each of the declared Type, before execution of the body of the method or constructor. The Identifier that appears in the DeclaratorId may be used as a simple name in the body of the method or constructor to refer to the formal parameter.

Given an class with Synchronized method A and B, a normal method C, there are 2 threads, one instance, can these two threads call A at the same time? call A and B at the same time? A & C at the same time?

A and B cannot be called together because they are locking on the same object(this). A and C can be called together.

In Java, static means that it's a variable/method of class, it belongs to the whool class but not to one of its certain objects.

It means that static keyword can be used only int a 'class scope' i.e. it doesn't have any sence inside methods. The variables you declare in an instance method are not instance variables -- they are local variables, whose scope is limited to the method that declares them. They are not attached to the object. Likewise, in a static method, the variables you declare are local variables, too.

Observer Design Pattern: Observer registers with subjects and any update on subject will be updated to the Observers

see http://www.youtube.com/watch?v=jsFhBvIeHrk&feature=autoplay&list=ULxlJTutQggvY&index=19&playnext=2

hashCode

public int hashCode()
Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Returns:
a hash code value for this object

protected  void

finalize()           Called by the garbage collector on an object when garbage collection determines that there are no more references to the object.

Ref: http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode()

Exceptions

We can actually use if else blocks to check exceptions. But it becomes too messy and unreadable. So we use try catch blocks. When an exception occurs an object of the corresponding exception class is instantiated. So, if not handled, will result in the program to crash. So, we catch that exception in the catch block.

A try can have many catches but only a finally block. Finally block always execute. And when u r catching a class and its child class exceptions, child class should be written in catch block before the parent.

Help me. Some thing is wrong with my quick sort. Help is appreciated

#include
#include

int* quicksort(int a[],int start,int end)
{
int i = start;
int j = end;
int pivot = rand()%(end-start+1);
if(a[start]
start++;
if(a[end]>a[pivot])
end--;
printf("num to swap %d and %d\n",a[start],a[end]);
if(start
{
int temp = a[start];
a[end]=a[start];
a[start] = temp;
quicksort(a,i,(i+j)/2);
quicksort(a,((i+j)/2)+1,j);
printf("array is %d\n",a[0]);
}
else
return a;
}

int main()
{
int A[5] = {34,564,78,9,2};
int *B = quicksort(A,0,4);
printf("%d\n",*(B+1));
return 0;
}