CSCI 3110 Design and Analysis of Algorithms I - Assignment 6

• 作业标题：CSCI 3110 - Assignment 6
• 课程名称：Dalhouse University CSCI 3110 Design and Analysis of Algorithms I
• 完成周期：2天

Instructions:

1. Before starting to work on the assignment, make sure that you have read and understood policies regarding the assignments of this course, especially the policy regarding collaboration. https://dal.brightspace.com/d2l/le/content/230447/Home?
   itemIdentifier=D2L.LE.Content.ContentObject.ModuleCO-3221550

2. Submit a PDF file with your assignment solutions via Brightspace. If you have not
   used Brightspace for assignment submission before, you may find the the following
   documentation for Brightspace useful: https://documentation.brightspace.com/
   EN/le/assignments/learner/submit_assignments.htm

3. If you submit a joint assignment, only one person in the study group should make the
   submission. At the beginning of the assignment, clearly write down the names and
   student IDs of the up to three group members.

4. We encourage you to typeset your solutions using LaTeX. However, you are free to
   use other software or submit scanned handwritten assignments as long as they are
   legible. We have the right to take marks off for illegible answers.

5. You may submit as many times as needed before the end of the grace period. A
   good strategy is to create an initial submission days in advance after you solve some
   problems, and make updates later.

1. Questions:

1. [10 marks] When introducing Euclid’s algorithm in class, I made use of the following
   claim: Let d, u and v be positive integers. We have d|u and d|v if and only if d|v and
   d|(u mod v).
   Now prove this claim.
   Hint: Make sure to prove both the “if” and “only if” in this claim. Recall that in
   class, we say d divides u if there exists an integer k, such that u = kd. This definition
   is useful. The following identity mentioned in class is also useful:
   u mod v = u − v⌊u/v⌋

2. [10 marks] Consider the weighted, connected and undirected graph G in Fig1
   Write down the edges of a minimum spanning tree of G constructed using Kruskal’s
   algorithm, in the order that they are selected by Kruskal’s algorithm.
   You can use (a, b) to denote an edge between vertices a and b.
   You need not actually draw the tree or show your steps

3. [10 marks] In the string metamorphosis problem, you are given two strings x[1..m] and
   y[1..n]. Your task is to determine the least costly way to transform x into y by
   a left-to-right scan of x while performing operations that affect individual symbols:
   copy, insert, delete and replace.

For example, the following is one way of transforming Delicious into Dalhousie:

copy the D
replace the e with a
copy the l
replace the i with h
delete the c and i
copy the o, u and s
insert i and e.

It is probably best to think of this process as follows: Use an array z to store intermediate results. Initially, z is empty, and when this process terminates, z = y. We use
indices i and j to keep track of the progress that we have made in x and z, respectively.
Initially, i = j = 1, and when we finish, we have i = m + 1, j = n + 1. During the
left-to-write scan of x,
A copy sets z[j] ← x[i] and increments both i and j.
A replace sets z[j] ← c for some character c, and increments both i and j.
A delete increments i only.
An insert sets z[j] ← c for some character c, and increments j.

。。。