UCCC2063
Analysis Algorithm Assignment

Lecturer / Tutor : Mr. Wong Chee Siang
Course: CS Name | ID | Cheng Shong Wei | 1103771 | Er Siang Chiang | 1203122 | Ng Yuan Wen | 1201733 |

Question 1 : Fibonacci
a. Iterative Fibonacci
1. Code:
#include <iostream>
#include <time.h> using namespace std; int main()
{
//loop until 80th Fibonacci long long count =10; while (count<=10000000000) { //variables time_t start,end; unsigned long long a = 1, b = 1;

//prompt start = clock(); //start timer for(unsigned long long n = 3; n <= count; ++n) //calculated by iterative { unsigned long long fib = a + b; a = b; b = fib; if (n==count) cout<<"Fibonacci Number: "<<fib<<endl; } //end timer show Runtime end=clock(); double diff ((double)(end - start)); double time = diff / CLOCKS_PER_SEC; cout<<"Runtime ("<< count <<"th) : "<< time <<" seconds"<<endl; cout<<"------------------------------------------------------"<<endl; count = count *10; } system ("pause"); return 0;

}

2. Analysis: n=3count1=count-3+1 T(n) =count-2
=O(count)
=O(n)

3. Table n-th Fibonacci no. | Time 1(sec) | Time 2(sec) | Time 3(sec) | Average(sec) | 10 | 0.001 | 0.001 | 0.001 | 0.001 | 100 | 0.001 | 0.001 | 0.001 | 0.001 | 1’000 | 0.002 | 0.001 | 0.001 | 0.0013 | 10’000 | 0.003 | 0.002 | 0.001 | 0.0020 | 100’000 | 0.003 | 0.001 | 0.002 | 0.0020 | 1’000’000 | 0.007 | 0.006 | 0.007 | 0.0067 | 10’000’000 | 0.053 | 0.048 | 0.047 | 0.0493 | 100’000’000 | 0.483 | 0.454 | 0.475 | 0.4706 | 1’000’000’000 | 4.495 | 4.612 | 4.503 | 4.5367 | 10’000’000’000 | 44.401 | 45.114 | 44.984 | 44.833 |

4. Graph

b. Recursive Fibonacci
1. Code:
#include <iostream>
#include <time.h> using namespace std;

//recursive Fibonacci long long fib(int x) { if (x == 0) return 0; if (x == 1) return 1; else { return fib(x-1)+fib(x-2); }
}

int main()
{
//variables time_t start,end; int count=10;

//loop until 80th Fibonacci while (count<=40) { start = clock(); //start timer cout << "Fibonacci Number: " <<fib(count)<<endl; //call function

//end timer show Runtime end=clock(); double diff ((double)(end - start)); double time = diff / CLOCKS_PER_SEC; cout<<"Runtime ("<< count <<"th) : "<< time <<" seconds"<<endl; cout<<"------------------------------------------------------"<<endl; count = count + 5; } system ("pause"); return 0;
}
2. Analysis:
Base: n = 1 is obvious
Assume T(n-1) = O(2n-1), therefore
T(n) = T(n-1) + T(n-2) + O(1) = O(2n-1) + O(2n-2) + O(1)
= O(2n)

3. Table n-th Fibonacci no. | Time 1(sec) | Time 2(sec) | Time 3(sec) | Average(sec) | 10 | 0 | 0 | 0 | 0 | 15 | 0 | 0 | 0.0001 | 0.00003 | 20 | 0.0001 | 0.0002 | 0.0002 | 0.00013 | 25 | 0.0009 | 0.0100 | 0.0011 | 0.00400 | 30 | 0.0079 | 0.0790 | 0.0081 | 0.03166 | 35 | 0.8490 | 0.8141 | 0.0833 | 0.58213 | 40 | 9.2580 | 9.2430 | 9.2370 | 9.24600 |

4. Graph

Machine Specification
Processor: Intel® Core™ i5-2450M CPU @ 2.50GHz
Installed memory (RAM): 6.00 GB
System type: 64-bit Operating System, x64-based processor

Discussion Iterative functions are loop based imperative repetitions of a process. Recursive function is a function that is partially defined by itself and consists of some simple case with a known answer. From the graph and the efficiency, we can clearly see, the recursive is a lot slower than the iterative. The time used to find the Fibonacci number by recursive is greatly increased because of the efficiency O(2n).The efficiency of iterative is O(n), so it can find very large term of Fibonacci number within a short period.
Conclusion
From the observation of the result, the best solution to solve the Fibonacci Series algorithm is by using the Fibonacci iterative algorithm.

Reference http://stackoverflow.com/questions/7450980/computing-algorithm-running-time-in-c http://en.wikipedia.org/wiki/Fibonacci_number

Question 2: Heapsort and Bucket Sort

1. Code and Analysis:

#include <iostream>
#include <time.h>
#include <cmath>
#include <fstream>
#include "list.h"

using namespace std;

void heapBottomUp (int arr[], int n); void maxKeyRemoval (int arr[], int &n); void bucketSort (int arr[], int &n, int bucket);
List<int> mergeSort (List<int> arrBucket, int n);
List<int> merge (List<int> left, List<int> right);

int main() { int optSort, n; int *arr; char inFname[15]; bool flag=false; ifstream inF; ofstream outF; clock_t timeStart, timeEnd;

while(1) { cout << "Please choose an sort algorithm:" << endl; cout << "(1) Heapsort" << endl; cout << "(2) Bucket sort" << endl; cout << "------------------------------------------------------" <<endl; cin >> optSort; if (optSort>=1 && optSort<=2) break; else cout << "Choice is not available, please re-enter." << endl; }

while (flag == false) { cout << "Please enter filename for input array." << endl; cin >> inFname; inF.open(inFname); if (inF.fail()) { cout << "Error in opening file!" << endl; } else { flag = true; cout << "Please enter the input size. " << endl; cin >> n; arr = new int[n]; for (int cnt=0; cnt<n; cnt++) inF >> arr[cnt]; } } if (optSort == 1) { timeStart = clock(); heapBottomUp (arr, n); int size = n; while (n-1 != 0) { maxKeyRemoval (arr, n); } timeEnd = clock(); cout << "Heapsort done!" << endl; cout << "Result stored in results.txt" << endl; cout << endl; outF.open("results.txt"); for (int cnt=0; cnt<size; cnt++) { outF << arr[cnt] << endl; } outF.close(); } else if (optSort == 2) { int bucket=n/10; timeStart = clock(); bucketSort (arr, n, bucket); timeEnd = clock();

cout << "Bucket sort done!" << endl; cout << "Result stored in results.txt" << endl; cout << endl; outF.open("results.txt"); for (int cnt=0; cnt<n; cnt++) { outF << arr[cnt] << endl; } cout << endl; }

double diff((double)(timeEnd - timeStart)); double second = diff / CLOCKS_PER_SEC; cout<<"Sorting Time: "<<second<<" seconds"<<endl;

delete [] arr; system ("PAUSE"); return 0;
}

void heapBottomUp (int arr[], int n) { // Constructs a heap from elements of an array in bottom-up approach for (int i=(n/2)-1; i>=0; i--) { int k=i; // location of parent int v=arr[k]; // key value of parent bool heap=false;

while (!heap && (2*k+1)<=(n-1)) { int j = 2*k+1; // child for parent k to be swapped with parent

// if left child key < right child key, set j=right child key if (j<(n-1)) { if (arr[j] < arr[j+1]) j=j+1; }

// case 1: parent key > child key if (v >= arr[j]) heap = true;

// case 2: parent key < child key, swap parent with child else { arr[k]=arr[j]; k=j; } } arr[k] = v; }
}

void maxKeyRemoval (int arr[], int &n) { // "Remove" the root of heap int tmp=arr[n-1]; arr[n-1]=arr[0]; arr[0]=tmp; n--;

heapBottomUp (arr, n);
}

void bucketSort (int arr[], int &n, int bucket) { int largest = arr[0]; int smallest = arr[0]; for (int i=0; i<n; i++) { if (arr[i] > largest) largest=arr[i]; if (arr[i] < smallest) smallest=arr[i]; } double range=(largest-smallest+1.0)/bucket;

// Set up empty buckets List<int> *arrBucket=new List<int> [bucket];

// Partition the input array for (int i=0; i<n; i++) { int x=(int)((arr[i]-smallest)/range); arrBucket[x].insert(arr[i]); }

int ptr=0; for (int i=0; i<bucket; i++) { mergeSort (arrBucket[i], arrBucket[i].size()); for (int j=1; j<=arrBucket[i].size(); j++) { arrBucket[i].get(j, arr[ptr]); ptr++; } } delete [] arrBucket;
}

List<int> mergeSort (List<int> arrBucket, int n) { // Sorts each bucket with recursive mergesort // Consider list is sorted for empty list or when list size = 1 if (arrBucket.size() <= 1) return arrBucket;

// Divide: // split list into 2 sublists List<int> left; List<int> right; for (int l=1; l<=(n/2); l++) { int x; arrBucket.get(l, x); left.insert(x); }

for (int r=(n/2)+1; r<=n; r++) { int y; arrBucket.get(r, y); right.insert(y); }

// Keep on spliting sublist until sublist size = 1 left=mergeSort(left, left.size()); right=mergeSort(right, right.size()); // Conquer: // Sublists are merged and then returned return merge(left, right);
}

List<int> merge (List<int> left, List<int> right) { List<int> result;

while (left.size()>0 || right.size()>0) { int firstL, firstR; left.get(1, firstL); right.get(1, firstR);

if (left.size()>0 && right.size()>0) { // Compare the first element of left sublist and right sublist // Insert the smaller element into result list

if (firstL <= firstR) { result.insert(firstL); left.remove(1); } else { result.insert(firstR); right.remove(1); } }

else if (left.size()>0) { result.insert(firstL); left.remove(1); }

else if (right.size()>0) { result.insert(firstR); right.remove(1); } }

return result;
}

(a) Heapsort
There are two main stages in heapsort, which are represented as two functions in the program: heapBottomUp and maxKeyRemoval.

heapBottomUp constructs a binary tree from the input array’s element and heapify it, while maxKeyRemoval sort the array by “removing” the root of heap continuously. A bottom-up approach is chosen to build the heap as it will be faster than top-down approach.

(b) Bucket Sort bucketSort function is used in bucket sort algorithm. Bucket sort set up empty buckets initially, then partition the input array into different buckets. Next, elements in each bucket is sort individually using a sorting algorithm or by recursively applying bucket sort. Finally, all elements are located back in original array.

In our case, mergesort is applied in the program, where includes two functions: mergeSort for dividing elements into sublist, and merge for merging sublists. The reason for choosing mergeSort is to run the sorting algorithm faster.

2. Table:

(a) Heapsort Input Size,Input Pattern, | First Running Time(s) | Second Running Time(s) | Third Running Time (s) | Average Running Time(s) | 102 | Random order | 0 | 0 | 0 | 0 | | Increasing order | 0 | 0 | 0 | 0 | | Decreasing order | 0 | 0 | 0 | 0 | 103 | Random order | 0.002 | 0.003 | 0.003 | 0.0027 | | Increasing order | 0.002 | 0.003 | 0.002 | 0.0023 | | Decreasing order | 0.002 | 0.001 | 0.002 | 0.0017 | 104 | Random order | 0.189 | 0.191 | 0.182 | 0.1873 | | Increasing order | 0.162 | 0.159 | 0.168 | 0.1630 | | Decreasing order | 0.139 | 0.135 | 0.138 | 0.1373 | 105 | Random order | 17.647 | 17.749 | 17.818 | 17.738 | | Increasing order | 15.548 | 15.407 | 15.439 | 15.4647 | | Decreasing order | 12.213 | 12.099 | 12.338 | 12.2167 | 106 | Random order | - | - | - | - | | Increasing order | - | - | - | - | | Decreasing order | - | - | - | - |

* - indicates computer unable to produce results

(b) Bucket Sort Input Size,Input Pattern, | First Running Time(s) | Second Running Time(s) | Third Running Time (s) | Average Running Time(s) | 102 | Random order | 0.001 | 0.002 | 0.002 | 0.0017 | | Increasing order | 0.002 | 0.002 | 0.001 | 0.0017 | | Decreasing order | 0.002 | 0.001 | 0.001 | 0.0013 | 103 | Random order | 0.01 | 0.015 | 0.015 | 0.0133 | | Increasing order | 0.015 | 0.015 | 0.015 | 0.015 | | Decreasing order | 0.015 | 0.013 | 0.0015 | 0.0098 | 104 | Random order | 0.101 | 0.108 | 0.107 | 0.1053 | | Increasing order | 0.098 | 0.108 | 0.099 | 0.1017 | | Decreasing order | 0.1095 | 0.109 | 0.104 | 0.1075 | 105 | Random order | 0.979 | 0.958 | 0.956 | 0.9643 | | Increasing order | 0.935 | 0.93 | 0.927 | 0.9307 | | Decreasing order | 0.94 | 0.927 | 0.928 | 0.9317 | 106 | Random order | 13.12 | 13.299 | 14.141 | 13.52 | | Increasing order | 12.988 | 12.687 | 12.715 | 12.7967 | | Decreasing order | 12.711 | 12.66 | 12.649 | 12.6733 |

3. Graph:

(a) Heapsort

Time

Input Size

Time

Input Size

Time

Input Size

(b) Bucket Sort
Time

Input Size

Time

Input Size

Time

Input Size

Machine Specification

Processor: Intel® Core™ 2 Duo CPU @ 2.40GHz Installed memory (RAM): 2.00GB System type: 64-bit Operating System

Discussion

(a) Heapsort Heapsort runs in O(n log n) in any cases: Input Size | n log n | 102 | 200 | 103 | 3000 | 104 | 40000 | 25000 | 109948.5 | 50000 | 234948.5 | 75000 | 365629.59 | 105 | 500000 | 106 | 6000000 |

(b) Bucket Sort
The average case performance for bucket sort is O(n+nlogn), where nlogn is the complexity of mergesort algorithm, while the worst case performace for bucket sort is O(n2).

Input Size | n+nlogn | n2 | 102 | 210 | 104 | 103 | 4000 | 106 | 104 | 50000 | 108 | 25000 | 134948.5 | 6.25x108 | 50000 | 284948.5 | 2.5x109 | 75000 | 440629.59 | 5.625x109 | 105 | 600000 | 1010 | 106 | 7000000 | 1012 |

By comparing graphs from our experiment results and theoretical analysis, we found that the theoretical analysis graphs does not tally with experimental results slightly. Theoretical analysis is a way of estimating the result based on theories and it cannot predict what the actual results be, but it does provide an idea of what results is likely to be produced in an experiment.

Conclusion
According to our results, bucket sort runs faster than heapsort in larger size array. This is because merge sort, which has considerably better data cache performance, is applied in the inner sort algorithm of bucket sort.

Reference

http://en.algoritmy.net/article/41160/Bucket-sort http://en.wikipedia.org/wiki/Heapsort http://en.wikipedia.org/wiki/Merge_sort http://en.wikipedia.org/wiki/Bucket_sort Question 3: Tower of Hanoi Problem
a. Recursive algorithm
1.Code:
#include <iostream>
#include <time.h> using namespace std;

void move_rings (int n, int src, int dest, int other)//recursive form of moving discs
{
if (n==1) { cout <<"Move the top disk from tower "<< src << " to tower "<< dest << endl; } else { move_rings (n-1, src, other, dest); cout <<"Move the top disk from tower "<< src << " to tower "<< dest << endl; move_rings(n-1, other, dest, src); }
}

int main()
{
int n = 0; clock_t timeS , timeE;

cout<<"Please input the number of disks:"<<endl; cin>>n;

while(n != 0) { timeS = clock(); move_rings(n,1,3,2); timeE = clock();

double diff((double)(timeE - timeS)); double second = diff / CLOCKS_PER_SEC; cout<<"Runtime: "<<second<<" seconds"<<endl;

cout<<"Please input the number of disks:"<<endl; cin>>n; }

system("pause"); return 0;
}

2.Table:

Experimental Results Input Size | Time1(s) | Time2(s) | Time3(s) | Average Time(s) | 3 | 0.013 | 0.016 | 0.019 | 0.016 | 6 | 0.142 | 0.143 | 0.141 | 0.142 | 9 | 0.883 | 0.774 | 0.832 | 0.830 | 12 | 6.326 | 6.396 | 6.519 | 6.414 | 15 | 52.888 | 53.760 | 53.596 | 53.415 |

3.Graph:

Graph of experimental results

4. Analysis:

Efficiency: T (n) = 1 if n =1 2 T (n-1) +1 otherwise Therefore, T (n) = 2T (n-1) + 1 = 2(2T (n – 2) + 1) + 1 = 4T (n-2) +2+1 = 4(2T (n-3) +1) +2+1 = 8T (n-3) +4+2+1 = 2i T (n – i) + j=0i-12j = 2n-1 T (1) + j=0n-22j = 2n - 1 T (n) = O (2n)
Theoretical Analysis:
Where T (n) = 2n - 1 Input Size | T(n) | 3 | 7 | 6 | 63 | 9 | 511 | 12 | 4095 | 15 | 32767 |

Graph of theoretical analysis and experimental result
Based on the order of growth of recursive algorithm of tower of Hanoi as well as the theoretical analysis, the experimental results is same as the theoretical analysis. Both the experimental and theoretical order of growth is O (2n) because the both of the graphs show that the algorithm grows exponentially.

b. Non- recursive algorithm
1.Code:
#include<iostream>
#include<stdlib.h>
#include<time.h> using namespace std;

#define MAXSTACK 100 struct details
{
int number; int beg; int end; int aux;
};
struct stack
{
int top; struct details item [MAXSTACK];
};
void push(struct stack *s, struct details *current)
{
if(s->top==MAXSTACK-1) { cout<<"Overflow"; exit(1); } else s->item[++(s->top)]= *current;

return;
}

void popandtest(struct stack *s, struct details *current,int *flag)
{
if(s->top==-1) { *flag=1; return; }

*flag=0; *current= s->item[s->top--];

return;
}

//towers of hanoi without recursion void towers(int n, int begpeg, int endpeg, int auxpeg)
{
struct stack s; struct details current; int flag; int temp; s.top=-1;

current.number=n; current.end=endpeg; current.beg=begpeg; current.aux=auxpeg;

while(1) { while(current.number!=1) { push(&s,&current); --current.number; temp=current.end; current.end=current.aux; current.aux=temp; }

cout<<"Move top disk from tower "<<current.beg<<" to tower "<<current.end<<endl; popandtest(&s,&current,&flag);

if(flag==1) return;

cout<<"Move top disk from tower "<<current.beg<<" to tower "<<current.end<<endl;

--current.number; temp=current.beg; current.beg=current.aux; current.aux=temp; }
}

int main()
{
int N; clock_t timeS , timeE;

cout<<"Enter the number of disk:"<<endl; cin>>N;

while(N != 0) {

timeS = clock(); towers(N,1,3,2); timeE = clock();

double diff((double)(timeE - timeS)); double second = diff / CLOCKS_PER_SEC; cout<<"Runtime: "<<second<<" seconds"<<endl;

cout<<"Enter the number of disk:"<<endl; cin>>N; } system("pause"); return 0;
}

2.Table:

Experimental Results Input Size | Time1(s) | Time2(s) | Time3(s) | Average Time(s) | 3 | 0.012 | 0.013 | 0.013 | 0.013 | 6 | 0.123 | 0.114 | 0.112 | 0.116 | 9 | 0.772 | 0.803 | 0.806 | 0.794 | 12 | 6.314 | 6.187 | 6.018 | 6.173 | 15 | 49.888 | 48.424 | 47.934 | 48.749 |

3.Graph:

Graph of experimental results

4.Analysis:

Efficiency:
T (n) = 2n – 1
T (n) = O (2n)
Theoretical Results:
Where T (n) = 2n - 1 Input Size | T (n) | 3 | 7 | 6 | 63 | 9 | 511 | 12 | 4095 | 15 | 32767 |

Graph of Theoretical Analysis

Machine Specification
Processor: Intel® Core™ i5-2410M CPU @ 2.30GHz
Installed memory (RAM): 4.00 GB
System type: 64-bit Operating System, x64-based processor

Discussion

When the input size is small, the running time for recursive algorithm and non-recursive algorithm is almost the same. As the input size increases, the rate of running time of recursive algorithm grows higher than the non-recursive algorithm which shows that the time complexity of recursive algorithm is in fact higher than the non-recursive algorithm.

Conclusion
Non-recursive algorithm of tower of Hanoi is slightly faster than the recursive algorithm because its time complexity actually is slightly lower than the other.

Reference http://www.seas.gwu.edu/~drum/cs1112/lectures/module9/module9.html http://wenku.baidu.com/view/2c4841375727a5e9856a6109.html
Question 4: Knapsack Problem
a. brute force algorithm
1. Code:
#include<iostream>
#include<cmath> using namespace std;

void BruteForce(int weights[5],int values[5],int A[5])
{

int subset = 0,bestValue = 0, bestWeight = 0 , bestChoice[5] = {0};

for(int i = 1 ; i <= pow(2.0,5.0)-1 ; i++) { int j = 4; int tempWeight = 0; int tempValue = 0;

while(A[j] != 0 && j > 0 ) { A[j] = 0; j = j - 1; }

A[j] = 1; for(int k = 0 ; k<5 ; k++) { if(A[k] == 1) { tempWeight = tempWeight + weights[k]; tempValue = tempValue + values[k]; } }

if((tempValue > bestValue ) && (tempWeight <= 6 )) { for(int b= 0;b<5;b++) bestChoice[b] = A[b];

bestValue = tempValue; bestWeight = tempWeight; } }

int count = 1; cout<<"Item: "; for(int a = 0 ; a < 5 ; a++) { if(bestChoice[a] == 1) { cout<<count<<" "; }

count++; } cout<<" "; cout<<"Weight: "<<bestWeight<<" "; cout<<"Value: "<<bestValue<<endl; }

int main()
{
int weights[] = { 3,2,1,4,5 }; int values[] = {250,200,150,400,500}; int A[5] = {0};

BruteForce(weights,values,A);

system("pause"); return 0;
}

2. Analysis: i=12n j=n1+k=1n = i=12n[ 1+…+1n+{1+…+1}(n)]
= (2n)* [1+1+1…..+1] (2n)
= O (2n*2n)
= O (n*2n)
= O (2n)

Therefore, the complexity of the Brute Force algorithm is O (2n). Since the complexity of this algorithm grows exponentially, it can only be used for small instances of the KP.
Otherwise, it does not require much programming effort in order to be implemented.
Besides the memory used to store the values and weights of all items, this algorithm requires a two one dimensional arrays (A[] and bestChoice[]).

b. dynamic programming
1. Code:
// A Dynamic Programming based solution for 0-1 Knapsack problem
#include<iostream>
using namespace std;
// A utility function that returns maximum of two integers int max(int a, int b) { return (a > b)? a : b; } // Returns the maximum value that can be put in a knapsack of capacity W int knapSack(int W, int wt[], int val[], int n)
{
int i, w; int K[6][7]; // Build table K[][] in bottom up manner for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } } return K[n][W];
}

int main()
{
int value[] = {250,200,150,400,500}; int weight[] = { 3,2,1,4,5 }; int capacity = 6; int n = sizeof(value)/sizeof(value[0]); cout<<"Best Value:"<<knapSack(capacity, weight, value, n)<<endl; system("pause"); return 0;
}

2. Analysis: i=0Nj=0Capacity1 = i=1N 1+…+1(Capacity)
= Capacity * [1+1+1+……+1] (N)
= Capacity * N
= O (N*Capacity)

Thus, the complexity of the Dynamic Programming algorithm is O (N*Capacity). In terms of memory, Dynamic Programming requires a two dimensional array with rows equal to the number of items and columns equal to the capacity of the knapsack. This algorithm is probably one of the easiest to implement because it does not require the use of any additional structures.
Machine Specification
Processor: Intel® Core™ i5-2410M CPU @ 2.30GHz
Installed memory (RAM): 4.00 GB
System type: 64-bit Operating System, x64-based processor

Discussion
The Knapsack Problem is an example of a combinatorial optimization problem, which seeks for a best solution from among many other solutions. For brute force algorithm, Brute force is a straightforward approach to solving a problem, usually directly based on the problem’s statement and definitions of the concepts involved. If there are n items to choose from, then there will be 2n possible combinations of items for the knapsack which results in slower algorithm if the input size is too big Item is either chosen or not chosen. A bit string of 0’s and 1’s is generated which is of length n. If the i th symbol of a bit string is 0, then the i th item is not chosen and if it is 1, the i th item is chosen.

For dynamic programming method, Dynamic Programming is a technique for solving problems whose solutions satisfy recurrence relations with overlapping sub-problems. Dynamic Programming solves each of the smaller sub-problems only once and records the results in a table rather than solving overlapping sub-problems over and over again which results in a better performance for the knapsack problem as the input size increases. The table is then used to obtain a solution to the original problem. The classical dynamic programming approach works bottom-up.

Conclusion
Dynamic programming is faster than brute force algorithm because the complexity of dynamic programming grows linearly but the complexity of brute force algorithm grows exponentially.
Reference
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm
http://jahovaos.com/groups/kb/wiki/fa460/