OC - PROJECT N°7 - AlgoInvest & Trade - Solve problems using algorithms

AlgoInvest&Trade, a financial company specializing in investment. The company seeks to optimize its investment strategies using algorithms, in order to generate more profits for its clients.

By Markus Spiske

Project Overview

Goal:

• Design an algorithm that will maximize the profit made by our clients after two years of investment. Your algorithm should suggest a list of the most profitable stocks we should buy to maximize a client's profit after two years.

We have the following constraints:

• Each share can only be purchased once.
• We cannot buy a fractional share.
• We can spend a maximum of 500 euros per customer.

Datasets:

• data.csv: list of 20 stocks
• data2.csv: list of 1000 stocks
• data3.csv: list of 1000 stocks

(back to top)

Built With & Tools

• Python
• Itertools
• Pandas
• Timeit
• Guppy

(back to top)

Getting Started

Clone the repo

git clone https://github.com/Jliezed/oc_project_7_algo_and_invest.git

Run the script with a virtual environment:

Install venv library (if not yet in your computer)

pip install venv

Create a virtual environment

python -m venv env

Activate the virtual environment

source env/bin/activate

Install packages using requirements.txt

pip install -r requirements.txt

Run a script

python bruteforce.py
python optimized_dynamic_programming.py
python optimized_glouton.py

(back to top)

Results

Bruteforce algorithm

• Bruteforce algorithm tests all the possible combinations of stocks to buy.
• The algorithm is very slow and does not allow to test the 1000 stocks dataset.
• Big O:
  • Time complexity: O(n!)
  • Space complexity: O(n!)

Greedy algorithm

• Greedy algorithm involves making locally optimal choices at each step with the hope of finding a global optimum solution.
• It is a simple algorithm that does not guarantee the best result.
• The algorithm is very fast and allows to test the 1000 stocks dataset.
• Big O:
  • Time complexity: O(n)
  • Space complexity: O(1)

Dynamic programming algorithm (based on Knapsack)

• Dynamic programming is a technique for solving problems by breaking them down into smaller subproblems
• Solving each subproblem only once, and storing the results for future use.
• It is a complex algorithm that guarantees the best result.
• The algorithm is very fast and allows to test the 1000 stocks dataset and more.
• Big O:
  • Time complexity: O(nU)
  • Space complexity: O(1)

Comparison of the three algorithms

(back to top)