CIS2203 Discrete Mathematics

CLO2 Exercises (algorithms)

1. Write the following algorithms.

a. Linear search algorithm.
-Get the search element from the user.
-Get the list from the user.
-Compare the search element with the first element in the list.
-If both are matched, then return the element index and stop searching.
-If both are not matched continue to next element in the list.
-Repeat steps 4 and 5 until search element is compared with last element in the
list.
-If last element in the list also doesn't match, then return -1.

b. Binary search algorithm.

-Get the list from the user.
-Get the search element from the user.
-Calculate the middle index
Compare the search element with the element in the middle index.
-If both are matched, then return the element index and stop searching.
-If both are not matched.
- If the target value is greater than the number in the middle index, then pick
sub list elements to the right of the middle index, and start with Step 3
- If the target value is less than the number in the middle index, then pick the
sub list elements to the left of the middle index, and start with Step 3.
-Repeat steps 4 and 5 until search element is compared with last element in the list.
-If last element in the list also doesn't match, then return -1.

c. Insertion sorting algorithm.

-Get a list
-Pick the first element in the unsorted list.
-If the list has one element, terminate.
-Pick next element
-Compare with all elements in the sorted sub-list
-Shift right all the elements in the sorted sub-list that is greater than the value to be
sorted
-Insert the value
-Repeat until list is sorted

d. Selection sorting algorithm.

-Get a list to sort

-Iterate elements of the list starting from index x
1. Set min to the element in the index x
2. Iterate unsorted list starting from x
1. Compare each element of unsorted list with the min value
2. Maintain the min value in the unsorted list
CIS2203 Discrete Mathematics
3. Maintain the min value location L
-Swap min found in location L with element in index x
-Repeat until list is sorted

2. What are the differences between algorithms and Programming (coding)?

Algorithm Programming (coding )

Algorithms describe the solution Programming is often the way that we

to a problem in terms of the data create a representation for our
needed to represent the problem solutions using specific programming
instance and the set of steps tool such as Python.
necessary to produce the
intended result.

3. List and briefly explain the algorithms Properties.

i. Input: an algorithm has input values from a specified set
ii. Output: from each set of input values an algorithm produces output
values from a specified set. The output values are the solution to the
problem
iii. Definiteness: the steps of an algorithm must be defined precisely
iv. Correctness: an algorithm should produce the correct output values for
each set of input values
v. Finiteness: an algorithm should produce the desired output after a finite
(but perhaps large) number of steps for input in the set
vi. Effectiveness: it must be possible to perform each step of an algorithm
exactly and in a finite amount of time
vii. Generality: the procedure should be applicable for all problems of the
desired form not just for a particular set of input values.

4. Complete the following Python code for Linear search algorithm .

def LinearSearch(data, key):

index = 0
found = False
while( index < len(data) ):
if( data[index] == key ):
found = True
break
index=index+1
return found
def LinearSearch(data, key):
index = 0
while( index < len(data) ):
if(data[index] == key ):
return index
CIS2203 Discrete Mathematics
index=index+1
return -1.

5. Complete the following Python code for selection sort algorithm .

def selectionSort(nlist):
for indx in range(0, len(nlist):
min = nlist[indx]
for L in range(indx+1,len(nlist)):
if nlist[L]<min:
min = nlist[L]
Location = L
temp = nlist[indx]
nlist[indx] = min
nlist[Location] = temp

nlist = [29, 72, 98, 13, 87, 66, 52, 51, 36]
selectionSort(nlist)
print(nlist)

6. Write an a python code function for :

a) Finding the maximum value in an array of numbers

def max(arr1):
max=arr1[0]
for i in range(len(arr1)):
if arr1[i]>max:
max=arr1[i]
return max

arr1=[2,8,9,0,-2]
print("the maximum value is", max(arr1))

b) Finding the minimum value in an array of numbers

def min(arr1):
min=arr1[0]
for i in range(len(arr1)):
if arr1[i]<min:
min=arr1[i]
return min

arr1=[2,8,9,0,-2]
print("the minimum value is", min(arr1))
CIS2203 Discrete Mathematics
c) Finding the sum of values in a list of numbers

def sum(lst1):
sum1=0
for i in range(len(lst1)):
sum1=lst1[i]+sum1
return sum1

lst1=[1,2,3,4,-2,0,3]
print(" the sum is",sum(lst1))

d) Counting all the numbers above 60 in a list of numbers

def count(list5):
count=0
for i in range (len(list5)):
if list5[i]>60:
count=count+1
return count
list5=[70,80,40,60,30,90]
print(" the count is",count(list5))
CIS2203 Discrete Mathematics

e) Linear Search

def LinearSearch(data, key):

index = 0

while( index < len(data) ):

if( data[index] == key ):

return index

index=index+1

return -1

f) Binary search

def binarySearch(alist, item):

first = 0
last = len(alist)-1
found = False
index = -1
while first<=last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
index=midpoint
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return index
P = [6, 12, 17, 23, 38, 45, 77, 84, 90]
print(binarySearch( P , 45))
print(binarySearch( P , 13
CIS2203 Discrete Mathematics

g) Selection sort

def selectionSort(nlist):

for indx in range(0, len(nlist)):

min = nlist[indx]

for L in range(indx+1,len(nlist)):

if nlist[L]<min:

min = nlist[L]

Location = L

temp = nlist[indx]

nlist[indx] = min

nlist[Location] = temp

nlist = [29, 72, 98, 13, 87, 66, 52, 51, 36]

selectionSort(nlist)

print(nlist)

h) Insertion sort
def insertionSort (nlist):
for index in range(1,len(nlist)):
currentvalue = nlist[index]
position = index
while position>0 and nlist[position-1]>currentvalue:
nlist[position]=nlist[position-1]
position = position-1
nlist[position]=currentvalue

nlist = [14,46,43,27,57,41,45,21,70]
insertionSort(nlist)
print(nlist)
CIS2203 Discrete Mathematics

7. How many loop iterations(passes) needed to find number 9 in the list [1 2 3 4 5 7 8 9 10]
a. Using linear search 8
b. Using binary search 3
8. The best case scenario in sequential search happens when the key search element is…
first element in the list.
9. The worst case scenario in linear search happens when……It is the last element or when
it is not in the list.
10. Which one is better to use linear or binary search? Justify your answer? Binary since it
has less complexity [logn<n]
11. What will be returned by the linear search algorithm if the
list=[ “Salem”, “Hassan”, “Abdullah”, “Saif”] and:
a. The key is Hassan answer: 1
b. The key is Ahmad answer:-1
12. What is the difference between selection and insertion sort? See slides

13. Write an algorithm that will display the maximum number in a list?

Set max to the first element in the list.

For each number x in the list L, compare x to max.
If x is more than max, set max to x.
Return the max.

14. Write a Python code to find the maximum number in a list of numbers

def max(arr1):
max=arr1[0]
for i in range(len(arr1)):
if arr1[i]>max:
max=arr1[i]
return max

arr1=[2,8,9,0,-2]
CIS2203 Discrete Mathematics

15. Consider the Binary search algorithm shown below:

If the item=14 and the alist= [2, 3, 5, 8, 9, 11, 13, 14, 18] answer the following
questions:
1) What will be the value of the variables (first, last, midpoint, index) after each
iteration (pass)
2) What will be the remaining numbers in the list after each iteration (pass)
3) How many iterations will be required to find the key
4) What will be returned by this algorithm (the output)

Solution:
1)

Iteration No midpoint first last index

1 4 5 8 -1
2 6 7 8 -1
3 7 7 8 7

2) After first pass : 11,13,14,18

After second pass: 14, 18
After 3rd pass: 14

3) 3 iterations
4) 7