Capella University Pseudocode Analyze and Synthesize Discussion

Overview

Analyze and synthesize pseudocode for an IT company.
This assessment is particularly important to the areas of IT and computer science, as both use a number of different programming languages to complete tasks via algorithms. You will demonstrate your ability to interpret and create algorithms and read and understand pseudocode (that is, English-like programming code). Capella University Pseudocode Analyze and Synthesize Discussion
ORDER NOW FOR COMPREHENSIVE, PLAGIARISM-FREE PAPERS
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:

What does the conversion function do? Please provide a detailed response.
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.
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:

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.
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.
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:

What does the f function do? Please provide a detailed response.
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.
What is the Big-O (worst-case) time complexity of the f function in terms of n? Justify your response.
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

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.

4 attachments

Slide 1 of 4

attachment_1

Assessment 4 Context

Algorithms

An algorithm is a method that will successfully complete a specific task. Specifically, an algorithm is a step-by-step process or method for completing a task, solving a problem, or determining a solution. An algorithm can have one or more inputs as well as one or more outputs. Capella University Pseudocode Analyze and Synthesize Discussion

A simple example might be to program a computer to add two numbers and output the sum. The input would be the two numbers; the output would be the sum. The algorithm would be the entire method and code that accepted the input and produced the expected correct output. While there are often many methods for solving the same problem, some methods are faster and require less space. This is very important in IT, as space and time are always limited.

Pseudocode

There are many different programming languages, each with specific strengths and attributes. Examples are Java, C#, Perl, Python, SQL, and Visual Basic. In this course, we will use an English-based language called pseudocode. The idea is that we can use pseudocode to create algorithms without having to worry about the specific syntax and the memory usage of a programming language or related environment.

When writing pseudocode, it is best to show every relevant step so that your pseudocode could easily be converted to an actual programming language if desired.

It is very important to understand pseudo-code, including the IF, THEN, ELSE construct; the WHILE loop construct; and the FOR loop construct. All programming languages have a form of the IF construct.

if (condition) then (action) else (action).

The else is not required, but it is optional as needed.

Recursive Algorithms

There are many types of algorithms. One type—recursive—is unique as it uses the concept of calling itself. Here is an example.

We know from earlier assessments that a factorial (!) is the decreasing product of the given number, such that:

7! = 7 * 6 * 5 * 4 * 3 * 2 * 1.

We can write a program (create pseudocode in our case) to take as input any number x and offer as output the value of the factorial x! The key is that we name a function that performs a task:

factorial(n)
{
if(n == 0)
return 1;
else
return n * factorial(n – 1);
}

Notice that inside the function called factorial(n), we make a call to that same exact function unless the value of n is 0. Also notice that when we call the function factorial(n – 1), we also reduce the value of n by 1.

The best way to really understand an algorithm is to step through it by hand. Let us do that here:

Suppose we start with n = 7.

This means that the value of 7 is passed to the function factorial as input. The first statement asks if the value of n is equal to 0. It is not because it is 7, so we move to the next step. The next step tells us to multiply the value of n (at this time 7) to the value that we get when we call the factorial function using the value n – 1, or 6.

So, the program, in memory, saves the value 7 and then calls the program with the value of 6. We repeat the steps. Because 6 does not equal 0, we move to the next step that says multiply 6 by the value you get when you call the function factorial on 6 – 1, or 5. This continues until n is decreased to 0 and the program ends.

The recursive portion has been storing in memory each value, 7 * 6 * 5 * 4 * 3 * 2 * 1 and then, once n = 0, it returns the product.

Recursion is not a simple concept and takes some getting used to.

Time Complexity

Because computers are fast, we generally use upper bounds to measure the speed of a program. For example, we might say that a specific sorting algorithm runs in O(n2) time or perhaps even faster at O(nlog n) time. The big O, or O( ), is a notation that notes the upper bound, or the closest fit upper bound. When we say a program runs in O(n2) time, we mean that for an input of size n, we can expect the algorithm to take approximately, or on the order of, n2 time to run. Generally, the unit of time referred to is the microsecond. However, keep in mind that this concept can be used for any unit of time and that this unit of time is largely determined by the clock speed of the computer processor. As we know, some computers are faster than others. The big O is actually known as an asymptotic upper bound.

Recurrence Relations

Sometimes, determining the run time of an algorithm, especially a recursive algorithm, might take further calculations. As we have seen, some programs can be quite involved and even call themselves. Recurrence relations can be used to analyze more complicated algorithms. They can also be used to investigate the relationship between input values in a sequence. Capella University Pseudocode Analyze and Synthesize Discussion

For example, suppose we have a simple algorithm that starts with 5, then adds 3 to get the next term, and repeats on the next term. This algorithm would have an input of 5 and the following output:

5, 8, 11, 14, 17, and so on.

Another way to write this algorithm would be to denote terms with an values:

a₁ = 5.

a₂ = 8.

a₃ = 11.

Given this notation, how can we determine a101?

This is where recurrence relations come into play. We know the base case: a1 = 5. We also know the recurrence relation:

a_n = a_n–1 + 3.

Let us start to write these out to see if we can come up with an equation:

a_n = a_n–1 + 3.

a_n = a_n–2 + 3 + 3.

a_n = a_n–3 + 3 + 3 + 3.

a_n = a_n–4 + 3 + 3 + 3 + 3 and so on until a_n–x is 5 and we stop.

First, notice that we are expanding this recursive (recurrence) equation. Placing parentheses provides us with a better look:

a_n = (a_n–1)+ 3.

a_n = ([a_n–2]+ 3) + 3.

a_n =([{a_n–3} + 3] + 3 )+ 3.

a_n =([{a_n–4 + 3} + 3] + 3) + 3 and so on until a_n–x is 5 and we stop.

If we continue, we would next expand the an–4 term into an–5 + 3 and so on. This will continue until we reach the last term. However, happily, we do not have to continue. We expand only until we see the following pattern:

a_n = a_n–x+ (3 * x).

The x represents the number of threes that we have. Notice that for an = ([{an–4 + 3} + 3] + 3) + 3, we have four threes and an an–4 term. So, we use x to represent this concept, as we know we get one more threes each time we expand and our an–4 term will become an–5.

a1₀₁ = a_101–100 + (3 * 100) = a₁ + 300 = 5 + 300 = 305.

Recall that a₁ was defined as 5.

So, to review, a recurrence equation can be used to find the value of any item in the sequence. However, to do this, the recurrence equation must be solved and evaluated.

Recurrence equations can be used to determine how long an algorithm will take to run.
attachment_2
attachment_3