## Resources for Code Optimization

2,426 total views, 10 views today

GATE CSE Resources

2,426 total views, 10 views today

Write a program which can do sum of large numbers having up to 1000 digits

Sum of Large Numbers in C

C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <stdio.h> #include <string.h> #include <ctype.h> void print(char *a, int l); int read(char *a); int sum(char *a, char* b, char * c, int al, int bl); int main(void) { char a[1000], b[1000], c[1000]; //a and b hold the input numbers and c hold the output number. Each array entry is a digit int al, bl; //for storing the number of digits of the two input numbers printf("Enter the first number "); al = read(a); printf("Enter the second number "); bl = read(b); int l = sum(a, b, c, al, bl); printf("sum = "); print(c, l); return 0; } int sum(char *a, char* b, char * c, int al, int bl) { int l = al > bl? al:bl;//l stores the no.of digit of output which may become l+1 due to carry from MSB int i = l; char carry = 0; while(al > 0 && bl > 0) { char val = a[--al] + b[--bl] + carry; c[i--] = val % 10; carry = val / 10; } while(al > 0)//If a has more digits than b { char val = a[--al] + carry; c[i--] = val % 10; carry = val / 10; } while(bl > 0)//If b has more digits than a { char val = b[--bl] + carry; c[i--] = val % 10; carry = val / 10; } c[0] = carry;//Assigning the final carry return l+1;//Return the no. of digits of output } int read(char *a) { char c; int i = 0; do { c = getchar(); } while(isspace(c)); //Reading and discarding any whitespace char typed while(isdigit(c)) { a[i++] = c - 48; //getchar returns the ASCII. So, for 1 it returns 49. Subtracting 48, we get the actual int value entered via keyboard c = getchar(); } return i;//Return the no. of digits read } void print(char *a, int l) { int i; if(a[0] != 0) printf("%d", a[0]);//If final carry is 0, ignore it for(i = 1; i < l; i++) { printf("%d", a[i]); } printf("\n"); } |

602 total views, 1 views today

The basis of this is that your ID must be in the list of authorized hosts in the server. So, for password-less login to work, generate your public key, and append it to the authorized_hosts file in the server.

To create a public key, from terminal do

1 |
ssh-keygen -t rsa |

To copy to authorized_hosts file do

1 |
cat ~/.ssh/id_rsa.pub | ssh serveruser@server 'cat &gt;&gt; ~/.ssh/authorized_keys' |

Test by

1 |
ssh serveruser@server |

If no password is asked, everything worked fine.

You can also do the following command to copy the key

1 |
ssh-copy-id serveruser@server |

1,644 total views, 3 views today

- http://sixrevisions.com/resources/10-puzzle-websites-to-sharpen-your-programming-skills/
- http://www.coderholic.com/10-more-puzzle-websites-to-sharpen-your-programming-skills/
- http://comeoncodeon.wordpress.com/page/2/
- http://tausiq.wordpress.com/
- http://www.iarcs.org.in/inoi/contests/allproblems.php
- http://www.careercup.com/
- https://www.interviewstreet.com/challenges/
- https://www.facebook.com/ProgrammingInterviews
- http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html
- http://www.cse.iitd.ernet.in/~sbaswana/Puzzles/Algo/algo.html
- http://www.comp.nus.edu.sg/~stevenha/programming/vol1.html
- http://www1.cs.columbia.edu/~kns10/interview/
- http://concentratedlemonjuice.blogspot.com/2008/05/puzzles_4358.html

2,438 total views, 1 views today

- $P$ is a subset of $NP$, but whether $P = NP$ is still not known
- $NPC$ is a subset of $NP$ (only if $P \neq NP$, $NPC$ is a proper subset of $NP$)
- $NPC$ is a proper subset of $NPH$

Reducing a problem $A$ to problem $B$ means converting an instance of problem $A$ to an instance of problem $B$. Then, if we know the solution of problem $B$, we can solve problem $A$ by using it.

You want to go from Bangalore to Delhi and you can get a ticket from Mumbai to Delhi. So, you ask your friend for a lift from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi.

Consider problems $A$, $B$ and $C$.

Assume all reductions are done in polynomial time.

- If $A$ is reduced to $B$ and $B$ $\in$ class $X$, then $A$ cannot be harder than $X$, because we can always do a reduction from $A$ to $B$ and solve $B$ instead of directly solving $A$. This reduction thus gives an upper bound for the complexity of $A$.
- If $A$ is reduced to $B$ and $A$ $\in$ class $X$, then $B$ cannot be easier than $X$. The argument is exactly same as for the one above. This reduction is used to show if a problem belongs to $NPH$ – just reduce some known $NPH$ problem to the given problem. This reduction thus gives a lower bound for the complexity of $B$.

- If $A$ is reduced to $B$ and $B$ $\in$ $NPC$, then $A$ $\in$ $NP$
- Here, we cannot say $A$ is $NPC$. All we can say is $A$ cannot be harder than $NPC$ and hence $NP$ (all $NPC$ problems are in $NP$). To belong to $NPC$, all $NP$ problems must be reducible to $A$, which we cannot guarantee from the given statement.

- If $A$ is reduced to $B$, $C$ is reduced to $A$ , $B \in NP $ and $C \in$ $NPC$, then $A$ $\in$ $NPC$
- Here, the first reduction says that $A$ is in $NP$. The second reduction says that all $NP$ problems can be reduced to $A$ (because $C$ is in $NPC$, by definition of $NPC$, all problems in $NP$ are reducible to $C$ and now $C$ is reduced to $A$). Hence, the two necessary and sufficient conditions for $NPC$ are satisfied and $A$ is in $NPC$

- If $A$ is reduced to $B$ and $B$ $\in$ $NPH$, then $A$ $\in$ $?$
- Here we can’t say anything about $A$. It can be as hard as $NPH$, or as simple as $P$.

1,559 total views, 7 views today

%d bloggers like this: