Merge branch 'main' of https://github.com/Angeld55/Introduction_to_programming_FMI

12 files changed, 670 insertions, 1 deletions

diff --git a/README.md b/README.md
index 01c0806..06210b3 100644
--- a/README.md
+++ b/README.md
@@ -10,6 +10,7 @@
  - **Тема  8:**  Въведение в указателите. Символни низове(стрингове). Основни операции с низове.
  - **Тема  9:**  Многомерни масиви. Работа с масиви от масиви.
  - **Тема  10:**  Предговор за указатели и референции. Заделяне на динамична памет. Оператори new и delete.
+ - **Тема  11:**  Анализ на алгоритми. Алгоритми за търсене и сортиране.
 
 
 
diff --git a/Sem. 10/README.md b/Sem. 10/README.md
index 213fb84..7a0b14e 100644
--- a/Sem. 10/README.md
+++ b/Sem. 10/README.md
@@ -89,6 +89,20 @@ void f()
  - Да се напише функция, която приема такъв стринг и връща нов стринг с ТОЧНА ГОЛЕМИНА, в който всички цифри са цензурирани. (Всяко число е заменено с '*')
  - Да се напише функция, която приема стринг и връща два стринга с ТОЧНА големина. Първият да бъде съставен само от малките букви, а другият да бъде съставен само от главните букви.
  - Да се напише функция, която приема два сортирани масива от цели числа и поставя в първия масив елементите от двата масива, но в сортиран вид (приемаме, че в първия има достатъчно място).
-
+ - Напишете програма, която приема от стандартния вход число N. След това се прочитат N реда и всеки ред започва с число M, което е дължината на реда. Да се напие функция, която обработва подадената матрица по следния начин:
+Връща се нова матрица, за което е заделена точна големина. Първият ред е конкатенацията на последния ред с първия ред на подадената матрица. Вторият ред е конкатенацията на предпоследния ред с втория ред на подадената матрица и тн.
 
 <h3>Задачи</h3>
+
+**Задача 1:** Решете 4-та задача от примерните, но приемете, че числата в масивите са в интервала [-100, 100].
+
+**Задача 2:** Напишете функция, която приема масив от цели числа и цяло число и елемент на масива. Функцията да преподрежда елементите, така че всички по-малки елементи от подадения да са в ляво от него, а всички по-големи - в дясно. (Забележка: Задачата да се реши с помощта на допълнителен масив - същестува и решение без допълнителна памет (Hoare's partition, Lomuto partition и други), но то не се изисква)
+
+*Вход: [1, 5, 6, 3, 0, -1, 2, 9, 7] ,3* *Изход: [1, 0, 2, ,-1, 3, 6, 5, 9, 7]*
+
+
+**Задача 3:** Напишете функция, която приема масив и връща масив от масиви, на който елементите му са всички непразни подмасиви на дадения.
+
+*Вход: [1, 2, 3]* 
+
+*Изход: [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]*
diff --git a/Sem. 10/example4.cpp b/Sem. 10/example4.cpp
new file mode 100644
index 0000000..8d2105e
--- /dev/null
+++ b/Sem. 10/example4.cpp
@@ -0,0 +1,85 @@
+#include <iostream>
+using namespace std;
+
+
+unsigned input(int**& matrix, int*& sizes)
+{
+	unsigned N;
+	cin >> N;
+
+	matrix = new int*[N];
+	sizes = new int[N];
+
+	for (unsigned i = 0; i < N; i++)
+	{
+		unsigned currentRowSize;
+		cin >> currentRowSize;
+
+		matrix[i] = new int[currentRowSize];
+		sizes[i] = currentRowSize;
+
+		for (unsigned j = 0; j < currentRowSize; j++)
+			cin >> matrix[i][j];
+	}
+
+	return N;
+}
+
+
+int* concat(const int* row1, unsigned row1Size, const int* row2, unsigned row2Size)
+{
+	int* result = new int[row1Size + row2Size];
+
+	for (unsigned i = 0; i < row2Size; i++)
+		result[i] = row2[i];
+	
+	for (unsigned i = 0; i < row1Size; i++)
+		result[row2Size + i] = row1[i];
+
+	return result;
+}
+
+void freeMatrix(int** matrix, unsigned rowsSize)
+{
+	for (int i = 0; i < rowsSize; i++)
+		delete[] matrix[i];
+	delete[] matrix;
+}
+
+void task(int** matrix, unsigned N, int* sizes)
+{
+	unsigned resultRowsCount = (N + 1) / 2;
+	int** resultMatrix = new int*[resultRowsCount];
+
+	int* resultSizes = new int[resultRowsCount];
+
+	for (unsigned i = 0; i < resultRowsCount; i++)
+	{
+		resultSizes[i] = sizes[i] + sizes[N - i - 1];
+		resultMatrix[i] = concat(matrix[i], sizes[i], matrix[N - i - 1], sizes[N - i - 1]);
+	}
+
+	//print
+	for (unsigned i = 0; i < resultRowsCount; i++)
+	{
+		for (unsigned j = 0; j < resultSizes[i]; j++)
+			cout << resultMatrix[i][j] << " ";
+		cout << endl;
+	}
+
+	delete[] resultSizes;
+	freeMatrix(resultMatrix, resultRowsCount);
+
+	delete[] sizes;
+	freeMatrix(matrix, N);
+}
+
+int main()
+{
+	int** matrix;
+	int* sizes;
+
+	unsigned N = input(matrix, sizes); //not sure if I need this func
+
+	task(matrix, N, sizes);
+}
diff --git a/Sem. 11/BinarySearch.cpp b/Sem. 11/BinarySearch.cpp
new file mode 100644
index 0000000..df678ce
--- /dev/null
+++ b/Sem. 11/BinarySearch.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <vector>
+using namespace std;
+
+
+bool linearSearch(const int arr[], unsigned size, int el)
+{
+	for (unsigned i = 0; i < size; i++)
+	{
+		if (arr[i] == el)
+			return true;
+	}
+	return false;
+}
+
+bool binarySearch(const int* arr, unsigned size, int searched)
+{
+	unsigned fromIndex = 0;
+	unsigned toIndex = size - 1;
+
+	while (fromIndex <= toIndex)
+	{
+		unsigned midIndex = fromIndex + (toIndex - fromIndex) / 2;
+
+		if (arr[midIndex] == searched)
+			return true;
+
+		if (arr[midIndex] < searched)
+			fromIndex = midIndex + 1;
+		else
+			toIndex = midIndex - 1;
+	}
+
+	return false;
+}
+
+
+
+int main()
+{
+	const unsigned SIZE = 8;
+	int arr[]  { 1, 12, 33, 14,35,4,17,38};
+	cout << linearSearch(arr, SIZE, 14);
+}
diff --git a/Sem. 11/BubbleSort.cpp b/Sem. 11/BubbleSort.cpp
new file mode 100644
index 0000000..217bf32
--- /dev/null
+++ b/Sem. 11/BubbleSort.cpp
@@ -0,0 +1,39 @@
+#include <iostream>
+using namespace std;
+
+
+void swap(int& a, int& b)
+{
+	int temp = a;
+	a = b;
+	b = temp;
+}
+
+void bubbleSort(int* arr, unsigned size)
+{
+	for (unsigned j = 0; j < size - 1; j++)
+	{
+		bool isSwapped = false;
+
+		for (unsigned i = 0; i < size - 1 - j; i++)
+		{
+			if (arr[i] > arr[i + 1])
+			{
+				swap(arr[i], arr[i + 1]);
+				isSwapped = true;
+			}
+		}
+
+		if (!isSwapped)
+			return;
+	}
+}
+
+int main()
+{
+	int arr[] = { 1,2,2,1, 1 };
+	selectionSort(arr, 5);
+
+	for (int i = 0; i < 5; i++)
+		cout << arr[i] << " ";
+}
diff --git a/Sem. 11/LinearSearch.cpp b/Sem. 11/LinearSearch.cpp
new file mode 100644
index 0000000..b0446e1
--- /dev/null
+++ b/Sem. 11/LinearSearch.cpp
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <vector>
+using namespace std;
+
+
+bool linearSearch(const int arr[], unsigned size, int el)
+{
+	for (unsigned i = 0; i < size; i++)
+	{
+		if (arr[i] == el)
+			return true;
+	}
+	return false;
+}
+
+bool binarySearch(const int arr[], unsigned size, int searched)
+{
+	unsigned fromIndex = 0;
+	unsigned toIndex = size - 1;
+
+	while (fromIndex <= toIndex)
+	{
+		unsigned midIndex = fromIndex + (toIndex - fromIndex) / 2;
+
+		if (arr[midIndex] == searched)
+			return true;
+
+		if (arr[midIndex] < searched)
+			fromIndex = midIndex + 1;
+		else
+			toIndex = midIndex - 1;
+	}
+
+	return false;
+}
+
+
+
+int main()
+{
+	const unsigned SIZE = 8;
+	int arr[]  { 1, 12, 33, 14,35,4,17,38};
+	cout << linearSearch(arr, SIZE, 14);
+}
+
diff --git a/Sem. 11/README.md b/Sem. 11/README.md
new file mode 100644
index 0000000..8f6d197
--- /dev/null
+++ b/Sem. 11/README.md
@@ -0,0 +1,33 @@
+
+
+# Анализ на алгоритми. Алгоритми за търсене и сортиране.
+Сложност: Функция по големината на входа (N)
+
+**Пример**: 
+
+ - При търсене в масив - големината на входа е големината на масива
+ -  При проверка число дали е просто - големината на входа е числото.
+
+При анализа на алгоритми НЕ се интересуваме от точната функция!
+Интересуваме се само то асимптотиката на функцията.
+Колко бързо расте функцията при n->безкрайност.
+
+![enter image description here](https://i.ibb.co/TP0Xrz4/ff.png)
+
+Тук релциите за по-малко и по-равно не са тези, които познаваме.
+Тук визираме скоростта на растежа на функцията.
+
+#### Алгоритми за търсене.
+
+ - Linear search
+ - Binary search
+#### Алгоритми за сортиране.
+ - Bubble sort
+ - Selection sort
+
+
+
+
+<h3>Задачи</h3>
+
+**Задача 1:**
diff --git a/Sem. 11/SelectionSort.cpp b/Sem. 11/SelectionSort.cpp
new file mode 100644
index 0000000..87cc6eb
--- /dev/null
+++ b/Sem. 11/SelectionSort.cpp
@@ -0,0 +1,34 @@
+#include <iostream>
+using namespace std;
+
+void swap(int& a, int& b)
+{
+	int temp = a;
+	a = b;
+	b = temp;
+}
+
+void selectionSort(int* arr, unsigned size)
+{
+	for (unsigned i = 0; i < size - 1; i++)
+	{
+		//findMin
+		int minElementIndex = i;
+		for (unsigned j = i + 1; j < size; j++)
+		{
+			if (arr[j] < arr[minElementIndex])
+				minElementIndex = j;
+		}
+		if (minElementIndex != i)
+			swap(arr[i], arr[minElementIndex]);
+	}
+}
+
+int main()
+{
+	int arr[] = { 1,2,2,1, 1 };
+	selectionSort(arr, 5);
+
+	for (int i = 0; i < 5; i++)
+		cout << arr[i] << " ";
+}
diff --git a/pract_KN/Pract 10/solutions.cpp b/pract_KN/Pract 10/solutions.cpp
new file mode 100644
index 0000000..7ba42bd
--- /dev/null
+++ b/pract_KN/Pract 10/solutions.cpp
@@ -0,0 +1,191 @@
+#include<iostream>

+#include<thread>

+#include<chrono>

+

+const int N = 30;		//game of life grid

+const int RFIRST = 4;	//rows first

+const int RSEC = 4;		//rows second

+const int CFIRST = 4;	//cols first

+const int CSEC = 4;		//cols second

+const int DIM = 4;		//used for three dimentional array

+//First->

+void plusFive(int* a) {

+	*a += 10;

+}

+

+//Second-> 

+void iterateOverMatrix(int matrix[RFIRST][CFIRST]) {

+	for (int i = 0; i < RFIRST; i++)

+		for (int j = 0; j < CFIRST; j++)

+			*(*(matrix + i) + j) = rand() % 100 + 1;

+}

+

+//Third->

+void iterateOverThreeDimentionalArray(int matrix[DIM][DIM][DIM]) {

+	for (int i = 0; i < DIM; i++) {

+		for (int j = 0; j < DIM; j++) {

+			for (int k = 0; k < DIM; k++) {

+				*(*(*(matrix + i) + j) + k) = rand() % 100 + 1;

+			}

+		}

+	}

+}

+

+//Fourth ->

+//Assume that we have correct first and second matrix

+void sumMatrices(const int first[RFIRST][RSEC], const int second[CFIRST][CSEC], int result[RFIRST][CSEC]) {

+	for (int i = 0; i < RFIRST; i++) {

+		for (int j = 0; j < CFIRST; j++) {

+			result[i][j] = first[i][j] + second[i][j];

+		}

+	}

+}

+

+//Fifth ->

+void multiplyMatrices(const int first[RFIRST][CFIRST], const int second[RSEC][CSEC], int result[RFIRST][CSEC]) {

+	for (int i = 0; i < RFIRST; i++) {

+		for (int j = 0; j < CSEC; j++) {

+			for (int k = 0; k < RSEC; k++) {

+				result[i][j] += first[i][k] * second[k][j];

+			}

+		}

+	}

+}

+

+//Sixth ->

+void evolveCell(const int matrix[N][N], int matrixCopy[N][N], int i, int j) {

+	int cnt = -matrix[i][j];					//because we add matrix [i][j] as well

+

+	bool iStartingPosAtZero = (i == 0);			//Fix start point corner case for (i == 0)

+	bool jStartingPosAtZero = (j == 0);			//Fix start point corner case for (j == 0)

+	bool iEndingPosAtLimit = (i == N - 1);		//Fix end point corner case   for (i == N-1)

+	bool jEndingPosAtLimit = (j == N - 1);		//Fix end point corner case   for (j == N-1) 

+

+	//Iterate among the neighbours:

+	for (int x = -1 + iStartingPosAtZero; x < 2 - iEndingPosAtLimit; x++)

+		for (int y = -1 + jStartingPosAtZero; y < 2 - jEndingPosAtLimit; y++)

+			cnt += matrix[i + x][j + y];

+

+	//evolve:

+	if (matrix[i][j] && cnt != 2 && cnt != 3) {

+		matrixCopy[i][j] = 0;

+	}

+	else if (!matrix[i][j] && cnt == 3) {

+		matrixCopy[i][j] = 1;

+	}

+	else {

+		matrixCopy[i][j] = matrix[i][j];

+	}

+}

+

+void evolve(int matrix[N][N]) {

+	int copyMatrix[N][N] = { 0 };

+	for (int i = 0; i < N; i++)

+		for (int j = 0; j < N; j++)

+			evolveCell(matrix, copyMatrix, i, j);

+

+	for (int i = 0; i < N; i++)

+		for (int j = 0; j < N; j++)

+			matrix[i][j] = copyMatrix[i][j];

+}

+

+void printMatrix(const int matrix[N][N]) {

+	for (int i = 0; i < N; i++) {

+		for (int j = 0; j < N; j++) {

+			std::cout.width(2);

+			if (matrix[i][j])

+				std::cout << "*" << " ";

+			else

+				std::cout << " " << " ";

+		}

+		std::cout << std::endl;

+	}

+}

+

+void start(int matrix[N][N]) {

+	//moving pattern:

+	//matrix[1][1] = 1;

+	//matrix[2][2] = 1;

+	//matrix[3][0] = 1;

+	//matrix[3][1] = 1;

+	//matrix[3][2] = 1;

+

+	//flipping ones:

+	//matrix[2][1] = matrix[2][2] = matrix[2][3] = 1;

+

+	//pattern:

+	/*matrix[10][10] = matrix[10][14] = 1;

+	matrix[11][12] = 1;

+	matrix[12][11] = matrix[12][13] = 1;

+	matrix[13][12] = 1;

+	matrix[14][10] = matrix[14][14] = 1;*/

+

+

+	//random pattern:

+	/*matrix[10][10] = matrix[10][14] = 1;

+	matrix[11][12] = 1;

+	matrix[12][11] = matrix[12][13] = 1;

+	matrix[13][13] = 1;

+	matrix[14][10] = matrix[14][14] = 1;*/

+}

+

+void gameOfLife() {

+	int matrix[N][N] = { 0 };

+	start(matrix); //-> Remove comments on the patterd you'd like to run, or make one yourself!

+	while (true) {

+		system("cls");

+		printMatrix(matrix);

+		evolve(matrix);

+		std::this_thread::sleep_for(std::chrono::milliseconds(300)); //Making the terminal sleep for 300 mseconds

+	}

+}

+

+void testsOnFirst() {

+	int a = 5;

+	plusFive(&a);

+	std::cout << a;

+}

+

+void testsOnSecond() {

+	int matrix[RFIRST][CFIRST] = { 0 };

+	iterateOverMatrix(matrix);

+	for (int i = 0; i < RFIRST; i++) {

+		for (int j = 0; j < RSEC; j++)

+			std::cout << matrix[i][j] << " ";

+		std::cout << std::endl;

+	}

+}

+

+void testsOnThird() {

+	int matrix3d[DIM][DIM][DIM] = { 0 };

+	iterateOverThreeDimentionalArray(matrix3d);

+	for (int i = 0; i < DIM; i++) {

+		for (int j = 0; j < DIM; j++) {

+			for (int k = 0; k < DIM; k++)

+				std::cout << matrix3d[i][j][k] << " ";

+			std::cout << std::endl;

+		}

+		std::cout << std::endl;

+	}

+}

+

+void testsOnFourth() {

+	int firstMatrix[RFIRST][CSEC] = { {1, 2, 3, 0}, {4, 5, 6, 1}, {7, 8, 9, 2}, {7, 6, 39, 5} };

+	int secondMatrix[RFIRST][CSEC] = { {10, 11, 12, 1}, {13, 14, 15, 3}, {0, 21, 22, 23}, {7, 8, 9, 2} };

+	int result[RFIRST][CFIRST] = { 0 };

+	sumMatrices(firstMatrix, secondMatrix, result);

+	multiplyMatrices(firstMatrix, secondMatrix, result);

+	for (int i = 0; i < RFIRST; i++) {

+		for (int j = 0; j < CFIRST; j++)

+			std::cout << result[i][j] << " ";

+		std::cout << std::endl;

+	}

+}

+

+int main() {

+	//testsOnFirst();

+	//testsOnSecond();

+	//testsOnThird();

+	//testsOnFourth();

+	//gameOfLife();

+}
\ No newline at end of file
diff --git a/pract_KN/Pract 10/многомерни-масиви.-Указателна-аритметика.pdf b/pract_KN/Pract 10/многомерни-масиви.-Указателна-аритметика.pdf
new file mode 100644
index 0000000..2b8223b
--- /dev/null
+++ b/pract_KN/Pract 10/многомерни-масиви.-Указателна-аритметика.pdf
diff --git a/pract_KN/Pract 11/solutions.cpp b/pract_KN/Pract 11/solutions.cpp
new file mode 100644
index 0000000..d6d4d0a
--- /dev/null
+++ b/pract_KN/Pract 11/solutions.cpp
@@ -0,0 +1,183 @@
+#include<iostream>

+

+//helpers:

+void initMatrix(int** matrix, int n, int m) {

+	for (int i = 0; i < n; i++)

+		for (int j = 0; j < m; j++)

+			matrix[i][j] = (i + j) * (i + j + 1) / 2 + j;

+}

+

+void initArray(int* arr, int length) {

+	for (int i = 0; i < length; i++)

+		arr[i] = rand() % 100;

+}

+

+void printArray(const int* arr, int length) {

+	for (int i = 0; i < length; i++)

+		std::cout << arr[i] << " ";

+}

+

+void printMatrix(int** matrix, int n, int m) {

+	for (int i = 0; i < n; i++) {

+		for (int j = 0; j < m; j++)

+			std::cout << matrix[i][j] << " ";

+		std::cout << std::endl;

+	}

+}

+

+void freeMatrix(int** arr, int n, int m) {

+	for (int i = 0; i < n; i++)

+		delete[] arr[i];

+	delete[] arr;

+}

+

+void freeArray(int* arr) {

+	delete[] arr;

+}

+

+//Task 1

+void deleteElementAtIndex(int* arr, int index, int& length) {

+	for (int i = index; i < length - 1; i++)

+		arr[i] = arr[i + 1];

+	arr[length - 1] = -1;

+	--length;

+}

+

+//Task 2:

+int findSum(int* row, int length) {

+	int res = 0;

+	for (int i = 0; i < length; i++)

+		res += row[i];

+	return res;

+}

+

+int rowWithBiggestSum(int** arr, int n, int m) {

+	int biggestSum = findSum(arr[0], m);

+	int row = 0;

+	for (int i = 1; i < n; i++) {

+		int currentSum = findSum(arr[i], m);

+		if (biggestSum < currentSum) {

+			biggestSum = currentSum;

+			row = i;

+		}

+	}

+	return row;

+}

+

+//Task 3:

+void removeRow(int** arr, int k, int& n) {

+	delete[] arr[k];

+	for (int i = k; i < n - 1; i++)

+		arr[i] = arr[i + 1];

+	--n;

+}

+

+//Task 4:

+void cycle(int* arr, int n, int k) {

+	int* copyArr = new int[n];

+	for (int i = 0; i < n; i++)

+		copyArr[i] = arr[(i + k) % n];

+	memcpy(arr, copyArr, n * sizeof(int));

+	delete[] copyArr;

+}

+

+//Task 5:

+void removeElements(int* arr, int& length) {

+	for (int i = 1; i < length - 1;) {

+		if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {

+			deleteElementAtIndex(arr, i, length);

+			i--;

+			if(i == 0) { //We don't want to deal with i == 0 case. Its always true in our solution.

+				i = 1;

+			}

+		}

+		else {

+			++i;

+		}

+	}

+}

+

+void testsOnTaskOne() {

+	int length = 0;

+	std::cin >> length;

+	int* arr = new int[length];

+	initArray(arr, length);

+	printArray(arr, length);

+	std::cout << std::endl;

+	deleteElementAtIndex(arr, 5, length);

+	printArray(arr, length);

+	freeArray(arr);

+}

+

+void testsOnTaskTwo() {

+	int n = 0;

+	int m = 0;

+	std::cin >> n >> m;

+	//Create dynamic array:

+	int** darray = new int* [n];

+	for (int i = 0; i < n; i++)

+		darray[i] = new int[m];

+

+	//Initialize:

+	initMatrix(darray, n, m);

+

+	int biggestSum = rowWithBiggestSum(darray, n, m);

+

+	printArray(darray[biggestSum], m);

+

+	freeMatrix(darray, n, m);

+}

+

+void testsOnTaskThree() {

+	int n = 0;

+	int m = 0;

+	std::cin >> n >> m;

+	//Create dynamic array:

+	int** darray = new int* [n];

+

+	for (int i = 0; i < n; i++)

+		darray[i] = new int[m];

+

+	//Initialize:

+	initMatrix(darray, n, m);

+

+	printMatrix(darray, n, m);

+	removeRow(darray, 0, n);

+	removeRow(darray, 3, n);

+	std::cout << std::endl;

+	printMatrix(darray, n, m);

+

+	freeMatrix(darray, n, m);

+}

+

+void testsOnTaskFour() {

+	int length = 0;

+	std::cin >> length;

+	int* arr = new int[length];

+	initArray(arr, length);

+	printArray(arr, length);

+	std::cout << std::endl;

+	cycle(arr, length, 1);

+	printArray(arr, length);

+	freeArray(arr);

+}

+

+void testsOnTaskFive() {

+	int length = 0;

+	std::cin >> length;

+	int* arr = new int[length];

+	initArray(arr, length);

+	printArray(arr, length);

+	std::cout << std::endl;

+	removeElements(arr, length);

+	printArray(arr, length);

+	freeArray(arr);

+}

+

+int main() {

+	//testsOnTaskOne();

+	//testsOnTaskTwo();

+	//testsOnTaskThree();

+	//testsOnTaskFour();

+	//testsOnTaskFive();

+}

diff --git a/pract_KN/Pract 11/Указатели и референции. Динамична памет..pdf b/pract_KN/Pract 11/Указатели и референции. Динамична памет..pdf
new file mode 100644
index 0000000..aede287
--- /dev/null
+++ b/pract_KN/Pract 11/Указатели и референции. Динамична памет..pdf