Skip to content

Latest commit

 

History

History
84 lines (64 loc) · 7.41 KB

README.md

File metadata and controls

84 lines (64 loc) · 7.41 KB
Raw

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