Written Homework 1 Solution

Submission will be done using gradescope (you will submit your homework as a pdf, either scanned or exported from a word processor). Details of the gradescope submission process will be posted to Piazza.




Your writeup must be neat and clear



There are 6 problems, some with multiple parts; clearly label your answers.



Each Problem will be scored out of 20 points (for a total of 120 points).

PROBLEM 1:​ The function ​num_distinct​to 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 ​exactly​​the 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) {




}







n(n−1)

2 .




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.

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 ​can​use recursion
You ​can​use 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 layers​​which takes an NxN integer array (for some constant N) and populates the entries 0..N​2-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 permutation​of {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 ​not​permutations 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 ​bijective​​function f​from POSITION-to-ELEMENT-AT-INDEX:




: {0..n − 1} → {0..n − 1} .



Since f is a bijection, it also has an ​inverse​which 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​_perm​which determines if a given array of n integers is a ​permutation​of {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)






}