In DucDuong92/Lab6R: This is the package for R lab 6

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

Opening speech

This is the report for R lab 6. In this repot, I will discuss about:
1. Present the speed of different algorithms.
2. Answer questions of the lab.

Before going to the details, let's take a look to how to install the package:

devtools::install_github('DucDuong92/Lab6R')

1. The speed of different algorithms

Base on the theory, brute force is the slowest one with O(2^n), dynamic take O(Wn) and greedy take O(n log n)

And the result of my code reflect exactly that result, brute_force always the slowest one. Dynamic_knapsack is faster (because of the improvements in the algorithm). Greedy_knapsack is the fastest one, but it cost is sometimes the return value is not the most optimum one.

You can see the running time below:

library(Lab6R)
data("knapsack_objects")
system.time(a <- brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500))
system.time(a <- dynamic_knapsack(x = knapsack_objects[1:16,], W = 3500))
system.time(a <- greedy_knapsack(x = knapsack_objects[1:16,], W = 3500))

2. Questions of the lab

Question 1.1.2: How much time does it takes to run the algorithm for n = 16 objects?
For brute_force algorithm, it take the time as follow:

system.time(a <- brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500))

Question 1.1.8: What performance gain could you get by parallelizing brute force search?

system.time(a <-brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500,parallel = TRUE))

Compare the time when having parallel, we see that the user time is improved, but not too much. Maybe because I only implement parallel for calculating the combination. In contrast, the elapsed time is higher. Maybe because it takes time to start 2 cores, but the work of each core is not so much.

Question 1.1.3: How much time does it takes to run the algorithm for n = 500 objects? For dynamic_knapsack algorithm, it take the time as follow:

system.time(a <-dynamic_knapsack(x = knapsack_objects[1:500,], W = 3500))

Question 1.1.4: How much time does it takes to run the algorithm for n = 1000000 objects? For greedy_knapsack algorithm, it take the time as follow:

set.seed(42)
n <- 1000000
knapsack_objects <-data.frame(
  w=sample(1:10000, size = n, replace = TRUE),
  v=runif(n = n, 0, 10000)
)

system.time(a <-greedy_knapsack(x = knapsack_objects[1:1000000,], W = 3500))

Question 1.1.6: What performance gain could you get by trying to improve your code?

By reduce the loops, skip some unnecessary task (Like don't recalculate some values that have the weight lower than weight of that element if(w[i]>j){m[i,j] <- m[i-1,j]}) the time need for calculating the result is improved, especially in the case of brute force and dynamic algorithm.

DucDuong92/Lab6R documentation built on May 22, 2019, 2:03 p.m.