Name: _ ID: _

Q1 Q2 Q3 Q4 Q5 Q6 SUM

/25 /20 /15 /15 /25 /20 /100

CSE 2046 Analysis of Algorithms

Spring 2020
Online Homework 2

Solution and Submission Notes

• Textbooks, slides, and notes are open.

• Internet usage is not allowed; however, computers and smartphones may be used for viewing
course materials provided for this course.
• Write your name, surname and student ID on the top of each exam solution page.
• Show all your work.
• Write the following sentence on the top of the first page with your handwriting and sign it:
“On my honor, I have neither given nor received any unauthorized assistance on this
examination.”
• Either print this PDF file (6 pages) or use blank A4 pages for your solutions. Solve all the
questions with your handwriting.
• Scan all the solution pages to a single PDF file named “firstname_lastname.pdf”. Do not
include raw photos, use an Android/IOS scanner application. All the writings should be very
readable. Page layouts should be portrait, not landscape.
• Upload the PDF file to https://ues.marmara.edu.tr system before the deadline. Give at least
15-20 minutes for scanning and upload process.

Page 1 / 8
Name: _ ID: _

On my honor, I have neither given nor received any unauthorized assistance on this examination.

Name Surname:________________________

Signature:________________________

Q-1. (25 pts) (a – 7 pts) How many character comparisons will the Horspool algorithm make in
searching the pattern 110110 in the binary text of 1000 zeros? (Do not forget to show the shift
table)

(b – 9 pts) How many character comparisons will the Boyer-Moore algorithm make in searching
the pattern 110110 in the binary text of 1000 zeros? (Show bad-symbol and good-suffix tables)

(c – 9 pts) For a binary text of n zeros, is it possible to have a pattern where bad symbol shift
is more than good suffix shift, i.e. d1>d2 ? If yes, show an example. If no, prove it.

Page 2 / 8
Name: _ ID: _

Q-2. (20 pts) Consider a staircase with n steps. Steps are indexed from 0 to n-1. Each step i
has some non-negative cost, cost[i]. A robot wants to climb these stairs. Once it pays the
cost, it can either climb one or two steps. Describe a dynamic programming algorithm to find
minimum cost to reach the top of the floor. Robot can either start from the step with index 0,
or the step with index 1. Following are some example inputs and outputs.

Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Minimum cost is obtained when the robot starts on cost[1], pay that cost and go to
the top.

Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Minimum cost is obtained when the robot starts on cost[0], and only step on 1s,
skipping cost[3].

Hint: Define f[i] as the final cost to climb to the top from step i. Find a recurrence relation for
f[i].

Page 3 / 8
Name: _ ID: _

Q-3. (15 pts) Apply the shortest augmenting path algorithm to find the maximum flow (source
is 1 and sink is 6).While applying BFS, visit the neighbors in alphabetical order. Show the labels and
BFS queue clearly in each iteration.

Also give the minimum cut that is found by your algorithm.

Page 4 / 8
Name: _ ID: _

Q-4. (15 pts) Use Huffman Coding to encode the following DNS string and find the
compression ratio.
AGATAACCATCGAAACAAAATCAAATA
(Note: You are expected to extract the statistical knowledge from the input itself.)

Page 5 / 8
Name: _ ID: _

Q-5. (25 pts) Consider a modified version of Assignment problem. There are n agents and m tasks
(where m≤n+1). Any agent can be assigned to perform any task, incurring some cost that may vary
depending on the agent-task assignment. It is required to perform ALL TASKS EXCEPT ONE (it
is enough to perform m-1 tasks) by assigning exactly one agent to each task in such a way that
the total cost of the assignment is minimized. Note that, some of the agents may not be assigned
to any task and stay idle.
(a – 15 pts) For the following utility matrix, define a bounding function and apply a best-first
branch-and-bound algorithm.

Task 1 Task 2 Task 3 Task 4

Agent a 1 2 6 5
Agent b 7 3 9 5
Agent c 4 4 7 3
Agent d 3 5 8 6

Page 6 / 8
Name: _ ID: _

(b – 10 pts) Describe a greedy algorithm for the above problem and apply your algorithm for the
same instance. What is the accuracy ratio for this instance? Show whether the performance ratio of
your greedy algorithm is unbounded above or not. (Prove your answer).

Task 1 Task 2 Task 3 Task 4

Agent a 1 2 6 5
Agent b 7 3 9 5
Agent c 4 4 7 3
Agent d 3 5 8 6

Page 7 / 8
Name: _ ID: _

Q-6. (20 pts) Lower Bound, P, NP, NP-Complete, Approximation.

(a – 7 pts) Suppose that we have n entries of mobile phones in an electronic store. These phones are
of 5 different brands. We want to sort these phone entries according to their brands. What is the
trivial lower bound of this sorting problem? Is this lower bound tight? Why?

(b – 4 pts) Mr. Safi claims that he finds an algorithm with O(2n) time complexity for TSP problem
with a performance ratio of 2 for Euclidian instances. What would be your your comment?

(c – 9 pts) It is proven that sorting problem can be reduced to Problem X, and Problem X can be
reduced to Traveling Salesman Problem (TSP). All reductions can be done in linear (O(n)) time. For
each of the following, indicate whether it is True, False, or Unknown. Describe your reasoning
(otherwise your answer will not be graded).
(i) Problem X may be solved by an algorithm with linear time complexity.

(ii) Problem X is NP-Complete (or NP-Hard).

(iii) Problem X can be reduced to Knapsack Problem in polynomial time.

Page 8 / 8