The k-Partition Problem

Batakliev, Emil (author), Robič, Borut (mentor)

In this thesis we will analyze the k-Partition Problem. Specifically, we will analyze the five best algorithms for solving the Partition Problem, after which we will analyze five new algorithms for solving the k-Partition Problem. Two of these algorithms will be my contribution towards both problems. After we have understood how each algorithm works, we will test them among each other in order to figure out which algorithm is the fastest and why. We will also consider each algorithm's accuracy, since some algorithms trade their speed for precision. There will be a total of 70 test cases used throughout the testing phase. Some test cases will be random, and others specifically used as difficult test cases in regards to certain algorithms. Finally, we will shed light on the difference between theory and practice, that is, to the algorithms time complexities and their execution time. The goal of the thesis is not to find the fastest algorithm, but rather to analyze each of the algorithms and understand which of them is best suited for a given situation.

• Language: English
• Keywords: array, algorithm, time complexity, space complexity
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2023
• PID: 20.500.12556/RUL-146398
• COBISS.SI-ID: 154896899
• Publication date in RUL: 30.05.2023

Secondary language

• Language: Slovenian
• Title: Posplošeni problem razdelitve

Abstract

V magisterskem delu bomo analizirali posplošeni problem razdelitve. Analizirali bomo pet najboljših algoritmov za reševanje problema razdelitve in pet novih algoritmov za reševanje posplošenega problema razdelitve. Dva izmed analiziranih algoritmov bosta prispevek k osnovnemu, pa tudi posplošenemu problemu razdelitve. Ko bomo razumeli, kako delujejo posamezni algoritmi, jih bomo testirali in paroma primerjali, da bi ugotovili, kateri je najhitrejši in zakaj. Upoštevali bomo tudi natančnost vsakega algoritma, saj nekateri algoritmi žrtvujejo svojo hitrost za natančnejšo rešitev. V fazi testiranja bo skupno uporabljenih 70 testnih primerov. Nekateri bodo naključni, nekateri pa specifično uporabljeni kot težki testni primeri za določene algoritme. Nazadnje bomo pokazali na razliko med teorijo in prakso; med asimptotično časovno zahtevnostjo algoritmov in njihovo dejansko hitrostjo (v praksi). Cilj diplomske naloge ni najti najhitrejši algoritem, temveč analizirati vsakega od algoritmov in razumeti, kateri algoritem je najboljši za posamezno situacijo.

• Keywords: niz, algoritem, časovna zahtevnost, prostorska zahtevnost