Skip to content

README.md

Latest commit

 

History

History
61 lines (42 loc) · 3.47 KB

README.md

File metadata and controls

61 lines (42 loc) · 3.47 KB

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