$24
Written Homework 1 Solution
PROBLEM 1: The function num_distinctto the right takes an array a[] of n integers and determines the number of distinct values in the array. This number is then returned.
Examples:
[5, 5, 5, 5, 5] has one distinct value.
[1, 2, 3, 4, 5] has five distinct values.
[1, 2, 3, 2, 1] has three distinct values.
Take a few minutes to understand the logic of the function and why it works.
int num_distinct(int a[], int n){ int i, j, ndistinct; bool is_dup;
ndistinct=0;
for(i=0; i<n; i++) { is_dup=false; for(j=0; j<i; j++) {
if(a[j] == a[i])
is_dup = true;
}
if(!is_dup)
ndistinct++;
}
return ndistinct;
}
Your job:write a linked-list version of exactlythe same algorithm. A linked list is a sequence of elements just like an array after all -- i.e., a given linked list either has duplicates or it does not.
Use the struct and function prototype below.
struct node {
int val;
node *next;
};
int num_distinct(node *lst) {
}
You will submit your code just within your homework document (i.e., you are not submitting your .cpp file). Of course, you are free and encouraged to try out your solution in a real program.
n(n−1)
2 .
PROBLEM 2: Consider a finite set S with n elements; the number of distinct subsets of S with exactly two is called "n choose 2" and typically written as (2n) .
You may Recall that (2n) =
Below is a (trivial) C++ function which takes a non-negative integer n and returns (2n) (also a non-negative integer):
unsigned int n_choose_2(unsigned int n) {
if(n==0)
return 0;
else
return n*(n-1)/2;
}
Your job: write a function which also returns (2n) but with the following constraints:
You cannot use the multiplication operator ‘*’
You cannot use the division operator ‘/’
You cannot have any loops
You cannot add any additional parameters to the function
Your function must be self-contained: no helper functions!
You cannot use any globals
You cannot use any static variables
You cannot use any "bit twiddling" operations -- no shifts, etc.
However, …
You canuse recursion
You canuse the ‘+’ and ‘-’ operators.
You will submit a scanned hardcopy (hand-written or printed) or pdf via gradescope. Of course, you are free to try out your solution in a real program.
In addition: argument of correctness required!
You must explain the logic of your solution! In other words, explain why it works. Think in terms of an inductive argument.
Just giving a correct C++ function is not sufficient and will not receive many points (possibly zero!)
Another note: an example is not an argument of correctness!
PROBLEM 3: Consider the C++ function below:
void fubar(unsigned int n) {
int i, j;
for(i=0; i<n; i++){
cout <<"tick" << endl;
}
for(i=0; i<n; i++) {
for(j=0; j<i; j++) {
cout <<"tick" << endl;
}
}
}
3.A: Complete the following table indicating how many “ticks” are printed for various parameters n.
Unenforceable rule: derive your answers “by hand” -- not simply by writing a program calling the function.
n
number of ticks printed when
fubar(n) is called
0
1
2
3
4
3.B: Derive a
closed-form expressing the number of ticks as a function of n --
i.e., complete
the following:
“For all
n ≥ 0 , calling fubar(n) results in _____________ ticks being
printed”
Give a brief justification of your answer; you do not need a formal proof.
PROBLEM 4: Consider the recursive C++ function below:
void foo(unsigned int n) {
if(n==0)
cout << "tick" << endl;
else {
foo(n-1);
foo(n-1);
foo(n-1);
}
}
4.A: Complete the following table indicating how many “ticks” are printed for various parameters n.
Unenforceable rule: derive your answers “by hand” -- not simply by writing a program calling the function.
number of ticks printed when
foo(n) is called
0
1
2
3
4
4.B: Derive a conjecture expressing the number of ticks as a function of n -- i.e., complete the following:
“Conjecture: for all n ≥ 0 , calling foo(n) results in _____________ ticks
being printed”
4.C: Prove your conjecture from part B (hint: Induction!)
QUESTION 5: Write a C++ function called layerswhich takes an NxN integer array (for some constant N) and populates the entries 0..N2-1 as follows:
The upper left entry (row-0, col-0) is 0.
Subsequent numbers are assigned along Southwest-to-Northeast diagonals, layer-by-layer.
For example, if N=4, your function would result in the following assignment to entries in the array:
0
2
5
9
1
4
8
12
3
7
11
14
6
10
13
15
(the individual “layers” are shown by alternating shading).
#define N 10 // or some other number...
// your function here
void layers(int a[][N]) {
}
QUESTION 6: Short description:
A. Write a function which determines if a given array of n integers is a permutationof {0..n-1}.
B. Write a function which takes a permutation of n integers and constructs its inverse.
Background: recall that a permutation of a set of integers is just an ordered listing of the elements. For example, consider the set S = {0, 1, 2} .
example permutations of S
These are notpermutations of S
[0, 1, 2]
[5, 0, 1]
[1, 2,
0]
[0, 1,
0]
[2, 0,
1]
[2, 1,
1]
Suppose an array of n integers is indeed a permutation of {0..n − 1} . We can view such an array as a bijectivefunction ffrom POSITION-to-ELEMENT-AT-INDEX:
: {0..n − 1} → {0..n − 1} .
Since f is a bijection, it also has an inversewhich is a function from
ELEMENT-to-POSITION-OF-ELEMENT:
f −1 : {0..n − 1} → {0..n − 1}
Examples of permutations of {0,1,2} and their inverses as array diagrams:
Permutation
Inverse
val
1
2
0
val
2
0
1
idx
0
1
2
idx
0
1
2
val
2
1
0
val
2
1
0
idx
0
1
2
idx
0
1
2
val
2
0
1
val
1
2
0
idx
0
1
2
idx
0
1
2
Finally, your tasks:
Write a C++ function is_permwhich determines if a given array of n integers is a permutationof {0..n-1}.
Write a function which takes a permutation as an array of n integers and constructs its inverse(also as an array). Your function will allocate storage for the inverse array and returns it as an integer pointer. If the array it receives is not a permutation of {0..n-1}, it returns nullptr instead.
Templates given below.
bool is_perm(int a[], int n) {
}
int * perm2inverse(int a[], int n) {
if(!is_perm(a, n)) // to get you started...
return nullptr;
otherwise, a[] is a permutation of 0..n-1; allocate and populate its
inverse array (and return it)
}
