Introduction to Computer Science - Exercise 7

Name: Saggi Mizrahi • ID: 032493124 • Group: מעוף א' • Date: December 04, 2013

Arrays

10.

Code:

/* psort.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

int getMaxIncDecSeq(int arr[], int n) {
    int hop = n / 2;
    int i = hop;
    while (arr[i] < arr[i - 1] || arr[i] < arr[i + 1]) {
        hop /= 2;
        hop = hop > 1 ? hop : 1;
        if (arr[i] > arr[i - 1]) {
            i += hop;
        } else {
            i -= hop;
        }
    }
    return i;
}

int main()
{
    int const SIZE = 7;
    int arr[SIZE];
    int num;
    cout << "enter " << SIZE << " numbers:";
    for (int i = 0; i < SIZE; i++) {
        cin >> num;
        arr[i] = num;
    }
    int i = getMaxIncDecSeq(arr, SIZE);

    cout << "a[" << i << "] : " << arr[i] << endl;
}

Outputs:

enter 7 numbers:13 19 23 25 16 14 8
a[3] : 25

enter 7 numbers:13 19 23 24 25 14 8
a[4] : 25

11.

Code:

/* psort.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

const int N = 7;

int findone(int arr[], int size, int gap) {
    int hop = size / 2;
    int i = hop;
    while (arr[i * gap] != 1 || arr[(i - 1) * gap] != 0) {
        hop /= 2;
        hop = hop > 1 ? hop : 1;
        if (arr[i * gap] == 0) {
            i += hop;
        } else {
            i -= hop;
        }
    }
    return i;
}
void getUpperLeft(int mat[][N], int n, int& row, int& col) {
    row = findone(mat[N - 1], N, 1);
    col = findone(&mat[0][N - 1], N, N);
}

int main()
{
    int row, col;
    int arr[N][N];
    int num;
    cout << "enter " << N*N << " numbers: " << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> num;
            arr[i][j] = num;
        }
    }
    getUpperLeft(arr, N, row, col);

    cout << "(" << row << ", " << col << ")" << endl;
}

Outputs:

enter 49 numbers: 
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
0 0 0 0 1 1 1
0 0 0 0 1 1 1
(4, 3)

enter 49 numbers: 
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
(6, 6)

enter 49 numbers: 
0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 1 1 1 1 1 1
0 1 1 1 1 1 1
0 1 1 1 1 1 1
0 1 1 1 1 1 1
0 1 1 1 1 1 1
(1, 1)

Pointers

1.

a)

א

Yes

ב

No

ג

1004
1044
1008

b)

א

Yes

ב

No

ג

1000
10
1004

c)

א

Yes

ב

Yes - *ptr1 is being assinged before ptr1 was set.

ג

**Unknown**

d)

א

Yes

ב

No

ג

20

e)

א

No - invalid conversion from 'int*' to 'int'

ב

yes

f)

א

Yes

ב

No

ג

9

g)

א

Yes

ב

No

ג

5
9

h)

א

Yes

ב

No

ג

9

i)

א

Yes

ב

No

ג

9
12
21
6

j)

א

Yes

ב

No

ג

9
10

k)

א

No - assignment to arithmatic expression

2.

Code:

/* swappy.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

void swap(int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int main()
{
    int x = 5;
    int y = 3;
    swap(x, y);
    cout << x << y;
}

Outputs:

35

3.

Code:

/* catend.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

void strcat(char* t, char* s) {
    for (;*t != '\0'; t++);
    for(;*s !='\0'; s++, t++) {
        *t = *s;
    }
    *t = '\0';
}

int strlen(char *s) {
    char* c;
    for (c = s; *c != '\0'; c++);
    return c - s;
}

int strcmp(char *s , char *t) {
    for (; *s == *t && *s != '\0'; s++, t++);
    return *s - *t;
}

bool strend(char *s, char *t) {
    int sn = strlen(s);
    int tn = strlen(t);
    if (tn > sn) {
        return false;
    }

    return strcmp(s + (sn - tn), t) == 0;
}


int main()
{
    const int MAX_WORD_LEN = 100;
    char word1[MAX_WORD_LEN * 2];
    char word2[MAX_WORD_LEN];
    cout << "enter 2 strings:" << endl;
    cin.getline(word1, MAX_WORD_LEN);
    cin.getline(word2, MAX_WORD_LEN);

    cout << "'" << word2 << "' is ";
    if (!strend(word1, word2)) {
        cout << "not ";
    }
    cout << "a suffix of '" << word1 << "'" << endl;

    strcat(word1, word2);
    cout << "concatenated: " << word1 << endl;
}

Outputs:

enter 2 strings:
Winston
on
'on' is a suffix of 'Winston'
concatenated: Winstonon

enter 2 strings:
Marlbro
bra
'bra' is not a suffix of 'Marlbro'
concatenated: Marlbrobra

4.

Code:

/* findocc.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>
#include <string.h>

using namespace std;

int* fincOccur(char* text, char* str, int& size);

int* findOccur(char* text, char* str, int& size) {
    int n = strlen(text);
    int* res = new int[n];
    char* c;
    int offset = 0;
    size = 0;

    while((c = strstr(text, str)) != 0) {
        res[size] = offset + (c - text);
        offset = res[size] + 1;
        size++;
        text = c + 1;
    }

    return res;
}


int main()
{
    const int MAX_WORD_LEN = 100;
    char word1[MAX_WORD_LEN * 2];
    char word2[MAX_WORD_LEN];
    int *indices;
    int n;
    cout << "enter 2 strings:" << endl;
    cin.getline(word1, MAX_WORD_LEN);
    cin.getline(word2, MAX_WORD_LEN);

    indices = findOccur(word1, word2, n);
    if (n > 0) {
        cout << indices[0];
    }
    for (int i = 1; i < n; i++) {
        cout << ", " << indices[i];
    }
}

Outputs:

enter 2 strings:
aababacdaba
aba
1, 3, 8
enter 2 strings:
aababacdaba
a
0, 1, 3, 5, 8, 10

5.

Code:

/* gradeinput.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

const int SUCCESS = 0;
const int ALLOCATION_ERROR = -1;

/* reallocates an array.
 * a must be heap allocated.
 * returns 0 on success.
*/
int realloc(int* &a, int size, int new_size) {
    int* old = a;
    a = new int[new_size];
    if (!a) {
        a = old;
        return ALLOCATION_ERROR;
    }
    for (int i = 0; i < size; i++) {
        a[i] = old[i];
    }

    delete [] old;
    return 0;
}

int readPositiveNumbers(int* &a, int &size, int &capacity) {
    capacity = 2;
    size = 0;
    int num;
    int rc;
    a = new int[size];
    cin >> num;
    while (num != -1) {
        if (size >= capacity) {
            if ((rc = realloc(a, capacity, capacity * 2)) != SUCCESS) {
                delete [] a;
                return rc;
            }
            capacity *= 2;
        }
        a[size] = num;
        size++;
        cin >> num;
    }
    return 0;
}

int main()
{
    int* a;
    int n;
    int capacity;
    int rc;

    cout << "please enter grades: ";
    if ((rc = readPositiveNumbers(a, n, capacity)) != SUCCESS) {
        return rc;
    }

    cout << "Got " << n << " grades in an array with capacity " <<
        capacity << endl;

    return 0;
}

Outputs:

please enter grades: 2 3 4 2 2 5 2 4 3 4 2 -1
Got 11 grades in an array with capacity 16

please enter grades: 2 3 4 2 2 5 2 4 3 4 2 9 123 123 123 1289 3 1 1 1 32 1 1024 123 -1
Got 24 grades in an array with capacity 32

Complexity

Reallocation is an O(n) operation. We do it log(n) times in increasing powers of 2. This means given n items the overall complexity will be the sum of 2^1 + 2^2 + ... + 2^{log(n)}.

This is equivalent to: {log(n)(log(n)+1)(2log(n)+1)}\over{6}

6.

Code:

/* threescompany.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

// ** <heapsort> ** //

// method decleration
void swap(int** a, int i1, int i2);
void heapsort(int** a, int n);
void heapify(int** a, int n);
void siftDown(int** a, int i, int n);
void siftUp(int** a, int i);


// swap 2 integers pointers in an array
void swap(int** a, int i1, int i2) {
    int* tmp = a[i1];
    a[i1] = a[i2];
    a[i2] = tmp;
}

// reorder misplaced child in heap
void siftUp(int** a, int i) {
    // stop if reached root of heap
    if (i == 0) {
        return;
    }

    int parentIdx = (i - 1) / 2;
    if (*a[i] > *a[parentIdx]) {
        swap(a, parentIdx, i);
        siftUp(a, parentIdx);
    }
}

// reorder misplaced parent in heap
void siftDown(int** a, int i, int n) {
    // stop if node has no children
    if (((i + 1) * 2) >= n) {
        return;
    }

    int son1Idx = (i * 2) + 1;
    int son2Idx = son1Idx + 1;
    int sonIdx = *a[son1Idx] > *a[son2Idx] ? son1Idx : son2Idx;
    if (*a[sonIdx] > *a[i]) {
        swap(a, sonIdx, i);
        siftDown(a, sonIdx, n);
    }
}

// Turn a random array in to a heap
void heapify(int** a, int n) {
    for (int i = 1; i < n; i++) {
        siftUp(a, i);
    }
}

// Sort an array using heapsort
void heapsort(int** a, int n) {
    heapify(a, n);

    // Sort the heap
    for (int i = 0; i < n; i++) {
        swap(a, 0, n - i - 1);
        siftDown(a, 0, n - i - 2);
    }
}

// ** </heapsort> ** //

// Print repeated pointed values and their indeces in relation to offset.
void printRepeatedItems(int** a, int n, int k, int* offset) {
    int** cache = new int*[k];
    int cacheIdx = 0;
    int c = -1;
    bool printed = false;
    for (int i = 0; i < n; i++) {
        if (*a[i] != c) {
            if (printed) {
                cout << endl;
                printed = false;
            }
            c = *a[i];
            cache[0] = 0;
            cacheIdx = 0;
        }
        if (cacheIdx < k) {
            cache[cacheIdx] = a[i];
            cacheIdx++;
        }
        if (cacheIdx == k) {
            printed = true;
            cout << c << ": ";
            cout << cache[0] - offset;
            for (int j = 1; j < k; j++) {
                cout << ", ";
                cout << cache[j] - offset;
            }
            cacheIdx++;
        } else if (cacheIdx > k) {
            cout << ", " << a[i] - offset;
        }
    }
    if (printed) {
        cout << endl;
    }
    delete [] cache;
}

void pointerArr(int* b[], int a[], int n) {
    for (int i = 0; i < n; i++) {
        b[i] = &a[i];
    }
}

const int SUCCESS = 0;
const int ALLOCATION_ERROR = -1;

/* reallocates an array.
 * a must be heap allocated.
 * returns 0 on success.
*/
int realloc(int* &a, int size, int new_size) {
    int* old = a;
    a = new int[new_size];
    if (!a) {
        a = old;
        return ALLOCATION_ERROR;
    }
    for (int i = 0; i < size; i++) {
        a[i] = old[i];
    }

    delete [] old;
    return 0;
}

int readPositiveNumbers(int* &a, int &size, int &capacity) {
    capacity = 2;
    size = 0;
    int num;
    int rc;
    a = new int[size];
    cin >> num;
    while (num != -1) {
        if (size >= capacity) {
            if ((rc = realloc(a, capacity, capacity * 2)) != SUCCESS) {
                delete [] a;
                return rc;
            }
            capacity *= 2;
        }
        a[size] = num;
        size++;
        cin >> num;
    }
    return 0;
}

int main()
{
    int* a;
    int n;
    int capacity;
    int** b;
    int rc;

    cout << "please enter numbers: ";
    if ((rc = readPositiveNumbers(a, n, capacity)) != SUCCESS) {
        return rc;
    }

    b = new int*[n];
    if (!b) {
        return ALLOCATION_ERROR;
    }
    pointerArr(b, a, n);
    heapsort(b, n);
    printRepeatedItems(b, n, 3, a);

    delete [] a;
    delete [] b;
    return 0;
}

Outputs:

please enter numbers: 2 3 4 2 2 5 2 4 3 4 2 -1
2: 6, 3, 0, 4, 10
4: 9, 7, 2

please enter numbers: 2 3 4 2 2 5 2 4 3 4 2 9 123 123 123 1289 3 1 1 1 32 1 1024 123 -1
1: 19, 21, 17, 18
2: 0, 6, 10, 3, 4
3: 8, 1, 16
4: 7, 9, 2
123: 12, 23, 14, 13

7.

Code:

/* sets.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

const int* PHI = NULL;

int* setcpy(int* set, int n) {
    int* res = new int[n];
    for (int i = 0; i < n; i++) {
        res[i] = set[i];
    }
    return res;
}

void setAppend(int* set, int &i, int v) {
    if (i == 0 || set[i - 1] != v) {
        set[i] = v;
        i++;
    }
}

void setTruncate(int* &set, int size, int capacity) {
    if (size == capacity) {
        return;
    }

    if (size == 0) {
        delete [] set;
        set = (int*) PHI;
    }

    int* res = new int[size];
    for (int i = 0; i < size; i++) {
        res[i] = set[i];
    }
    delete [] set;
    set = res;
}

int* unite(int* a, int sizeA, int* b, int sizeB, int& sizeAuniteB) {
    if (a == PHI) {
        sizeAuniteB = sizeB;
        return setcpy(b, sizeB);
    }
    if (b == PHI) {
        sizeAuniteB = sizeA;
        return setcpy(a, sizeA);
    }

    int capacity = sizeA + sizeB;
    int* res = new int[capacity];
    sizeAuniteB = 0;
    int ia = 0;
    int ib = 0;
    int item;
    while (ia < sizeA && ib < sizeB) {
        if (a[ia] < b[ib]) {
            item = a[ia];
            ia++;
        } else {
            item = b[ib];
            ib++;
        }
        setAppend(res, sizeAuniteB, item);
    }

    while (ia < sizeA) {
        setAppend(res, sizeAuniteB, a[ia]);
        ia++;
    }

    while (ib < sizeB) {
        setAppend(res, sizeAuniteB, b[ib]);
        ib++;
    }

    setTruncate(res, sizeAuniteB, capacity);
    return res;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int* intersect(int* a, int sizeA, int* b, int sizeB, int& sizeAintB) {
    if (a == PHI || b == PHI) {
        sizeAintB = 0;
        return (int*) PHI;
    }

    int capacity = max(sizeA, sizeB);
    int* res = new int[capacity];
    sizeAintB = 0;
    int ia = 0;
    int ib = 0;
    while (ia < sizeA && ib < sizeB) {
        if (a[ia] < b[ib]) {
            ia++;
        } else if (a[ia] > b[ib])  {
            ib++;
        } else {
            res[sizeAintB] = a[ia];
            ia++;
            ib++;
            sizeAintB++;
        }
    }

    setTruncate(res, sizeAintB, capacity);
    return res;
}

int* minus_(int* a, int sizeA, int* b, int sizeB, int& sizeAminB) {
    if (a == PHI) {
        sizeAminB = 0;
        return (int*) PHI;
    }
    if (b == PHI) {
        sizeAminB = sizeA;
        return setcpy(a, sizeA);
    }
    int capacity = sizeA;
    int* res = new int[capacity];
    sizeAminB = 0;
    int ia = 0;
    int ib = 0;
    while (ia < sizeA && ib < sizeB) {
        if (a[ia] < b[ib]) {
            res[sizeAminB] = a[ia];
            sizeAminB++;
            ia++;
        } else if (a[ia] > b[ib])  {
            ib++;
        } else {
            ia++;
            ib++;
        }
    }

    while (ia < sizeA) {
        res[sizeAminB] = a[ia];
        ia++;
        sizeAminB++;
    }

    setTruncate(res, sizeAminB, capacity);
    return res;
}

int* xor_(int* a, int sizeA, int* b, int sizeB, int& sizeAxorB) {
    int un, in;
    int* u = unite(a, sizeA, b, sizeB, un);
    int* i = intersect(a, sizeA, b, sizeB, in);
    int* m = minus_(u, un, i, in, sizeAxorB);
    delete [] u;
    delete [] i;
    return m;
}

int* readset(int& n) {
    int* res;
    cout << "please enter number of items in set: ";
    cin >> n;

    if (n == 0) {
        return (int*) PHI;
    }

    cout << "please enter set items: ";
    res = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }

    return res;
}

void printset(int* s, int n) {
    if (s == PHI) {
        cout << "{}";
        return;
    }

    cout << "{";
    if (n > 0) {
        cout << s[0];
    }

    for (int i = 1; i < n; i++) {
        cout  << ", " << s[i];
    }

    cout << "}";
}

int main()
{
    int an, bn, un, in, m1n, m2n, xn;
    int *setA, *setB, *u, *i, *m1, *m2, *x;

    setA = readset(an);
    setB = readset(bn);

    u = unite(setA, an, setB, bn, un);
    i = intersect(setA, an, setB, bn, in);
    m1 = minus_(setA, an, setB, bn, m1n);
    m2 = minus_(setB, bn, setA, an, m2n);
    x = xor_(setA, an, setB, bn, xn);

    cout << "A : "; printset(setA, an); cout << endl;
    cout << "B : "; printset(setB, bn); cout << endl;
    cout << "A ∪ B : "; printset(u, un); cout << endl;
    cout << "A ∩ B : "; printset(i, in); cout << endl;
    cout << "A \\ B : "; printset(m1, m1n); cout << endl;
    cout << "B \\ A : "; printset(m2, m2n); cout << endl;
    cout << "A △ B : "; printset(x, xn); cout << endl;
}

Outputs:

please enter number of items in set: 4
please enter set items: 1 2 3 4
please enter number of items in set: 6
please enter set items: 3 4 5 6 10 23
A : {1, 2, 3, 4}
B : {3, 4, 5, 6, 10, 23}
A ∪ B : {1, 2, 3, 4, 5, 6, 10, 23}
A ∩ B : {3, 4}
A \ B : {1, 2}
B \ A : {5, 6, 10, 23}
A △ B : {1, 2, 5, 6, 10, 23}

please enter number of items in set: 0
please enter number of items in set: 4
please enter set items: 3 4 5 6
A : {}
B : {3, 4, 5, 6}
A ∪ B : {3, 4, 5, 6}
A ∩ B : {}
A \ B : {}
B \ A : {3, 4, 5, 6}
A △ B : {3, 4, 5, 6}

please enter number of items in set: 4
please enter set items: 1 2 3 4
please enter number of items in set: 0
A : {1, 2, 3, 4}
B : {}
A ∪ B : {1, 2, 3, 4}
A ∩ B : {}
A \ B : {1, 2, 3, 4}
B \ A : {}
A △ B : {1, 2, 3, 4}

8.

Code:

/* sets.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

int* notIn(int arr[], int aLen, int indices[], int indLen);

int* notIn(int arr[], int aLen, int indices[], int indLen) {
    if (aLen == indLen) {
        return NULL;
    }

    int* buckets = new int[aLen];
    int* res = new int[aLen];
    for (int i = 0; i < aLen; i++) {
        buckets[i] = 0;
    }

    for (int i = 0; i < indLen; i++) {
        buckets[indices[i]]++;
    };

    int n = 0;
    for (int i = 0; i < aLen; i++) {
        if (!buckets [i]) {
            res[n] = arr[i];
            n++;
        }
    }
    delete [] buckets;

    return res;
}

int* readnums(int& n) {
    int* res;
    cout << "please enter number of items in array: ";
    cin >> n;

    cout << "please enter items: ";
    res = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }

    return res;
}

void printarr(int* s, int n) {
    if (s == NULL) {
        cout << "[]";
        return;
    }

    cout << "[";
    if (n > 0) {
        cout << s[0];
    }

    for (int i = 1; i < n; i++) {
        cout  << ", " << s[i];
    }

    cout << "]";
}

int main()
{
    int aLen, indLen;
    int *arr, *indices;
    arr = readnums(aLen);
    indices = readnums(indLen);
    int* res = notIn(arr, aLen, indices, indLen);
    printarr(res, aLen - indLen);

    delete [] arr;
    delete [] indices;
    delete [] res;
}

Outputs:

please enter number of items in array: 5
please enter items: 2 3 14 11 14
please enter number of items in array: 3
please enter items: 2 0 4
[3, 11]
please enter number of items in array: 5
please enter items: 2 3 14 11 14
please enter number of items in array: 5
please enter items: 1 0 4 3 2
[]

9.

Code:

/* psort.cpp
 *
 * Saggi Mizrahi 04 December 2013
 */
#include <iostream>

using namespace std;

void swap(int* a[], int i1, int i2) {
    int* tmp = a[i1];
    a[i1] = a[i2];
    a[i2] = tmp;
}

void bubblesort(int* a[], int n) {
    bool hasSwapped = true;
    for (int i = 0; i < n && hasSwapped; i++) {
        hasSwapped = false;
        for (int j = 1; j < (n - i); j++) {
            if (*a[j - 1] > *a[j]) {
                hasSwapped = true;
                swap(a, j - 1, j);
            }
        }
    }
}

int* readnums(int& n) {
    int* res;
    cout << "please enter number of items in array: ";
    cin >> n;

    cout << "please enter items: ";
    res = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }

    return res;
}

void pointerSort(int arr[], int size, int* pointers[]) {
    for (int i = 0; i < size; i++) {
        pointers[i] = &arr[i];
    }

    bubblesort(pointers, size);
}

void pointerSort2(int arr[], int size, int** &pointers) {
    pointers = new int*[size];
    pointerSort(arr, size, pointers);
}


void printparr(int** s, int n) {
    if (s == NULL) {
        cout << "[]";
        return;
    }

    cout << "[";
    if (n > 0) {
        cout << *s[0];
    }

    for (int i = 1; i < n; i++) {
        cout  << ", " << *s[i];
    }

    cout << "]";
}

int main()
{
    int aLen;
    int *arr, **indices;
    arr = readnums(aLen);
    pointerSort2(arr, aLen, indices);

    printparr(indices, aLen);

    delete [] arr;
    delete [] indices;
}

Outputs:

please enter number of items in array: 5
please enter items: 2 562 14 11 14
[2, 11, 14, 14, 562]
please enter number of items in array: 8
please enter items: 2 3 14 11 14 0 123 -2
[-2, 0, 2, 3, 11, 14, 14, 123]