Skip to content

FilipeLopesPires/SubsetSum

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 

Repository files navigation

SubsetSum

A Study on 'The Subset-Sum Problem'

Description

The goal of this project is to study different implementations of the solution to the well-known Subset-Sum Problem in terms of computational complexity and execution time. The implemented solutions are:

  • Brute Force
  • Branch and Bound
  • Meet in the Middle

The thid implementation presented the best results, with a computational complexity of O(2^(n/2)).

Repository Structure

\study - the written report on the study conducted is made available here

\src - contains the source code, written in C

Authors

The authors of this repository are Filipe Pires and João Alegria, and the project was developed for the Algorithms and Data Structures Course of the licenciate's degree in Informatics Engineering of the University of Aveiro.

For further information, please read our report or contact us at filipesnetopires@ua.pt or joao.p@ua.pt.