Description
1. (20 pts) You are given an infinite array A that contains n integers in the first n positions
(indexing starts with 1) and ∞ in all other positions. You do not know the value of n. Your
task is to design an iterative algorithm that finds the value of n using O(log n) accesses to
array A. Asymptotically slower solutions receive the grade of 0.
(a) Describe your algorithm in plain English (maximum 5 short sentences).
(b) Describe your algorithm in pseudocode.
(c) For each loop in your algorithm, state a useful loop invariant (without proof). State
the corresponding termination condition(s) and how correctness follows from the termination condition(s).
(d) Argue that the running time is O(log n) (as measured by the number of accesses to
array A). Mention the running time of each logical block of your algorithm.
2. (20 pts) You are given an array A of n images. Some of these images might be identical. For
i 6= j ∈ [n] you can invoke a comparison procedure that returns whether the images A[i] and
A[j] are identical or not. This procedure is denoted by A[i] == A[j]. Design a divide and
conquer algorithm to decide whether there is an image that appears more than n/2 times
in A using O(n) invocations of the comparison procedure. Solutions using asymptotically
more invocations of the comparison procedure receive the grade of 0.
(a) Describe your algorithm in plain English (maximum 5 short sentences).
(b) Describe your algorithm in pseudocode.
(c) Provide a concise argument of correctness of your algorithm.
(d) State the recurrence of the number of invocations of the comparison procedure (do not
forget the base case).
3. (20 pts) You are given two arrays D (of positive integers) and P (of positive reals) of size
n each. They describe n jobs. Job i is described by a deadline D[i] and profit P[i]. Each
job takes one unit of time to complete. Job i can be scheduled during any time interval
[t, t + 1) with t being a positive integer as long as t + 1 ≤ D[i] and no other job is scheduled
during the same time interval. Your goal is to schedule a subset of jobs on a single machine
to maximize the total profit – the sum of profits of all scheduled jobs. Design an efficient
greedy algorithm for this problem.
(a) Describe your algorithm in plain English (maximum 5 short sentences).
(b) Describe your algorithm in pseudocode.
(c) Formally prove correctness of your greedy procedure. You may use the framework
introduced in class – argue by induction that the partial solution constructed by the
algorithm can be extended to an optimal solution.
1 of 2
CSC373, Assignment 1
(d) Analyze the running time of your algorithm (in terms of the total number of operations).
4. (20 pts) You are given an array A of n ≥ 3 points in the Euclidean 2D space. The points
A[1], A[2], . . . , A[n] form the vertices (in clockwise order) of the convex polygon P. A triangulation of P is a collection of n − 3 interior diagonals of P such that the diagonals do
not intersect except possibly at the vertices. The total length of a triangulation of P is the
sum of the lengths of the n − 3 interior diagonals used to form that triangulation. Design
an efficient dynamic programming algorithm to find the total length of a triangulation with
the minimum total length.
(a) Describe the semantic array.
(b) Describe the computational array. Don’t forget the base case.
(c) Justify why the above two arrays are equivalent.
(d) What is the running time of your algorithm (as measured by the total number of
operations)?
5. (20 pts) You are a manufacturer of chocolate goods. You start with a large rectangular
chocolate bar that consists of W × H tiles arranged into W rows and H columns. You
have a machine that can make a horizontal or a vertical break along tile edges. There are n
possible goods that you can manufacture. Good i is described by wi
, hi and pi
. This means
that manufacturing good i requires a rectangular chocolate bar consisting of exactly wi × hi
tiles (wi rows and hi columns). The value of pi
is how much profit you can make from good
i. You can manufacture the same good more than once. What is the maximum overall
profit that you can get starting with the large rectangular chocolate bar, performing a series
of break operations, and manufacturing goods? Design an efficient dynamic programming
algorithm. Note: W, H, wi
, hi are positive integers and the pi are reals.
(a) Describe the semantic array.
(b) Describe the computational array. Don’t forget the base case.
(c) Justify why the above two arrays are equivalent.
(d) What is the running time of your algorithm (as measured by the total number of
operations)?
2 of 2
