Analysis
We are tasked with designing an algorithm that detects and lists peaks of interest for a video.
However, we need clarification on what constitutes a peak of interest, beyond what’s outlined in
the problem statement. We also need know what intensity data means, based on what’s
contained in the requirements. We can assume that identified peaks will be used for generating
a thumbnail library. This assumption is reasonable because the problem statement outlines the
end goal being to come closer to an algorithm that can auto-generate thumbnails for videos.
We can also assume that frames that contain high contrast colors, rapidly changing colors
between one frame and the next, and implied motion (say, a figure hovering in mid-air) would
meet the peak-of-interest criteria. This is reasonable because we can view metrics of thumbnails
from example videos, the metrics of what moments get viewed the most could be viewed
directly and this may satisfy our question about what constitutes a peak of interest. One other
assumption we can make is that the peaks of interest will be specific frames from which to
generate a thumb nail. This assumption is reasonable because the specs for the problem
suggest that this would be the use case.
An issue that could arise is that when dealing with lengthy videos(30+ minutes, which generate
arrays of at least 1800 elements), which is the space complexity the operation entails. A
connected issue is the performance of the algorithm when parsing arrays of such a size. This
means that the peaks of interest would have to be ranked in order to exclude under a certain
interest rating, say a rating of 90. An array would be used, and when filled with frames that rate
at or above the interest threshold, algorithm would return that array with the result of narrowing
down interest peaks.
Design
The algorithm would resemble the pseudo-code below.
void interestPeaks(int[] values, int count):
integer interestThreshold = 90 //Set the minimum interest peak threshold
Integer[] peaks = new array[] //Peaks of interest exceeding 90 will be stored here
count = values.length
For i = 0 to values.length: //Loop for finding peaks of interest meeting the threshold
If values[i] ≥ interest: //Test each element to see if it meets the threshold
For j = 0 to peaks.length:
Peaks[j] = values[i] //Add the element to the peak
count–
Justification
Our design is the best design because the interest peak threshold would be hardcoded, and this
is an advantage because realistically videos would generate enough data that to exclude peaks
of interest below 90(based on the problem spec) would not negatively impact the number of
frames that could serve as thumbnails.
ADJ Problem set 2, Rob Feil
Analysis
We are being asked to design an algorithm to efficiently merge two priority queues(definition 5).
To start with, we can assume the resultant priority queue(PQ) will be a max PQ(definition 5)
utilizing the implementation shown in K. This is reasonable because K specifies a heap-ordered
PQ(definition 4). Another assumption is that the input PQs will be valid PQs. This is reasonable
because the goal is ensuring the merged structure does not violate heap order. Per definition 3,
that means an element within a max PQ would need to be moved to a different location within
the structure to preserve max heap rules.
The problem prompt tells us the algorithm should be efficient, and should be measured by these
metrics:
● M1: Algorithm efficiency: our metric would use the number of comparisons and
exchanges as a measure of computational time for a design.
● M2: Algorithm’s ability to maintain a heap-sorted array while keeping the number of
nodes that violate the heap rule(definition 3), and produce a heap-sorted array without
violating the max heap rule(definition 4).
Design
Our algorithm will resemble the following pseudocode:
void update(Value value, Key key)
target = NULL
array values = new array
for i = 0 to n - 1:
if values[i] = value
target = i
if target = NULL
return
keys[target] = new_PQ
if keys[target/2] new_PQ:﹤
swim(target)
else if new_PQ ﹤ max(keys[2 * target], keys[2 * target] + 1):
sink(target)
Justification
To show correctness of design(M2) and efficiency(M1), consider:
● Tree containing a node with the value: Since the data structure is a PQ, the tree will be
complete prior to the algorithm running