COMPARATIVE STUDY BETWEEN DYNAMIC

PROGRAMMING AND GREEDY TECHNIQUE

NAME– DIGANTA ROYCHOWDHURY
College Name- Camellia Institute of Engineering & Technology
Department name- Computer Science and Engineering
University Roll No – 27100124041, Sem- 4th
Paper Name (Paper Code)- Design and Analysis of Algorithm (PCC-CS 404)
Email id: diganta7478640883@[Link]

Abstract

Dynamic Programming (DP) and the Greedy technique I. Introduction

are two fundamental approaches used in algorithm design
for solving optimization problems. While DP breaks down Algorithms play a crucial role in solving complex
problems into subproblems and solves them recursively computational problems efficiently. Two widely used
with memorization, the Greedy technique follows a step- strategies in algorithm design are Dynamic
by-step approach, making locally optimal choices at each Programming and the Greedy technique. These
step. This report provides a comparative analysis of these strategies are applied in a variety of real-world
two techniques, highlighting their characteristics, scenarios, including shortest path finding, resource
applications, advantages, and limitations. The study aims allocation, and data compression. This report explores
to understand the best scenarios where each technique is the fundamental differences between these techniques
preferable and how they impact computational efficiency. and evaluates their effectiveness in solving optimization
problems.

Table of Contents
Main Body
I. Introduction
II. Overview of Dynamic Programming and Greedy
II. Overview of Dynamic Programming and Greedy Technique
Technique
Dynamic Programming (DP)
III. Comparison Between Dynamic Programming and
Greedy Technique Dynamic Programming is an optimization technique
used for solving problems that exhibit overlapping
IV. Applications of Dynamic Programming and Greedy subproblems and optimal substructure. It involves
Technique breaking a problem into smaller subproblems,
solving each subproblem once, and storing the
V. Conclusion results to avoid redundant computations. DP can be
VI. Recommendations implemented in two ways:

VII. Appendices a. Top-Down Approach (Memorization): Solves the

problem recursively and stores previously computed
VIII. References results.
 b. Bottom-Up Approach (Tabulation): Builds a V. Conclusion
solution iteratively by solving smaller subproblems
first. Both Dynamic Programming and the Greedy
technique are essential for solving optimization
Greedy Technique problems. DP ensures an optimal solution by
solving subproblems but may have high time and
The Greedy algorithm follows a problem-solving space complexity. The Greedy technique, on the
approach where the best possible choice is made at other hand, provides quick solutions with less
each step with the hope that these choices will lead to computational overhead but does not always
an optimal solution. Unlike DP, Greedy algorithms do guarantee the best solution. The choice between
not store previous results, making them faster in these techniques depends on the problem type,
execution but not always optimal. constraints, and efficiency requirements.
III. Comparison Between Dynamic Programming and Greedy
Technique
[Link]
Feature Dynamic Programming Greedy Technique
a. Use DP when the problem has overlapping
Suitable for problems with Works well for problems where subproblems and optimal substructure.
Problem Type overlapping subproblems local choices lead to global
and optimal substructure optimum b. Prefer Greedy algorithms for problems where
local optimization leads to a globally optimal
Makes decisions step by step
Stores intermediate results solution.
Computation without storing previous
to avoid precomputation
computations
c. Optimize DP implementations using space-
Higher computational cost Generally faster due to lack of efficient techniques like tabulation.
Complexity
due to additional storage recursion/memorization
d. Experiment with hybrid approaches combining
Example
Fibonacci Sequence,
Activity Selection, Huffman
DP and Greedy techniques for enhanced
Knapsack Problem, Matrix performance.
Problems Coding, Kruskal’s Algorithm
Chain Multiplication

IV. Applications of Dynamic Programming and Greedy

Technique VII. Appendices
a. Pseudocode for Dynamic Programming and Greedy
Dynamic Programming Applications:
algorithm examples.
a. Shortest Path Problems: Bellman-Ford Algorithm.
b. Graphical representation of DP and Greedy solutions.
b. Knapsack Problem: Used in resource allocation.
c. Additional real-world case studies comparing both
c. Fibonacci Sequence Calculation: Uses memorization techniques.
to improve efficiency.

d. Matrix Chain Multiplication: Finds the optimal order

References
for multiplying matrices.
[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
Greedy Technique Applications: (2009). Introduction to Algorithms. MIT Press.

a. Graph Algorithms: Prim’s and Kruskal’s algorithm [2] Kleinberg, J., & Tardos, É. (2006). Algorithm Design.
for Minimum Spanning Tree. Pearson.

[3] Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The

b. Huffman Coding: Data compression in file storage. Design and Analysis of Computer Algorithms. Addison-
Wesley.
c. Activity Selection Problem: Scheduling tasks
efficiently.

d. Dijkstra’s Algorithm: Finds the shortest path in a

graph with non-negative weights.