DMCH(3) - HackMD

The Islamic University of Gaza Discrete Mathematics Lab - 2023/2024 Discussion || ch(3) Eng: Amal I. Mahfouz , Eng: hashem hejazy **** section 3.1 * 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 * 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 * 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 * 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; * 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 --- --- section 3.2 * 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 * 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. * 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 * 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! --- section 3.3 * 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) * 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) * 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) * 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. 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 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. --- * 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