Clearly identify a problem that is solved using computer programs. Identify what

Question

Clearly identify a problem that is solved using computer programs.

Identify what Data Structures and Algorithms are used to solve that problem

If the time complexity of the algorithm is known to the public, explain this time complexity. If the time complexity is not known, come up with a hypothesis for a time complexity. Clearly state what evidence this time complexity is based on. The time complexity should be explained using Big O notation. The time complexity should be asymptotically tight.

Asymptotically Tight definition -> http://xlinux.nist.gov/dads/HTML/asymptoticallyTightBound.html

Explanation / Answer

An Anagram Detection Example

A good example problem for showing algorithms with different orders of magnitude is the classic anagram detection problem for strings. One string is an anagram of another if the second is simply a rearrangement of the first. For example, 'heart' and 'earth' are anagrams. The strings 'python'and 'typhon' are anagrams as well. For the sake of simplicity, we will assume that the two strings in question are of equal length and that they are made up of symbols from the set of 26 lowercase alphabetic characters. Our goal is to write a boolean function that will take two strings and return whether they are anagrams.

Solution 1

Checking Off

Our first solution to the anagram problem will check to see that each character in the first string actually occurs in the second. If it is possible to

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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