SAN FRANCISCO STATE UNIVERSITY

Computer Science Department

CSC510 Section 04 – Analysis of Algorithms

Algorithm Challenge 1: Complexity Functions

Instructor: Jose Ortiz

08/04/2020

Full Name:                                                                                            

Student ID:                                                                                           

Assignment Instructions. Must read!

Note: Failure to follow the following instructions in detail will impact your grade negatively.

1. This algorithm challenge is worth 9%, and will be graded using a grading point scale where the maximum possible grade is 100 points. For instance, if your grade in this assignment is 85/100, then this is equivalent to 0.85*9%=7.65% of 10%

2. The deadline of this assignment will be announced by the instructor in class.

3. Each section of this algorithm challenge is worth 25 points

4. Take into account that in this type of assignments, I am more interested in the way you approach the problem rather than in your final solution.

Problem Statement

1. Create an optimized function “print s(n,s)” that prints the given argument s (representing a string) k times. k represents the number of iterations of the inner loop. The print statement that prints s is in the inner loop of the function

(a) Initial conditions: i = 1, j = 1, i <= n, and j <= i

(b) i and j increments: i = i + 1 and j = j ∗ 2

(c) input as arguments in the function: n (an integer representing the size of the input), and s (the string)

(d) output: print s k times

(e) example: n=5, s=”hello CSC510-01 class”, given these conditions, the function “print s(n,s)” will print s 11 times

Your work here

1. Describe the algorithm to solve the problem. Note that you must show all your work (e.g including summations)

(a) Use n=5 as your base example to create the algorithm

(b) Refine your algorithm from (a) to cover all the cases for any given n size

(c) Finally, based on (b) state the complexity of your algorithm as (1) A complexity function T(n), and (2) time complexity with big O notation

2. Write the pseudocode to that represents the algorithm in part (1) for T(n)

3. Provide an optimization for the pseudocode in part (2). Note that there is always a way to optimize your algorithm. I want you to think hard about this.

4. Create/implement the code based on your optimized pseudocode from part (3). You are free to use your favorite programming language in this problem. For this part you are allowed to type your code, copy and paste, or screenshots of your code.