COMP-4540/8540
Design and Analysis of Algorithms
Winter 2022
Assignment 2
Due Date: March 21 (Monday) (before 11:59p.m.)
In doing any problem involving algorithm design, you must provide the following for each algorithm
you design:
• A clear description of the key idea underlying the algorithm;
• A correctness proof of the algorithm;
• A time complexity analysis of the algorithm.
Missing any of the above will result in receiving a zero mark regardless whether the algorithm is correct.
—————————————————————————————————————————————–
1. Given an n×n matrix M in which every entry is either a 0 or 1. Present an algorithm that determines
if ∃i, 1 ≤ i ≤ n, such that M [i, j] = 0 and M [j, i] = 1, ∀j, 1 ≤ j ≤ n ∧ j 6= i, using examining an
entry of M as the key operation. Your algorithm must examine at most 3n−⌊lg n⌋− 3 entries of M .
2. For the problem in Question 1, use an adversary argument to prove that 3n − ⌊lg n⌋ − 3 is a lower
bound.
3. Given n non-vertical lines in the plane L = {Li | 1 ≤ i ≤ n} such that no two lines are parallel, no
three lines intersect at a point, and Li is represented by y = mix+ bi (recall that mi is the slope of
Li). A point p = (xp, yp) on a line Li is y-visible if yp > yq for all other points q lying on other lines
in L with xq = xp. A line Li is y-visible if it contains a y-visible point. Present an algorithm that
takes L as input and returns all the y-visible lines as output in O(n lg n) time.
1