CSCI 3110 Design and Analysis of Algorithms I - Assignment 2

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

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. [12 marks] Order all the following twelve functions by order of growth from slowest
   to fastest. That is, find an arrangement f1(n), f2(n), . . . , f12(n) of these functions
   such that f1 = O(f2(n)), f2 = O(f3(n)), . . . , f11 = O(f12(n)). Partition your list into
   groups such that two functions f(n) and g(n) are in the same group if and only if
   f(n) = Θ(g(n))

2. [8 marks] The following is the pseudocode of the algorithm maxsubrangesum1 for the
   maximum subrange sum problem shown in class:
   maxsubrangesum1(x, n)

1: max ← 0
2: for lower ← 1 to n do
3:     for upper ← lower to n do
4:         sum ← 0
5:     for i ← lower to upper do
6:         sum ← sum + x[i]
7:     if sum > max then
8:         max ← sum
9: return max

3. [10 marks] Consider the following problem:
   Input: an array, A, of n integers (positive, negative, or 0).
   Output: two indices i and j, with 1 ≤ i ≤ j ≤ n, such that the subrange sum
   ai + ai+1 + · · · + aj is closest to 0 (i.e., such that |ai + ai+1 + · · · + aj| is minimized).
   Note that we do not allow empty subranges in this version of the problem. If there are
   multiple solutions with the same subrange sum, just return one.

。。。