1. Implementați algoritmul de căutare binară. Scrieți o funcție analoagă find_array, care va primi un număr n, un vector sortat v cu n elemente și un număr x. Funcția va determina în mod eficient una dintre pozițiile pe care se afla numărul x.

    int n = 5;
int v[NMAX] = {-1, 4, 5, 10, 30};
int pos = binarysearch(n, v, 10);  // pos = 3
int pos = binarysearch(n, v, 2);   // pos = -1

  2. Scrieți o funcție care primește ca parametri 2 vectori și dimensiunile lor și care găsește diferenta între cei 2 vectori (elementele din primul vector care nu sunt în al doilea vector - asemănător diferenței între mulțimi). De asemenea, funcția mai primește ca parametru un vector diff în care se vor stoca elementele din diferența. Funcția va returna numărul de elemente găsite.

    int n = 5;
int v[NMAX] = {1, -1, 2, -2, 0};

int m = 8;
int w[NMAX] = {10, 8, 1, 2, 5, 5, 5, 5};

int diff[NMAX];
int d = diff_array(n, v, m, w, diff);
print_array(d, diff); // afiseaza: -1 -2 0

d = diff_array(m, w, n, v, diff);
print_array(d, diff); // afiseaza: 10 8 5 5 5 5

  3. Se citește de la tastatură un vector v sortat crescător de lungime n. Se mai dau 2 numere x și y. Să se determine fără a parcurge tot vectorul câte numere sunt în intervalul [x, y] în vector.

    Hint: Necesita modificarea algoritmului de binary search.

    int v[NMAX] = {-1, 4, 5, 10, 30, 30, 30, 40};
int n = sizeof(v) / sizeof(int); // ce face această linie? discutați cu asistentul :D

  4. Scrieți o funcție care primește o matrice a (n x m), un indice de coloana col și afișează cele 2 diagonale care pornesc cu elementul a[0][col]. Elementele afișate sunt înlocuite cu 0 în matrice. Exemplu:

    n = 3, m = 4
col = 1

1 2 3 4
3 4 5 6
6 7 8 9

2 5 9      // prima diagonala
2 3        // cea de-a doua diagonala

1 0 3 4    // se afișează matricea modificata
0 4 0 6
6 7 8 0

  5. Definim o submatrice b a matricei a (n x n), o matrice de dimensiune L x C (1 <= L <= n, 1 <= C <= n), astfel încât b se regăsește ca bloc continuu în a. Exemplu:

    n = 4;
a =  {
    {  1,   2,   3,   4},
    {  5,   6,   7,   8},
    {  9,  10,  11,  12},
    { 13,  14,  15,  16}
};

    Submatrici:

    • de dimensiuni 1x1: Orice element luat sigur :p
    • de dimensiuni 1x2: Orice pereche de 2 elemente consecutive pe linie sau coloana (exemplu: {1, 2} sau {1, 5}) ...
    • de dimensiune 2x2: avem 9 submatrici (2 dintre ele sunt îngroșate mai jos)

    {1,2, 3, 4},

    {5, 6, 7, 8},

    {9, 10, 11, 12},

    {13, 14, 15, 16}

    de dimesiune nxn: este una singura, chiar a

  6. a. Scrieți o funcție care primește o matrice a cu n x n elemente și 4 numere x, y, p, q. Se cere să se afișeze pe ecran submatricea din a cu colțul stânga sus în (x, y) și colțul din dreapta jos în (p, q).

    void print_submatrix(int a[NMAX][NMAX], int x, int y, int p, int q);

    b. Folosind funcția scrisă anterior, să se printeze toate submatricile unei matrice a cu n x n elemente.

    void print_all_submatrix(int n, int a[NMAX][NMAX]);

    c. Folosindu-vă de faptul ca ați învățat să parcurgeți toate submatricile, scrieți o functie care determină dintre TOATE SUBMATRICILE unei matrice a cu nxn elemente, pe aceea care are sumă maximă. Afișați suma și submatricea pe ecran.

    void find_maxsum_submatrix(int n, int a[NMAX][NMAX]);

    Exemplu:

    int n = 4;
int a[NMAX][NMAX] = {
    { -1, -20,   3,  4},
    { -5,   6,   7,  8},
    { -9, -10, -11, 12},
    {-13,  14,  15, 16}
};

  7. Să se printeze în spirală o matrice n x m.

    Exemplu:

    Input:
int a[NMAX][NMAX] = {
    { 1,   2,  3, 4},
    { 12, 13, 14, 5},
    { 11, 16, 15, 6},
    { 10,  9,  8, 7}
};
Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

    Input:
int a[NMAX][NMAX] = {
    { 1,    2,   3,   4,   5},
    { 16, 17, 18, 19,  6},
    { 15, 24, 25, 20,  7},
    { 14, 23, 22, 21,  8},
    { 13, 12, 11, 10,  9}
};
Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

    Hint: definiți următoarele funcții

    // printeaza conturul unei matrice
void print_matrix_border(int a[NMAX][NMAX], int x, int y, int p, int q);

void print_spiral_recursive(int a[NMAX][NMAX], int x, int y, int p, int q);

  8. Să se scrie o funcție care să printeze diagonalele unei matrice (a cu dimensiune n x n), câte una pe o linie.

    void print_diagonals(int n, int m, int a[NMAX][NMAX]);

  9. Să implementeze funcții pentru interschimbarea a 2 linii sau a 2 coloane dintr-o matrice.

    void swap_matrix_rows(int n, int m, int a[NMAX][NMAX],
                    int row_index1, int row_index2);
void swap_matrix_cols(int n, int m, int a[NMAX][NMAX],
                    int col_index1, int col_index2);

  10. Să se scrie o funcție care primește o matrice a cu dimensiunile n și m. O poziție (x, y) din matrice se consideră specială dacă separă matricea în 4 zone cu număr nenul de elemente (se exclude linia și coloana. Se să determine poziția unui element special din matrice astfel încât diferența între cea mai mare și cea mai mică sumă din cele 4 formate prin acest împărțire este minimă).
    În cazul în care o astfel de poziție nu există, se va afișa perechea -1 -1.

    int find_special_element(int n, int m, size_t a[NMAX][NMAX]);

    Input: n = 4, m = 4
a =
1 2 3 4
4 3 2 1
5 6 7 8
8 7 6 5

Output:
2 1

    Explicație: Singurele elemente candidat sunt:

    • poziția (1, 1) care împarte matricea în 4 submatrice cu sumele 1, 7, 26 și 13, diferența maximă fiind 25
    • poziția (1, 2) care împarte matricea în 4 submatrice cu sumele 3, 4, 13 și 26, diferența maximă fiind 23
    • poziția (2, 1) care împarte matricea în 4 submatrice cu sumele 5, 10, 11, 8, diferența maximă fiind 6
    • poziția (2, 2) care împarte matricea în 4 submatrice cu sumele 10, 15, 5, 5, diferența maximă fiind 10

  11. a. Să se rezolve problema pc-loto de pe Hackerrank.
    b. Să se scrie o funcție care primește un vector, lungimea sa n și un număr natural k < n și printează pe ecran cele mai mari k numere din vector, separate prin câte un spațiu.
    Follow-up: Rezolvați problema fără a sorta complet vectorul..

  12. Să se scrie o funcție care returnează lungimea celei mai lungi subsecvențe crescătoare dintr-un vector primit ca parametru.
    Hint: Termenul de subsecvență se referă la o serie de elemente aflate pe poziții consecutive într-un vector.

    int longest_increasing_subarray(int v[NMAX], int n);

  13. Să se rezolve problema c_perm de pe Hackerrank.