Primary Task Response: Within the answers area, write 500–700 words that respond

Question

Primary Task Response: Within the answers area, write 500–700 words that respond to the following questions with your thoughts, ideas, and comments.Be substantive and clear, and use examples to reinforce your ideas.

Discuss and analyze the greedy paradigm. This paradigm, like divide and conquer, is fairly intuitive, and programmers likely use it in their everyday lives. Complete the following:

Discuss 2 scenarios where you use or might use this scheme in everyday life.

Be sure to detail the constraints of the scenario, and detail how and why your approach is a greedy approach.

Explanation / Answer

Algorithm Design Paradigms: General approaches to the construction of efficient solutions to problems.

Such methods are of interest because:

Although more than one technique may be applicable to a specific problem, it is often the case that an algorithm constructed by one approach is clearly superior to equivalent solutions built using alternative techniques.

Greedy Algorithms "take what you can get now" strategy

The solution is constructed through a sequence of steps, each expanding a partially constructed solution obtained so far. At each step the choice must be locally optimal – this is the central point of this technique.

Examples:

Minimal spanning tree
Shortest distance in graphs
Greedy algorithm for the Knapsack problem
The coin exchange problem
Huffman trees for optimal encoding

Greedy techniques are mainly used to solve optimization problems. They do not always give the best solution.

Example:

Consider the knapsack problem with a knapsack of capacity 10 and 4 items given by the < weight :value> pairs: <5:6>, <4:3>, <3: 5>, <3: 4>. The greedy algorithm will choose item1 <5:6> and then item3 <3:5> resulting in total value 11, while the optimal solution is to choose items 2, 3, and 4 thus obtaining total value 12.

It has been proven that greedy algorithms for the minimal spanning tree, the shortest paths, and Huffman codes always give the optimal solution.

Optimisation Problems

In contrast to dynamic programming, however,

In order to give a precise description of the greedy paradigm we must first consider a more detailed definition of the environment in which typical optimisation problems occur. Thus in an optimisation problem, one will have, in the context of greedy algorithms, the following:

In other words: An optimisation problem involves finding a subset, S, from a collection of candidates, C; the subset, S, must satisfy some specified criteria, i.e. be a solution and be such that the objective function is optimised by S. `Optimised' may mean

Divide-and-Conquer, Decrease-and-Conquer

These are methods of designing algorithms that (informally) proceed as follows:

Given an instance of the problem to be solved, split this into several smaller sub-instances (of the same problem), independently solve each of the sub-instances and then combine the sub-instance solutions so as to yield a solution for the original instance.

With the divide-and-conquer method the size of the problem instance is reduced by a factor (e.g. half the input size), while with the decrease-and-conquer method the size is reduced by a constant.

Examples of divide-and-conquer algorithms:

Computing an (a > 0, n a nonnegative integer) by recursion
Binary search in a sorted array (recursion)
   Mergesort algorithm, Quicksort algorithm (recursion)
The algorithm for solving the fake coin problem (recursion)

Examples of decrease-and-conquer algorithms:

Insertion sort
Topological sorting
Binary Tree traversals: inorder, preorder and postorder (recursion)
Computing the length of the longest path in a binary tree (recursion)
Computing Fibonacci numbers (recursion)
Reversing a queue (recursion)
Warshall’s algorithm (recursion)

The issues here are two:

The answer to the second question depends on the nature of the problem.

In most cases the answer to the first question is: using the same method. Here another very important issue arises: when to stop decreasing the problem instance, i.e. what is the minimal instance of the given problem and how to solve it.

When we use recursion, the solution of the minimal instance is called “terminating condition”

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.