commit 2e0369babba439d6e8e4492b95870cc8d4c2810e
parent f2b6c4c61487ed00d5c244ea7c4231ff15aaeb68
Author: William Lindholm <a22willi@student.his.se>
Date: Wed, 29 Nov 2023 16:39:30 +0100
Merge branch 'master' of https://github.com/LindholmLabs/DSA-Assignments
Diffstat:
2 files changed, 95 insertions(+), 21 deletions(-)
diff --git a/Problem2/Problem2.cpp b/Problem2/Problem2.cpp
@@ -1,15 +1,79 @@
-
+// Problem 2: Social Network
+// Description:
+// Course: IT405G - Datastructures and Algorithms
+// Authors: William Lindholm, Lili Tran, Victor Adamson
+// Date: 29-11-2023
+//
#include <iostream>
#include <queue>
+#include <vector>
+#include <list>
using namespace std;
-int main()
-{
- queue<int> network;
+class Graph {
+private:
+ int V;
+ vector<int>* adj;
+public:
+ Graph(int V);
+ void addEdge(int v, int w);
+ bool isEdge(int v, int w);
+ int getNumNodes();
+ void printGraph();
+};
+
+Graph::Graph(int V) {
+ this->V = V;
+ adj = new vector <int>[V];
+}
+
+void Graph::addEdge(int v, int w) {
+ adj[v].push_back(w);
+}
- while (!network.empty()) {
- cout << ' ' << network.front();
- network.pop();
+bool Graph::isEdge(int v, int w) {
+ vector<int>::iterator i;
+ for (i = adj[v].begin(); i != adj[v].end(); i++) {
+ if (w == *i) {
+ return(true);
+ }
+ return(false);
}
+}
+
+int Graph::getNumNodes() {
+ return V;
+}
+
+void Graph::printGraph() {
+ for (int v = 0; v < V; ++v) {
+ cout << "\nAdjacency list of node " << v << "\n head ";
+ vector<int>::iterator i;
+ for (i = adj[v].begin();
+ i != adj[v].end(); ++i) {
+ cout << "-> " << *i << " ";
+ }
+ }
+}
+
+int main(){
+ Graph network(4);
+ network.addEdge(0, 1); //A dislikes B
+ network.addEdge(1, 2); //B dislikes C
+ network.addEdge(1, 3); //B dislikes D
+ network.addEdge(2, 3); //C dislikes D
+ network.addEdge(2, 1); //C dislikes B
+ network.printGraph();
+ queue<int> queue;
+ const int i = network.getNumNodes();
+ list<int> nodes[4];
+ cout << "\n" << "Number of nodes: " << i << "\n";
+ vector<bool> visited[4];
+
+}
+
+bool isAdversary(Graph network, vector<bool> visited[4]) {
+
+ return true;
}
\ No newline at end of file
diff --git a/Problem4/Problem4.cpp b/Problem4/Problem4.cpp
@@ -1,20 +1,30 @@
-// Problem4.cpp : This file contains the 'main' function. Program execution begins and ends there.
+// Problem 1: Bucket Sort
+// Description: Sort a vector using a modified version of bucket sort.
+// Course: IT405G - Datastructures and Algorithms
+// Authors: William Lindholm, Lili Tran, Victor Adamson
+// Date: 29-11-2023
//
#include <iostream>
+#include <cmath>
-int main()
-{
- std::cout << "Hello World!\n";
-}
+using namespace std;
+
+// Temp
+// Från labbanvisningarna
+// T(n) = T(n-1)+T([n/2])+n
+// T(1) = 1
+// Recursive function to calculate T(n)
+int T(int n) {
+ int result = T(n - 1) + T(ceil(n / 2.0)) + n;
-// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
-// Debug program: F5 or Debug > Start Debugging menu
+ return result;
+}
-// Tips for Getting Started:
-// 1. Use the Solution Explorer window to add/manage files
-// 2. Use the Team Explorer window to connect to source control
-// 3. Use the Output window to see build output and other messages
-// 4. Use the Error List window to view errors
-// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
-// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
+int main() {
+ int n;
+ cout << "Enter a value for n: ";
+ cin >> n;
+ cout << "T(" << n << ") = " << T(n) << endl;
+ return 0;
+}
