Overview

Analyze and synthesize pseudocode for an IT company.

Context

The Assessment 4 Context document contains information about algorithms, including recursion, as well as pseudocode and basic programming principles.

Resources

Suggested Resources

The following optional resources are provided to support you in completing the assessment or to provide a helpful context. For additional resources, refer to the Research Resources and Supplemental Resources in the left navigation menu of your courseroom.

• Binary and Hexadecimal Expansions and Operations.
  • Read this document to learn about binary, decimal, and hexadecimal number systems and Microsoft Excel’s conversion tool.

• Algorithms | Transcript.
  • This presentation includes the following topics:
    • Characteristics of algorithms.
    • Notation for algorithms.
    • The Euclidean algorithm.
    • Recursive algorithms.
    • Complexity of algorithms.
• Number Theory and Recurrence Relations | Transcript.
  • This presentation includes the following topics:
    • Number systems.
    • Hexadecimal number system.
    • Recurrence relation.
    • Fibonacci sequence.
    • Towers of Hanoi.
    • Solving recurrence relations.

Library Resources

The following e-book from the Capella University Library is linked directly in this course:

• Koshy, T. (2004). Discrete mathematics with applications. Burlington, MA: Elsevier Academic Press.
  • Chapters 4 and 5.

The resource listed below is relevant to the topics and assessments in this course and is not required. Unless noted otherwise, this resource is available for purchase from the.

• Johnsonbaugh, R. (2018). Discrete mathematics (8th ed.). New York, NY: Pearson.
  • The following chapters and sections are particularly useful for your work in this assessment.
    • Chapter 4, “Algorithms,” sections 4.1 through 4.3. This chapter allows you to look at examples of algorithms, analyze algorithms, and work with recursive algorithms.
    • Chapter 4, “Algorithms,” sections 4.3 and 4.4. Section 4.4 focuses on recursive algorithms.
    • Chapter 5, “Introduction to Number Theory.” This chapter focuses on divisors, representations of integers and integer algorithms, the Euclidean algorithm, and the RSA public-key cryptosystem.
    • Chapter 7, “Recurrence Relations.” This chapter focuses on solving recurrence relations and applications to the analysis of algorithms.
    • Appendix C, “Pseudocode.”

Assessment Instructions

Assume that you are an IT professional working at an IT company. You have been asked to assess some snippets of code/pseudocode. Read over the pseudocode samples below and answer the corresponding questions.

Pseudocode Sample 1 and Questions

// Description
// number is a positive integer with n digits, where number_i refers to the i^th digit of number
// n is the number of digits of c
// base is a positive integerfunction conversion(number,base,n)
value = 0;
unit = 1;
for i = 0 to n
value = value + number_i * unit;
unit = unit * base;
end
return value;Respond to the following:

1. What does the conversion function do? Please provide a detailed response.
2. In terms of n, how many computational steps are performed by the conversion function? Note: One computational step is considered one operation: one assignment, one comparison, et cetera. For example, the execution of a = c + d may be considered two computational steps: one addition and one assignment.
3. What is the Big-O time complexity of the conversion function in terms of n? Justify your response.

Pseudocode Sample 2 and Questions

function printToScreen(n)
for i = 1 to n
for j = 1 to i
print(“*”);
end
print(“n”);
endRespond to the following:

1. What does the printToScreen function do? Please provide a detailed response. Specifically, describe the pattern formed by the *’s being printed. Note that print(“*”) will print one star and print(“n”) will print a carriage return, which effectively brings the cursor to a new line.
2. In terms of n, how many computational steps are performed by the printToScreen function? Justify your response. Note: One computational step is considered one operation: one assignment, one comparison, et cetera. For example, the execution of print(“Hello“) may be considered one computational step: one print operation.
3. What is the Big-O (worst-case) time complexity of the printToScreen function in terms of n? Justify your response.

Pseudocode Sample 3 and Questions

// n is a non-negative integerfunction f(n)
if n == 0 || n == 1
return 1;
else
return n*f(n-1);Respond to the following:

1. What does the f function do? Please provide a detailed response.
2. In terms of n, how many computational steps are performed by the f function? Justify your response. Note: One computational step is considered one operation: one assignment, one comparison, et cetera. For example, the execution of 3*3 may be considered one computational step: one multiplication operation.
3. What is the Big-O (worst-case) time complexity of the f function in terms of n? Justify your response.
4. Define a recurrence relation a_n, which is the number of multiplications executed on the last line of the function f, “return n*f(n-1);”, for any given input n. Hint: To get started, first determine a₁, a₂, a₃ …. From this sequence, identify the recurrence relation and remember to note the initial conditions.

Pseudocode Synthesis

1. Write pseudocode for a function called swapLarge. This function has an input 3 integers: x, y, and z. The algorithm will swap the values of two of these variables. Specifically, it will swap the largest value and the second largest value. For example, if x = 1, y = 2, and z = 3, then the output would be x = 1, y = 3, and z = 2.
   

   Algorithms Scoring Guide

   CRITERIA				DISTINGUISHED
   Derive recurrence relation including initial conditions.				Derives recurrence relation including initial conditions and relates derivation to algorithm time complexity analysis.
   Analyze purpose of recursive and non-recursive algorithms.			.	Analyzes purpose of recursive and non-recursive algorithms and evaluates its efficiency.
   Analyze the time complexity of recursive and non-recursive algorithms via computational steps and Big-O.			.	Analyzes the time complexity of recursive and non-recursive algorithms via computational steps and Big-O and clearly derives Big-O as an upper-bound of the expression of computational steps.
   Synthesize pseudocode as instructed.				Synthesizes pseudocode as instructed and integrates best coding practices and efficient design schemes.