A repository for practicing DS/Algo in Python, based on Rance D. Necaise^{^1} and Michael T. Goodrich et al.^{^2}

After cloning the repository, you may run the programs using PyCharm or an IDE/editor of your choice.

• Python 3.6 is used up until commit 36f2d11. Subsequent commits use Python 3.10 (or higher) features.

• Commit 4466df5 uses __future__.annotations^{^3} to set recursive type-hinting (requires Python 3.7 or higher).

• progression.py uses the @override decorator^{^4} to emphasize polymorphism.

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

This project is licensed under the GNU GPL v3 License.

• Hat tip to anyone whose code was used

1. Necaise, R. D. (2011). Data Structures and Algorithms using Python. Hoboken, NJ, USA: Wiley.

2. Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2013). Data Structures and Algorithms in Python. (B. L. Golub, Ed.) Hoboken, NJ, USA: Wiley.

3. __future__ Statement Definitions. Retreived from the Official Python Documentation: https://docs.python.org/3.11/library/__future__.html

4. Korpela, M. (6 August 2023). overrides. Retrieved from PyPI: https://pypi.org/project/overrides/

5. Stroud, K. A., & Booth, D. J. (2020). Engineering Mathematics (8th ed.). London, UK: Red Globe Press (Macmillian).

6. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). Massachusetts, USA: MIT Press.

7. Lutz, M. (2013). Learning Python (5th ed.). Sebastopol, CA, USA: O'Reilly Media, Inc.

8. Levitin, A. (2012). Introduction To The Design & Analysis of Algorithms (3rd ed.). Essex, UK: Pearson Education.

9. Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press.

10. Tustumi, W. H. A., Gog, S., Telles, G. P., & Louza, F. A. (2016). An improved algorithm for the all-pairs suffixprefix problem. Journal of Discrete Algorithms, 37(C), 34–43.

11. Kim, D.K., Kim, M. & Park, H. Linearized Suffix Tree: an Efficient Index Data Structure with the Capabilities of Suffix Trees and Suffix Arrays. Algorithmica 52, 350–377 (2008).

12. Nong, G., Zhang, S., & Chan, W. H. (2009). Linear SAIS (Suffix Array Construction by Almost Pure Induced-Sorting). 2009 Data Compression Conference (pp. 193-202). Snowbird, UT, USA: IEEE. doi:10.1109/DCC.2009.42

13. Li, Z., Li, J., & Huo, H. (2018). Optimal In-Place Suffix Sorting. Tsinghua University, IIIS. Beijing: arXiv. arXiv:1610.08305v6

14. Guruprasad, H. S. (25 June 2020). Horspool Algorithm. Retrieved from YouTube: https://www.youtube.com/watch?v=W4h6555g5qo

15. Kettani, H. (2024). Space & Time Tradeoffs: Boyer-Moore Algorithm. CSC 3323 Analysis of Algorithms. Morocco.

16. Ramesh, B. (21 April 2020). Boyer-Moore-Horspool Algorithm. Retrieved from YouTube: https://youtu.be/4Oj_ESzSNCk

17. Langmead, Ben. (2024). Suffix-based indexing data structures: learning materials. figshare. Collection. https://doi.org/10.6084/m9.figshare.c.7205547

18. Harris, E. (27 March 2020). SAIS (Suffix Array Induced Sorting) Part 1. Retrieved from YouTube: https://www.youtube.com/watch?v=yb0Os_MTU_4

19. Lu, F. (25 March 2024). Longest Repeated Substring in Linear Time DC3 + LCP. Retireved from YouTube: https://www.youtube.com/watch?v=H2vGH_6p6GU

20. Trie - Wikipedia

21. Suffix Tree - Wikipedia

22. Suffix Array - Wikipedia

23. LCP Array - Wikipedia

24. Suffix Array and LCP Generator

25. Ukkonen Visualizer

26. Applications of Suffix Array and LCPs