lcus_optimized
This is our working repository as we research ways to speed up the LCuS algorith, using strategies from Kosowski's 2004 paper. Our naive implementation can be found at https://github.com/robynburger/LCuS_Naive
Science Score: 44.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
○DOI references
-
○Academic publication links
-
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (9.2%) to scientific vocabulary
Repository
This is our working repository as we research ways to speed up the LCuS algorith, using strategies from Kosowski's 2004 paper. Our naive implementation can be found at https://github.com/robynburger/LCuS_Naive
Basic Info
- Host: GitHub
- Owner: robynburger
- Language: Python
- Default Branch: main
- Size: 49.8 KB
Statistics
- Stars: 1
- Watchers: 2
- Forks: 1
- Open Issues: 0
- Releases: 0
Metadata Files
README.md
Description of LCuS
LCuS.py is an optimized O(n^4) approach to solving the longest cubic subsequence (LCuS) problem.
For a string of characters, LCuS.py identifies the longest subsequence repeated three distinct times. It returns the optimal breakpoints to seperate the string into three consecutive substrings, each containing an interation of the subsequence.
For more information, see paper (* citation)
Requirements
- Install python 3.12 or higher <!-- 2. Use Conda or other similar environment to run NumPy package: (https://www.numpy.org) -->
Running LCuS
LCuS is still experimental and is not yet functional. As such, you cannot run
it yet.
<!-- Clone the repository:
$ git clone https://github.com/robynburger/LCS_naieve
Run LCuS.py:
$ python LCuS.py
Enter command line arguments: ``` Enter string:
Use ideal parameters? (Yes/No):
If user types 'Yes:
Your file was saved: results/s/ideal.txt
If user types 'No':
Enter positive integers j, l, m:
Note: 1 <= i < j <= k < l <= m <= {len(s)}.
j:
l:
m:
Your file was saved: results/s/jlm.txt ``` -->
Authors and Acknowledgements
Written by Robyn Burger and Allison Shi under the mentorship of Dr. Brendan Mumey and Dr. Adiesha Liyanage.
Funded by the National Science Foundation (NSF) as part of research conducted at Montana State University for the summer 2024 Algorithms REU.
Adapated from longest tandem subsequence problem:
Kosowski, Adrian., An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem, Lecture Notes in Computer Science, volume 3246 (2004) 93-100.
Owner
- Login: robynburger
- Kind: user
- Repositories: 1
- Profile: https://github.com/robynburger
Citation (CITATION.cff)
cff-version: 1.2.0 message: "If you use this software, please cite it as below." authors: - family-names: "Burger" given-names: "Robyn" - family-names: "Shi" given-names: "Allison" title: "Longest Cubic Subsequence Problem" version: 2.0.4 url: "https://github.com/robynburger/LCS_optimized"