DS8001_lec01exSoln_introAlgos.pdf

Notes LECTURE 1: INTRODUCTION TO ALGORITHMS EXERCISES DS 8001...

Notes LECTURE 1: INTRODUCTION TO ALGORITHMS EXERCISES DS 8001 n btraitedfrom c s is p Man each timefiction is called n 5 times so lol Notes I failed nlstimes E X 1: B IG -O C OMPLEXITY C ALCULATION divided by 5 myfn each the n thenfunction is called oflog Determine the big-O complexities of the following functions: n def myFunc1(n): def myFunc2(n): n 2Ttime if n 0: return foo(m-1, foo(m, n-1)) functions is lay print(foo(1,1)) fooLo 2 return 3 M Cevik DS 8001 - Intro. to Algorithms Exercises 6/9  Notes E X 3: A NAGRAMS ⇤ An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once. Examples include “arc = car”, “python = typhon”, and “eleven plus two = twelve plus one”. ⇤ In this question, we will focus on the Anagram Detection Problem (ADP) for words only, given as strings, assuming that the two given strings are of equal length, n, and that they are made up of symbols from the set of 26 lowercase alphabetic characters. ⇤ Goal is to write a boolean function that will take two strings and return whether they are anagrams. We will consider alternative algorithms for the ADP. (Alternative 1) The first solution algorithm for the ADP checks to see that each character in the first string actually occurs in the second. If it is possible to “checkoff” each character, then the two strings must be anagrams. Checking off a character is accomplished by replacing it with the special Python value “None”. Task: Perform big-O analysis on ADP1. Show your work, i.e., mention the input size, define the elementary operations, compute On and then provide big-O complexity (i.e., do not just guess big-O). M Cevik DS 8001 - Intro. to Algorithms Exercises 7/9 g E X 3: A NAGRAMS - A LTERNATIVE 1 Notes in def ADP1(s1,s2): s2_list = list(s2) pos1 = 0 anemones still_ok = True while pos1 < len(s1) and still_ok: Worstcase Reversed so till the end for egg pos2 = 0 I found = False ITÉ while pos2 < len(s2_list) and not found: if s1[pos1] == s2_list[pos2]: found = True else: On in ite n n nh z pos2 = pos2 + 1 if found: s2_list[pos2] = None else: still_ok = False pos1 = pos1 + 1 return still_ok # Examples print(ADP1(’abcdef’,’fedcba’)) print(ADP1(’abcxyz’,’fedcba’)) M Cevik DS 8001 - Intro. to Algorithms Exercises 8/9 Notes ⇤ 6 E X 3: A NAGRAMS - A LTERNATIVE 2 An alternative approach is provided below. Explain the main logic of ADP2. That is, explain clearly what this algorithm is doing, how exactly it is checking whether the two strings are anagrams. Also, guess its big-O complexity and provide an explanation. code def ADP2(s1,s2): unicode c1 = * 26 c2 = * 26 ordreturnsspecified char of a 7 97 yo for i in range(len(s1)): pos = ord(s1[i]) - ord(’a’) c1[pos] = c1[pos] + 1 ord a 122 for i in range(len(s2)): Ord z11 pos = ord(s2[i]) - ord(’a’) c2[pos] = c2[pos] + 1 j = 0 still_ok = True while j < 26 and still_ok: if c1[j] == c2[j]: j = j+1 else: still_ok = False return still_ok M Cevik DS 8001 - Intro. to Algorithms Exercises 9/9