CS5800-Homework 01 Solved

1           Problem 1
         1.1    1(a)

 

Pseudocode 1 Find the first common element

 

1: function TraversalList(node)

           2:                numberCount ← 0

           3:                tempPtr ← node

           4:                while tempPtr 6= None do

           5:                            numberCount ← numberCount + 1

           6:                            tempPtr ← tempPtr.next

           7:               end while

           8:                return numberCount

9: end function

10:

11: function GetIntersection(head1,head2) 12: num1 ← TraversalList(head1)

         13:                       num2 ← TraversalList(head2)

         14:                 if num1 > num2 then

         15:                            offset ← num1 − num2

         16:                              for i = 0 → offset − 1 do

         17:                                   head1 ← head1.next

         18:                        end for

         19:                         while (head1 6= None)and(head2 6= None) do

         20:                                    if head1 = head2 then

         21:                                             return head1.data

         22:                                  end if

         23:                         end while

         24:             else

         25:                            offset ← num2 − num1

         26:                              for i = 0 → offset − 1 do

         27:                                   head2 ← head2.next

         28:                        end for

         29:                         while (head1 6= None)and(head2 6= None) do

         30:                                    if head1 = head2 then

         31:                                             return head1.data

         32:                                  end if

         33:                         end while

         34:              end if

         35:               return −1

36: end function

 

1.2         1(b)
# link l i s t node class Node:

              def         i n i t        ( self ,       data ) :

s e l f . data = data # assign data s e l f . next = None # i n i t i a l i z e next as s e l f . head = None

 class LinkedList : def     i n i t    ( s e l f ) :

s e l f . head = None

def append( self , newNode) :

                        if         s e l f . head is Node:

s e l f . head = newNode

return last = s e l f . head

while( last . next) : last = last . next

last . next = newNode

def printList ( s e l f ) : temp = s e l f . head

while(temp) :

print(temp . data ) temp = temp . next
NULL
 
 
def TraversalList (node) :# how many nodes num = 0 ptr = node

while( ptr ) :

num += 1 ptr = ptr . next

return num

def getIntersection (head1 ,                      head2) :

numA = TraversalList (head1) numB = TraversalList (head2)

if numA > numB:

offset = numA − numB return helper ( offset , head1 ,           head2)
are
in
the
l i s t
else :

offset = numB − numA return helper ( offset , head2 ,
head1)
 
 

 
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

def
helper (num, head1 , head2) : ptr1 , ptr2 = head1 , head2 for i in range(num) :

if ( ptr1 == None) : return −1

ptr1 = ptr1 . next

while( ptr1 != None and ptr2 != None) :

if ptr1 is ptr2 : # check address         is same return ptr1 . data

ptr1 = ptr1 . next ptr2 = ptr2 . next return −1
if  
  name             == ’        main       ’ :

intersection = Node(7) # define
intersection
 
# f r i s t : 1−>3−>5−>7−>9 listA = LinkedList () listA . head = Node(1) listA . append(Node(3) ) listA . append(Node(5) ) listA . append( intersection ) listA . append(Node(9) )

#listA . printList ()

# second : 2−>7−>12 listB = LinkedList () listB . head = Node(2) listB . append( intersection ) listB . append(Node(12) )

#listB . printList ()

print( getIntersection ( listA . head ,

# the         result         should be 7
listB . head) )
55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

2           Problem 2
According to the definition of θ - notation:

0 ≤ C1 ∗ (f(n) + g(n)) ≤ max(f(n),g(n)) ≤ c2 ∗ (f(n) + g(n))

Show that there exist positive constants c1,c2 and n0 for all n ≤ n0 Since max(f(n),g(n)) ≥ f(n) and max(f(n),g(n) ≥ g(n) :

 

Since f(n) and g(n) are asymptotically non-negative functions: it means that f(n) ≥ 0,g(n) ≥ 0

f(n) + g(n) ≥ max(f(n),g(n))

Therefore, we can combine the above two inequalities as follow:

 

So, max(f(n),g(n)) = Θ(f(n) + g(n)) because there exists 

3           Problem 3
         3.1       Is 2n + 1 = O(2n)?

According to the definition of O-notation:

0 ≤ f(n) ≤ cg(n) for all n ≥ n0

show that there exist positive constant c and n0 for all n ≥ n0

2n + 1 = 2 ∗ 2n

So for any c ≥ 2, there exists 0 ≤ 2n + 1 ≤ c ∗ 2n for n ≥ 1 Therefore, 2n + 1 = O(2n)

         3.2      Is 22n = O(2n)?

According to the definition of O-notation:

0 ≤ f(n) ≤ cg(n) for all n ≥ n0

show that there exist positive constant c and n0 for all n ≥ n0

22n = 2n ∗ 2n

So if c = O(2n), we will need a constant c such that 0 ≤ 2n ∗ 2n which is c = 2n. However, 2n is not a constant. Therefore, 22n 6= O(2n)

4           Problem 4
 √

         n0.001           lnlnn       22lnn           2ln2 n                   nlnn      n!     (lnn)!

5           Problem 5
         5.1      a. 

According to the simple master theorem: a = 2,b = 2,c = 4 :

logb a = 1 −→ c > logb a so case 3: T(n) = Θ(n4)

         5.2      b.  

According to the simple master theorem:  logb a = 0 −→ c > logb a so case 3: T(n) = Θ(n)

         5.3     c.  

According to the simple master theorem: a = 16,b = 4,c = 2 :

logb a = 2 −→ c = logb a so case 2: T(n) = Θ(n2 logn)

         5.4     d.  

According to the simple master theorem: a = 7,b = 3,c = 2 :

logb a ≈ 1.77 −→ c > logb a so case 3: T(n) = Θ(n2)

         5.5     e.  

According to the simple master theorem: a = 7,b = 2,c = 2 :

logb a ≈ 2.8 −→ c < logb a so case 1: T(n) = Θ(nlog2 7 )

         5.6      f.  

According to the simple master theorem:   :

  so case 2: 

         5.7       g. T(n− 2) + n2

The subtraction occurring inside to T won’t change the asymptotics of the solution. According to the simple master theorem, a = 1, b = 1, c=2, logb a = 1,c > logb a, so case 3 T(n) = Θ(n2)

6           Problem 6
         6.1      a. 

According to the master theorem: a = 4,b = 3,f(n) = nlgn nlogb a = nlog3 4 ≈ n1.26 So case 1, T(n) = Θ(nlog3 4)

         6.2      b.  

 

Assume n = 3k,k = log3 n

 

  lg3

         6.3      c.  

 

According to the simple master theorem:  

logb a = log24 = 2,c > logba So case 3, 

         6.4      d.  

The subtraction occurring inside to T won’t change the asymptotic of the solution According to the simple master theorem: a = 3,b = 3,c = 1

logb a = log3 3 = 1,c > logb a So case 2, T(n) = Θ(nlogn)

         6.5     e.  

 

Assume n = 2k,k = lgn

 

 , since k = lgn

Since  is harmonic series, therefore it can be approximated as lgk

Since k = lgn, the result T(n) = n ∗ lglgn

         6.6      f.  

Assume that T(n) ≤ cn where c is a positive constant

         T      T n                T n                T n