INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA
UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY
EXAMINATION PAPER
GRADE In numbers: Written:
Lecturer’s
Prof. Dr. Name: Michał Surname: MAŁAFIEJSKI
Title:
Educational
Cycle: ☒ B.A. ☐ M.A. ☐ Ph.D CTE
Program:
Academic Instruction
2019-2020 ☒English ☐ Georgian ☐ Turkish Date: 07.07.2019
Year: Language:
Dur.
Semester: ☐ Fall ☒ Spring Course Name: INTRODUCTION TO PROGRAMMING 180 Grp:
(min.):
Course Code: Type: ☐ Quiz ☐ Midterm ☐ Excuse Midterm ☒ Final ☐ Excuse Final ☐ Make-up ☐ Proficiency
Student’s ID
Full Name: Signature:
№:
During the exam, students are allowed to use the following (as defined by the lecturer )1:
☒ Books ☒ Dictionary ☒ Internet ☒ Calculator ☒ Formulas ☒ Tables
☐ Other :
Note: If you think that something is defined not precisely enough, please write down clearly any additional assumptions you have made.
IMPORTANT! Please read and perform the following steps:
1. Please login to the server ibsu.animima.org and create in your home folder the directory with
the following name (precisely!): finexam, then create four subfolders problem1, problem2,
problem3, problem4, problem5, problem6, problem7, problem8 in the folder finexam.
2. In each of the folders: problem1-problem8 create obligatory subfolder solution.
3. Please restrict an access to the folder finexam and all its subfolders (-R flag) to the owner only
(700).
4. You may create any additional files and (sub)folders in finexam folder. Files from solution
folders will be graded only. Please check at the end of the exam if you have all your solutions there.
5. You may leave readme.txt file in the main folder or any problem subfolders with any detailed
information for me. I will take that into account while grading your solutions.
6. During the exam you must record your activity using ttyrec command as follows: to record all
the activity while solving each of the problems (separately), for example to record the process of
writing the solution to the Problem 1 please use the command ttyrec rec1.play (or any name
with .play suffix) in the folder problem1. Please do not type Ctrl-d during recording! It will finish
definitely the recording process, the same as writing exit command. To play the recording you may
use command ttyplay filename.
7. Recording is obligatory to show the activity and the process of solving to the following problems:
problem1, problem2, problem3.
Problem 1. (5 points) (writing code in C language)
Write the program in C language solving the following problem. Your program should run with the
command from bash terminal command line:
showgen string1 string2
where showgen is the name of your program, string1 is a starting string of characters (letters a-z
only) and string2 is a finishing string of characters (letters a-z only). If the strings are of different
length or the first string (string1) is greater in lexicographical order (where a<b<...<z) than the
second one string (string2), the program is doing nothing. In the case when string1 is not grater
(in lex order) than string2 then your program must do the following:
1 Filled by the lecturer! The tick(s) must be (☒) made only electronically before printing. Handwritten ticks will not be taken into consideration!
IBSU. R3.F17E; Revision No.: 0 Page No: 1 /6
INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY
EXAMINATION PAPER
GRADE In numbers: Written:
starting from string1 print out all the strings that are between those two strings in lexicographical
order and are of the same length and finish the sequence with string2. Use letters a-z only.
See the example: running showgen xy ye you have to print
xy
xz
ya
yb
yc
yd
ye
Please note that to get points you must backup all the files (source codes, input and output files,
readme.txt file) with the description of the solution in the appropriate folder named solution on
the server ibsu.animima.org. Test your program and show how to run it. Recording of the solving
process to that problem is obligatory.
Problem 2. (5 points) (writing code in C language)
Analyze carefully the following partial source code. Complete the code only in the specified places
(marked symbolically by the dots) such that it produces the outputs as the result of running for the
following inputs.
#include <stdio.h>
Input 100 75 75
#include <math.h>
Output 2795.08
/* three lines are enough, but you may write more */
float mysterious(int x, int y, int z) {
…………………………………………………………………………………… Input 5 5 5
……………………………………………………………………………………
…………………………………………………………………………………… Output 10.83
}
float amazing(int x, int y, int z) { Input 1 1 0
if (x > y + z) return mysterious(0,y,z);
Output 0.00
if (y > x + z) return mysterious(x,0,z);
if (z > x + y) return mysterious(x,y,0);
return mysterious(x,y,z);
Input 100 30 40
}
Output 0.00
int main()
{
int a,b,c; Input 10 9 8
float res;
scanf("%d %d %d",&a,&b,&c); Output 34.20
res = amazing(a,b,c);
printf("%.2f\n",res);
return 0; Input 10 10 10
}
Output 43.30
Please note that to get points you must backup all files (source codes, inputs, outputs) in the
appropriate folder named solution on the server ibsu.animima.org. Recording of the solving
process to that problem is obligatory.
Problem 3. (5 points) (writing code in C language)
IBSU. R3.F17E; Revision No.: 0 Page No: 2 /6
INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY
EXAMINATION PAPER
GRADE In numbers: Written:
Analyze carefully the following partial source code. Complete the code only in the specified places
(marked by the dots) such that it produces the outputs as the result of running for the following
inputs. Please describe in txt file the idea of the algorithm.
#include <stdio.h>
#define SIZE 100 Input 2
22
struct TASK {
01
int start;
int length; Output total time=4
};
/* hint: use sorting algorithm */
Input 3
int best_schedule_on_one_machine(int n, struct TASK *A)
{ 13
…………………………………………………………………………………… 31
……………………………………………………………………………………
…………………………………………………………………………………… 22
……………………………………………………………………………………
…………………………………………………………………………………… Output total time=7
……………………………………………………………………………………
……………………………………………………………………………………
…………………………………………………………………………………… Input 3
…………………………………………………………………………………… 13
……………………………………………………………………………………
…………………………………………………………………………………… 73
…………………………………………………………………………………… 33
……………………………………………………………………………………
…………………………………………………………………………………… Output total time=10
}
int main() Input 5
{
51
int num,i;
struct TASK S[SIZE]; 43
scanf("%d",&num); /* assume that num <= SIZE */
01
for(i=0;i<num;i++)
scanf("%d %d\n",&S[i].start,&S[i].length); 02
printf("total time=%d\n",best_schedule_on_one_machine(num,S));
52
return 0;
} Output total time=10
Please note that to get points you must backup all files (source codes, inputs, outputs) in the
appropriate folder named solution on the server ibsu.animima.org. Recording of the solving
process to that problem is obligatory.
Problem 4. (5 points) (writing code in C language) (SPOJ)
Link: https://www.spoj.com/ITP2020/problems/ITPCPTS/
Problem: Write the program that finds the square of minimum distance between two points among n
points on the plane.
Input: In the first line there is a number 2 <= n <= 30000. In each of n next lines there are two
integers from [-1000000,1000000] denoting coordinates of a point.
Output: Print a square of the distance between closest two points.
Example:
Input:
IBSU. R3.F17E; Revision No.: 0 Page No: 3 /6
INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY
EXAMINATION PAPER
GRADE In numbers: Written:
5
11
22
33
02
20
Output:
2
Note: There are given three test cases. Two first test cases are worth 1 point each and the third test case is worth 3 points.
Please note that to get points you must backup all the files (source codes, input and output files,
readme.txt file) with the description of the solution in the appropriate folder named solution on
the server ibsu.animima.org. Test your program and show how to run it.
Problem 5 (5 points) (writing code in C language) (SPOJ)
Link: https://www.spoj.com/ITP2020/problems/ITPMFLET
Problem: You are given the sequence of words consisting of letters (a-z,A-Z) only, each word in a
separate line. Your goal is to write to the output the number of occurrences of the most frequent
small letter in all the words of even length and the number of occurrences of the most frequent
capital letter in all the words of odd length.
Input: At most 1000 words composed from the letters only (a-z,A-Z) written in separate lines. Each
word is of length at most 100 characters.
Output: In one line write down two numbers: the number of occurrences of the most frequent small
letter in all the words of even length and the number of occurrences of the most frequent capital
letter in all the words of odd length.
Example:
Input:
JoHn
BRuNo
KAMiL
ANna
MAGDA
Output:
23
Please note that to get points you must backup all the files (source codes, input and output files,
readme.txt file) with the description of the solution in the appropriate folder named solution on
the server ibsu.animima.org. Test your program and show how to run it.
Problem 6. (5 points) (writing code in C language) (SPOJ)
Link: https://www.spoj.com/ITP2020/problems/PCPFRSEQ/
Problem: Find the average age of all persons with the most frequent name. If there are a few names
that are the most frequent (i.e., with the same number of occurrences), calculate separately the
average age of all persons with a given name, and write the results in separate lines.
IBSU. R3.F17E; Revision No.: 0 Page No: 4 /6
INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY
EXAMINATION PAPER
GRADE In numbers: Written:
Input: There are given at most 1000 records, where each record is written in a separate line ending
with newline character (even after the last line). Each record consists of a name (of length at most 25
characters) and age (the integer between 0 and 150), separated by whitespace and ending with a
newline character.
Output: In each line write the name and the average age (represented as a floating point number
with the precision limited to two decimal points) for each most frequent name. If there are two or
more most frequent names, write names in the lexicographical order, e.g., Anna before Gilbert, as in
the example below.
Example:
Input:
Gilbert 35
Anna 35
Anna 15
Gilbert 20
Joseph 40
Output:
Anna 25.00
Gilbert 27.50
Note: There are 6 test cases. First two of them, you may see in case of wrong answer, and the rest four test cases are hidden.
Points for test cases: 0.5,0.5,1,1,1,1. Altogether you may get 5 points for this problem.
Please note that to get points you must backup all the files (source codes, input and output files,
readme.txt file) with the description of the solution in the appropriate folder named solution on
the server ibsu.animima.org. Test your program and show how to run it.
Problem 7. (5 points) (writing code in C language) (SPOJ)
Link: https://www.spoj.com/ITP2020/problems/ITPST1/
Problem: Write the program simulating the stack using 10-element array. At the beginning the stack
is empty and then some elements are pushed to the stack or popped (taken) from the stack related to
the commands given in the input.
Input: In the input there are at most 10000 commands, where each command consists from one or
two lines. The first type of the command, represented by the line with a char '-', is the command of
taking an element from the top of a stack and writing it to the output. The second command,
represented by two lines with a char '+' in the first line and an integer number from range [-
1000000000,1000000000] in the second line, is the pushing a number to the top of the stack.
Output: In the sequence of lines write to the output the result of the performing of all the commands,
as follows: if we pushed a number to the stack, we write ':)', in the case of illegal command (e.g.,
pushing an element to the full stack or popping an element from an empty stack) we write ':(',
otherwise if we pop an element from the stack we write this number the the output.
Example: see https://www.spoj.com/ITP2020/problems/ITPST1/
Note: there are two test cases (worth 1 and 4 points).
IBSU. R3.F17E; Revision No.: 0 Page No: 5 /6
INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY - INTERNATIONAL BLACK SEA UNIVERSITY
EXAMINATION PAPER
GRADE In numbers: Written:
Please note that to get points you must backup all the files (source codes, input and output files,
readme.txt file) with the description of the solution in the appropriate folder named solution on
the server ibsu.animima.org. Test your program and show how to run it.
Problem 8. (5 points)
Please describe in details using example, what is a HEAP structure (definition) and how you may
use it to sort efficiently a sequence of integers. Starting from the sequence
(14,18,6,2,15,19,13,9,3,7,5,20) build min-HEAP by applying procedure heapify (create a heap out of
given array of elements). Then, TWO times apply the following procedure: remove the minimum
element from the heap by replacing it with the last element from the array and restore the heap
property. Write down the final array (heap of ten elements) after performing all these operations.
Please note that to get points you must backup all the files (solution, readme.txt file, etc) with the
description of the solution in the appropriate folder named solution on the server
ibsu.animima.org.
IBSU. R3.F17E; Revision No.: 0 Page No: 6 /6
