I1101 Final

Lebanese University I1101 BS - Computer Science
Faculty of Science Introduction to Programming Duration : 90 minutes

Section I Final Exam - Session 1 - Solution 2020 - 2021
Question 1 - Sum of the first and the last digits of a number (20 pts - 10 minutes)
Write a C program that asks the user to enter an integer number greater than 9, then calculates the sum of the first
and the last digits of the number.
Running example:
Input a number greater than 9: -12
Input a number greater than 9: 925
Sum of the first and the last digits: 14
Solution
#i n c l u d e <s t d i o . h>
i n t main ( )
{
i n t nb , sum ;
do{
p r i n t f ( ” Input a p o s i t i v e number : ” ) ;
s c a n f (”%d”,&nb ) ;
} w h i l e ( nb <10);
sum = nb%10;
w h i l e ( nb>=10)
nb /=10;
sum +=nb ;
p r i n t f ( ”Sum o f t h e f i r s t and t h e l a s t d i g i t s : %d ” , sum ) ;
return 0;
}
Page 1 of 8
Question 2 - The missing value (80 pts - 80 minutes)
We have an array T [N ] containing all integers in the interval 0 · · · N , except one integer.
We want to determine which integer is missing from T using multiple approaches.
Example: for the following array T of size N = 6, the missing value is 4.
5 6 3 2 1 0
1. (5 pts) Write the function int find(int T[], int N, int e) that given an array T of size N and an integer
e returns 1 if e is an element of T , otherwise returns 0.
Solution
i n t f i n d ( i n t T [ ] , i n t N, i n t e )
{
int i ;
f o r ( i =0; i <N; i ++)
i f (T [ i ]==e )
return 1;
return 0;
}
Page 2 of 8
2. (10 pts) Version 1: Loop over the interval 0 · · · N and search for each value in T using the function find, return
the missing value. Write the function int findMissingValueV1(int T[], int N) that given an array T of
size N returns the missing value.
Solution
i n t f i n d M i s s i n g V a l u e V 1 ( i n t T [ ] , i n t N)
{
int i ;
f o r ( i =0; i<=N; i ++)
i f ( f i n d (T, N, i )==0)
return i ;
}
Page 3 of 8
3. (5 pts) Write the function int sumArray(int T[], int N) that given an array T of size N returns the sum of
the elements in the array.
Solution
i n t sumArray ( i n t T [ ] , i n t N)
{
i n t i , sum = 0 ;
f o r ( i = 0 ; i <N; i ++)
sum += T [ i ] ;
r e t u r n sum ;
}
Page 4 of 8
4. (10 pts) Version 2: The sum of numbers from 0 to N is equal to i=0 i = N ×(N
PN +1)
2 . It suffices to calculate
the difference between the above sum and the sum of elements in T . Using the function sumArray, write the
function int findMissingValueV2(int T[], int N) that given an array T of size N returns the missing value.
Solution
{
r e t u r n N∗ (N + 1 ) / 2 − sumArray (T, N ) ;
}
Page 5 of 8
5. (20 pts) Version 3: We are trying simultaneously to determine the missing value and to sort the array using
minimum selection algorithm. At each iteration, after looking for the minimum on the right side of the array,
the first time when the minimum doesn’t match the index is the missing value.
Write the function int findMissingValueV3(int T[], int N) that given an array T of size N sorts T using
minimum selection algorithm, determines and returns the missing value.
Solution
{
i n t i , j , imin , aux , m i s s i n g v a l u e =−1;
f o r ( i = 0 ; i <N − 1 ; i ++)
{
imin = i ;
f o r ( j = i + 1 ; j <N; j ++)
i f (T [ j ]<T [ imin ] )
imin = j ;
i f ( imin != i )
{
aux = T [ imin ] ;
T [ imin ] = T [ i ] ;
T [ i ] = aux ;
}
i f ( m i s s i n g v a l u e==−1 && T [ i ] != i )
missingvalue = i ;
}
i f ( m i s s i n g v a l u e == −1)
r e t u r n N;
return missingvalue ;
}
Page 6 of 8
6. (10 pts) Bubble sort is a sorting algorithm that repeatedly steps through the array, compares adjacent elements
and swaps them if they are in the wrong order. The pass through the array is repeated until the array is sorted.
The algorithm is named for the way larger elements bubble to the end of the array.
Write the function void bubbleSort(int T[], int N) that sorts array T using bubble sort algorithm.
Solution
v o i d b u b b l e s o r t ( i n t T [ ] , i n t N)
{
i n t i , j , aux , swapped ;
f o r ( i = N − 1 ; i >0; i −−)
{
swapped = 0 ;
f o r ( j = 0 ; j <i ; j ++)
{
i f (T [ j ]>T [ j + 1 ] )
{
aux = T [ j ] ;
T[ j ] = T[ j + 1 ] ;
T [ j + 1 ] = aux ;
swapped = 1 ;
}
}
i f ( ! swapped ) break ;
}
}
Page 7 of 8
7. (20 pts) Version 4: We will be using a solution based on binary search. For this, call the function bubbleSort
first to sort T . Then modify binary search algorithm to locate the missing value.
If the middle element matches the index, it means the missing value is on the right side. If the middle element is
greater than the index, look on the left side. When there’s just one element left to compare, it means you have
located the element that precedes the missing value.
Write the function int findMissingValueV4(int T[], int N) that given an array T of size N sorts T by call-
ing bubbleSort function and then finds the missing value using the modified version of binary search algorithm.
Solution
{
i n t l e f t , r i g h t , middle ;
b u b b l e s o r t (T, N ) ;
l e f t = 0;
right = N − 1;
w h i l e ( l e f t <r i g h t )
{
middle = ( l e f t + r i g h t ) / 2 ;
i f (T [ middle ] == middle ) l e f t = middle + 1 ;
i f (T [ middle ]> middle ) r i g h t = middle − 1 ;
}
return right + 1;
}
Good Luck !
Page 8 of 8

I1101 Final

Uploaded by

Copyright:

Available Formats

I1101 Final

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

I1101 Final

Uploaded by

Copyright:

Available Formats

Lebanese University I1101 BS - Computer Science

Faculty of Science Introduction to Programming Duration : 90 minutes

You might also like