COMP 305: Algorithms and Complexity Final Project
- Hasan Can Aslan
- Arda Bakır
- Atilla Özbek
- Erdem Özkur
TA: Amir Mohamad Akhlaghi Gharelar
- Dynamic Programming Approach Exploration (Arda - Attila)
- Linear Programming Approach Exploration (Hasan)
- Knuth Morris Pratt Pattern Searching Algorithm Exploration (Hasan – Arda)
- Test Cases (Erdem - Attila)
- Demo Implementation (Erdem - Attila)
- Repo Updates (Hasan)
- Proof and Correctness (Erdem)
- Presentation
Date | Subject |
---|---|
May 16, 2021 | Planning |
May 20, 2021 | Brainstorming |
May 21, 2021 | Exploring different approaches |
May 25, 2021 | Discussing our exploration results |
May 26, 2021 | Try to implement results |
June 3, 2021 | Finalize implementation |
June 4, 2021 | Presentation preparation |
June 5, 2021 | Final presentation |
You can just run beautiful_strings.py. Program starts with test cases. In order to change inputs, you can modify files in the test directory.
python beautiful_strings.py
Divide problem into 2 phases:
- Find substrings (Divide & Conquer)
- For each substring check beautifulness (KMP)
- TODO
- Find substrings: O(2^n)
- For each substring check beautifulness: O(n)