Problem Write your answers in the file assign5.txt (which you should create). Us

Question

Problem

Write your answers in the file assign5.txt (which you should create). Use jEdit, TextEdit, WordPad, or some other editor that can produce “plain text” or “plain ascii” files.

Trace in-place selection sort on the following array of letters (sort into alphabetical order):

That is, after each pass (outer loop iteration) of selection sort, show the contents of the array and the number of letter-to-letter comparisons performed on that pass (an exact number, not big-O).

Trace in-place insertion sort on the following array of letters (sort into alphabetical order):

That is, after each pass (outer loop iteration) of insertion sort, show the contents of the array and the number of letter-to-letter comparisons performed on that pass (an exact number, not big-O).

For each problems segment given below, do the following and write your answers in assign5.txt:

Create an algorithm to solve the problem (describe it in English as part of your answer).

Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor.

Identify the operations that must be counted.

Count the operations performed by the algorithm or code. Express the count as a function of the factors you identified in Step 2. If the count cannot be expressed as a simple function of those factors, define the bounds that can be placed on the count: the best case (lower bound) and worst case (upper bound).

Determine what the Best Case Inputs are, and the Worst Case Inputs are.

Transform your count formula into big-O notation by:

Taking the efficiency with worst case input,

Dropping insignificant terms.

Dropping constant coefficients.

c. Determine if 2 arrays contain the same elements in the same order. You may assume the arrays are of the same length.
d. Counting total number of characters that have a duplicate within a string (i.e. "gigi the gato" would result in 3, since g, i, and t are repeated.)
e. Finding an empty row in a 2-D array where empty is defined as a row with all entries equal to 0.

Questions and answers

A couple of questions and my answers on Assignment 5:

Q: Can you give an example of the format you want the answer in for parts a and b?

A: If the unsorted array was G A D F for selection sort the answer would be:

Q: parts c, d, and e, part 1: What format should we write our algorithm in?

A: English - less formal than the pseudocode we did at the beginning of class. E.g., suppose the problem was "count the 0 elements of an array of ints". You might say

set count to 0
go through the elements of the array:
for each one, test if it is 0 and if so add 1 to count

On the other hand, just saying "add 1 for each 0 in the array" is too informal, since it does not mention how you find the 0's

Explanation / Answer

Here is the solution as per the given criteria:-

An algorithm is simply a numerical recipe which sets of values as input. It performs some mathematical operation and returns transformed values as output.
In programming language, it means writing what is variously called a function, method or subroutine, depending on the programming language.

If You want to learn something well? Then aTry to teach it. Take your algorithm learning material, rewrite it into your own words in a way that someone unfamiliar with it can understand.

Share code snippets and build an example. Use it to showcase it and make it clear for someone to understand.

The benefit will be that you've now published something others can use as reference, and since it's written in your own words, if you start to forget, you can return easily to your publication and refresh yourself (and perhaps add a bit more as you go).

Especially useful if a lot of what you may do day in and day out doesn't necessarily have much to do with algorithms, but you want to stay fresh.

Something like this would both be a great learning tool as well as something fun to emulate to get a good understanding of various algorithms and to be able to visually see how they work.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.