---
# System prepended metadata

title: DMCH(3)

---


<p style="font-size: 14px;text-align:center">
The Islamic University of Gaza
</p>

<p style="font-size: 14px;text-align:center">
    Discrete Mathematics Lab - 2023/2024
</p>
<p style="color:#000033;font-weight: bold;text-align:center">
   Discussion || ch(3)
</p>

<p style="text-align:right">
    Eng: Amal I. Mahfouz , Eng: hashem hejazy
</p>



****

<p style="color:#000066;font-weight: bold;">
   section 3.1
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.1.3: Devise an algorithm that finds the sum of all the integers
 in a list.
    
    Input:  List of integers with length n. 
    Output: The sum of all integers in the list
    
    procedure sum(L: List of integers) 
       sum := 0                  // Initialize the sum to 0  
       for i in L :             // Iterate through each element in the list L
           sum := sum + i      // Add the current element (i) to previous sum
       return sum 
</p>


<p style="color:#000066;font-weight: bold;">
   * 3.1.4:Describe an algorithm that takes as input a list of n integers and produces as output the largest difference obtained by subtracting an integer in the list from the one
 following it.
    
    
    Input: List of integers with length n. 
    Output: The largest difference obtained by subtracting an integer in the list from 
    the one following it. 
    
    
    procedure largest difference(L: List of integers) 
      diff := - math.inf                  //ensure that any valid difference will be 
                                            larger than this initial value
      n := length(L)                     // the length of the list
      for i := 0to n-2
        if (L[i+1] - L[i] > diff) then 
            diff := L[i+1] - L[i]
      return diff
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.1.7:Describe an algorithm that takes as input a list of n integers and finds the location of the last even integer in the list or returns 0 if there are no even integers in the list.
    
    Input: List of integers with length n. 
    Output: location of the last even integer in the list or returns 0 if there are no
            even integers in the list. 
    
    
    procedure LastEvenLocation(L: List of integers)
            last := 0 
            n := length(L)
            for i:=0 to n-1
               if L[i] % 2 == 0 then
                  last := i
            return last
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.1.15:Describe an algorithm that inserts an integer x in the appropriate position into the list a1,a2,…,an of integers that are in increasing order.
    
    Input: List of integers with length n as in increasing order , 
           and an integer X. 
    Output: A new list with x inserted at the correct position to maintain the sorted 
            order.
    
    // we will use use a binary search approach to find the correct position for 𝑥

    
    
    procedure insertSorted(L: ArrayList of integers , X: integer)
       low  := 0
       high := L.size() - 1
    
       while (low <= high) do :
             mid := (low + high) / 2
            if (L.get(mid) == X) then    // x is already in the correct position 
                 return L;
            else if (L.get(mid) < x) then
                 low := mid + 1
            else then 
                high = mid - 1
            
        L.add(low, X);
        return L;
    
    
            
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.1.37:Use the bubble sort to sort 3, 1, 5, 7, 4, showing the lists obtained at each step.
                        
                        3,1,5,7,4
    first iteration :
    step 1 : compare 3 , 1  >>  result : 1,3,5,7,4  
    step 2 : compare 3 , 5  >>  result : 1,3,5,7,4
    step 3 : compare 5 , 7  >>  result : 1,3,5,7,4
    step 4 : compare 7 , 4  >>  result : 1,3,5,4,7
    
    second iteration:
    step 5 : compare 1 , 3  >>  result : 1,3,5,4,7
    step 6 : compare 3 , 5  >>  result : 1,3,5,4,7
    step 7 : compare 5 , 4  >>  result : 1,3,4,5,7
    
    third iteration:
    step 8 : compare 1 , 3  >>  result : 1,3,4,5,7
    step 9 : compare 3 , 4  >>  result : 1,3,4,5,7
    
    foruth iteration:
    step 10 : compare 1 , 3  >>  result : 1,3,4,5,7
    
    
    
    
    
</p>
---


---


<p style="color:#000066;font-weight: bold;">
   section 3.2
</p>
<p style="color:#000066;font-weight: bold;">
   * 3.2.1: Determine whether each of these functions is O(x).
    
 a) f(x) = 10
           
                yes
    
 b) f(x) = 3x+7
    
                yes
    
 c) f(x) = x^2 +x+1
    
                No
    
 d) f(x) = 5logx
    
                yes
    
 e) f(x) = ⌊x⌋
         
                yes
    
 f) f(x) = ⌈x/2⌉
    
                yes
    
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.2.3:Use the definition of “f(x)isO(g(x))” to show that x^4 + 9x^3 +4x+7 is O(x^4).

    
    |f(x)| ≤ C ⋅ | x^4 |
    
    |x^4 + 9x^3 +4x+7 | ≤ C ⋅ | x^4 |
    
    *    x^4   is O(x^4) because x^4 ≤ C.x^4            for c = 1
    *    x^3   grows slower than x^4 , 9.x^3 ≤ C 9.x^4  for c = 9 , x ≥ 1
    *    4X    grows slower than x^4 , 4.x   ≤ C 4.x^4  for c = 4 , x ≥ 1
    *    7     grows slower than x^4 , 7     ≤ C 7.x^4  for c = 7 , x ≥ 1
    
    |f(x)| ≤ ( 1 + 9 + 4 + 7 ) ⋅  x^4 = 21.x^4 
    
    If x ≥ 1 then we have: 
    x^4 + 9𝑥^3 + 4𝑥 + 7  ≤ 𝑥^4 + 9.𝑥^4 + 4.𝑥^4 + 7.𝑥^4   
    Therefore 𝑥4 + 9𝑥3 + 4𝑥 + 7   is O(𝑥4 ), taking witnesses C = 21 and k = 1.
    


    
    
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.2.7:  Find the least integer n such that f(x)is O(x^n) for each of these functions.
    
 a) f(x) = 2x^3 +x^2logx
    
           x^2.logx grows slower than  x^3
           f(x)= 2.X^3 + X^2 . X 
           f(x) is O(x^n) is n = 3
    
 b) f(x) = 3x^3 +(logx)^4
    
           The (log𝑥)4 is insignificant compared to the 𝑥3 term, so
           f(x)= 3x^3 + x^3
           f(x) is O(x^n) is n = 3
    
 c) f(x) = (x^4 +x^2 +1)/(x^3 +1)
    
    
           f(x) ≈ x^4 / x^3  ≈ x
           f(x) is O(x^n) is n = 1
    
    
 d) f(x) = (x^4 +5logx)/(x^4 + 1)
    
           f(x) ≈ x^4 / x^4 ≈ 1 
           f(x) is O(x^n) is n = 0
    
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.2.21:Arrange the functions √n, 1000logn, nlogn,2n!, 2^n, 3^n,
 and n^2/1,000,000 in a list so that each function is big-O
 of the next function.
    
          1000logn,  √n, nlogn , n^2/1,000,000, 2^n, 3^n, 2n!
        
</p>
 
 

---

<p style="color:#000066;font-weight: bold;">
   section 3.3
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.3.1: Give a big-O estimate for the number of operations
 (where an operation is an addition or a multiplication)
 used in this segment of an algorithm.
    
    t := 0
    for i := 1 to 3
      for j := 1 to 4
        t := t +ij
    
    
    
    answer : O(1)
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.3.2:Give a big-O estimate for the number additions used in
 this segment of an algorithm.
    
    t := 0
    for i := 1 to n
      for j := 1 to n
         t := t +i+j

    
    
    answer : O(𝑛2) 
</p>

<p style="color:#000066;font-weight: bold;">
   * 3.3.3:  Give a big-O estimate for the number of operations,
 where an operation is a comparison or a multiplication,
 used in this segment of an algorithm (ignoring comparisons used to test the conditions in the for loops, where
 a1,a2, ...,an are positive real numbers).
    
     m:= 0
     for i := 1 to n
        for j := i +1 to n
            m:=max(aiaj,m)
    
    answer : O(𝑛2) 
</p>
 
 <p style="color:#000066;font-weight: bold;">
   * 3.3.13: The conventional algorithm for evaluating a polynomial anx^n + an−1x^n−1 + ⋯+a1x+a0 at x = c can be
 expressed in pseudocode by
    
     procedure polynomial(c,a0,a1,…,an: real numbers)
     power := 1
     y := a0
     for i := 1 to n
         power := power ∗ c
         y := y+ai ∗ power
      return y {y = anc^n +an−1c^n−1 + ⋯+a1c+a0}
where the final value of y is the value of the polynomial at x = c.
    
    
<p style="color:#000066;font-weight: bold;">
   a) Evaluate 3x2 + x +1   ,at x = 2 by working through each step of the algorithm showing the values a signed at each assignment step.
    
    n = 2
    c = 2 
    a0= 1  , a1= 1 , a2= 3
    
    first iteration: 
    power = 1 , y = 1 
    after iteration : 
    power = 2 , y = 3
    
    
    second iteration: 
    power = 2 , y = 3
    after iteration : 
    power = 4 , y = 15
    
    
    
    
    
</p>


<p style="color:#000066;font-weight: bold;">
   b) Exactly how many multiplications and additions are used to evaluate a polynomial of degree n at x = c? (Do not count additions used to increment the loop variable.)
    
    
       in every iteration we have 2 multiplications ,and 1 addition;
       so the for loop we have n iterations with total being:
              2n multiplications and n additions.
</p>
    
 

---

</p>

  <p style="color:#000066;font-weight: bold;">
   * 3.3.19: How much time does an algorithm using 2^50 operations
 need if each operation takes these amounts of time?
    
 a) 10^−6 s
    
    2^50 * 10^-6 = 35.702 year
    
 b) 10^−9 s
    
    2^50 * 10^-9 = 13.031 day
    
 c) 10^−12 s
    
    2^50 * 10^-12 = 18.765 minutes
</p>