CSCI 3104
Algorithms
Sptring 1996
Class notes
Page 12
Previous page || Next page
Friday, March 15, 1996
Exam 1
Open book, open notes. There are five questions,
each problem is worth 8 points.
Please write your name at the top of this page.
Consider this optimization problem:
You have an amount of time, T, in which you
can carry out tasks. A set of
n different tasks are available
and you have to choose which ones you
are going to carry out.
You know how long each task takes.
The goal is to make use of all of your time T.
Be sure you understand the goal.
It is to select a
subset of tasks whose times add up to no more than T
and as close to T as possible.
You cannot carry out a task more than once.
All times are integers. For notation
let the given tasks be numbered 1, 2, ... , n, and let
T[i] be the time that task i takes.
1.
How many potential solutions would an
exhaustive search algorithm go through?
2.
In one or two sentences, describe
a greedy approach to this problem.
3.
In one or two sentences, describe
a local optimization approach to this problem.
4.
Describe a dynamic programming approach
to this problem by describing the
subproblems that arise: what are their parameters,
and what constitutes a solution to a subproblem.
5.
In your dynamic programming approach, how many
different subproblems are there?
Previous page || Next page
Copyright © 1996
Karl Winklmann
Last edited (or copied to this place) at 2:04 PM, Friday, March 15, 1996.