I think i cant give a complete list of all programming techniques,
because i dont know them at all =D. But Here is a list, hope its
helps:
** Dinamic Programming (read knapsack problem, coins problems, min-
max, ...), and for other cases like the C problem, i recommend you try
to find a recursive expression for the problem, i think it easier, but
obviously is slower than an iterative one. By example, consider the C
problem as follows: i is the position of the current element in the
pattern "welcome to code jam" and j is the position of the current
element in the text, and the recursive function is "solutions related
to find the i-th character of pattern in the text, starting at j-th
character"
f(i, j) = {
Recursive:
if (pattern[i]==text[j]) { //If the character i of
pattern and the character j of text are equal you go for the next
character of pattern and the next character of text
sol[i][j]=sol[i][j]+f(i+1, j+1);
}
sol[i][j]=sol[i][j]+f(i, j+1); //go for the same
character of pattern and the next of text
,
Base:
if (i==length of pattern) { //The pattern was
recognized succesfully
return 1;
}
if (j==length of text) { //You reached the end of the
text and the pattern wasnt found
return 0;
}
}
This is a simple bactracking, exploring "all" the solutions, but there
is "something special" here ;), possibly you are calculating f more
than once. Example: the known pattern and the text: "wwelcome to code
jam", find 'w' in the first position then you have to find 'e' or f(2,
2), text[1]!=pattern[1], then find f(2, 3), ..., or you can find w in
the second position and then find f(2, 3). The function at values 2
and 3 is calculating more than once, but nothing change: you are
searching for the same solutions in both cases, the solutions related
to i and j values. Then simply, dont calculate again =D, use
memoization: use an additional array, and intialize it, put all their
values at -1 (why this value?, because the problem hasn't negative
solutions, then if the current 'dp' array element is -1, you have not
calculated that case, otherwise, you're calculating more than once the
same value). Now the function can be rewritten as follows:
dp[i][j]=-1 for all i<length of pattern and j<length of text
f(i, j) = {
if (we are in a recursive case then if dp[i][j]!=-1) { //
The solution has been calculated before
return dp[i][j];
}
else { //Calculate it
dp[i][j]=0;
//Go for the next conditionals
}
Recursive:
if (pattern[i]==text[j]) { //If the character i of
pattern and the character j of text are equal you go for the next
character of pattern and the next character of text
sol[i][j]=sol[i][j]+f(i+1, j+1);
}
sol[i][j]=sol[i][j]+f(i, j+1); //go for the same
character of pattern and the next of text
,
Base:
if (i==length of pattern) { //The pattern was
recognized succesfully
return 1;
}
if (j==length of text) { //You reached the end of the
text and the pattern wasnt found
return 0;
}
}
I continue with the list:
** String searching (kmp, boyer-moore, rabin karp, ...)
** Computational geometry (convex hull, line intersection, closest
pair, ...)
** Graph theory (conectivity, searching in a graph: dfs, bfs, minimum
cost path: dijkstra, bellman, ford, minimum spanning trees: prim,
kruskal, network flow: maximum flow, maximum bipartite matching,
minimum set cover. Traveling shoemaker problem, ...)
** Hashing
** Some Maths (tau, sigma, phi functions, numeric methods, primality
test, sieving, modular arithmetic, combinatorics, probability, number
theory, gcd, lcm...)
** Trees (binary trees, balanced binary trees, binary indexed trees,
segment/ interval trees, binomial heap, fibonacci heap, suffix
trees, ...)
** Sorting (quicksort, mergesort, heapsort, radix sort, counting
sort), generally std sort is enough for problems ;)
** Searching (binary search, linear search, hashing)
** Grids
** Other data structures
** And many other problems
** And, of course, practice, practice and practice =D
As you seen, there are several programming techniques, explain each of
them will take a lot of time, you can read one algorithm or theme, by
week, and then practice enough with the knowledge acquired, and then
go for another one. Maybe some people here, would like to complete
this list o add 'elements' =D.
On Sep 6, 4:02 pm, vicky <[email protected]> wrote:
> hats off to u all .for me , can somebody give a "comprehensive" list
> of all different currently known techniques of programming . also if
> possible plz explain me about, from where to prepare questions
> particular to each technique(branch and bound especially).
>
> On Sep 6, 3:03 am, sameer mhatre <[email protected]> wrote:
>
> > Your solution is same as mine. Only difference is that I am traversing test
> > string backward and using hash map to improve running time.
>
> > You can improve the running time of your code by avoiding inner loop which
> > traverse 0 to 18. We can keep each distinct characters of target string
> > "welcome to code jam" in the hash map as a key and value for the key will be
> > the array holding respective positions in the target string.
>
> > So while traversing outer loop for test string you just need to check
> > whether the character is available in the hash map. If it is not then no
> > need to traverse inner loop. But if the character exist then just need to
> > traverse it's respective positions (retrieve array values corresponding to
> > that key) only.
>
> > You can check my solution user "sam6230i". My solution is in JAVA.
>
> > On Fri, Sep 4, 2009 at 1:44 PM, smloh <[email protected]> wrote:
>
> > > I'm going to try to provide an intuitive explanation of the logic I
> > > used for Problem C, in the hope it may help some fellow programmers.
>
> > > First the code, in old-fashioned C:
> > > #include <stdio.h>
> > > #include <stdlib.h>
> > > #include <string.h>
> > > int main(int argc,char *argv[])
> > > {
> > > char *wstr="welcome to code jam";
> > > FILE * pFile, *pOut;
> > > char buffer [600];
> > > int mults[19];
> > > int numCases;
> > > pFile = fopen ("c-large.in" , "r");
> > > pOut= fopen("c-large.out","w");
> > > if (pFile == NULL) perror ("Error opening file");
> > > else
> > > {
> > > fscanf(pFile, "%d\n", &numCases);
> > > for (int num=0;num<numCases;num++)
> > > {
> > > fgets(buffer, 600, pFile);
> > > for (int i=0;i<19;i++) mults[i]=0;
> > > fprintf(pOut,"Case #%d: ",num+1);
> > > int len=strlen(buffer);
> > > for (int i=0;i<len;i++){
> > > for (int j=0;j<19;j++){
> > > if (j==0) {
> > > if (buffer[i]==wstr[j]) mults[j]++;
> > > }else if (mults[j-1]>0){
> > > if (buffer[i]==wstr[j])
> > > mults[j]=(mults[j]+mults[j-1])%10000;
> > > }
> > > }
> > > }
> > > if (mults[18]<1000) fprintf(pOut,"0");
> > > if (mults[18]<100) fprintf(pOut,"0");
> > > if (mults[18]<10) fprintf(pOut,"0");
> > > fprintf(pOut,"%d\n",mults[18]);
> > > }
> > > fclose (pFile);
> > > }
> > > return 0;
> > > }
>
> > > Explanation:
> > > Let's call the string we are testing the "test string", and "welcome
> > > to code jam" the "target string".
>
> > > For each test case, the outer loop of this algorithm iterates over the
> > > test string, which is stored in buffer[]. The inner loop iterates
> > > over the target string, which is stored in wstr[].
>
> > > As we go over the test string, we keep track of a number mults[j] for
> > > each character in the target string.
> > > This is defined as:
>
> > > mults[j] = the number of ways to build the target string up to the jth
> > > character, using the characters in the test string we have evaluated
> > > so far
> > > * to correlate to the code, "jth character" counts from 0
>
> > > Intuitively, we can describe mults[j] as the number of ways to "get
> > > to" the jth character in "welcome to code jam" that we have found so
> > > far.
>
> > > When j==0, each time we encounter a character match ("buffer[i]==wstr
> > > [j]"), we increment mults[0] by 1, since we have 1 more potential
> > > first character for our target string.
>
> > > When j>0, each time we encounter a match, we increment mults[j] by
> > > mults[j-1].
>
> > > This is because there are mults[j-1] ways so far to form the target
> > > string up (j-1)th character. Each of these ways, when combined with
> > > the character in we are currently evaluating, gives us a new way to
> > > form the target string up to the jth character.
>
> > > We also mod(%) the calculations by 10000, since only the values less
> > > than 10000 at each step affect the last 4 digits of our final result.
>
> > > When we are done iterating over the entire test string, mults[18]
> > > will, by definition, be the number of ways to build the entire target
> > > string, using the characters in the entire test string.- Hide quoted text
> > > -
>
> > - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
