Data Structures for Computer Scientists
Text Processing: Lecture 2
Dr. Franc Brglez, Computer Science, NCSU
11 April 2005
(click here for the course home page)
(Textbook: Data Structures and Algorithms in Java, 3rd Edition)
(Package that made these slides possible: Prosper)
CSC316-001 – Data Structures for Computer Scientists: Text Processing: Lecture 2 – p.1/2
Lecture Outline
greeedy methods
0-1 knapsack problem (exam)
fractional knapsack problem
text compression problem (exam)
task scheduling problem
CSC316-001 – Data Structures for Computer Scientists: Text Processing: Lecture 2 – p.2/2
© 2004 Goodrich, Tamassia Greedy Method and Compression 2
The Greedy Method
Technique (§ 11.4.2)
The greedy method is a general algorithm
design paradigm, built on the following
elements:
configurations: different choices, collections, or
values to find
objective function: a score assigned to
configurations, which we want to either maximize or
minimize
It works best when applied to problems with the
greedy-choice property:
a globally-optimal solution can always be found by a
series of local improvements from a starting
configuration.
The 0/1 knapsack problem
Given a knapsack and a set of n items of some weight and
profit, choose a subset that does not exceed the maximum
weight of W and maximizes the cumulative profit function.
Let wi, pi be the weight and profit, and xi the decision variable
associated with associated with the i-th item. Here, xi = 1 if
item is placed into the knapsack, and xi = 0 otherwise.
The objective (profit) function to be maximized is
Pn
i=1 pixi, subject to Pn
i=1 wixi W
Here, the runtime of ’brute-force’ method is O(2n), prohibitive
as n gets large.
We need to consider ‘greedy solutions strategies’ that may or
may not always lead to a ’globally optimum solutions’.
. – p.1/5
