/COMP305-CountingBeautifulStrings

COMP 305: Algorithms and Complexity Final Project

Primary LanguagePythonMIT LicenseMIT

Counting Beautiful Strings

COMP 305: Algorithms and Complexity Final Project

Team Members

  • Hasan Can Aslan
  • Arda Bakır
  • Atilla Özbek
  • Erdem Özkur

TA: Amir Mohamad Akhlaghi Gharelar

Planning

Tasks

  • 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

Meeting Schedule

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

Project

Installing

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

Our Approach

Divide problem into 2 phases:

  • Find substrings (Divide & Conquer)
  • For each substring check beautifulness (KMP)

Results

  • TODO

Complexity Analysis

  • Find substrings: O(2^n)
  • For each substring check beautifulness: O(n)