讲解SCC 120、辅导C/C++编程、讲解C/C++语言、辅导BJTU/LU
- 首页 >> C/C++编程SCC 120 Fundamentals of Computer Science
Term 1 Coursework
Deadline for submission: Friday 16th November, 2018, at 20:00 (week 10)
Submission is electronic as PDF file on Moodle.
This coursework is worth 20% for both BJTU and LU credits.
Please answer all questions. You must do this coursework completely by yourself. In this
instance, it means you are not even allowed to discuss the coursework questions with
other students. Your submitted files will automatically be checked for plagiarism.
You are allowed to ask the instructor about these questions. But I can only clarify the
questions or give you suggestions if you get stuck, and I will try not to tell you whether
you have the correct answer (to be fair to all students).
MY E-MAIL: yuanjd@bjtu.edu.cn
1
Coursework Term 1 SCC120
18/19
For the following 3 questions, let A = {a, b, c, e, m, n, r, y} and B = {a, d, e, k, l}.
Q1. What is A B
[1 mark]
Q2. What is B – A [1 mark]
Q3. What is A B
[1 mark]
For the following 5 questions, let f(x) = 2x – 2 and g(x) = 3x + 3.
Q4. What is the function f + g
[1 mark]
Q5. What is the function f * g
[2 marks]
Q6. What is the function f g
[2 marks]
Q7. Find the inverse function of f(x).
[3 marks]
Q8. Define f(x) recursively.
[3 marks]
2
Q9. Convert the following English statement into a proposition.
“Stephen Moffat is a bad, bad man if Clara is really dead”.
[1 mark]
For the following 2 questions, here are some equivalences.
Implication : (P Q) ( ~ P Q)
Associativity : (P Q) R P (Q R)
Commutivity : (P Q) (Q P)
Domination : (P True) True
Q10. To convert (D E) ~G into ~G (D E), which equivalence do you apply?
[1 mark]
Q11. To convert (D E) G into ~(D E) G, which equivalence do you apply?
[2 marks]
Q12. What is the decimal equivalent of the two’s complement 8-bit binary 11110010?
[2 marks]
Consider the following C code, used in Qs 13-15.
char drink[] = “tea”;
strcpy(drink, “coffee”);
Q13. What is the size of the array drink?
[2 marks]
Q14. If the runtime allocates the character ‘t’ in drink at address 128 (decimal), what is the
address of the character ‘a’, assuming each byte has its own address?
[2 marks]
Q15. What is the result after executing statement strcpy(drink, “coffee”)?
[2 marks]
3
Consider the following C code, used for Qs 16-17
int sum = 0;
for (i=0; i<6; i++) {
printf (“Counting…\n”);
for (j=0; j<i; j++)
sum = sum + 1;
}
Q16. How many “Counting…” messages will be printed?
[2 marks]
Q17. What is the value of sum after executing this code?
[2 marks]
Q18. Which of the following statements are NOT true for structures? Tick all that apply.
a. Fields of a structure can be randomly accessed using an integer index like arrays.
b. Fields of a structure must be the same data type.
c. Structures are compound data structures.
d. In C, programmers must provide methods as part of the structure definition to access fields
of the structure.
[2 marks]
Q19. A speed camera takes digital images of the number plates of vehicles detected speeding.
An image is stored locally in a structure. At the end of every day, the collection of records is
uploaded to a database in the local police authority. For the software that executes in the
speed camera, what is the main disadvantage of storing the digital images in an array
compared with storing them in a linked list?
[2 marks]
4
[2 marks]
Q21)The following questions are mainly focus on the Big O notation of functions.
1) The following functions represent the number of statements executed by some algorithms for
input data sets of size n. What is the asymptotic (Big O) complexity class (and name) of each
function? Rank the functions in terms of order of increasing complexity, that is, worse efficiency.
(a) f1(n) = n + 15
(b) f2(n) = 5/4 + 2n2
+ 3n
(c) f3(n) = 10n + n3
+ 234
(d) f4(n) = 432 [5 marks]
2) Consider the code fragment below. Assume the inputs are two arrays of size N and M
respectively.
for (i = 0; i < N; i++) {
sequence of statements
}
for (j = 0; j < M; j++) {
sequence of statements
}
Determine worst-case complexity for each of the following cases. Also explain why.
Each sequence of statements in each loop is O(1)
Each sequence of statements has O(N) complexity
Each sequence of statements in each loop is O(1) but the second loop counts to N
instead of M
[6 marks]
Q20. Consider the following C function foo() that scans a linked list. The
.
structure cell
contains a field called next which is a pointer to another instance of cell
int foo(cell* head){
int
cel
c =
l* c
0;
urrent = head;
while (cu
c = c
rren
+ 1;
t != NULL){
}
return c;
current = current->next;
}
What does the function foo do?
3) What is the worst case complexity class of the following code? Assume n is the size of the input
array.
for (j=1; j<n; j=j*10) {
... some O(1) code ...
}
4) What is the worst complexity class of the following code fragment? Assume the inputs are two
arrays of size N and M respectively. In the code, “condition” takes constant time, “sequence1” takes
O(N) time, and “sequence2” takes O(N2
) time.
for (int i=0; i<M; i++) {
if (condition) {
sequence1
} else {
sequence2
}
}
What if “condition” takes O(N) time?
5) What is the worst complexity of this code? Assume the input is a table with n rows.
for (int i=0; i<n; i++) {
for (int j=n-5; j<n; j++) {
for (int k=j; k<n; k++) {
... some O(1) code ...
}
}
}
6) The following code fragment takes O(N2
) time in the worst case. Assume the input is a ring with
N elements.
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
... some O(1) code ...
}
}
Make one change (i.e. can only add or replace a single character!) to the above code fragment to get
each of these complexities. There can be more than one way to get some of these.
(a) O(N4
)
(b) O(N3
)
(c) O(N2
) - make a change to get the same time
(d) O(N)
(e) O(1)
5
[5 marks]
[2 marks]
[6 marks]
[2 marks]
6
Q22. (a) Give one example of an input (i.e. an array of integers and an integer to search for)
where sentinel search is faster than linear search. Please explain the reasons.
(b) Give one example of an input (i.e. an array of integers and an integer to search for)
where sentinel search with sorted array (the algorithm in slide titled Sentinel on Sorted) is
faster than sentinel search. Please explain the reasons.
(c) Give one example of an input (i.e. an array of integers and an integer to search for)
where binary search is faster than sentinel search with sorted array. Please explain the
reasons.
[3 marks]
[3 marks]
[3 marks]
7
(b) The best-case runtime for insertion sort is O(n). Using the sequence of integers above,
what would the input be to achieve the best-case runtime?
(c) The worst-case runtime for insertion sort is O(n2
). Using the sequence of integers above,
what would the input be to achieve the worst-case runtime?
(d) What’s the average case of the insertion sort? Please provide details of time complexity
function T(N) and the Big O notation.
[2 marks]
[2 marks]
[4 marks]
Q23. This question is about insertion sort. Let’s say you have an array with these integers:
15,5,30,10,20,6,2,3.
(a) Write out manually what insertion sort would do with this set of integers.
[4 marks]
Q24. (a) Write loop invariant for linear search and binary search.
(b) Write the loop invariant for insertion sort, prove the correctness of insertion sort.
[2 marks]
[5 marks]