Genmix: Project for Algorithms and Data Structures

1. Project Overview

Genmix is a project developed for the Algorithms and Data Structures (010123103) course. The primary goal of this project is to address the complex process of sequencing scenes in a film.

Traditionally, arranging scenes relies on time-consuming methods like Brute Force or trial and error. This project proposes using Dynamic Programming (DP) as a more efficient approach to find the optimal scene order that maximizes an "emotional score", thereby enhancing the audience's viewing experience. The project also includes a performance comparison between the DP approach and the Brute Force method, complete with visualizations for a clearer understanding.

2. Objectives

• To design an algorithm for sequencing scenes to achieve the highest possible score.
• To compare the performance of Dynamic Programming against the Brute Force method.
• To create clear visualizations of the results.

3. Core Concepts

The project is built upon the following key concepts:

• Dynamic Programming (DP): A technique that solves complex problems by breaking them down into simpler subproblems and storing their results (Memoization) to avoid redundant calculations. The problem's structure is similar to the Knapsack Problem.
• Three-Act Structure: The scene sequencing logic is based on the conventional film narrative structure, which is divided into three parts:
  • Act 1: Setup - Introduction of characters and situations.
  • Act 2: Confrontation - Rising conflict and tension.
  • Act 3: Resolution - The climax and conclusion.
• Transition Bonus: A scoring mechanism that awards extra points for effective transitions between scenes, such as moving from an exposition scene to a climax.

4. Implementation Details

Development Environment

• Language: Python
• Libraries: Matplotlib, Pydot

Features

• Timeline Visualization: Generates a timeline that visually organizes scenes into the three acts.
• DP Flowchart: A flowchart illustrating the working process of the Dynamic Programming algorithm.
• Performance Analysis: Includes a comparison table showing the runtime of DP vs. Brute Force and a graph of their Big O complexities.

5. Results and Conclusion

Strengths

• The Dynamic Programming approach proved to be significantly faster and more accurate than Brute Force.
• Visualizations effectively demonstrate the results, making them easy to interpret.

Weaknesses and Future Work

• The DP method may face memory issues as the number of states (scenes) increases.
• Further improvement can be made by incorporating Machine Learning to automate and refine the calculation of Transition Bonus scores.

Conclusion

Dynamic Programming is a highly effective method for optimizing scene sequences. It offers a faster and higher-quality result compared to traditional methods and has potential applications in industries like film, gaming, and advertising.

6. Team Members

This project was created by:

• นายนครินทร์ บุญก่อเกื้อ 6701012610198
• นายณัฐปคัลภ์ พรเฉลิมพงศ์ 6701012610058
• นายพิทักษ์ ปทุมวัน 6701012610104
• นายโภควินท์ ยิ่งกุลบวรภัค 6701012610295

Submitted to

อาจารย์ ดร. วีระ สอิ้ง

ภาคเรียนที่ 2 ปีการศึกษา 2567