A list of algorithms for Competitive Programming

Solving problems on SPOJ, I realised I used to forget the algorithms which I had previously used. For this fallacy of mine I am listing the algorithms and the corresponding SPOJ problems. There may be better resources on net similar to this but this is my effort. You can also find solutions to these problems on my github page http://www.github.com/kanirudh/SPOJ/

1. Sorting:
     Using the library function for sorting usually does the trick. You need to know how to define a comparator function for sorting user-defined structure arrays.
   
     http://www.spoj.com/problems/DOTAA/

2. String Algorithms
 
     Patten Matching
     a) KMP Algorithm
     http://www.spoj.com/problems/NHAY/
     b) Rabin Karp 

3. Dynamic Programming Algorithms
   
     a) 0/1 Knapsack
     http://www.spoj.com/problems/LKS/
   
     b) Longest Increasing Subsequence
     http://www.spoj.com/problems/XMEN/

     c) Longest Common Subsequence
     http://www.spoj.com/problems/LCS/
     http://www.spoj.com/problems/TRIP/

4. Divide And Conquer
     a) Closest Pair of Points
     http://www.spoj.com/problems/CLOPPAIR/

     b) Binary Search
     http://www.spoj.com/problems/PIE/
     http://www.spoj.com/problems/EKO/
     http://www.spoj.com/problems/OPCPIZZA/
 

5. Graph Algorithms
    ( DFS, BFS, Djisktra, Floyd-Warshall, Bellman-Ford, kruskal)
    http://www.spoj.com/problems/PARADOX/

6. Maths
    Gaussian Elimination
    http://www.spoj.com/problems/XMAX/






 

HTKBook Tutorial and Solutions

While re-creating the chapter 3 of the HTK I encountered the following problems and the solutions to the those problems when I found them

1. The 'gram' file copy the text shown the book into a file 'gram.txt' and run the following command
HParse gram.txt wdnet

2. HSlab does not work showing the following error " MakeXGraf: Not compiled with X11 support" 

Step1. Open htk/HTKLib/htik_htklib_nt.mkf

          Change HGraf.null.obj -> HGraf_WIN32.obj
          Change HGraf.null.olv -> HGraf_WIN32.olv
          Run "nmake /f htk_htklib_nt.mkf all" under HTKLib directary
Step2. Open htk/HTKTools/Makefile.in
           Delete -lXll (lower case of "L")
           Run "nmake /f htk_htktools_nt.mkf all" under HTKTools directory

Found a awesome site which lists all the common error noticed when using HTK. Here is the link for your benefit: HTK Problems and Solutions

Note: The tutorial given in the HTKBook it misses one thing which training dataset. It suggests using TIMIT Database for training. But TIMIT is not free.

I decided to skip a step and search for pre-trained models available online. First I found this one
http://www.keithv.com/software/htk/us/
But then again this did not work as given, many errors occured in the pronounciation dictonary.

Next I found this one http://www.repository.voxforge1.org/downloads/Nightly_Builds/ which has a nicely trained hmm models along with the respective dictionary which is very helpful. Now note you cannot run the live recogniser with these models because they use the following feature extraction scheme which is "MFCC_0_D_N_Z" , but you can sucessfully use the HVite decoding example given in the tutorial. The accuracy for decoding module is very low using these models since they use features described above but which is only possile using HCompV used for training.

I couldn't find a way to emulate the features using HCopy

The next database I tries was the part of TIMIT database available freely( thanks to MIT) , the link is following MIT TIMIT Corpora . The problem with this I am facing is that the pronounciation dictionary is and label files are not matching and some phoneme are not there.

Hacking my way through HTK, I was told that TIMIT label format needs to be modified quite a bit for use with HTK.

Incase of any queries you can contact me.