Data Structures and Algorithms (Python)

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

Contents

Folders	Corresponding Directories ^1	^2
Chapter 1	Abstract Data Types	Python Primer
Chapter 2	Arrays	Object-Oriented Programming
Chapter 3	Sets and Maps	Algorithm Analysis
Chapter 4	Algorithm Analysis	Recursion
Chapter 5	Searching and Sorting	Array-Based Sequences
Chapter 6	Linked Structures	Stacks, Queues, and Deques
Chapter 7	Stacks	Linked Lists
Chapter 8	Queues	Trees
Chapter 9	Advanced Linked Lists	Priority Queues
Chapter 10	Recursion	Maps, Hash Tables, and Skip Lists
Chapter 11	Hash Tables	Search Trees
Chapter 12	Advanced Sorting	Sorting and Selection
Chapter 13	Binary Trees	Text Processing
Chapter 14	Search Trees	Graph Algorithms
Chapter 15		Memory Management and B-Trees

Getting Started

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

Release Notes

• 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.

Contributing

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

License

This project is licensed under the GNU GPL v3 License.

Acknowledgments

• Hat tip to anyone whose code was used

References

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