Coin Change : Greedy vs Dynamic Programming

Nov 27, 2017Download as pptx, pdf4 likes3,696 views

This document contains a presentation on solving the coin change problem using greedy and dynamic programming algorithms. It introduces the coin change problem and provides an example. It then describes the greedy algorithm approach and how it works for some cases but fails to find an optimal solution in other cases when coin values are not uniform. The document next explains dynamic programming, its four step process, and how it can be applied to the coin change problem to always find an optimal solution using a bottom-up approach and storing results of subproblems to build the final solution.

GROUP MEMBER LIST
 Abu Nowshad Rasel 161-15-6861
 Shahrun Siddique Taki 161-15-7195
 Syeda Khadizatul Maria 161-15-7333
 Md. Mehedi Hassan 161-15-7338

Coin Change : Greedy vs
Dynamic Programming
PRESENTATION TOPIC

Greedy Algorithm
 What is greedy algorithm ?
 An algorithm is greedy if it builds a solution in small
steps , choosing a decision at each step
myopically[=locally, not considering what happen ahead to
optimize some underlying criterion.
 It is easy to design a greedy algorithm for a problem .
There may be different ways to choose the next step
locally.

Coin Change Problem
Coin Change is the problem of finding the number of ways of making
changes for a particular amount of taka, n, using a given unlimited
amounts of coins.
Example :
Available coins : ৳1, ৳5, ৳10, ৳25
Make change : ৳48
∴ 48 - 25 = 23 →
23 - 10 = 13 →
13 - 10 = 3 →
3 - 1*3 = 0 →
25
10
10
111

Result :
 Number of coins requires to make change to 48 = 6
 Coin set = { 1,1,1,10,10,25 }

Advantage of greedy
#Greedy is easy to be implemented. Just search the
Best choice from the current state that reachable .
#In simple case, greedy often give the best solution.

Failure of Greedy Algorithm
A greedy algorithm is a simple but in many
problems, a greedy strategy does not produce
an optimal solution. The greedy algorithm
fails to find optimal solution in some case,
because it makes decisions based only on the
information it has at any one step, and
without regard to the overall problem.
In coin change problem , if every coin is a
multiple of all smaller coins, then we can use
greedy approach to get the optimal solution.

In some fictional monetary system :
Available coins : 1,7,10
Make change :15 taka
∴ 15 - 10 = 5 →
5 - 1*5 = 0 →
This requires six coins .
A better solution would be to use two 7 taka and one 1 taka
+ + = 15
This only requires three coins
10
1 1 1 1 1
7 7 1
For example :

Available coins : 4,10,25
Make change : 41 taka
∴ 41 - 25 = 16 →
16 - 10 = 6 →
6- 4 = 2 →
2 → ??
In this case , greedy algorithm fail to solve . But the
required result is one 25 taka and four 4 taka.
So the greedy algorithm does not give an optimal
solution always.
25
10
4
Another example:

Dynamic Programming
Dynamic programming (also known as dynamic
optimization) is a method for solving a complex problem
by breaking it down into a collection of simpler
subproblems, solving each of those subproblems just
once, and storing their solutions
DP is used to solve problems with the following
characteristics:
 Simple Subproblems
 Optimal structure of the problems
 Overplapping sub-problems

Dynamic Programming Solution (4 steps)
 1. Characterize the structure of an optimal solution.
 2. Recursively define the value of an optimal solution.
 3. Compute the value of an optimal solution in a bottom-up
fashion.
 4. Construct an optimal solution from computed information

Greedy vs. DP
 Similarities
Optimization problems
Optimal substructure
Make choice at each step
Differences
 Dynamic Programming is Bottom up while Greedy is top-down -Optimal substructure
Dynamic programming can be overkill; greedy algorithms tend to be easier to code

Coin Change With Dynamic Programming
 Make a change, Total = 6
 Available Coin Set = { 2, 3, 5 }
T[i] [j] is the 2D array to denote the minimum number of coins require to make the
change Coin[i] is the sorted array of available coin sets. [Index Start from 1]
 If V == 0, then 0 coins required.
T[i][j] = 0
 If V > 0
Case 1: T [i][j] = T [i-1][j] If Coin[i] is not takes
Case 2: T [i][j] = 1 + T [i] [j–Coin [i]] If Coin[ i ] is taken

T [i][j] = MIN ( T [i-1][j] , 1 + T[i][j-Coin[i] )
0 1 2 3 4 5 6
2
3
5
0
0
0
0
∞ ∞ ∞ ∞ ∞ ∞
∞ 1 ∞ 2 ∞ 3
∞
∞ 1 1 2 1 2
1 1 2 2 2

Result:
 Number of Coins requires to make a change to 6 = 2
 Coin Set = { 3, 3 }

This document discusses the coin changing problem and compares dynamic programming and greedy algorithms for solving it. The coin changing problem involves finding the minimum number of coins needed to make change for a given amount using an unlimited supply of coins. Dynamic programming breaks the problem down into subproblems that are solved once and stored, while greedy algorithms make locally optimal choices at each step to try to find a global optimum. The document provides examples of solving coin changing problems using both dynamic programming and greedy algorithms and analyzes their time complexities.

Time and space complexityAnkit Katiyar

The document discusses time and space complexity analysis of algorithms. Time complexity measures the number of steps to solve a problem based on input size, with common orders being O(log n), O(n), O(n log n), O(n^2). Space complexity measures memory usage, which can be reused unlike time. Big O notation describes asymptotic growth rates to compare algorithm efficiencies, with constant O(1) being best and exponential O(c^n) being worst.

Minimum spanning treeHinal Lunagariya

The document discusses minimum spanning tree algorithms for finding low-cost connections between nodes in a graph. It describes Kruskal's algorithm and Prim's algorithm, both greedy approaches. Kruskal's algorithm works by sorting edges by weight and sequentially adding edges that do not create cycles. Prim's algorithm starts from one node and sequentially connects the closest available node. Both algorithms run in O(ElogV) time, where E is the number of edges and V is the number of vertices. The document provides examples to illustrate the application of the algorithms.

Face recognition pptSantosh Kumar

This document provides an overview of facial recognition technology. It discusses the history of facial recognition, how the technology works by detecting nodal points on faces and creating faceprints for identification. It also covers implementations, comparing images to templates to verify or identify individuals, and applications in security and surveillance. Strengths are its non-invasive nature, but it can be impacted by changes in appearance.

Fractional Knapsack Problemharsh kothari

This document discusses the greedy algorithm approach and the knapsack problem. It defines greedy algorithms as choosing locally optimal solutions at each step in hopes of reaching a global optimum. The knapsack problem is described as packing items into a knapsack to maximize total value without exceeding weight capacity. An optimal knapsack algorithm is presented that sorts by value-to-weight ratio and fills highest ratios first. An example applies this to maximize profit of 440 by selecting full quantities of items B and A, and half of item C for a knapsack with capacity of 60.

01 Knapsack using Dynamic ProgrammingFenil Shah

0/1 knapsackAmin Omi

The document discusses the 0-1 knapsack problem and how it can be solved using dynamic programming. It first defines the 0-1 knapsack problem and provides an example. It then explains how a brute force solution would work in exponential time. Next, it describes how to define the problem as subproblems and derive a recursive formula to solve the subproblems in a bottom-up manner using dynamic programming. This builds up the solutions in a table and solves the problem in polynomial time. Finally, it walks through an example applying the dynamic programming algorithm to a sample problem instance.

Dot net assemblyDr.Neeraj Kumar Pandey

This document discusses assemblies in .NET. It begins with an introduction to assemblies, which are compiled .NET code files with the extension .exe or .dll. Assemblies include metadata and intermediate language code. There are two types of assemblies: private assemblies used only by one application, and shared assemblies stored in the global assembly cache (GAC) to be used by multiple applications. The document then covers strong naming assemblies, which involves assigning an assembly a unique name, version number, culture, and public key for deployment and security. Finally, it discusses the GAC which stores strongly named assemblies to be shared across applications on a machine.

Divide and conquer - Quick sortMadhu Bala

Coin Change ProblemDEVTYPE

This document discusses algorithms for solving the coin change problem of finding the minimum number of coins needed to make a given monetary value. It describes greedy, recursive, and dynamic programming approaches. The greedy algorithm works optimally for coin denominations of 10, 5, 1 by always selecting the highest value coin first. However, the greedy approach does not always give the optimal solution in general. Dynamic programming improves on the recursive solution by storing intermediate results in an array to avoid recomputing the same subproblems.

Greedy algorithmsRajendran

This document discusses greedy algorithms and dynamic programming techniques for solving optimization problems. It covers the activity selection problem, which can be solved greedily by always selecting the shortest remaining activity. It also discusses the knapsack problem and how the fractional version can be solved greedily while the 0-1 version requires dynamic programming due to its optimal substructure but non-greedy nature. Dynamic programming builds up solutions by combining optimal solutions to overlapping subproblems.

Greedy AlgorithmWaqar Akram

This document provides an introduction to greedy algorithms. It defines greedy algorithms as algorithms that make locally optimal choices at each step in the hope of finding a global optimum. The document then provides examples of problems that can be solved using greedy algorithms, including counting money, scheduling jobs, finding minimum spanning trees, and the traveling salesman problem. It also provides pseudocode for a general greedy algorithm and discusses some properties of greedy algorithms.

Greedy Algorithm - Knapsack ProblemMadhu Bala

The document discusses the knapsack problem and greedy algorithms. It defines the knapsack problem as an optimization problem where given constraints and an objective function, the goal is to find the feasible solution that maximizes or minimizes the objective. It describes the knapsack problem has having two versions: 0-1 where items are indivisible, and fractional where items can be divided. The fractional knapsack problem can be solved using a greedy approach by sorting items by value to weight ratio and filling the knapsack accordingly until full.

Greedy algorithmssandeep54552

Greedy algorithms work by making locally optimal choices at each step to arrive at a global optimal solution. They require that the problem exhibits the greedy choice property and optimal substructure. Examples that can be solved with greedy algorithms include fractional knapsack problem, minimum spanning tree, and activity selection. The fractional knapsack problem is solved greedily by sorting items by value/weight ratio and filling the knapsack completely. The 0/1 knapsack problem differs in that items are indivisible.

Traveling salesman problemJayesh Chauhan

The document describes the traveling salesman problem (TSP) and how to solve it using a branch and bound approach. The TSP aims to find the shortest route for a salesman to visit each city once and return to the starting city. It can be represented as a weighted graph. The branch and bound method involves reducing the cost matrix by subtracting minimum row/column values, building a state space tree of paths, and choosing the path with the lowest cost at each step. An example demonstrates these steps to find the optimal solution of 24 for a 5 city TSP problem.

Min-Max algorithmDr. C.V. Suresh Babu

The minmax algorithm is used in two-player turn-based games to determine the optimal move for a player assuming the opponent plays optimally. It works by having one player act as the maximizer trying to maximize their score, and the other as the minimizer trying to minimize the score. The algorithm analyzes all possible moves and countermoves to determine the outcome with the best score for the maximizer. It is optimal if both players play optimally but has limitations due to its exhaustive search of all possibilities.

Stressen's matrix multiplicationKumar

Strassen's algorithm improves on the basic matrix multiplication algorithm which runs in O(N3) time. It achieves this by dividing the matrices into sub-matrices and performing 7 multiplications and 18 additions on the sub-matrices, rather than the 8 multiplications of the basic algorithm. This results in a runtime of O(N2.81) using divide and conquer, providing an asymptotic improvement over the basic O(N3) algorithm.

Analysis of algorithmRajendra Dangwal

Graph coloring using backtrackingshashidharPapishetty

This document summarizes graph coloring using backtracking. It defines graph coloring as minimizing the number of colors used to color a graph. The chromatic number is the fewest colors needed. Graph coloring is NP-complete. The document outlines a backtracking algorithm that tries assigning colors to vertices, checks if the assignment is valid (no adjacent vertices have the same color), and backtracks if not. It provides pseudocode for the algorithm and lists applications like scheduling, Sudoku, and map coloring.

Branch and boundDr Shashikant Athawale

The branch-and-bound method is used to solve optimization problems by traversing a state space tree. It computes a bound at each node to determine if the node is promising. Better approaches traverse nodes breadth-first and choose the most promising node using a bounding heuristic. The traveling salesperson problem is solved using branch-and-bound by finding an initial tour, defining a bounding heuristic as the actual cost plus minimum remaining cost, and expanding promising nodes in best-first order until finding the minimal tour.

Randomized Algorithm- Advanced AlgorithmMahbubur Rahman

Single source Shortest path algorithm with exampleVINITACHAUHAN21

The document discusses greedy algorithms and their application to solving optimization problems. It provides an overview of greedy algorithms and explains that they make locally optimal choices at each step in the hope of finding a globally optimal solution. One application discussed is the single source shortest path problem, which can be solved using Dijkstra's algorithm. Dijkstra's algorithm is presented as a greedy approach that runs in O(V2) time for a graph with V vertices. An example of applying Dijkstra's algorithm to find shortest paths from a source node in a graph is provided.

04 brute forceHira Gul

The document discusses various algorithm design techniques, including brute force. It describes brute force as the simplest approach that directly solves a problem based on its definition. While brute force is widely applicable and simple, its algorithms tend to be inefficient. Examples given of brute force algorithms include selection sort, string matching, and exhaustive search. Selection sort is then explained in more detail, along with pseudocode. Brute force string matching is also explained, with pseudocode provided.

Breadth First Search & Depth First SearchKevin Jadiya

Recursion tree methodRajendran

- Recurrences describe functions in terms of their values on smaller inputs and arise when algorithms contain recursive calls to themselves. - To analyze the running time of recursive algorithms, the recurrence must be solved to find an explicit formula or bound the expression in terms of n. - Examples of recurrences and their solutions are given, including binary search (O(log n)), dividing the input in half at each step (O(n)), and dividing the input in half but examining all items (O(n)). - Methods for solving recurrences include iteration, substitution, and using recursion trees to "guess" the solution.

Greedy with Task Scheduling Algorithm.pptRuchika Sinha

Dynamic programmingShakil Ahmed

The document discusses dynamic programming and provides examples of problems that can be solved using dynamic programming including unidirectional traveling salesman problem, coin change, longest common subsequence, and longest increasing subsequence. Source code is presented for solving these problems using dynamic programming including dynamic programming tables, tracing optimal solutions, and time complexity analysis. Various online judges are listed that contain sample problems relating to these dynamic programming techniques.

Greedy AlgorihmMuhammad Amjad Rana

This document outlines greedy algorithms, their characteristics, and examples of their use. Greedy algorithms make locally optimal choices at each step in the hopes of finding a global optimum. They are simple to implement and fast, but may not always reach the true optimal solution. Examples discussed include coin changing, traveling salesman, minimum spanning trees using Kruskal's and Prim's algorithms, and Huffman coding.

Coding Concept.pptssuser3b64952

The document provides information on the TCS NQT exam structure and syllabus which includes sections on verbal ability, reasoning, numerical ability, programming logic, and hands-on coding questions in C/C++, Java, Perl, and Python. It also outlines the exam pattern for Capgemini which consists of online tests in pseudo code, English, behavioral questions, and games, followed by technical and HR interviews assessing programming concepts, operating systems, data structures, and DBMS. Sample coding problems and solutions are provided for finding the kth largest factor of a number and minimizing coin distribution to values between 1 to N.

DynamicProgramming.pptxSaimaShaheen14

Dynamic programming is a powerful technique for solving optimization problems by breaking them down into overlapping subproblems. It works by storing solutions to already solved subproblems and building up to a solution for the overall problem. Three key aspects are defining the subproblems, writing the recurrence relation, and solving base cases to build up solutions bottom-up rather than top-down. The principle of optimality must also hold for a problem to be suitable for a dynamic programming approach. Examples discussed include shortest paths, coin change, knapsack problems, and calculating Fibonacci numbers.

More Related Content

What's hot (20)

Divide and conquer - Quick sortMadhu Bala

Coin Change ProblemDEVTYPE

Greedy algorithmsRajendran

Greedy AlgorithmWaqar Akram

Greedy Algorithm - Knapsack ProblemMadhu Bala

Greedy algorithmssandeep54552

Traveling salesman problemJayesh Chauhan

Min-Max algorithmDr. C.V. Suresh Babu

Stressen's matrix multiplicationKumar

Analysis of algorithmRajendra Dangwal

Graph coloring using backtrackingshashidharPapishetty

Branch and boundDr Shashikant Athawale

Randomized Algorithm- Advanced AlgorithmMahbubur Rahman

Single source Shortest path algorithm with exampleVINITACHAUHAN21

04 brute forceHira Gul

Breadth First Search & Depth First SearchKevin Jadiya

Recursion tree methodRajendran

Greedy with Task Scheduling Algorithm.pptRuchika Sinha

Dynamic programmingShakil Ahmed

Greedy AlgorihmMuhammad Amjad Rana

Divide and conquer - Quick sortMadhu Bala

Coin Change ProblemDEVTYPE

Greedy algorithmsRajendran

Greedy AlgorithmWaqar Akram

Greedy Algorithm - Knapsack ProblemMadhu Bala

Greedy algorithmssandeep54552

Traveling salesman problemJayesh Chauhan

Min-Max algorithmDr. C.V. Suresh Babu

Stressen's matrix multiplicationKumar

Analysis of algorithmRajendra Dangwal

Graph coloring using backtrackingshashidharPapishetty

Branch and boundDr Shashikant Athawale

Randomized Algorithm- Advanced AlgorithmMahbubur Rahman

Single source Shortest path algorithm with exampleVINITACHAUHAN21

04 brute forceHira Gul

Breadth First Search & Depth First SearchKevin Jadiya

Recursion tree methodRajendran

Greedy with Task Scheduling Algorithm.pptRuchika Sinha

Dynamic programmingShakil Ahmed

Greedy AlgorihmMuhammad Amjad Rana

Similar to Coin Change : Greedy vs Dynamic Programming (20)

Coding Concept.pptssuser3b64952

DynamicProgramming.pptxSaimaShaheen14

dynamic-programming unit 3 power point presentationShrinivasa6

Introduction to Algorithm Design and Analysis.pdfKiran K

Linear ProgrammingPulchowk Campus

This document discusses linear programming techniques for managerial decision making. Linear programming can determine the optimal allocation of scarce resources among competing demands. It consists of linear objectives and constraints where variables have a proportionate relationship. Essential elements of a linear programming model include limited resources, objectives to maximize or minimize, linear relationships between variables, homogeneity of products/resources, and divisibility of resources/products. The linear programming problem is formulated by defining variables and constraints, with the objective of optimizing a linear function subject to the constraints. It is then solved using graphical or simplex methods through an iterative process to find the optimal solution.

Sienna 1 introchidabdu

This document introduces the topic of algorithms for a computer science course. It defines an algorithm as a step-by-step method for solving a problem and notes key properties like being unambiguous, terminating, and giving the correct output. The document gives examples of algorithms for finding the maximum of three numbers and computing greatest common divisors. It outlines some common algorithm design approaches and topics that will be covered in the course like graph algorithms and sorting.

32 algorithm-typesashish bansal

The document describes several types of algorithms. It discusses simple recursive algorithms, backtracking algorithms, divide and conquer algorithms, dynamic programming algorithms, greedy algorithms, branch and bound algorithms, brute force algorithms, and randomized algorithms. Examples are provided for each type of algorithm to illustrate how it works. The purpose is to highlight the different approaches that can be used to solve algorithmic problems.

Std 10 computer chapter 9 Problems and Problem SolvingNuzhat Memon

Std 10 computer chapter 9 Problems and Problem Solving Problem and Types of problem Problem solving Flowchart Symbols of flowchart Flowchart to calculate area of rectangle Flowchart to calculate area and perimeter of circle Flowchart to compute simple interest Flowchart to find youngest student amongst two students Flowchart to find youngest student amongst three students Flowchart to find youngest student amongst any number of students Flowchart to find sum of first 50 odd numbers Flowchart to interchange or swap values of two variables with extra variable Flowchart to interchange or swap values of two variables without extra variable Advantage and disadvantage of flowchart Algorithm Advantage of flowchart disadvantage of flowchart Algorithm Algorithm to find sum of numbers divisible by 11 in the range of 1 to 100 Algorithm to compute interest Algorithm to find total weekly pay of employee

Greedy algorithms -Making change-Knapsack-Prim's-Kruskal'sJay Patel

The document discusses greedy algorithms, which attempt to find optimal solutions to optimization problems by making locally optimal choices at each step that are also globally optimal. It provides examples of problems that greedy algorithms can solve optimally, such as minimum spanning trees and change making, as well as problems they can provide approximations for, like the knapsack problem. Specific greedy algorithms covered include Kruskal's and Prim's for minimum spanning trees.

Quantitativetechniqueformanagerialdecisionlinearprogramming 090725035417-phpa...kongara

The document provides information about linear programming, including: - Linear programming is a technique to optimize allocation of scarce resources among competing demands. It involves determining variables, constraints, and an objective function. - The linear programming model consists of linear objectives and constraints, where variables have a proportionate relationship (e.g. increasing labor increases output proportionately). - Essential elements of a linear programming model include limited resources, an objective to maximize or minimize, linear relationships between variables, identical resources/products, and divisible resources. - Linear programming problems can be solved graphically by plotting constraints and objective function to find the optimal point, or algebraically using the simplex method through iterative tables.

Coin change using dparfin97

GreedymethodMeenakshi Devi

The document discusses greedy algorithms, their characteristics, and an example problem. Greedy algorithms make locally optimal choices at each step in the hope of finding a global optimum. They are simpler and faster than dynamic programming but may not always find the true optimal solution. The coin changing problem is used to illustrate a greedy approach of always selecting the largest valid coin denomination at each step.

013-number-theory-properties-in-science.pdfverdemarco991

Daa unit 2jinalgoti

The document discusses the divide-and-conquer algorithm design paradigm. It defines divide-and-conquer as breaking a problem down into smaller subproblems, solving those subproblems recursively, and combining the solutions to solve the original problem. Examples of algorithms that use this approach include merge sort, quicksort, and matrix multiplication. Divide-and-conquer allows for problems to be solved in parallel and more efficiently uses memory caches. The closest pair problem is then presented as a detailed example of how a divide-and-conquer algorithm works to solve this problem in O(n log n) time compared to the brute force O(n2) approach.

Algorithm Using Divide And ConquerUrviBhalani2

Daa unit 2snehajiyani

The document discusses the divide-and-conquer algorithm design paradigm. It defines divide-and-conquer as breaking a problem down into smaller subproblems, solving those subproblems recursively, and combining the solutions to solve the original problem. Examples of algorithms that use this approach include merge sort, quicksort, and matrix multiplication. Advantages include solving difficult problems efficiently in parallel and with good memory performance. The document also provides an example of applying divide-and-conquer to the closest pair of points problem.

Kk20503 1 introductionLow Ying Hao

Dr. James Mountstephens will be teaching the Algorithm Analysis course this semester. He outlines some rules for lectures, including being punctual and not talking during lectures. He describes the course as crucial and difficult, covering complex topics. Students will have quizzes, assignments, a midterm, and final exam. The textbook is recommended reading. The first two lectures may be the hardest, covering introductions to algorithms and their analysis.

Should a football team go for a one or two point conversion? A dynamic progra...Laura Albert

The document discusses using dynamic programming to determine when an NFL team should attempt a one-point or two-point conversion after scoring a touchdown. It models the problem as a series of decisions based on the score differential and remaining possessions. The dynamic programming approach considers all possible outcomes at each stage and guarantees an optimal solution, without enumerating all possibilities. It formulates the problem as a longest path problem to maximize the probability of winning.

Dynamic Itemset CountingTarat Diloksawatdikul

Dynamic Itemset Counting (DIC) is an algorithm for efficiently mining frequent itemsets from transactional data that improves upon the Apriori algorithm. DIC allows itemsets to begin being counted as soon as it is suspected they may be frequent, rather than waiting until the end of each pass like Apriori. DIC uses different markings like solid/dashed boxes and circles to track the counting status of itemsets. It can generate frequent itemsets and association rules using conviction in fewer passes over the data compared to Apriori.

Dynamic Itemset CountingTarat Diloksawatdikul

Coding Concept.pptssuser3b64952

DynamicProgramming.pptxSaimaShaheen14

dynamic-programming unit 3 power point presentationShrinivasa6

Introduction to Algorithm Design and Analysis.pdfKiran K

Linear ProgrammingPulchowk Campus

Sienna 1 introchidabdu

32 algorithm-typesashish bansal

Std 10 computer chapter 9 Problems and Problem SolvingNuzhat Memon

Greedy algorithms -Making change-Knapsack-Prim's-Kruskal'sJay Patel

Quantitativetechniqueformanagerialdecisionlinearprogramming 090725035417-phpa...kongara

Coin change using dparfin97

GreedymethodMeenakshi Devi

013-number-theory-properties-in-science.pdfverdemarco991

Daa unit 2jinalgoti

Algorithm Using Divide And ConquerUrviBhalani2

Daa unit 2snehajiyani

Kk20503 1 introductionLow Ying Hao

Should a football team go for a one or two point conversion? A dynamic progra...Laura Albert

Dynamic Itemset CountingTarat Diloksawatdikul

More from Syeda Khadizatul maria (7)

MyselfSyeda Khadizatul maria

Syeda Khadizatul Maria is a 22-year-old student from Sirajgong who is currently a last semester student studying BSc in Computer Science and Engineering at Daffodil International University. She completed her secondary and higher secondary education at Monipur High School and BAF Shaheen College respectively. She enjoys spending time with her family and friends, reading books, drawing, watching movies, and traveling. Her future goals are to study abroad to gain international experiences and career opportunities.

Computer GraphicsSyeda Khadizatul maria

This presentation discusses 3D display methods. It is presented by 4 group members and covers topics such as parallel projection, perspective projection, depth cueing, visible line identification, visible surface identification, and surface rendering. Parallel projection discards the z-coordinate and extends parallel lines until they intersect the view plane, while perspective projection shows lines converging to give a realistic view. Depth cueing identifies the front and back of objects by varying intensity. Algorithms also determine which lines and surfaces are visible from the viewing position. Surface rendering sets intensities based on lighting and material properties.

Black box testingSyeda Khadizatul maria

This presentation introduces black box testing, which examines software functionality without knowledge of internal structures. Black box testing can find incorrect, missing, or interface errors, as well as errors in data access or behavior. Examples of systems suitable for black box testing include calculators, operating systems, websites, and databases. The presentation discusses techniques for black box testing like equivalence partitioning, boundary value analysis, decision tables, state transition testing, and error guessing. Advantages are that testing can be done efficiently on large systems by non-technical testers, while disadvantages include difficulty designing test cases without specifications and identifying all possible inputs.

HoneypotSyeda Khadizatul maria

A honeypot is a computer security mechanism designed to detect unauthorized access. It acts as a trap for attackers by diverting their attention from real network resources. The main functions of a honeypot are to build attacker profiles, identify preferred attack methods, and capture new viruses. Honeypots are classified by their level of interaction (low interaction provides emulated services while high interaction uses actual operating systems), implementation (physical vs virtual), and purpose (research to discover new attacks vs production to detect threats).

Gene expression-analysis Syeda Khadizatul maria

This presentation introduces gene expression analysis. It defines a gene as the basic unit of heredity made of DNA that codes for proteins. Gene expression analysis studies how genes are transcribed into RNA and translated into proteins. The central dogma of biology is explained as transcription of DNA to mRNA and translation of mRNA to proteins. Techniques for measuring gene expression at different levels like microarrays, RNA-Seq and reporter genes are also presented. Applications of gene expression analysis include cancer research and protein purification.

Book reviewSyeda Khadizatul maria

Currency converterSyeda Khadizatul maria

Syeda Khadizatul Maria created a currency converter program with modules to convert currencies, reset the converter, and exit the program. She designed the program using a JFrame in Netbeans IDE, adding buttons, labels, text fields and combo boxes. She wrote action listeners for the components, tested for bugs, and concluded that currency converters allow people to get the best exchange rates when traveling.

MyselfSyeda Khadizatul maria

Computer GraphicsSyeda Khadizatul maria

Black box testingSyeda Khadizatul maria

HoneypotSyeda Khadizatul maria

Gene expression-analysis Syeda Khadizatul maria

Book reviewSyeda Khadizatul maria

Currency converterSyeda Khadizatul maria

Recently uploaded (20)

How to Share Accounts Between Companies in Odoo 18Celine George

Final Evaluation.docx...........................l1bbyburrell

IPL QUIZ | THE QUIZ CLUB OF PSGCAS | 2025.pdfQuiz Club of PSG College of Arts & Science

CNS infections (encephalitis, meningitis & Brain abscessMohamed Rizk Khodair

LEONOR NA FASE CONCELHIA. _Colégio Santa Teresinha

How to Create Kanban View in Odoo 18 - Odoo SlidesCeline George

Module_2_Types_and_Approaches_of_Research (2).pptxdrroxannekemp

Redesigning Education as a Cognitive Ecosystem: Practical Insights into Emerg...Leonel Morgado

PUBH1000 Slides - Module 11: Governance for HealthJonathanHallett4

The History of Kashmir Karkota Dynasty NEP.pptxArya Mahila P. G. College, Banaras Hindu University, Varanasi, India.

This slide is an exercise for the inquisitive students preparing for the competitive examinations of the undergraduate and postgraduate students. An attempt is being made to present the slide keeping in mind the New Education Policy (NEP). An attempt has been made to give the references of the facts at the end of the slide. If new facts are discovered in the near future, this slide will be revised. This presentation is related to the brief History of Kashmir (Part-I) with special reference to Karkota Dynasty. In the seventh century a person named Durlabhvardhan founded the Karkot dynasty in Kashmir. He was a functionary of Baladitya, the last king of the Gonanda dynasty. This dynasty ruled Kashmir before the Karkot dynasty. He was a powerful king. Huansang tells us that in his time Taxila, Singhpur, Ursha, Punch and Rajputana were parts of the Kashmir state.

Cyber security COPA ITI MCQ Top QuestionsSONU HEETSON

How to Configure Extra Steps During Checkout in Odoo 18 WebsiteCeline George

Module 1: Foundations of Researchdrroxannekemp

The role of wall art in interior designingmeghaark2110

Wall art and wall patterns are not merely decorative elements, but powerful tools in shaping the identity, mood, and functionality of interior spaces. They serve as visual expressions of personality, culture, and creativity, transforming blank and lifeless walls into vibrant storytelling surfaces. Wall art, whether abstract, realistic, or symbolic, adds emotional depth and aesthetic richness to a room, while wall patterns contribute to structure, rhythm, and continuity in design. Together, they enhance the visual experience, making spaces feel more complete, welcoming, and engaging. In modern interior design, the thoughtful integration of wall art and patterns plays a crucial role in creating environments that are not only beautiful but also meaningful and memorable. As lifestyles evolve, so too does the art of wall decor—encouraging innovation, sustainability, and personalized expression within our living and working spaces.

How to Manage Amounts in Local Currency in Odoo 18 PurchaseCeline George

COPA Apprentice exam Questions and answers PDFSONU HEETSON

Look Up, Look Down: Spotting Local History EverywhereHistory of Stoke Newington

U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptxMayuri Chavan

puzzle Irregular Verbs- Simple Past TenseOlgaLeonorTorresSnch

Myasthenia gravis (Neuromuscular disorder)Mohamed Rizk Khodair

How to Share Accounts Between Companies in Odoo 18Celine George

Final Evaluation.docx...........................l1bbyburrell

IPL QUIZ | THE QUIZ CLUB OF PSGCAS | 2025.pdfQuiz Club of PSG College of Arts & Science

CNS infections (encephalitis, meningitis & Brain abscessMohamed Rizk Khodair

LEONOR NA FASE CONCELHIA. _Colégio Santa Teresinha

How to Create Kanban View in Odoo 18 - Odoo SlidesCeline George

Module_2_Types_and_Approaches_of_Research (2).pptxdrroxannekemp

Redesigning Education as a Cognitive Ecosystem: Practical Insights into Emerg...Leonel Morgado

PUBH1000 Slides - Module 11: Governance for HealthJonathanHallett4

The History of Kashmir Karkota Dynasty NEP.pptxArya Mahila P. G. College, Banaras Hindu University, Varanasi, India.

Cyber security COPA ITI MCQ Top QuestionsSONU HEETSON

How to Configure Extra Steps During Checkout in Odoo 18 WebsiteCeline George

Module 1: Foundations of Researchdrroxannekemp

The role of wall art in interior designingmeghaark2110

How to Manage Amounts in Local Currency in Odoo 18 PurchaseCeline George

COPA Apprentice exam Questions and answers PDFSONU HEETSON

Look Up, Look Down: Spotting Local History EverywhereHistory of Stoke Newington

U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptxMayuri Chavan

puzzle Irregular Verbs- Simple Past TenseOlgaLeonorTorresSnch

Myasthenia gravis (Neuromuscular disorder)Mohamed Rizk Khodair

Coin Change : Greedy vs Dynamic Programming

1. WELCOME TO OUR PRESENTATION

2. GROUP MEMBER LIST  Abu Nowshad Rasel 161-15-6861  Shahrun Siddique Taki 161-15-7195  Syeda Khadizatul Maria 161-15-7333  Md. Mehedi Hassan 161-15-7338

3. Coin Change : Greedy vs Dynamic Programming PRESENTATION TOPIC

4. Greedy Algorithm  What is greedy algorithm ?  An algorithm is greedy if it builds a solution in small steps , choosing a decision at each step myopically[=locally, not considering what happen ahead to optimize some underlying criterion.  It is easy to design a greedy algorithm for a problem . There may be different ways to choose the next step locally.

5. Coin Change Problem Coin Change is the problem of finding the number of ways of making changes for a particular amount of taka, n, using a given unlimited amounts of coins. Example : Available coins : ৳1, ৳5, ৳10, ৳25 Make change : ৳48 ∴ 48 - 25 = 23 → 23 - 10 = 13 → 13 - 10 = 3 → 3 - 1*3 = 0 → 25 10 10 111

6. Result :  Number of coins requires to make change to 48 = 6  Coin set = { 1,1,1,10,10,25 }

7. Advantage of greedy #Greedy is easy to be implemented. Just search the Best choice from the current state that reachable . #In simple case, greedy often give the best solution.

8. Failure of Greedy Algorithm A greedy algorithm is a simple but in many problems, a greedy strategy does not produce an optimal solution. The greedy algorithm fails to find optimal solution in some case, because it makes decisions based only on the information it has at any one step, and without regard to the overall problem. In coin change problem , if every coin is a multiple of all smaller coins, then we can use greedy approach to get the optimal solution.

9. In some fictional monetary system : Available coins : 1,7,10 Make change :15 taka ∴ 15 - 10 = 5 → 5 - 1*5 = 0 → This requires six coins . A better solution would be to use two 7 taka and one 1 taka + + = 15 This only requires three coins 10 1 1 1 1 1 7 7 1 For example :

10. Available coins : 4,10,25 Make change : 41 taka ∴ 41 - 25 = 16 → 16 - 10 = 6 → 6- 4 = 2 → 2 → ?? In this case , greedy algorithm fail to solve . But the required result is one 25 taka and four 4 taka. So the greedy algorithm does not give an optimal solution always. 25 10 4 Another example:

11. Dynamic Programming Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions DP is used to solve problems with the following characteristics:  Simple Subproblems  Optimal structure of the problems  Overplapping sub-problems

12. Dynamic Programming Solution (4 steps)  1. Characterize the structure of an optimal solution.  2. Recursively define the value of an optimal solution.  3. Compute the value of an optimal solution in a bottom-up fashion.  4. Construct an optimal solution from computed information

13. Greedy vs. DP  Similarities Optimization problems Optimal substructure Make choice at each step Differences  Dynamic Programming is Bottom up while Greedy is top-down -Optimal substructure Dynamic programming can be overkill; greedy algorithms tend to be easier to code

14. Coin Change With Dynamic Programming  Make a change, Total = 6  Available Coin Set = { 2, 3, 5 } T[i] [j] is the 2D array to denote the minimum number of coins require to make the change Coin[i] is the sorted array of available coin sets. [Index Start from 1]  If V == 0, then 0 coins required. T[i][j] = 0  If V > 0 Case 1: T [i][j] = T [i-1][j] If Coin[i] is not takes Case 2: T [i][j] = 1 + T [i] [j–Coin [i]] If Coin[ i ] is taken

15. T [i][j] = MIN ( T [i-1][j] , 1 + T[i][j-Coin[i] ) 0 1 2 3 4 5 6 2 3 5 0 0 0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 ∞ 2 ∞ 3 ∞ ∞ 1 1 2 1 2 1 1 2 2 2

16. Result:  Number of Coins requires to make a change to 6 = 2  Coin Set = { 3, 3 }

17. Thank You

Coin Change : Greedy vs Dynamic Programming

Recommended

More Related Content

What's hot (20)

Similar to Coin Change : Greedy vs Dynamic Programming (20)

More from Syeda Khadizatul maria (7)

Recently uploaded (20)

Coin Change : Greedy vs Dynamic Programming