Computational Aspects of Generating Catalan Numbers

Bachelor Thesis Nikola Horníková

Supervisor

doc. RNDr. Tatiana Jajcayová, PhD.


Anotation

Catalan Numbers appear in various contexts in Computer science. The nthCatalan number is given directly in terms of binomial coefficients, and the recursive definition given by a non-linear recurrence relation is also known.One of the mathematical objects to which the Catalan numbers are related areso called Hankel matrices, and those, in turn, are used with Hidden Markov models


Goal

The goal of the theses is to study this connection between the Catalan numbers and Hidden Markov models. Possible means to achieve this is to connect various different combinatorial problems in Informatics in which Catalan Numbers appear, employ some knowledge of statistics and probability, understandHidden Markov models and design good tests and algorithms. This requires to use “intelligent" approach to programming as the sequence of Catalan Numbers grows very fast.


Main Chapters


Time schedule

31.10. 2019 : Web page

12.11. 2019 : Time schedule

26.11. 2019 : Resources and presentation

12.1. 2020 : Prototype

13.1.2020 - 9.4.2020 : Additional research and implementation

10.4. 2020 : Finishing research

10.5. 2020 : Writing chapters: Introduction, Conclusion

20.5. 2020 : Final touches

22.5. 2020 : Thesis done

22.5. 2020 : Application done

15.6. 2020 : Finishing presentation

x.6. 2020 Presenting

Resources

Type Title Author(s)
Bachelor Thesis Bounded Locally Testable Matrices Marian Opial
Book Fibonacci and catalan numbers : an introduction Ralph P. Grimaldi
Book Discrete and combinatorial mathematics Ralph P. Grimaldi
Book Introduction to Algorithms, Third Edition Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Book Applied Combinatorics Alan Tucker
Article History of catalan numbers Igor Pak
Article The catalan numbers Tanja Stojadinovic
Article Catalan numbers Tom Davis
Article Hankel transforms of linear combinations of catalan numbers Michael Dougherty, Christopher French, Benjamin Saderholm, Wenyang Qian
Article Catalan numbers,the hankel transform and fibonacci numbers Aleksandar Cvetkovic, Predrag Rajkovic, and Milos Ivkovic
Article Enumeration of certain young tableaux with bounded height Desainte-Catherine M. and X. G. Viennot
Article A determinant property of catalan numbers M. E. Mays and J. Wojciechowski
Article Some aspects of hankel matrices in coding theory and combinatorics Ulrich Tamm
Book Markov Chains and Stochastic Stability S. P. Meyn and R. L. Tweedie
Book An introduction to Markov Chains Ander Stolver
Book Markov processes: Theory and examples Jan Swart and Anita Winter
Book Speech and Language Processing Daniel Jurafsky and James H. Martin
Article A Revealing Introduction to Hidden Markov Models Mark Stamp
Article Learning Hidden Markov Models using Non-Negative Matrix Factorization George Cybenko and Valentino Crespi
Article Synthesis of hidden Markov models and processes with finite-rank Hankel matrices M. Vidyasagar
Article The Complete Realization Problem for Hidden Markov Models
M. Vidyasagar
Documentation Rust documentation https://doc.rust-lang.org/1.3.0/ [23.11.2019]
Book The Rust Programming Language Steve Klabnik and Carol Nichols


Final Version


Theory

Check it out HERE!

Application

You can run it here (except for the last one):


Presentation

Presentation can be viewed HERE!