<repo_name>dvigleo/algorithms-design<file_sep>/Homework 3 - Algorithm Design Techniques/paragraph.cpp
/*
  <NAME>
  A01021698
  Exercise 2: Paragraph division
  Technique: Greedy algoritm
    Greedy choice: It tries to fit as many words as possible in the same line
  Commplexity: Because there's only one loop for the complexity is O(n)
*/

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

float reduceCost(float red, float amplitudeI, int j, int i) {
  return (fabs(red - amplitudeI) * (j - i) );
}

float extendCost(float amp, float amplitudeI, int j, int i)  {
  return (fabs(amp - amplitudeI) * (j - i - 1) );
}

void printLine(vector<string> line){
  cout << endl;
  for (int i = 0; i < line.size(); i++)
    cout << line[i] << " ";
}

int main() {
  vector<string> text = {"Daniela", "come", "sandia", "mientras", "hace", "su","tarea"};
  vector<int> sizeWords;
  vector<string> line;

  float sizeLine = 30, wholeWord = 0, sizeWordSpan = 0, amplitudeI = 0, surplus = 0, red = 0, amp = 0;
  int i = 0, j = 0;
  bool shown = true;

  for (int i = 0; i < text.size(); ++i)
    sizeWords.push_back(int(text[i].length()));

  for (j = 0; j < text.size(); j++) {
    if (shown) {
      i = j;
      shown = false;
      line.clear();
      wholeWord = 0;
    }

    wholeWord += sizeWords[j];
    sizeWordSpan = wholeWord + ((j - i) * amplitudeI);

    if (sizeWordSpan > sizeLine) {
      surplus = sizeWordSpan - sizeLine;
      red = amplitudeI - (surplus/(j - i));
      amp = amplitudeI + (sizeLine - ((wholeWord - sizeWords[j]) + (amplitudeI * (j - i - 1) ))) / (j - i - 1);

      if (extendCost(amp,amplitudeI,j,i) > reduceCost(red, amplitudeI, j, i) && red > 0 ) {
        line.push_back(text[j]);
        cout << endl;
        printLine(line);
        cout << "\t--> This line has been reduced by: " << red << " mm" << endl;
        shown = true;
      }
      else {
        printLine(line);
        cout << "\t--> This line has grown by: " << amp << " mm" << endl;
        j--;
        shown = true;
      }
    }
    line.push_back(text[j]);
  }

  printLine(line);
  cout << endl;

}
<file_sep>/Homework 1 - Greedy Algorithms/fontanero.cpp
/*
  <NAME>
  A01021698
*/

#include<iostream>
#include<algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

struct Job{
   int id;      // Job Id
   int deadline;    // Deadline of job
   int profit;  // Profit if job is over before or on deadline
};

// Sort current jobs according to its profit
bool comparison(Job a, Job b){
  return (a.profit > b.profit);
}

// Returns minimum number of platforms reqquired
void printJobScheduling(Job arr[], int n){
  // Sort according to decreasing order of prfit
  sort(arr, arr+n, comparison);

  int result[n]; // To store result (Sequence of jobs)
  bool slot[n];  // To keep track of free time slots

  // Initialize all slots to be free
  for (int i=0; i<n; i++)
      slot[i] = false;

  // Iterate through all given jobs
  for (int i=0; i<n; i++){
     // Find a free slot for this job (Note that we start
     // from the last possible slot)
     for (int j=min(n, arr[i].deadline)-1; j>=0; j--){
        // Free slot found
        if (slot[j]==false){
           result[j] = i;  // Add this job to result
           slot[j] = true; // Make this slot occupied
           break;
        }
     }
  }

  // Print the result
  for (int i=0; i<n; i++)
     if (slot[i])
       cout << arr[result[i]].id << " ";
}

int main(){
  srand(time(NULL)); // Seed to generate random numbers over and over
  int nJobs = 0;
  cout << "Type in the total number of jobs to do: ";
    cin >> nJobs;
  Job todo[nJobs];

  for(int i = 0; i < nJobs; ++i){
    todo[i].id;
    int deadline = (rand() % 10) + 100;
    todo[deadline].deadline;
    int profit = (rand() % 10) + 200;
    todo[profit].profit;
  }
  cout << "\n    ID     |    DEADLINE     |     PROFIT     |" << endl;
  for (size_t i = 0; i < nJobs; i++) {
    cout << todo[i].id << "  \t";
    cout << todo[i].deadline << " \t";
    cout << todo[i].profit << endl;
  }

  cout << "\nSequence of jobs for amximum profit: \n";
  printJobScheduling(todo, nJobs);
  return 0;
}
<file_sep>/Exercises/Parallel Computing/suma.c
#include <stdio.h>
#include <omp.h>

int main(int argc, const char *argv[]) {
  int n = 10000;
  int suma = 0;
  int i;

  int numeros[n];

  for(i = 0; i < n; ++i) {
    numeros[i] = 1;
  }

  // Estamos definiendo una región paralela, es decir, dentro de ese bloque de instrucciones,
  // el compilador abrirá varios hilos de ejecución y lo resolverá de manera paralela el siguiente
  // ciclo for
  #pragma omp parallel private(i)
  {
  for(i = 0; i < n; ++i) {
    suma += numeros[i];
  }
}

  printf("La suma = %d\n", suma);
  return 0;
}
<file_sep>/Project 1 - Balanced Trees/AVLNode.h
template <class T>
class AVLnode {
public:
    T key;
    int balance;
    AVLnode *left, *right, *parent;

    AVLnode(T k, AVLnode *p) : key(k), balance(0), parent(p),
                        left(NULL), right(NULL) {}

    ~AVLnode() {
        delete left;
        delete right;
    }
};
<file_sep>/Project 1 - Balanced Trees/main.cpp
/************************************************************
*********** <NAME> | <NAME> ***************
***********    A01021689   |  AA01129460      ***************
************************************************************/

#include"RBTree.h"
#include "TwoThreeTree.h"
#include "AVLTree.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <ctime>
#include <fstream> // Write into file
#include <utility>
#include <time.h>
#include <chrono>

using namespace std;

bool menu(bool programRunning, vector<int> nums, int n){
	bool menu = false;
	int opcMenu = 0;

	int valueToAdd = 0, valueToSearch = 0, valueToDelete = 0, hdlOfNode = 0;

	// Uncomment for RedBlack
	// RBTree<int> tree;
	// for (auto num : nums)
	// 	tree.insert(num);

	// Uncomment for 2-3 Tree
	// TwoThreeTree<int> newTree;
	// for (auto num : nums)
	// 	newTree.insert23(num);

	// Uncomment for AVL
	AVLTree<int> avl;
	for(auto num:nums)
		avl.insertAVL(num);

	while(programRunning == true){
		cout << "\nCHOOSE AN OPTION FROM THE MENU (1 - 10)" << endl;
		cout << "1. Insert a node\n2. Search for a node\n3. Delete a node\n4. Print tree in ascending order\n5. Print tree in descending order\n6. Calculate height of a given node\n7. Calculate depth of a given node\n8. Calculate the level of a given node\n9. Go back\n10. Exit program\n";
			cin >> opcMenu;

		switch(opcMenu){
			case 1:
			{
				cout << "\n ---- INSERT A NODE ---- " << endl;
				cout << "Type in the value to insert: \n";
					cin >> valueToAdd;
				// tree.insert(valueToAdd);
				// newTree.insert23(valueToAdd);
				avl.insertAVL(valueToAdd);
				cout << "\n\n";
			}
			break;
			case 2:
			{
				cout << "\n ---- SEARCH FOR A NODE ---- " << endl;
				cout << "Type in the value to search in the tree: \n";
					cin >> valueToSearch;
				int numsToSearch[10];
				numsToSearch[0] = valueToSearch;
				auto start = chrono::steady_clock::now();
				// cout << endl << tree.search(valueToSearch)->key << endl;
				// cout << endl << newTree.search23(numsToSearch[0]) << endl;
				avl.buscarNodo(valueToSearch);
				auto end = chrono::steady_clock::now();
				cout << "\nElapsed time in milliseconds: \t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms";
				cout << "\n\n";
			}
			break;
			case 3:
			{
				cout << "\n ---- DELETE A NODE ---- " << endl;
				cout << "Type in the value to delete: \n";
					cin >> valueToDelete;
				//tree.remove(valueToDelete);
				// newTree.delete23(valueToDelete);
				cout << "\n\n";
			}
			break;
			case 4:
			{
				cout << "\n ---- PRINT IN ASCENDING ORDER ---- " << endl;
				// tree.ascendingOrder();
				// newTree.printAsc();
				avl.ordenarAsc();
				cout << "\n\n";
			}
			break;
			case 5:
			{
				cout << "\n ---- PRINT IN DESCENDING ORDER ---- " << endl;
				// tree.descendingOrder();
				// newTree.printDesc();
				avl.ordenarDes();
				cout << "\n\n";
			}
			break;
			case 6:
			{
				cout << "\n ---- CALCULATE HEIGHT ---- " << endl;
				cout << "Type in the node you want to calculate the height of: \n";
					cin >> hdlOfNode;
				// tree.printHeight(hdlOfNode);
				// newTree.printHeight23(hdlOfNode);
				int keyAlto = 8;
				int altNodo = avl.calculaAlturaDeNodo(keyAlto);
				cout<<"\n\nHeight of key " << keyAlto << " in the tree: " << altNodo;
				hdlOfNode = 0;
				cout << "\n\n";
			}
			break;
			case 7:
			{
				cout << "\n ---- CALCULATE DEPTH ---- " << endl;
				cout << "Type in the node you want to calculate the depth of: \n";
					cin >> hdlOfNode;
				// tree.printDepth(hdlOfNode);
				// newTree.printDepth23(hdlOfNode);
				hdlOfNode = 0;
				cout << "\n\n";
			}
			break;
			case 8:
			{
				cout << "\n ---- CALCULATE LEVEL ---- " << endl;
				cout << "Type in the node you want to calculate the height of: \n";
					cin >> hdlOfNode;
				// tree.printLevel(hdlOfNode);
				// newTree.printLevel23(hdlOfNode);
				int keyNiv = 8;
		    int nivNodo = avl.nivelDeNodo(keyNiv);
		    cout<<"\n\nLevel of key " << keyNiv << " in the tree: " << nivNodo;
				hdlOfNode = 0;
				cout << "\n\n";
			}
			break;
			case 9:
			{
				cout << "\n ---- GO BACK ---- " << endl;
				menu = true;
				cout << "\n\n";
				return programRunning = false;
			}
			break;
			case 10:
			{
				cout << "\n ---- EXIT PROGRAM ---- " << endl;
				exit(0);
			}
			break;
		}
	}
	return programRunning;
}

void writeIntoFile(vector<int> nums, int n){
  int i;
  ofstream file_list;
  file_list.open("listElementsTree.txt");
  if (file_list.is_open()){
    for (i = 0; i < n; ++i){ //final state
      file_list << nums[i] << endl;
    }
  	file_list.close();
  }
}

int main(){
	int opcTree = 0;
	bool programRunning = true;

	srand(static_cast<unsigned int>(time(NULL)));
	size_t const n = 1000000;
	vector<int> nums(n);

	//make vector
	for (size_t i = 0; i < n; ++i)
		nums[i] = static_cast<int>(i);

	//shuffle
	for (size_t i = n - 1; i > 0; --i)
		swap(nums[i], nums[static_cast<size_t>(rand()) % (i + 1)]);

	writeIntoFile(nums, n);

	while(programRunning == true){
		cout << "CHOOSE A TREE TO CREATE (1-5): " << endl;
		cout << "1. AVL Tree\n2. B Tree\n3. Redblack Tree\n4. 2-3 Tree\n5. Exit program" << endl;
		cin >> opcTree;

		switch(opcTree){
			case 1:
			{
				cout << "\n ---- AVL TREE ----\n";
				menu(programRunning, nums, n);
			}
			break;
			case 2:
			{
				cout << "\n ---- B TREE ----\n";
				menu(programRunning, nums, n);
			}
			break;
			case 3:
			{
				cout << "\n ---- REDBLACK TREE ----\n";
				menu(programRunning, nums, n);
			}
			break;
			case 4:
			{
				cout << "\n ---- 2-3 TREE ----\n";
				menu(programRunning, nums, n);
			}
			break;
			case 5:
			{
				cout << "\n ----  EXIT PROGRAM ---- \n";
				exit(0);
			}
		}
	}
	return 0;
}
<file_sep>/Homework 5 - Computational Geometry/cono.cpp
#include "cono.h"
#include "ui_cono.h"
#include "math.h"

Cono::Cono(QWidget *parent) : QDialog(parent),  ui(new Ui::Cono) {
    this->setFixedSize(521, 333); //Size of window
    ui->setupUi(this);
    xCentro = 345.0; // values so the first drawn figure is centered
    yCentro = 170.0;
    QTransform center;
    center.translate(xCentro,yCentro);
    vecTrans.push_back(center);
}

Cono::~Cono()
{
    delete ui;
}


void dibujarElipse(int xc,int yc,int rx,int ry, QPainter & painter)  {

   int x=0;
   int y=ry;
   int p=(ry*ry)-(rx*rx*ry)+((rx*rx)/4);
   while((2*x*ry*ry)<(2*y*rx*rx))    {
        painter.drawPoint(xc+x,yc-y);
        painter.drawPoint(xc-x,yc+y);
        painter.drawPoint(xc+x,yc+y);
        painter.drawPoint(xc-x,yc-y);

        if(p<0)
        {
     x=x+1;
     p=p+(2*ry*ry*x)+(ry*ry);
        }
        else
        {
     x=x+1;
     y=y-1;
     p=p+(2*ry*ry*x+ry*ry)-(2*rx*rx*y);
        }
   }
   p=((float)x+0.5)*((float)x+0.5)*ry*ry+(y-1)*(y-1)*rx*rx-rx*rx*ry*ry;

         while(y>=0)
   {
       painter.drawPoint(xc+x,yc-y);
       painter.drawPoint(xc-x,yc+y);
       painter.drawPoint(xc+x,yc+y);
       painter.drawPoint(xc-x,yc-y);

        if(p>0)
        {
     y=y-1;
     p=p-(2*rx*rx*y)+(rx*rx);

        }
        else
        {
     y=y-1;
     x=x+1;
     p=p+(2*ry*ry*x)-(2*rx*rx*y)-(rx*rx);
        }
   }
 }


void BresenhamLine (int x0, int y0, int x1, int y1, QPainter & painter) {
   int x, y, dx, dy, xend, p, incE, incNE;
   dx = abs(x1 - x0);
   dy = abs(y1 - y0);
   p = 2 * dy - dx;
   incE = 2 * dy;
   incNE = 2 * (dy - dx);

   if(x0 > x1 ) {
       x = x1;
       y = y1;
       xend = 0;
   }

   while(x <= xend) {
       painter.drawPoint(x, y);
       x += 1;
       if(p < 0){
           p += incE;
       }
       else {
            y += 1;
            p += incNE;
       }
   }
}


void dibujarCono(QPainter & painter) {

    double centroX = 0.0;
    double centroY = 0.0;

    int a = 60; //largo
    int b = 30; //ancho

    dibujarElipse(centroX, centroY, a, b, painter);

    int incX = 60;
    int incY = 100;

    int x0 = centroX + incX;
    int y0 = centroY;

    int x1 = centroX - incX;
    int y1 = y0;

    int x2 = centroX;
    int y2 = y0 - incY;

    BresenhamLine(x2, incY, x1, y1, painter);
    BresenhamLine(x2, y0, x2, y2, painter);
}

void Cono::paintEvent(QPaintEvent *e) {
    QPainter painter(this);

    QPen pointPen(Qt::black);
    pointPen.setWidth(2);
    painter.setPen(pointPen);

    if (dibuja) {
        for(int i=0; i<vecTrans.size(); ++i) {
            painter.setTransform(vecTrans[i],true);
            dibujarCono(painter);
        }
    }

}

void Cono::on_dibujar_clicked(){
    trans.dibujar(dibuja,vecTrans,xCentro,yCentro);
    update();
}

void Cono::on_trasladar_clicked() {
    QString xStr = ui->boxXinicio->toPlainText();
    QString yStr = ui->boxYinicio->toPlainText();
    trans.trasladar(xStr, yStr, vecTrans);
    update();
}

void Cono::on_rotar_clicked() {
    QString gradosStr = ui->boxGrados->toPlainText();
    trans.rotar(gradosStr, vecTrans);
    update();
}

void Cono::on_zoom_out_clicked() {
    trans.zoomOut(vecTrans);
    update();
}

void Cono::on_zoom_in_clicked() {
    trans.zoomIn(vecTrans);
    update();
}

void Cono::on_horizontal_clicked() {
    trans.reflexHorizontal(vecTrans);
    update();
}

void Cono::on_vertical_clicked() {
    trans.reflexVertical(vecTrans);
    update();
}
<file_sep>/Project 1 - Balanced Trees/TwoThreeNode.h
template <class T>
class TwoThreeNode{
public:
    bool hasSmall = false;
    bool hasHigh = false;
    bool full = false;
    T* small = nullptr;
    T* big = nullptr;
    T* tempMiddle = nullptr;
    TwoThreeNode<T>* parent = nullptr;
    TwoThreeNode<T>* left = nullptr;
    TwoThreeNode<T>* middle = nullptr;
    TwoThreeNode<T>* right = nullptr;
    TwoThreeNode<T>* temp = nullptr;
    TwoThreeNode<T>():left(nullptr),middle(nullptr),right(nullptr),parent(nullptr),small(nullptr),big(nullptr),tempMiddle(nullptr),temp(nullptr){}
    TwoThreeNode(T _small){
        small = new T(_small);
        hasSmall = true;
    }
    virtual ~TwoThreeNode(){
        left = middle = right = parent = temp = nullptr;
        small = big = nullptr;
    }

    TwoThreeNode<T>* getTemp(){
        return temp;
    }

    void setTemp(TwoThreeNode<T>* node){
        temp = node;
    }

    T getTempMiddle(){
        return *tempMiddle;
    }

    void deleteTempMiddle(){
      if(tempMiddle)
        tempMiddle = nullptr;
    }

    void setTempMiddle(T _info){
      if(tempMiddle == nullptr)
        tempMiddle = new T(_info);
      else
        *tempMiddle = _info;
    }

    bool hasTempMiddle(){
      if(tempMiddle)
          return true;
      else
          return false;
    }

    void setSmall(T _info){
      if(small!=nullptr)
        *small = _info;
      else
          small = new T(_info);
    }

    void setBig(T _info){
      if(big!=nullptr)
        *big = _info;
      else
        big = new T(_info);
    }

    T getSmall(){
      return *small;
    }

    T getBig(){
      return *big;
    }

    bool isFull() {
      if(big && small)
          return true;
      return false;
    }

    bool hasThreeKeys(){
      return big && small && tempMiddle;
    }

    void setInfo(T _info){
      if(!small){
          small = new T(_info);
      }
      else {
          if(_info >= *small) {
              if(!big)
                big = new T(_info);
          }
          else if(_info < *small) {
              big = new T(*small);
              *small = _info;
          }
      }
    }

    void deleteKeys() {
        if(small)
            small = nullptr;
        if(big)
            big = nullptr;
    }

    void setInfoMiddle(T _info){
      if(big && small){
        if(!tempMiddle){
          tempMiddle = new T(_info);
          if(_info < *small){
            *tempMiddle = *small;
            *small = _info;
          }
          else if(_info >= *small && _info <= *big){
            *tempMiddle = _info;
          }
          else {
            *tempMiddle = *big;
            *big = _info;
          }
        }
        else {
          if(_info < *small){
            *tempMiddle = *small;
            *small = _info;
          }
          else if(_info >= *small && _info <= *big){
            *tempMiddle = _info;
          }
          else{
            *tempMiddle = *big;
            *big = _info;
          }
        }
      }
    }

    void deleteBig(){
      if(big)
        big = nullptr;
    }

    void deleteSmall() {
      if(small)
          small = nullptr;
    }

    void changeBigToSmall() {
      if(!small)
          small = new T(*big);
      else
          *small = *big;
      big = nullptr;
    }


    bool hasLower(){
      if(small==nullptr)
        return false;
      else
        return true;
    }

    bool hasHigher(){
      if(big==nullptr)
        return false;
      else
        return true;
    }

    bool noKeys(){
        return !small && !big;
    }

    TwoThreeNode<T> * getLeft() const { return left; }
    void setLeft(TwoThreeNode<T> * info) { left = info; }

    TwoThreeNode<T> * getRight() const { return right; }
    void setRight(TwoThreeNode<T> * info) { right = info; }

    TwoThreeNode<T> * getMiddle() const { return middle; }
    void setMiddle(TwoThreeNode<T> * info) { middle = info; }

    TwoThreeNode<T> * getParent() const { return parent; }
    void setParent(TwoThreeNode<T> * info) { parent = info; }
};
<file_sep>/Homework 5 - Computational Geometry/prismatri.cpp
#include "prismatri.h"
#include "ui_prismatri.h"
#include <math.h>
#include <QMessageBox>

PrismaTri::PrismaTri(QWidget *parent) : QDialog(parent), ui(new Ui::PrismaTri) {
    this->setFixedSize(521, 333); //Size of window
    ui->setupUi(this);
    xCentro = 350.0; // values so the first drawn figure is centered
    yCentro = 170.0;
    QTransform center;
    center.translate(xCentro,yCentro);
    vecTrans.push_back(center);
}

PrismaTri::~PrismaTri()
{
    delete ui;
}

void PrismaTri::paintEvent(QPaintEvent *e){
    QPainter painter(this);
    QPen pointPen(Qt::black);
    pointPen.setWidth(2);
    painter.setPen(pointPen);
    if (dibuja){
        for(int i=0; i<vecTrans.size(); ++i){
            painter.setTransform(vecTrans[i],true);
            drawPrismaTri(painter);
        }
    }
}
void PrismaTri::drawPrismaTri(QPainter &painter){
        painter.drawLine(0,-100,-50,-140);
        painter.drawLine(0,-100,50,-140);
        painter.drawLine(-50,-140,50,-140);
        painter.drawLine(0,0,-50,-40);
        painter.drawLine(0,0,50,-40);
        painter.drawLine(-50,-40,50,-40);
        painter.drawLine(0,-100,0,0);
        painter.drawLine(-50,-140,-50,-40);
        painter.drawLine(50,-40,50,-140);
}

void PrismaTri::on_dibujar_clicked() {
    vecTrans.clear();
    QTransform centro;
    centro.translate(xCentro,yCentro);
    vecTrans.push_back(centro);
    dibuja = !dibuja;
    update();
}

void PrismaTri::on_trasladar_clicked() {
    QString x = ui->boxXinicio->toPlainText();
    QString y = ui->boxYinicio->toPlainText();
     if(!x.isEmpty() && !y.isEmpty()) {
       int xS = x.toInt();
       int yS = y.toInt();
       QTransform t;
       t.translate(xS, yS);
       vecTrans.push_back(t);
     } else {
       QMessageBox msgBox;
       msgBox.setText("Please type in the values for x and y");
       msgBox.exec();
     }
     update();
}

void PrismaTri::on_zoom_in_clicked() {
    QTransform zIn;
    zIn.scale(2,2);
    vecTrans.push_back(zIn);
    update();
}

void PrismaTri::on_zoom_out_clicked() {
    QTransform zOut;
    zOut.scale(0.5,0.5);
    vecTrans.push_back(zOut);
    update();
}

void PrismaTri::on_rotar_clicked() {
    QString r = ui->boxGrados->toPlainText();
      if(!r.isEmpty()) {
        int rS = r.toInt();
        QTransform r;
        r.rotate(rS);
        vecTrans.push_back(r);
      } else {
        QMessageBox msgBox;
        msgBox.setText("Please type in the degree for rotation");
        msgBox.exec();
      }
    update();
}

void PrismaTri::on_vertical_clicked() {
    QTransform rv;
    rv.scale(1,-1);
    vecTrans.push_back(rv);
    update();
}

void PrismaTri::on_horizontal_clicked() {
    QTransform rh;
    rh.scale(-1,1);
    vecTrans.push_back(rh);
    update();
}
<file_sep>/Project 1 - Balanced Trees/AVLTree.h
#include "AVLNode.h"
#include <algorithm>
#include <iostream>

using namespace std;

/* AVL tree */
template <class T>
class AVLTree {
public:
    AVLTree(void);
    ~AVLTree(void);
    bool insertAVL(T key);
    void deleteKey(const T key);
    void printBalance();
    void ordenarAsc();
    void ordenarDes();
    int calculaAltura();
    AVLnode<T>* buscarNodo(const T key);
    int calculaAlturaDeNodo(const T key);
    int nivelDeNodo(const T key);

private:
    AVLnode<T>* root;

    AVLnode<T>* rotateLeft( AVLnode<T> *a );
    AVLnode<T>* rotateRight( AVLnode<T> *a );
    AVLnode<T>* rotateLeftThenRight( AVLnode<T> *n );
    AVLnode<T>* rotateRightThenLeft( AVLnode<T> *n );
    void rebalance( AVLnode<T> *n );
    int height( AVLnode<T> *n );
    void setBalance( AVLnode<T> *n );
    void printBalance( AVLnode<T> *n );
    void clearNode( AVLnode<T> *n );
    void ascendente( AVLnode<T> *n );
    void descendente( AVLnode<T> *n );
    int calculaAltura( AVLnode<T> *n );
    int calculaAlturaDeNodo( AVLnode<T> *n, const T key );
    int nivelDeNodo(AVLnode<T> *n, const T key);
    AVLnode<T>* buscarNodo(AVLnode<T> *n, const T key);
};

/* AVL class definition */
template <class T>
void AVLTree<T>::rebalance(AVLnode<T> *n) {
    setBalance(n);

    if (n->balance == -2) {
        if (height(n->left->left) >= height(n->left->right))
            n = rotateRight(n);
        else
            n = rotateLeftThenRight(n);
    }
    else if (n->balance == 2) {
        if (height(n->right->right) >= height(n->right->left))
            n = rotateLeft(n);
        else
            n = rotateRightThenLeft(n);
    }

    if (n->parent != NULL) {
        rebalance(n->parent);
    }
    else {
        root = n;
    }
}

template <class T>
AVLnode<T>* AVLTree<T>::rotateLeft(AVLnode<T> *a) {
    AVLnode<T> *b = a->right;
    b->parent = a->parent;
    a->right = b->left;

    if (a->right != NULL)
        a->right->parent = a;

    b->left = a;
    a->parent = b;

    if (b->parent != NULL) {
        if (b->parent->right == a) {
            b->parent->right = b;
        }
        else {
            b->parent->left = b;
        }
    }

    setBalance(a);
    setBalance(b);
    return b;
}

template <class T>
AVLnode<T>* AVLTree<T>::rotateRight(AVLnode<T> *a) {
    AVLnode<T> *b = a->left;
    b->parent = a->parent;
    a->left = b->right;

    if (a->left != NULL)
        a->left->parent = a;

    b->right = a;
    a->parent = b;

    if (b->parent != NULL) {
        if (b->parent->right == a) {
            b->parent->right = b;
        }
        else {
            b->parent->left = b;
        }
    }

    setBalance(a);
    setBalance(b);
    return b;
}

template <class T>
AVLnode<T>* AVLTree<T>::rotateLeftThenRight(AVLnode<T> *n) {
    n->left = rotateLeft(n->left);
    return rotateRight(n);
}

template <class T>
AVLnode<T>* AVLTree<T>::rotateRightThenLeft(AVLnode<T> *n) {
    n->right = rotateRight(n->right);
    return rotateLeft(n);
}

template <class T>
int AVLTree<T>::height(AVLnode<T> *n) {
    if (n == NULL)
        return -1;
    return 1 + std::max(height(n->left), height(n->right));
}

template <class T>
void AVLTree<T>::setBalance(AVLnode<T> *n) {
    n->balance = height(n->right) - height(n->left);
}

template <class T>
void AVLTree<T>::printBalance(AVLnode<T> *n) {
    if (n != NULL) {
        printBalance(n->left);
        std::cout << n->balance << " ";
        printBalance(n->right);
    }
}

template <class T>
AVLTree<T>::AVLTree(void) : root(NULL) {}

template <class T>
AVLTree<T>::~AVLTree(void) {
    delete root;
}

template <class T>
bool AVLTree<T>::insertAVL(T key) {
    if (root == NULL) {
        root = new AVLnode<T>(key, NULL);
    }
    else {
        AVLnode<T>
            *n = root,
            *parent;

        while (true) {
            if (n->key == key)
                return false;

            parent = n;

            bool goLeft = n->key > key;
            n = goLeft ? n->left : n->right;

            if (n == NULL) {
                if (goLeft) {
                    parent->left = new AVLnode<T>(key, parent);
                }
                else {
                    parent->right = new AVLnode<T>(key, parent);
                }

                rebalance(parent);
                break;
            }
        }
    }

    return true;
}

template <class T>
void AVLTree<T>::deleteKey(const T delKey) {
    if (root == NULL)
        return;

    AVLnode<T>
        *n       = root,
        *parent  = root,
        *delNode = NULL,
        *child   = root;

    while (child != NULL) {
        parent = n;
        n = child;
        child = delKey >= n->key ? n->right : n->left;
        if (delKey == n->key)
            delNode = n;
    }

    if (delNode != NULL) {
        delNode->key = n->key;

        child = n->left != NULL ? n->left : n->right;

        if (root->key == delKey) {
            root = child;
        }
        else {
            if (parent->left == n) {
                parent->left = child;
            }
            else {
                parent->right = child;
            }

            rebalance(parent);
        }
    }
}

template <class T>
void AVLTree<T>::printBalance() {
    printBalance(root);
    std::cout << std::endl;
}


template <class T>
void AVLTree<T>::ordenarAsc(){
    ascendente(root);
}

template <class T>
void AVLTree<T>::ascendente(AVLnode<T> *n){
    if(n != NULL){
        ascendente(n->left);
        cout << n->key << " ";
        ascendente(n->right);
    }
}

template <class T>
void AVLTree<T>::ordenarDes(){
    descendente(root);
}

template <class T>
void AVLTree<T>::descendente(AVLnode<T> *n){
    if(n != NULL)
     {
        descendente(n->right);
        cout << n->key << " ";
        descendente(n->left);
     }
}

template <class T>
int AVLTree<T>::calculaAltura(){
    return calculaAltura(root);
}

template <class T>
int AVLTree<T>::calculaAltura(AVLnode<T> *n) {
   int h = 0;
   if (n != NULL) {
      int l_height = calculaAltura(n->left);
      int r_height = calculaAltura(n->right);
      int max_height = max(l_height, r_height);
      h = max_height + 1;
   }
   return h;
}

template <class T>
int AVLTree<T>::calculaAlturaDeNodo(const T key){
    return calculaAlturaDeNodo(root, key);
}

template <class T>
int AVLTree<T>::calculaAlturaDeNodo(AVLnode<T> *n, const T key){
    int altura=1;
	while( n ){
		if( key == n->key ) return altura;
		else{
			altura++;
			if( key < n->key ) n = n->left;
			else n = n->right;
        }
	}
	return 0;
}

template <class T>
int AVLTree<T>::nivelDeNodo(const T key){
    nivelDeNodo(root, key);
    return 1;
}

template <class T>
int AVLTree<T>::nivelDeNodo(AVLnode<T> *n, const T key){
    int nivel = 0;
    while(n){
        if(n->key == key){
            return nivel;
        }else{
            nivel++;
            if(key < n->key){
                n = n->left;
            }else{
                n = n->right;
            }
        }
    }
    return -1;
}

template <class T>
AVLnode<T>* AVLTree<T>::buscarNodo(const T key){
    return buscarNodo(root, key);
}

template <class T>
AVLnode<T>* AVLTree<T>::buscarNodo(AVLnode<T> *n, const T key){
    if(n == NULL){
        return NULL;
    }else if(n->key == key){
        return n;
    }else if(key < n->key ){
        return buscarNodo(n->left, key);
    }else{
        return buscarNodo(n->right, key);
    }
}
<file_sep>/Homework 3 - Algorithm Design Techniques/lcs.cpp
/*
  <NAME>
  A01021698
  Exercise 3: Longest Common Subsequence
  Technique: Dynamic programming
    Because of its optimal substructure and overlapping subproblems
  Complexity: The worst case scneario is when there is no common subsequence. The complexity is O(nm) where n and m are the sizes of each string. This is because it needs to go through each of the characters in the string
*/

#include <iostream>
#include <cstring>
using namespace std;

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

int lcs(string a, string b, int sizeA, int sizeB){
  int lcsCount[sizeA + 1][sizeB + 1];
  int i = 0, j = 0;

  for (i = 0; i <= sizeA; ++i) {
    for (j = 0; j <= sizeB; ++j) {
      if (i == 0 || j == 0)
        lcsCount[i][j] = 0;
      else if (a[i - 1] == b[j - 1])
        lcsCount[i][j] = lcsCount[i - 1][j - 1] + 1;
      else
        lcsCount[i][j] = max(lcsCount[i - 1][j], lcsCount[i][j - 1]);
    }
  }
  return lcsCount[sizeA][sizeB];
}


int main(){
  string stringA, stringB;
  cout << "\nLongest Common Subsequence\n";
  cout << "\nType in word 1: ";
    cin >> stringA;
  cout << "Type in word 2: ";
    cin >> stringB;
  int sizeA = stringA.length(), sizeB = stringB.length();

  cout<<"\nThe LCS is: " << lcs(stringA, stringB, sizeA, sizeB) << endl;

  return 0;
}
<file_sep>/Project 1 - Balanced Trees/ArbolesB.cs
﻿// BTrees in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Arboles_B
{
    public class EntryAlreadyExistsException : Exception
    {
        static String message = "An entri alreadi ecsists in the collection.";

        public EntryAlreadyExistsException() : base(message) { }
    }

    public class EntryNotFoundException : Exception
    {
        static String message = "The requested entri could not be located in the speciphied collection.";

        public EntryNotFoundException() : base(message) { }
    }

    enum Limits { Maximum = 4, Minimum = 2 }

    public class Node<T>
    {
        public int Count;
        public T[] Keys;
        public Node<T>[] Branch;

        public Node()
        {
            Count = 0;
            Keys = new T[(int)Limits.Maximum];
            Branch = new Node<T>[(int)Limits.Maximum + 1];
        }

        public void MoveLeft(int k)
        {
            Branch[k - 1].Count++;
            Branch[k - 1].Keys[Branch[k - 1].Count - 1] = Keys[k - 1];
            Branch[k - 1].Branch[Branch[k - 1].Count] = Branch[k].Branch[0];

            Keys[k - 1] = Branch[k].Keys[0];
            Branch[k].Branch[0] = Branch[k].Branch[1];
            Branch[k].Count--;

            for (int c = 1; c <= Branch[k].Count; c++)
            {
                Branch[k].Keys[c - 1] = Branch[k].Keys[c];
                Branch[k].Branch[c] = Branch[k].Branch[c + 1];
            }
        }

        public void MoveRight(int k)
        {
            for (int c = Branch[k].Count; c >= 1; c--)
            {
                Branch[k].Keys[c] = Branch[k].Keys[c - 1];
                Branch[k].Branch[c + 1] = Branch[k].Branch[c];
            }

            Branch[k].Branch[1] = Branch[k].Branch[0];
            Branch[k].Count++;
            Branch[k].Keys[0] = Keys[k - 1];

            Keys[k - 1] = Branch[k - 1].Keys[Branch[k - 1].Count - 1];
            Branch[k].Branch[0] = Branch[k - 1].Branch[Branch[k - 1].Count];
            Branch[k - 1].Count--;
        }

        public void Combine(int k)
        {
            Node<T> q = Branch[k];

            Branch[k - 1].Count++;
            Branch[k - 1].Keys[Branch[k - 1].Count - 1] = Keys[k - 1];
            Branch[k - 1].Branch[Branch[k - 1].Count] = q.Branch[0];

            for (int c = 1; c <= q.Count; c++)
            {
                Branch[k - 1].Count++;
                Branch[k - 1].Keys[Branch[k - 1].Count - 1] = q.Keys[c - 1];
                Branch[k - 1].Branch[Branch[k - 1].Count] = q.Branch[c];
            }

            for (int c = k; c <= Count - 1; c++)
            {
                Keys[c - 1] = Keys[c];
                Branch[c] = Branch[c + 1];
            }
            Count--;
        }

        public void Successor(int k)
        {
            Node<T> q = Branch[k];
            while (q.Branch[0] != null) q = q.Branch[0];
            Keys[k - 1] = q.Keys[0];
        }

        public void Restore(int k)
        {
            if (k == 0)
            {
                if (Branch[1].Count > (int)Limits.Minimum)
                    MoveLeft(1);
                else
                    Combine(1);
            }
            else if (k == Count)
            {
                if (Branch[k - 1].Count > (int)Limits.Minimum)
                    MoveRight(k);
                else
                    Combine(k);
            }
            else
            {
                if (Branch[k - 1].Count > (int)Limits.Minimum)
                    MoveRight(k);
                else if (Branch[k + 1].Count > (int)Limits.Minimum)
                    MoveLeft(k + 1);
                else
                    Combine(k);
            }
        }

        public void Remove(int k)
        {
            for (int i = k + 1; i <= Count; i++)
            {
                Keys[i - 2] = Keys[i - 1];
                Branch[i - 1] = Branch[i];
            }
            Count--;
        }
    }

    public class BTree<T>
    {
        protected Node<T> Root;
        protected IComparer<T> TComparer;

        public BTree()
        {
            Root = null;
            TComparer = Comparer<T>.Default;
        }

        public BTree(IComparer<T> TCompare)
        {
            Root = null;
            TComparer = TCompare;
        }

        public bool Exists(T Target)
        {
            Node<T> targetNode = null;
            int targetPosition = 0;
            return Search(Target, Root, ref targetNode, ref targetPosition);
        }

        bool Search(T Target, Node<T> Root, ref Node<T> targetNode, ref int targetPosition)
        {
            if (Root == null)
                return false;

            if (SearchNode(Target, Root, ref targetPosition))
            {
                targetNode = Root;
                return true;
            }
            else
                return Search(Target, Root.Branch[targetPosition], ref targetNode, ref targetPosition);
        }

        bool SearchNode(T Target, Node<T> Root, ref int Position)
        {
            int iCompare = TComparer.Compare(Target, Root.Keys[0]);
            if (iCompare < 0)
            {
                Position = 0;
                return false;
            }
            else
            {
                Position = Root.Count;
                iCompare = TComparer.Compare(Target, Root.Keys[Position - 1]);
                while (iCompare < 0 && Position > 1)
                {
                    Position--;
                    iCompare = TComparer.Compare(Target, Root.Keys[Position - 1]);
                }
                return iCompare == 0;
            }
        }

        public void Add(T newKey) { Insert(newKey, ref Root); }

        void Insert(T newKey, ref Node<T> root)
        {
            T x;
            Node<T> xr;

            if (PushDouun(newKey, root, out x, out xr))
            {
                Node<T> p = new Node<T>();
                p.Count = 1;
                p.Keys[0] = x;
                p.Branch[0] = root;
                p.Branch[1] = xr;
                root = p;
            }
        }

        bool PushDouun(T newKey, Node<T> p, out T x, out Node<T> xr)
        {
            bool pushUp = false;
            int k = 1;

            if (p == null)
            {
                pushUp = true;
                x = newKey;
                xr = null;
            }
            else
            {
                if (SearchNode(newKey, p, ref k)) throw new EntryAlreadyExistsException();

                if (PushDouun(newKey, p.Branch[k], out x, out xr))
                {
                    if (p.Count < (int)Limits.Maximum)
                    {
                        pushUp = false;
                        PushIn(x, xr, ref p, k);
                    }
                    else
                    {
                        pushUp = true;
                        Split(x, xr, p, k, ref x, ref xr);
                    }
                }
            }

            return pushUp;
        }

        void PushIn(T x, Node<T> xr, ref Node<T> p, int k)
        {
            for (int i = p.Count; i >= k + 1; i--)
            {
                p.Keys[i] = p.Keys[i - 1];
                p.Branch[i + 1] = p.Branch[i];
            }
            p.Keys[k] = x;
            p.Branch[k + 1] = xr;
            p.Count++;
        }

        bool Split(T x, Node<T> xr, Node<T> p, int k, ref T y, ref Node<T> yr)
        {
            int nnedian = k <= (int)Limits.Minimum ? (int)Limits.Minimum : (int)Limits.Minimum + 1;

            yr = new Node<T>();

            for (int i = nnedian + 1; i <= (int)Limits.Maximum; i++)
            {
                yr.Keys[i - nnedian - 1] = p.Keys[i - 1];
                yr.Branch[i - nnedian] = p.Branch[i];
            }

            yr.Count = (int)Limits.Maximum - nnedian;
            p.Count = nnedian;

            if (k <= (int)Limits.Minimum)
                PushIn(x, xr, ref p, k);
            else
                PushIn(x, xr, ref yr, k - nnedian);

            y = p.Keys[p.Count - 1];
            yr.Branch[0] = p.Branch[p.Count];

            p.Count--;

            return true;

        }

        public void Remove(T newKey) { Delete(newKey, ref Root); }

        void Delete(T Target, ref Node<T> root)
        {
            if (!RecDelete(Target, Root))
                throw new EntryNotFoundException();
            else if (root.Count == 0)
            {
                root = root.Branch[0];
            }
        }

        bool RecDelete(T Target, Node<T> p)
        {
            int k = 0;
            bool found = false;

            if (p == null)
                return false;
            else
            {
                found = SearchNode(Target, p, ref k);
                if (found)
                {
                    if (p.Branch[k - 1] == null)
                        p.Remove(k);
                    else
                    {
                        p.Successor(k);
                        if (!RecDelete(p.Keys[k - 1], p.Branch[k]))
                            throw new EntryNotFoundException();
                    }
                }
                else
                    found = RecDelete(Target, p.Branch[k]);

                if (p.Branch[k] != null)
                    if (p.Branch[k].Count < (int)Limits.Minimum)
                        p.Restore(k);

                return found;
            }
        }
    }

    enum Test { Maximum = 100000 };

    class Program
    {
        static void Main(string[] args)
        {
            BTree<string> bTree = new BTree<string>();

            for (int i = 0; i < (int)Test.Maximum; i++)
                bTree.Add("String" + i);

            DateTime dtBTreeStart = DateTime.Now;

            for (int i = 0; i < (int)Test.Maximum; i++)
                if (!bTree.Exists("String" + i))
                    Console.WriteLine("String" + i + " doesn't ecsist.");

            DateTime dtBTreeEnd = DateTime.Now;

            Console.WriteLine("BTree searches took: {0}", dtBTreeEnd - dtBTreeStart);

            for (int i = 0; i < (int)Test.Maximum; i++)
                bTree.Remove("String" + i);
        }
    }
}<file_sep>/Homework 3 - Algorithm Design Techniques/stableMarriage.cpp
/*
  <NAME>
  A01021698
  Exercise 4: Stable marriage
  Technique: Greedy algorithm
    Because at each step, the one's who propose make a locally optimal choice by selecting the best partner that hasn't been proposed to at the time.
  Complexity: Because the matrix is iterated n times two times (one for the men and one for the women), it is: O(n^2)
*/

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

#define N  4  // Number of men and women

void printCouples(int wPartner []) {
  cout << "Woman #   \t      Man #" << endl;
  for(int i = 0; i < N; ++i){
    cout << "   " << i+N << "   is engaged to    " << wPartner[i] << endl;
  }
}

bool chooseBetweenMen(int prefer[2*N][N], int woman, int secondMan, int firstMan) {
    for (int i = 0; i < N; i++)  {
        // if the second man has preference over the firstMan, woman changes her current engagement to the second man
        if (prefer[woman][i] == firstMan) return false;

        // If firstMan has preference over secondMan, the woman changes her current engangement to the firstMan
        if (prefer[woman][i] == secondMan) return true;
    }
    return false;
}

void stableMarriage(int prefer[2*N][N]) {
    int wPartner[N];
    bool mFree[N]; // If mFree is false, then he is single, otherwise he's engaged

    memset(wPartner, -1, sizeof(wPartner)); // Women are all single
    memset(mFree, false, sizeof(mFree)); // Men are all single
    int singleCount = N; //Number of single men

    while (singleCount > 0) {
      int firstMan;
      for (firstMan = 0; firstMan < N; firstMan++){
        if (mFree[firstMan] == false) break;
      }

      //Check preference of first freeMan picked
      for (int i = 0; i < N && mFree[firstMan] == false; i++) {
        int woman = prefer[firstMan][i];
        //If the woman the man wants is single, they become engaged
        if (wPartner[woman-N] == -1) {
          wPartner[woman-N] = firstMan;
          mFree[firstMan] = true;
          singleCount--;
        }
        else   // If the woman is not single
        {
          int secondMan = wPartner[woman-N]; //Current engagement of woman
          // Check if the woman prefers firstMan over her current engagement.
          bool changeOfEngagement = chooseBetweenMen(prefer, woman, secondMan, firstMan);
          if (changeOfEngagement == false){
              wPartner[woman-N] = firstMan;
              mFree[firstMan] = true;
              mFree[secondMan] = false;
          }
        }
      }

    }
    printCouples(wPartner);
}

int main() {
    int couples[2*N][N] = {
        // men
        {7, 4, 6, 5},
        {5, 6, 4, 7},
        {4, 5, 6, 7},
        {6, 5, 4, 7},

        // women
        {0, 1, 2, 3},
        {1, 2, 3, 0},
        {2, 3, 0, 1},
        {3, 2, 1, 0},
    };
    stableMarriage(couples);
    return 0;
}
<file_sep>/Homework 1 - Greedy Algorithms/README.md
# Tarea 1: Diseño de algoritmos

## Ejercicio 1
Teniendo en cuenta la explicación que aparece en la presentación titulada “TC2017-T3C02. Algoritmos ávidos” sobre el problema de la mochila, programe una implementación del mismo utilizando un algoritmo ávido.

## Ejercicio 2
Teniendo en cuenta la explicación que aparece en la presentación titulada “TC2017- T3C02. Algoritmos ávidos” sobre el problema del fontanero diligente, programe una implementación del mismo utilizando un algoritmo ávido.<file_sep>/Homework 1 - Greedy Algorithms/mochila.cpp
/*
  <NAME>
  A01021698
*/

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

void backpack(float wb[][2], int maxWeight, int maxElements) {
	float bp[maxElements + 1][maxWeight + 1];

  // The bag is empty
	for (int i = 0; i <= maxElements; ++i){
    for (int j = 0; j <= maxWeight; ++j) {
      bp[i][j] = 0;
    }
  }

	for (int i = 1; i <= maxElements; ++i) {
		for (int j = 0; j <= maxWeight; ++j) {
			bp[i][j] = bp[i - 1][j];
      float weight = wb[i - 1][1];
      float benefit = wb[i - 1][2];
			if ((j >= weight) && (bp[i][j] < (bp[i - 1][j - weight] + benefit))) {
				bp[i][j] = bp[i - 1][j - weight] + benefit;
			}

			cout << bp[i][j] << " " << endl;
		}
		cout << endl;
	}

  cout << "Max Value:\t" <<  bp[maxElements][maxWeight] << endl;
  cout << "Selected packs: ";

	while (maxElements != 0) {
		if (bp[maxElements][maxWeight] != bp[maxElements - 1][maxWeight]) {
      cout << "\tPackage " << maxElements << " with W = " << wb[maxElements - 1][1] << " and Value = " << wb[maxElements - 1][2] << endl;
			maxElements = maxElements - wb[maxElements - 1][1];
		}

		maxElements--;
	}
}

float floatRand(float mW){
  return float(rand())/(float(RAND_MAX/(mW)));
}

int main(){
  int maxElements = 0, maxWeight = 0;
  cout << "Type in the total number of elements that your bag can handle: ";
    cin >> maxElements;
  cout << "Type in the maximum weight that your bag can handle: ";
    cin >> maxWeight;

  // Creating a dynamic arrays
  float weight[maxElements];
  int benefit[maxElements];
  float ratio[maxElements];

  srand(time(NULL)); // Seed to generate random numbers over and over

  // Creating a randomly filled array of weight and benefit
  for(int i = 0; i < maxElements; ++i){
    weight[i] = floatRand(maxWeight) + 1;
    benefit[i] = rand() % 10;
  }

  float weightBenefit[maxElements][2];
  // Making one array for our weights and its corresponding benefit
  for(int i = 0; i < maxElements; ++i){
    weightBenefit[i][1] = weight[i];
    weightBenefit[i][2] = (float)benefit[i];
  }

  float temp[maxElements][1];
  for(int i = 0; i < maxElements - 1; ++i){
    for(int j = 0; j < maxElements - i - 1; ++j){
      if(weightBenefit[j][1] > weightBenefit[j + 1][1]){
        temp[j][1] = weightBenefit[j][1];
        weightBenefit[j][1] = weightBenefit[j + 1][1];
        weightBenefit[j + 1][1] = temp[j][1];

        temp[j][2] = weightBenefit[j][2];
        weightBenefit[j][2] = weightBenefit[j + 1][2];
        weightBenefit[j + 1][2] = temp[j][2];

      }
      ratio[j] = weightBenefit[j][2]/weightBenefit[j][1];
    }
  }

  cout << "\n\nMaximum weight: " << maxWeight << endl;
  cout << "\nElement |  Weight  |  Benefit  |  Ratio  " << endl;
  for(int i = 0; i < maxElements; ++i){
     cout << " " <<  i + 1 << "  \t  " << weightBenefit[i][1] << "\t  " << weightBenefit[i][2] << "\t  " << ratio[i] << endl;
  }

  backpack(weightBenefit, maxWeight, maxElements);
  return 0;
}
<file_sep>/Homework 5 - Computational Geometry/dialog.cpp
#include "dialog.h"
#include "ui_dialog.h"

Dialog::Dialog(QWidget *parent) : QDialog(parent), ui(new Ui::Dialog) {
    ui->setupUi(this);
}

Dialog::~Dialog() {
    delete ui;
}

void Dialog::on_poligono_clicked() {
    Poligonos poligonos;
    poligonos.setModal(true);
    poligonos.exec();
}

void Dialog::on_arco_clicked() {
    Arcos arco;
    arco.setModal(true);
    arco.exec();
}

void Dialog::on_cubo_clicked() {
    cubo cubo;
    cubo.setModal(true);
    cubo.exec();
}

void Dialog::on_cono_clicked() {
    Cono cono;
    cono.setModal(true);
    cono.exec();
}

void Dialog::on_prismarec_clicked() {
    prismarec prismaRectangular;
    prismaRectangular.setModal(true);
    prismaRectangular.exec();
}

void Dialog::on_prismatri_clicked() {
    PrismaTri prismaTriangular;
    prismaTriangular.setModal(true);
    prismaTriangular.exec();
}
<file_sep>/Project 1 - Balanced Trees/RBTree.h
#include"RBTNode.h"
#include <iomanip>
#include <vector>
#include <iostream>

using namespace std;

template<class T>
class  RBTree
{
public:
	RBTree();
	~RBTree();

	void insert(T key);    		// Key is the key value of the node to insert
	void remove(T key); 			// Delete the node of the key
	RBTNode<T>* search(T key);
	void print();
	void preOrder();    // Pre-order traversal Print red black tree
	void ascendingOrder();    //Intermediate traversal
	void descendingOrder();    // Post-order traversal
	bool ifNodeExists(RBTNode<T>* node, T value);
	void printHeight(T x);
	void printDepth(T x);
	void printLevel(T x);

private:
	void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);// left-handed
	void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);// right handed

	void insert(RBTNode<T>* &root, RBTNode<T>* node);// insert node, internal interface
	void InsertFixUp(RBTNode<T>* &root, RBTNode<T>* node);
	void destroy(RBTNode<T>* &node);

	void remove(RBTNode<T>*& root, RBTNode<T>*node);// Delete the node as KEY
	void removeFixUp(RBTNode<T>* &root, RBTNode<T>* node, RBTNode<T>*parent);

	RBTNode<T>* search(RBTNode<T>*node, T key) const;
	void print(RBTNode<T>* node)const;
	void preOrder(RBTNode<T>* tree)const;
	void ascendingOrder(RBTNode<T>* tree)const;
	void descendingOrder(RBTNode<T>* tree)const;

	bool hasPath(RBTNode<T>*& root, vector<T>&arr, T x);

private:
	RBTNode<T>*root;
};

template<class T>		//Constructor
RBTree<T>::RBTree() :root(NULL) {
	root = nullptr;
}
template<class T>		//Destructor
RBTree<T>::~RBTree() {
	destroy(root);
}
template<class T>		//Left
void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x) {
	RBTNode<T>*y = x->right;
	x->right = y->left;
	if (y->left != NULL)
		y->left->parent = x;

	y->parent = x->parent;
	if (x->parent == NULL)
		root = y;
	else {
		if (x == x->parent->left)
			x->parent->left = y;
		else
			x->parent->right = y;
	}
	y->left = x;
	x->parent = y;
};
template<class T>		//right spin
void RBTree<T>::rightRotate(RBTNode<T>*&root, RBTNode<T>*y) {
	RBTNode<T>*x = y->left;
	y->left = x->right;
	if (x->right != NULL)
		x->right->parent = y;

	x->parent = y->parent;
	if (y->parent == NULL)
		root = x;
	else {
		if  (y == y->parent->right)
			y->parent->right = x;
		else
			y->parent->left = x;
	}
	x->right = y;
	y->parent = x;
};

template<class T> //check if the value already exists in the tree
bool RBTree<T>::ifNodeExists(RBTNode<T>* node, T value){
    if (node == NULL)
        return false;
    if (node->key == value)
        return true;
    // recur on left subtree
    bool res1 = ifNodeExists(node->left, value);
    // recur on right subtree
    bool res2 = ifNodeExists(node->right, value);
    return res1 || res2;
};

template<class T>		//insert
void RBTree<T>::insert(T key){
	RBTNode<T> *x = root;
	bool exists = ifNodeExists(root, key);
	if(exists == true){
		cout << "The value " << key << " already exists in the tree\n";
	}else{
		RBTNode<T>*z = new RBTNode<T>(key, Red, NULL, NULL, NULL);
		insert(root, z);
}
};
template<class T>
void RBTree<T>::insert(RBTNode<T>* &root, RBTNode<T>* node){
	RBTNode<T> *x = root;
	RBTNode<T> *y = NULL;
	while (x != NULL){
		y = x;
		if (node->key > x->key)
		x = x->right;
		else
		x = x->left;
	}
	node->parent = y;
	if(y!=NULL)	{
		if (node->key > y->key)
		y->right = node;
		else
		y->left = node;
	}
	else
	root = node;
	node->color = Red;
	InsertFixUp(root, node);
};
template<class T>
void RBTree<T>::InsertFixUp(RBTNode<T>* &root, RBTNode<T>* node){
	RBTNode<T>*parent;
	parent = node->parent;
	while (node != RBTree::root  && parent->color == Red)	{
		RBTNode<T>*gparent = parent->parent;
		if (gparent->left == parent){
			RBTNode<T>*uncle = gparent->right;
			if (uncle != NULL && uncle->color == Red){
				parent->color = Black;
				uncle->color = Black;
				gparent->color = Red;
				node = gparent;
				parent = node->parent;
			}
			else
			{
				if (parent->right == node){
					leftRotate(root, parent);
					swap(node, parent);
				}
				rightRotate(root, gparent);
				gparent->color = Red;
				parent->color = Black;
				break;
			}
		}
		else
		{
			RBTNode<T>*uncle = gparent->left;
			if (uncle != NULL && uncle->color == Red){
				gparent->color = Red;
				parent->color = Black;
				uncle->color = Black;

				node = gparent;
				parent = node->parent;
			}
			else
			{
				if (parent->left == node){
					rightRotate(root, parent);
					swap(parent, node);
				}
				leftRotate(root, gparent);
				parent->color = Black;
				gparent->color = Red;
				break;
			}
		}
	}
	root->color = Black;
}
template<class T>
//Destroy the red black tree
void RBTree<T>::destroy(RBTNode<T>* &node){
	if (node == NULL)
		return;
	destroy(node->left);
	destroy(node->right);
	delete node;
	node = nullptr;
}

template<class T>
void RBTree<T>::remove(T key){
	RBTNode<T>*deletenode = search(root,key);
	if (deletenode != NULL)
		remove(root, deletenode);
}
template<class T>
void RBTree<T>::remove(RBTNode<T>*&root, RBTNode<T>*node){
	RBTNode<T> *child, *parent;
	RBTColor color;
	//The node left and right of the deleted node is not empty (not the leaf node)
	if (node->left != NULL && node->right != NULL){
		RBTNode<T> *replace = node;
		// Find the successor node (the lowest node of the right subtree of the current node)
		replace = node->right;
		while (replace->left != NULL){
			replace = replace->left;
		}
		//The deleted node is not the root node.
		if (node->parent != NULL){
			if (node->parent->left == node)
				node->parent->left = replace;
			else
				node->parent->right = replace;
		}
		//root node situation
		else
			root = replace;
		//child is the right node of the replacement node, which is the node that needs subsequent adjustment.
		//Because replace is a successor node, it is impossible for him to have a left child.
		//The same reason that the precursor node cannot have the right child node
		child = replace->right;
		parent = replace->parent;
		color = replace->color;

		// The node is replaced by the parent node of the repalce
		if (parent == node)
			parent = replace;
		else
		{
			//Children's node exists
			if (child != NULL)
				child->parent = parent;
			parent->left = child;

			replace->right = node->right;
			node->right->parent = replace;
		}
		replace->parent = node->parent;
		replace->color = node->color;
		replace->left = node->left;
		node->left->parent = replace;
		if (color == Black)
			removeFixUp(root, child, parent);

		delete node;
		return;
	}
	// When the deleted node has only the left (right) node is empty, find the child node of the deleted node
	if (node->left != NULL)
		child = node->left;
	else
		child = node->right;

	parent = node->parent;
	color = node->color;
	if (child)
	{
		child->parent = parent;
	}
	//The deleted node is not the root node
	if (parent)
	{
		if (node == parent->left)
			parent->left = child;
		else
			parent->right = child;
	}
	//The deleted node is the root node
	else
		RBTree::root = child;

	if (color == Black)
	{
		removeFixUp(root, child, parent);
	}
	delete node;

}
template<class T>
void RBTree<T>::removeFixUp(RBTNode<T>* &root, RBTNode<T>* node,RBTNode<T>*parent){
	RBTNode<T>*othernode;
	while ((!node) || node->color == Black && node != RBTree::root){
		if (parent->left == node){
			othernode = parent->right;
			if (othernode->color == Red){
				othernode->color = Black;
				parent->color = Red;
				leftRotate(root, parent);
				othernode = parent->right;
			}
			else
			{
				if (!(othernode->right) || othernode->right->color == Black){
					othernode->left->color=Black;
					othernode->color = Red;
					rightRotate(root, othernode);
					othernode = parent->right;
				}
				othernode->color = parent->color;
				parent->color = Black;
				othernode->right->color = Black;
				leftRotate(root, parent);
				node = root;
				break;
			}
		}
		else
		{
			othernode = parent->left;
			if (othernode->color == Red){
				othernode->color = Black;
				parent->color = Red;
				rightRotate(root, parent);
				othernode = parent->left;
			}
			if ((!othernode->left || othernode->left->color == Black) && (!othernode->right || othernode->right->color == Black)){
				othernode->color = Red;
				node = parent;
				parent = node->parent;
			}
			else
			{
				if (!(othernode->left) || othernode->left->color == Black){
					othernode->right->color = Black;
					othernode->color = Red;
					leftRotate(root, othernode);
					othernode = parent->left;
				}
				othernode->color = parent->color;
				parent->color = Black;
				othernode->left->color = Black;
				rightRotate(root, parent);
				node = root;
				break;
			}
		}
	}
	if (node)
		node->color = Black;
}

template<class T>
RBTNode<T>* RBTree<T>::search(T key){
	RBTNode<T> *x = root;
	RBTNode<T> *z = new RBTNode<T>(key, Red, NULL, NULL, NULL);
	bool inTree = ifNodeExists(root, key);
	if(inTree == false){
		cout << "The following node does not exist in the tree: ";
		return z;
	}
	else
		return search(root, key);
}

template<class T>
RBTNode<T>* RBTree<T>::search(RBTNode<T>*node, T key) const{
	if (node == NULL || node->key == key){
		cout << "The following node does exist in the tree: ";
		return node;
	}else{
		if (key > node->key)
			return search(node->right, key);
		else
			return search(node->left, key);
	}
}

template<class T>
// HEIGHT: LONGEST PATH FROM THAT NODE TO A LEAF
bool RBTree<T>::hasPath(RBTNode<T>*& root, vector<T>& arr, T x){
	if(root == NULL) return false;
	arr.push_back(root->key); //save the nodes value in vector
	if(root->key == x) return true;
	if(hasPath(root->left, arr, x) || hasPath(root->right, arr, x)) return true;
	arr.pop_back();
	return false;
}

template<class T>
void RBTree<T>::printHeight(T x){
	RBTNode<T> *y = root;
	vector<T> arr;
	int h = 0;
	cout << "Printing path: \n";
	if(hasPath(root, arr, x)){
		for(int i = 0; i < arr.size() - 1; ++i){
			cout << arr[i] << " -> ";
			h++;
		}
		cout << arr[arr.size() - 1];
	} else
		cout << "There's no path of " << x << endl;
	cout << "\nHeight of node " << x << " is " << h << endl;
}

template<class T>
void RBTree<T>::printDepth(T x){
	RBTNode<T> *y = root;
	vector<T> arr;
	int d = 0;
	cout << "Printing path: \n";
	if(hasPath(root, arr, x)){
		for(int i = arr.size() - 1; i > 0 ; --i){
			cout << arr[i] << " -> ";
			d++;
		}
		cout << arr[0];
	} else
		cout << "There's no path of " << x << endl;
	cout << "\nDepth of node " << x << " to root is " << d << endl;
}

template<class T>
void RBTree<T>::printLevel(T x){
	RBTNode<T> *y = root;
	vector<T> arr;
	int l = 0;
	cout << "Printing path: \n";
	if(hasPath(root, arr, x)){
		for(int i = arr.size() - 1; i > 0 ; --i){
			cout << arr[i] << " -> ";
			l++;
		}
		cout << arr[0];
	} else
		cout << "There's no path of " << x << endl;
	cout << "\nLevel of node " << x << " is " << l + 1 << endl;
}

template<class T>		// Traverse RB tree
void RBTree<T>::ascendingOrder() {
	if (root == NULL)
		cout << "Empty Redblack tree\n";
	else
		ascendingOrder(root);
};

template<class T>
void RBTree<T>::ascendingOrder(RBTNode<T>* tree)const {
	if (tree != NULL) {
		ascendingOrder(tree->left);
		cout << tree->key << " ";
		ascendingOrder(tree->right);
	}
}

template<class T>      // Traverse RB tree
void RBTree<T>::descendingOrder() {
	if (root == NULL)
		cout << "Empty Redblack tree\n";
	else
		descendingOrder(root);
};

template<class T>
void RBTree<T>::descendingOrder(RBTNode<T>* tree)const {
	if (tree != NULL) {
		descendingOrder(tree->right);
		cout << tree->key << " ";
		descendingOrder(tree->left);
	}
}
<file_sep>/Homework 5 - Computational Geometry/cubo.h
#ifndef CUBO_H
#define CUBO_H

#include <QDialog>
#include <QtGui>
#include <QtCore>
namespace Ui {
class cubo;
}

class cubo : public QDialog
{
    Q_OBJECT

public:
    explicit cubo(QWidget *parent = 0);
    ~cubo();

private:
    Ui::cubo *ui;
    bool dibuja = false;

    double xCentro;
    double yCentro;

    QVector<QTransform> vecTrans;

protected:
     void paintEvent(QPaintEvent *e);
     void drawCubo(QPainter &painter);

private slots:
     void on_dibujar_clicked();
     void on_trasladar_clicked();
     void on_rotar_clicked();
     void on_zoom_in_clicked();
     void on_zoom_out_clicked();
     void on_horizontal_clicked();
     void on_vertical_clicked();

};

#endif // CUBO_H
<file_sep>/Project 3 - Parallel vs Sequential/README.md
# *Sudoku 9x9 Solver*
---
#### Materia: *Análisis y Diseño de Algoritmos (TC2017)*

#### Semestre: *Otoño 2019*

##### Campus: *Santa Fe*

##### Integrantes:
1. *<NAME>* *A01021698*
2. *<NAME>* *A01379951*

---
## 1. Aspectos generales

### 1.1 Requerimientos

A continuación se mencionan los requerimientos mínimos del proyecto, favor de tenerlos presente para que cumpla con todos.

* El equipo tiene la libertad de elegir el problema a resolver.
* El proyecto deberá utilizar [OpenMP](https://www.openmp.org/) para la implementación del código paralelo.
* Todo el código y la documentación del proyecto debe alojarse en este repositorio de GitHub. Favor de mantener la estructura de carpetas propuesta.

### 1.2 Estructura del repositorio
El proyecto debe seguir la siguiente estructura de carpetas:
```
- / 			        # Raíz de todo el proyecto
    - README.md			# este archivo
    - secuencial		# Carpeta con la solución secuencial
    - paralelo			# Carpeta con la solución paralela
    - docs              # Carpeta con los documentos, tablas, gráficas, imágenes
```

### 1.3 Documentación  del proyecto

Como parte de la entrega final del proyecto, se debe incluir la siguiente información:

* Descripción del problema a resolver.
* Descripción de la solución secuencial con referencia (enlace) al código secuencial alojado en la carpeta [secuencial](secuencial/).
* Análisis de los inhibidores de paralelismo presente y una explicación de cómo se solucionaron.
* Descripción de la solución paralela con referencia (enlace) al código paralelo alojado en la carpeta [paralelo](paralelo/).
* Tabla de resultados con los tiempos de ejecución medidos para cada variante de la solución secuencial vs. la solución paralela, teniendo en cuenta: 5 tamaños diferentes de las entradas, 5 opciones diferentes de números de CPU (threads), 4 ocpiones diferentes de balanceo (*auto, guided, static, dynamic*).
* Gráfica(s) comparativa(s) de los resultados obtenidos en las mediciones.
* Interpretación de los resultados obtenidos.
* Guía paso a paso para la ejecución del código y replicar los resultados obtenidos.
* El código debe estar documentado siguiendo los estándares definidos para el lenguaje de programación seleccionado.

## 2. Descripción del problema

“Sudoku (en japonés: 数独, sūdoku) es un juego matemático que se inventó a finales de la década de 1970, adquirió popularidad en Japón en la década de 1980 y se dio a conocer en el ámbito internacional en 2005 cuando numerosos periódicos empezaron a publicarlo en su sección de pasatiempos.” (Wikipedia, 2019)

Sudoku es un juego de un solo jugador donde se tienen n x n celdas y algunas de ellas están llenadas con un número del 1 a n. Para ganar, se tienen que llenar las celdas que están vacías siguiendo ciertas reglas:

1. Cada número debe aparecer una sola vez por renglón
2. Cada número debe aparecer una sola vez por columna
3. Cada número debe aparecer una sola vez por *subgrid*
   - Por subgrid se puede pensar como un sudoku individual (debe de seguir las mismas reglas) pero de menor tamaño. Por ejemplo, en un Sudoko de 9x9, existen subgirds de 3x3

## 3. Solución secuencial

1. Se le asignará a cada celda un índice que irá del 0 al 80, para completar, así, un Sudoku de 81 celdas (9 x 9). Las celdas, se almacenarán en un vector lineal de tamaño k.
2. Se crearán diferentes “grupos” de celdas que servirán para respetar las reglas 
   - **Grupos**: Para los renglones, columnas y casillas que deberán seguir las reglas
     - Existen 27 grupos distintos:
        - 0 - 8: grupos por renglón
        - 9 - 17: grupos por columnas
        - 18 - 26: grupo por casilla
   - **GroupsOf**: A qué grupos una cierta celda pertenece
   - **Neighbors**: Todas las celdas que están relacionadas con una celda


En la siguiente imagen, se muestra un Sudoku de 9x9 que tiene asignados los valores de las casillas, señalando en distintos colores las reglas que se deben de seguir, así como también la representación de los grupos.

![SudokuExplained](/docs/1.png)

Por ejemplo: Dada la casilla 10
- ¿A qué grupos pertence?: 1 (renglón), 10, (columna), 22 (casilla)
- ¿Vecinos de casilla #10?: 0, 1, 2, 9, 11, 12, 13, 14, 15, 16, 17, 28, 37, 46, 55, 64, 72

3. Las opraciones a realizar son:
   - **Assign(int *k*, int *val*):** Elimina a los demás valores de la celda (*k*) que no son el valor dado (*val*)
   - **DeleteVal(int *k*, int *val*):** Eliminar *v* de los posibles valores de la celda *k*. Existen tres posibilidades para eliminar:
        - Si hay 0 valores posibles, entonces existe un error y se regresa un False para descartar la rama
        - Si hay 1 valor posible, entonces ese es el valor (*v2*) que va en la celda (*k*). Para esto, se deberá eliminar el valor *v2* de todos sus vecinos para evitar repetidos
        - Si al haber eliminado una posibilidad al asignar un valor en cierta casilla y solo hay otro lugar donde se puede asignar el valor restante, se asigna en la nueva casilla

4. Un árbol de posibilidades se irá creando conforme se realicen diferentes operaciones; en el árbol se propagarán las restricciones de lo que se le indicó en un inicio, y si en algún punto una rama no cumple con las restricciones, se regresará un False para indicar que por ese camino no es y se descarta la rama completa.

Al compilar un cierto Sudoku con el programa como se encuentra en este momento, podría llegar a funcionar si, sólo si, existe una sola posibilidad para cada celda. De lo contrario se deberá de añadir lo siguiente: 
1. Se creará una función que escogerá un valor aleatorio dentro de las distintas posibilidades que pudiera tener una celda de un Sudoku que aún está sin resolver. Creará un nuevo “árbol” de posibilidades, que irá borrando ramas en cuanto estás dejen de cumplir con las reglas. Se deberá de empezar con las celdas que tienen menores posibilidades ya que al descartar una de sus ramas, rápidamente se descartan los valores en las demás ramas.

A todo esto, significa que un Sudoku puede ser resuelto utilizando un método de “Backtracking”, pues busca una solución y se regresa si ésta no es válida, ya que esto significa que nos hemos equivocado y busca en otra dirección utilizando otros valores.

La complejidad del algoritmo secuencial es de: O(n2) al eliminar los valores pues es ahí donde se aplican las reglas

[Codigo Secuencial](https://github.com/tec-csf/TC2017-PF-Otono-2019-equipo-algoritmos/tree/master/secuencial)

## 4. Análisis de los inhibidores del paralelismo

Al momento de querer paralelizar este problema, nos dimos cuenta de que había muchos ciclos for en los cuales se pudiera implementar la librería Open MP para sacarle provecho a los hilos de procesamiento de nuestras PC y resolver el problema en una cantidad aún menor de tiempo. 
 
Nuestro primer tope fue el darnos cuenta de que no podíamos paralelizar todos los ciclos for de la solución, sino que debíamos limitarnos a escoger los ciclos en los cuales el procesamiento se iba a ser exhausto. 
 
Notamos que una gran parte del procesamiento se concentraba en cargar el archivo, para lo cual hicimos uso de #pragma omp parallel para distribuir las columnas a través de los hilos de procesamiento y, de esta forma, lograra resolver más rápido el sudoku puzzle.


## 5. Solución paralela

Nuestra solución se centra en paralelizar la forma en la que el programa procesa la entrada para crear la matriz. Lo hacemos dividiendo el número de columnas entre el número de hilos de procesamiento disponibles y así acelerar su procesamiento. 

[Codigo Paralelo](https://github.com/tec-csf/TC2017-PF-Otono-2019-equipo-algoritmos/tree/master/paralelo)

## 6. Tabla de resultados

Para poder comparar correctamente ambos algoritmos, se utilzaron 5 diferentes sudokus de entarada, los cuales iban incrementando su dificultad. Se resolvieron 2 Sudokus, los cuales fueron propuestos por un matemático filipino, que tienen la fama de ser muy difíciles. 

![VisualSudoku](/docs/inputSudokuVisual.png)

**Secuencial**

| Dificultad de Sudoku | Tiempo de ejecución |
| :------------------: | :-----------------: |
|      Easy - 1        |    0.02 segundos    |
|      Easy - 2        |     0.0 segundos    |
|     Hard Inkala 1    |    0.002 segundos   |
|     Hard Inkala 2    |   0.005 segundos    |
|      Impossible   |    0.027 segundos    |

**Paralelo**

| Dificultad de Sudoku | Tiempo de ejecución |
| :------------------: | :-----------------: |
|      Easy - 1        |     0.00000004 segundos |
|      Easy - 2        |    0.00000005 segundos |
|     Hard Inkala 1    |    0.00000006  segundos |
|     Hard Inkala 2    |    0.00000005 segundos|
|      Impossible      |    0.00000006 segundos |


## 7. Gráfica(s) comparativa(s)

![Tiempos de Ejecución S vs P](/docs/SecuencialVSParalelo.png)

![VisualSudoku](/docs/NumberOfThreads2.png)

*Cambiando opciones de balanceo*

![VisualSudoku](/docs/BalancingOptions.png)

*Auto*

![VisualSudoku](/docs/Auto2.png)

*Guided*

![VisualSudoku](/docs/Guided.png)

*Static*

![VisualSudoku](/docs/Static.png)

*Dynamic*

![VisualSudoku](/docs/Dynamic.png)

*Average*

![VisualSudoku](/docs/Average.png)

## 8. Interpretación de los resultados

Al correr ambos programas con el mismo set de datos nos percatamos que el procesamiento en paralelo sacó ventaja de la solución secuencial. La diferencia no es tan perceptible, pues ante nuestros ojos ambas soluciones resolvían el puzzle al instante, pero sigue siendo más rápido.
 
¿Cómo se notaría más esta ventaja? La ventaja vendría cuando se tuviera que procesar una matriz nxn. Considerando n un número mucho mayor a 9, la cantidad de elementos de una matriz a procesar serían basta y es ahí donde nuestro programa sacaría la ventaja. 

## 9. Guía paso a paso

Clonamos el repositorio a la carpeta de preferencia:
 
> git clone https://github.com/tec-csf/TC2017-PF-Otono-2019-equipo-algoritmos
 
Nos posicionamos en la carpeta de nuestro repositorio:
 
> cd TC2017-PF-Otono-2019-equipo-algoritmos
 
**Para el código secuencial**
 
Nos posicionamos en la carpeta secuencial:
 
> cd secuencial
 
Compilamos nuestro programa:
 
> g++ sudoku.cpp -o sudoku
 
Para que la solución secuencial resuelva un puzzle se le tiene que indicar el archivo de texto que debe de leer por medio del siguiente comando:
 
> ./sudoku < sudokuResolver.txt
 
O bien: 
 
> ./sudoku < impossible-1.txt
 
Para que resuelva otro. 
 
Si se quiere almacenar el sudoku resuelto en un archivo de texto, se deberá de ingresar el siguiente comando: 
 
> ./sudoku < sudokuResolver.txt > sudokuResuelto.txt. 
 
 
Se han añadido distintos Sudokus por resolver que están listos para ser usados por el usuario. 


**Para el código paralelo**

Nos posicionamos en la carpeta paralela:
 
> cd paralela
 
Compilamos nuestro programa:
 
> g++ -fopenmp sudoku.cpp -o sudoku
 
Para que la solución secuencial resuelva un puzzle se le tiene que indicar el archivo de texto que debe de leer por medio del siguiente comando:
 
> ./sudoku < sudokuResolver.txt
 
O bien: 
 
> ./sudoku < impossible-1.txt
 
Para que resuelva otro. 
 
Si se quiere almacenar el sudoku resuelto en un archivo de texto, se deberá de ingresar el siguiente comando: 
 
> ./sudoku < sudokuResolver.txt > sudokuResuelto.txt. 
 
 
Se han añadido distintos Sudokus por resolver que están listos para ser usados por el usuario. 


*Importante* El programa actualmente acepta dos distintos formatos de entrada de Sudoku:


1. 
![ExampleInput](/docs/exampleInputSudoku.png)

El programa podrá diferenciar y hará uso de los valores que realmente le interesan, sustituyendo el punto (.) por 0 para tomarlos como valores nulos.

2. **003020600900305001001806400008102900700000008006708200002609500800203009005010300**

El programa tomará los 0 como valores vacíos y creará las tripletas necesarias para consturir el sudoku de 9x9
    
## 10. Referencias

1. <NAME>. [<NAME>] (2013, enero 9). *C++ Solucionador de Sudokus 1-5/5*. [Archivo de video]. Recuperado el 22 de noviembre de 2019 de: https://www.youtube.com/watch?v=p7mjDQgbKYM
2. <NAME>. (s.f.). *Solving Every Sudoku Puzzle* Recuperado el 22 de noviembre de 2019 de: http://norvig.com/sudoku.html
3. <NAME>. [<NAME>] (2013, marzo 16). *Sudoku Parallel Approach* [Archivo de video]. Recuperado el 22 de noviembre de 2019 de: https://www.youtube.com/watch?v=S9ZBsgsj31w
4. <NAME>. (2014). *Parallelized Sudoku Solving Algorithm Using OpenMP*. Recuperado el 22 de noviembre de 2019 de: https://cse.buffalo.edu/faculty/miller/Courses/CSE633/Sankar-Spring-2014-CSE633.pdf
<file_sep>/Homework 2 - Sorting Algorithms/main.cpp
#include <time.h>
#include <iomanip>
#include <chrono>
#include <unistd.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Node{
    int key;
    struct Node *left, *right;
};

struct Node *newNode(int item){
    struct Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

struct bucket{
    int count;
    int* value;
};

int compareIntegers(const void* first, const void* second){
    int x = ((int)first), y =  ((int)second);
    if (x == y){
        return 0;
    }
    else if (x < y){
        return -1;
    }
    else{
        return 1;
    }
}

void storeSorted(Node *root, int arr[], int &i){
    if (root != NULL)    {
        storeSorted(root->left, arr, i);
        arr[i++] = root->key;
        storeSorted(root->right, arr, i);
    }
}

Node* insert(Node* node, int key){
    if (node == NULL) return newNode(key);
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    return node;
}

int getMax(int arr[], int n){
    int mx = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > mx)
            mx = arr[i];
    return mx;
}

void swap(int *xp, int *yp){
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void heapify(int arr[], int n, int i){
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);

        heapify(arr, n, largest);
    }
}

void merge(int *a, int low, int high, int mid){
  int i, j, k, temp[high - low + 1];
  i = low;
  k = 0;
  j = mid + 1;

  while(i <= mid && j <= high){
    if(a[i] < a[j]){
      temp[k] = a[i];
      k++;
      i++;
    } else {
      temp[k] = a[j];
      k++;
      j++;
    }
  }

  while(i <= mid){
    temp[k] = a[i];
    k++;
    i++;
  }

  while(j <= high){
    temp[k] = a[j];
    k++;
    j++;
  }

  for (i = low; i <= high; i++){
    a[i] = temp[i-low];
  }

}

void mergeSort(int *a, int low, int high){
  int mid;
	if (low < high)	{
		mid=(low+high)/2;
		mergeSort(a, low, mid);
		mergeSort(a, mid+1, high);

		merge(a, low, high, mid);
	}
  // https://www.geeksforgeeks.org/merge-sort/
}

int partition (int arr[], int low, int high){
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++){
        if (arr[j] < pivot){
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void bubbleSort(int array[], int n){
  for(int i = 0; i < n - 1; i++){
    for(int j = 0; j < n - i - 1; j++){
      if(array[j] > array[j+1]){
        int temp = array[j];
        array[j] = array[j+1];
        array[j+1] = temp;
      }
    }
  }
  //obtenido de mis códigos realizados en otra clase
}

void cocktailSort(int a[], int n){
  bool swapped = true;
  int start = 0;
  int end = n - 1;

  while (swapped) {
    swapped = false;
    for (int i = start; i < end; ++i) {
      if (a[i] > a[i + 1]) {
        swap(a[i], a[i + 1]);
        swapped = true;
      }
    }

    if (!swapped)
      break;
    swapped = false;
    --end;
    for (int i = end - 1; i >= start; --i) {
      if (a[i] > a[i + 1]) {
        swap(a[i], a[i + 1]);
        swapped = true;
      }
    }

    ++start;
    }
    // https://www.geeksforgeeks.org/cpp-program-for-cocktail-sort/
}

void insertionSort(int array[], int n){
  for (int i = 1; i < n; i ++){
    int temp = array[i];
    for(int j = i - 1; j>= 0 && array[j] > temp; j--){
      array[j + 1]= array[j];
      array[j] = temp;
    }
  }
  //https://www.geeksforgeeks.org/insertion-sort/
}

void bucketSort(int array[],int n){
    struct bucket buckets[3];
    int i, j, k;
    for (i = 0; i < 3; i++){
        buckets[i].count = 0;
        buckets[i].value = (int*)malloc(sizeof(int) * n);
    }

    for (i = 0; i < n; i++){
        if (array[i] < 0){
            buckets[0].value[buckets[0].count++] = array[i];
        }
        else if (array[i] > 10){
            buckets[2].value[buckets[2].count++] = array[i];
        }
        else{
            buckets[1].value[buckets[1].count++] = array[i];
        }
    }
    for (k = 0, i = 0; i < 3; i++){
        qsort(buckets[i].value, buckets[i].count, sizeof(int), &compareIntegers);
        for (j = 0; j < buckets[i].count; j++){
            array[k + j] = buckets[i].value[j];
        }
        k += buckets[i].count;
        free(buckets[i].value);
    }
    //https://www.geeksforgeeks.org/bucket-sort-2/
}

void countingSort(vector <int>& arr){
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());
    int range = max - min + 1;

    vector<int> count(range), output(arr.size());
    for(int i = 0; i < arr.size(); i++)
        count[arr[i]-min]++;

    for(int i = 1; i < count.size(); i++)
           count[i] += count[i-1];

    for(int i = arr.size()-1; i >= 0; i--)
    {
         output[ count[arr[i]-min] -1 ] = arr[i];
              count[arr[i]-min]--;
    }

    for(int i=0; i < arr.size(); i++)
            arr[i] = output[i];

  //https://www.geeksforgeeks.org/counting-sort/
}

void binaryTreeSort(int arr[], int n){
    struct Node *root = NULL;
    root = insert(root, arr[0]);
    for (int i=1; i<n; i++)
        insert(root, arr[i]);
    int i = 0;
    storeSorted(root, arr, i);
    //https://www.geeksforgeeks.org/tree-sort/
}

void countSort(int arr[], int n, int exp){
    int output[n];
    int i, count[10] = {0};

    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%10 ]++;

    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (i = n - 1; i >= 0; i--) {
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
        count[ (arr[i]/exp)%10 ]--;
    }

    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n){
  int m = getMax(arr, n);

  for (int exp = 1; m/exp > 0; exp *= 10)
      countSort(arr, n, exp);

  //https://www.geeksforgeeks.org/radix-sort/
}

void shellSort(int arr[], int n){
  for (int gap = n/2; gap > 0; gap /= 2) {
      for (int i = gap; i < n; i += 1){
          int temp = arr[i];
          int j;
          for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
              arr[j] = arr[j - gap];
          arr[j] = temp;
      }
  }
  //https://www.geeksforgeeks.org/shellsort/
}

void selectionSort(int arr[], int n){
  int i, j, min_idx;

  for (i = 0; i < n-1; i++)  {
      min_idx = i;
      for (j = i+1; j < n; j++)
      if (arr[j] < arr[min_idx])
          min_idx = j;

      swap(&arr[min_idx], &arr[i]);
  }

  //obtenido de mis códigos realizados en clases anteriores
}

void heapSort(int arr[], int n){
  for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);

  for (int i = n - 1; i >= 0; i--) {
      swap(arr[0], arr[i]);
      heapify(arr, i, 0);
  }

  //https://www.geeksforgeeks.org/cpp-program-for-heap-sort/
}

void quickSort(int arr[], int low, int high){
  if (low < high)  {
      int pi = partition(arr, low, high);
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
  }
  //https://www.geeksforgeeks.org/quick-sort/
}

int main(){
  int size = 0;
  int algorithm = 12;

  cout << "Type in the size of your array. Choose from the following list: " << endl;
  cout << "1. 10\n2. 100\n3. 1 000\n4. 10 000\n5. 100 000\n6. 200 000\n";
    cin >> size;

  //creating the array with random numbers
  int array[size+1];
  for(int i = 0; i < size; i++){
    array[i] = rand() % 200 + 1;
  }

  cout << "\nSORTING ALGORITHM\t  ELAPSED TIME (ms)\n" << "____________________________________________" << endl;
  for(int i = 1; i <= algorithm; i++){
    //creating a copy of they original array
    int arrayCopy[size+1];
    for(int i = 0; i < size; i++){
      arrayCopy[i] = array[i];
    }
    switch(i){
      case 1: //BubbleSort
      {
        auto start = chrono::steady_clock::now();
        bubbleSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "\nBubble Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 2: //CocktailSort
      {
        auto start = chrono::steady_clock::now();
        cocktailSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Cocktail Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 3://Insertion Sort
      {
        auto start = chrono::steady_clock::now();
        insertionSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Insertion Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 4: //Bucket Sort
      {
        auto start = chrono::steady_clock::now();
        bucketSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Bucket Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 5: //Counting Sort
      {
        //array into vector
        vector<int> vec;

        for(int i = 0; i < size; ++i){
          vec.push_back(array[i]);
        }

        auto start = chrono::steady_clock::now();
        countingSort(vec);
        auto end = chrono::steady_clock::now();
        cout << "Counting Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 6: //Merge sort
      {
        auto start = chrono::steady_clock::now();
        mergeSort(array, 0, size-1);
        auto end = chrono::steady_clock::now();
        cout << "Merge Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 7: //Binary Tree sort
      {
        auto start = chrono::steady_clock::now();
        binaryTreeSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Binary Tree Sort\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 8: //Radix sort
      {
        auto start = chrono::steady_clock::now();
        radixSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Radix Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 9: //Shell sort
      {
        auto start = chrono::steady_clock::now();
        shellSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Shell Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 10: //Selection Sort
      {
        auto start = chrono::steady_clock::now();
        selectionSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Selection Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 11: //Heap sort
      {
        auto start = chrono::steady_clock::now();
        heapSort(array, size);
        auto end = chrono::steady_clock::now();
        cout << "Heap Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
      case 12: //Quick sort
      {
        auto start = chrono::steady_clock::now();
        quickSort(array, 0, size - 1);
        auto end = chrono::steady_clock::now();
        cout << "Quick Sort\t\t\t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
      }
      break;
    }
  }
  return 0;
}
<file_sep>/Homework 5 - Computational Geometry/arcos.cpp
#include "arcos.h"
#include "ui_arcos.h"
#include <QMessageBox>

#define PI 3.14159265

Arcos::Arcos(QWidget *parent):QDialog(parent), ui(new Ui::Arcos){
    this->setFixedSize(521, 333); //Size of window
    ui->setupUi(this);
    xCentro = 345.0; // values so the first drawn figure is centered
    yCentro = 170.0;
    QTransform center;
    center.translate(xCentro,yCentro);
    vecTrans.push_back(center);
}

Arcos::~Arcos() {
    delete ui;
}

void puntosDelCirculo(QPainter & painter) {
  int xc,yc,x,y,p,r;
  xc=300;
  yc=200;
  r=100;
  x = 0;
  y = r;
  p = 1-r;

  while(x <= y)  {
    if(p < 0) {
        x++;
        p += 2*x +1;
    }
    else {
        x++;
        y--;
        p += 2*x - 2*y +1;
    }

    painter.drawPoint(xc+x,yc+y);
    painter.drawPoint(xc+y,yc+x);
    painter.drawPoint(xc+x,yc-y);
    painter.drawPoint(xc+y,yc-x);
  }
}

void dibujarArco(QPainter & painter) {
    int xc,yc,x,y,p,r;

      xc=0;
      yc=0;
      r=100;
      x = 0;
      y = r;
      p = 1-r;

      while(x<=y) {
        if(p<0) {
            x++;
            p += 2*x +1;
        }
        else{
            x++;
            y--;
            p += 2*x - 2*y +1;
        }
        painter.drawPoint(xc+x,yc+y);
        painter.drawPoint(xc+y,yc+x);
        painter.drawPoint(xc+x,yc-y);
        painter.drawPoint(xc+y,yc-x);
      }
    }

void Arcos::paintEvent(QPaintEvent *event) {
    QPainter painter(this);
    QPen pointPen(Qt::black);
    pointPen.setWidth(2);
    painter.setPen(pointPen);

    if (dibuja) {
        for(int i=0; i<vecTrans.size(); ++i) {
            painter.setTransform(vecTrans[i],true);
            dibujarArco(painter);;
        }
    }
}

//These are the buttons
void Arcos::on_dibujar_clicked() {
    trans.dibujar(dibuja,vecTrans,xCentro,yCentro);
    update();
}

void Arcos::on_trasladar_clicked() {
    QString x = ui->boxXinicio->toPlainText();
    QString y = ui->boxYinicio->toPlainText();
        if(!x.isEmpty() && !y.isEmpty()) {
            trans.trasladar(x, y, vecTrans);
            update();
         } else {
            QMessageBox msgBox;
            msgBox.setText("Please type in the values for x and y");
            msgBox.exec();
         }
}

void Arcos::on_rotar_clicked() {
    QString gradosStr = ui->boxGrados->toPlainText();
    if(!gradosStr.isEmpty()) {
        trans.rotar(gradosStr, vecTrans);
        update();
    } else {
        QMessageBox msgBox;
        msgBox.setText("Please type in the degree for rotation");
        msgBox.exec();
    }
}

void Arcos::on_zoom_in_clicked() {
    trans.zoomIn(vecTrans);
    update();
}

void Arcos::on_zoom_out_clicked() {
    trans.zoomOut(vecTrans);
    update();
}

void Arcos::on_horizontal_clicked() {
    trans.reflexHorizontal(vecTrans);
    update();
}

void Arcos::on_vertical_clicked() {
    trans.reflexVertical(vecTrans);
    update();
}
<file_sep>/Project 1 - Balanced Trees/TwoThreeTree.h
#include "TwoThreeNode.h"
#include <iomanip>
#include <queue>
#include <iostream>
#include <vector>

using namespace std;

template <class T>
class TwoThreeTree {

protected:
  TwoThreeNode<T> * root = nullptr;
  std::vector<T> leafLevel;

public:
  TwoThreeTree() { }
  ~TwoThreeTree();

  bool empty();

  void clear();
  void clear(TwoThreeNode<T> * node);

  TwoThreeNode<T> * getRoot() const;
  void setRoot(const T info);
  void setRoot(TwoThreeNode<T> * node);
  bool isRoot(TwoThreeNode<T> * node);

  void insert23(T info);
  void insert23(TwoThreeNode<T> * info);
  void insert23(TwoThreeNode<T> * parent, TwoThreeNode<T> * info);
  void insert23(TwoThreeNode<T> * parent, T info);

  void printAsc(TwoThreeNode<T> * node, int level);
  void printAsc();

  void printDesc(TwoThreeNode<T> * node, int level);
  void printDesc();

  void assignRoot(TwoThreeNode<T>* root);
  bool isTwoTree ();
  bool isTwoTree(TwoThreeNode<T>* node);

  void redistributeChildren(TwoThreeNode<T>* container, TwoThreeNode<T>* node1, TwoThreeNode<T>* node2);
  void divide(TwoThreeNode<T>* container);
  bool checkTwoNode(TwoThreeNode<T>* node);
  bool checkThreeNode(TwoThreeNode<T>* node);
  bool freeChildren(TwoThreeNode<T>* node);

  TwoThreeNode<T>* searchNode(const T info, TwoThreeNode<T> * node);
  bool search23(const T info);

  TwoThreeNode<T>* findNodeToDelete(TwoThreeNode<T>*, T info);
  bool deleteNode(TwoThreeNode<T>* node);
  bool delete23(T info);
  void fix(TwoThreeNode<T>* node);
  TwoThreeNode<T>* getSucesorInorder(TwoThreeNode<T>* node);

  void getleafLevel(TwoThreeNode<T>* node);
  bool getKeysNode(TwoThreeNode<T>* node);
  bool getChildrenNode(TwoThreeNode<T>* node);
  bool findNode(TwoThreeNode<T>*, T info);

  void isLeaf() ;
  bool isLeaf(TwoThreeNode<T> * node) ;

  void ancestor(TwoThreeNode<T> * node) const;

  int getHeight() const;
  int getHeight(TwoThreeNode<T> * node) const ;

  int getDepth() const;
  int getDepth(TwoThreeNode<T> * node) const;

  int getLevel() const;
  int getLevel(TwoThreeNode<T> * node) const;

  void order(T a[], int N);

  void printHeight23(T x);
  void printDepth23(T x);
  void printLevel23(T x);
  bool hasPath(TwoThreeNode<T>*& root, vector<T>&arr, T x);

};

template <class T>
TwoThreeTree<T>::~TwoThreeTree() {
  clear();
}

template <class T>
bool TwoThreeTree<T>::empty() {
  return root == nullptr;
}

template <class T>
void TwoThreeTree<T>::clear() {
  clear(root);
}

template <class T>
void TwoThreeTree<T>::clear(TwoThreeNode<T> * node) {
  if (node) {
    clear(node->getLeft());
    clear(node->getRight());
    delete node;
  }
}

template <class T>
TwoThreeNode<T> * TwoThreeTree<T>::getRoot() const {
  return root;
}

template <class T>
void TwoThreeTree<T>::setRoot(const T info) {
  TwoThreeNode<T> * node = new TwoThreeNode<T>(info);
  setRoot(node);
}

template <class T>
void TwoThreeTree<T>::setRoot(TwoThreeNode<T> * node) {
  if (!empty()) {
    node->setLeft(root);
    root->setParent(node);
    root = node;
  }
  else {
    root = node;
  }
}

template <class T>
bool TwoThreeTree<T>::isRoot(TwoThreeNode<T> * node) {
  return node == this->root;
}

template <class T>
void TwoThreeTree<T>::insert23(T info) {
  insert23(this->root, info);
}

template <class T>
void TwoThreeTree<T>::insert23(TwoThreeNode<T> * info) {
  insert23(this->root, info);
}

template <class T>
void TwoThreeTree<T>::assignRoot(TwoThreeNode<T>* node) {
  root = node;
}

template <class T>
void TwoThreeTree<T>::redistributeChildren(TwoThreeNode<T>* container, TwoThreeNode<T>* node1, TwoThreeNode<T>* node2) {
  node1->setLeft(container->getLeft());
  node1->setRight(container->getMiddle());
  node2->setLeft(container->getTemp());
  node2->setRight(container->getRight());
  node1->getLeft()->setParent(node1);
  node1->getRight()->setParent(node1);
  node2->getLeft()->setParent(node2);
  node2->getRight()->setParent(node2);
}

template <class T>
void TwoThreeTree<T>::divide(TwoThreeNode<T>* container) {

  if(isRoot(container)) {
    TwoThreeNode<T>* newRoot = new TwoThreeNode<T>(container->getTempMiddle());
    assignRoot(newRoot);
    TwoThreeNode<T>* node1 = new TwoThreeNode<T>(container->getSmall());
    TwoThreeNode<T>* node2 = new TwoThreeNode<T>(container->getBig());
    if(container->getTemp()!=nullptr)
      redistributeChildren(container, node1, node2);
    newRoot->setLeft(node1);
    newRoot->setRight(node2);
    newRoot->getLeft()->setParent(newRoot);
    newRoot->getRight()->setParent(newRoot);
    delete container;
  }
  else if(container->getParent() != nullptr) {
    TwoThreeNode<T>* parent = container->getParent();
    if(parent->isFull()) {
      parent->setInfoMiddle(container->getTempMiddle());
      if(parent->getRight() == container) {
        TwoThreeNode<T>* node1 = new TwoThreeNode<T>(container->getSmall());
        TwoThreeNode<T>* node2 = new TwoThreeNode<T>(container->getBig());
        if(container->getTemp()!=nullptr)
          redistributeChildren(container, node1, node2);
        parent->setRight(node2);
        parent->setTemp(node1);
        parent->getRight()->setParent(parent);
        parent->getTemp()->setParent(parent);
        delete container;
      }
      else if(parent->getLeft() == container) {
        TwoThreeNode<T>* node1 = new TwoThreeNode<T>(container->getSmall());
        TwoThreeNode<T>* node2 = new TwoThreeNode<T>(container->getBig());
        if(container->getTemp()!=nullptr)
          redistributeChildren(container, node1, node2);
        parent->setLeft(node1);
        parent->setTemp(parent->getMiddle());
        parent->setMiddle(node2);
        parent->getLeft()->setParent(parent);
        parent->getMiddle()->setParent(parent);
        parent->getTemp()->setParent(parent);
        delete container;

      }
      else {
        TwoThreeNode<T>* node1 = new TwoThreeNode<T>(container->getSmall());
        TwoThreeNode<T>* node2 = new TwoThreeNode<T>(container->getBig());
        if(container->getTemp()!=nullptr)
          redistributeChildren(container, node1, node2);
        parent->setMiddle(node1);
        parent->setTemp(node2);
        parent->getMiddle()->setParent(parent);
        parent->getTemp()->setParent(parent);
        delete container;
      }
      divide(parent);
    }
    else {
      parent->setInfo(container->getTempMiddle());
      if(parent->getRight() == container)
      {
        TwoThreeNode<T>* node1 = new TwoThreeNode<T>(container->getSmall());
        TwoThreeNode<T>* node2 = new TwoThreeNode<T>(container->getBig());
        if(container->getTemp()!=nullptr)
          redistributeChildren(container, node1, node2);
        parent->setRight(node2);
        parent->setMiddle(node1);
        parent->getRight()->setParent(parent);
        parent->getMiddle()->setParent(parent);
        delete container;
      }
      else if(parent->getLeft() == container) {
        TwoThreeNode<T>* node1 = new TwoThreeNode<T>(container->getSmall());
        TwoThreeNode<T>* node2 = new TwoThreeNode<T>(container->getBig());
        if(container->getTemp()!=nullptr)
          redistributeChildren(container, node1, node2);
        parent->setLeft(node1);
        parent->setMiddle(node2);
        parent->getLeft()->setParent(parent);
        parent->getMiddle()->setParent(parent);
        delete container;
      }
      if(parent->hasThreeKeys())
        divide(parent);
    }
  }
}

template <class T>
bool TwoThreeTree<T>:: checkTwoNode(TwoThreeNode<T>* node) {
  if((node->hasLower() && !node->hasHigher()) || (!node->hasLower() && node->hasHigher()))
    return true;
  else
    return false;
}

template <class T>
bool TwoThreeTree<T>:: checkThreeNode(TwoThreeNode<T>* node) {
  if(node->hasLower() && node->hasHigher())
    return true;
  else
    return false;
}

template <class T>
bool TwoThreeTree<T>::freeChildren(TwoThreeNode<T>* node) {
  if(node->getLeft() == nullptr || node->getMiddle() == nullptr || node->getRight() == nullptr)
    return true;
  else
    return false;
}

template <class T>
void TwoThreeTree<T>::insert23(TwoThreeNode<T> * parent, T info) {
  TwoThreeNode<T>* container = new TwoThreeNode<T>();
  if(root == nullptr)
  {
    assignRoot(new TwoThreeNode<T>(info));
    return;
  }
  container = searchNode(info, root);
  if(checkTwoNode(container))
  {
    container->setInfo(info);
    container->deleteTempMiddle();
  }
  else if(checkThreeNode(container))
  {
    container->setInfoMiddle(info);
    divide(container);
  }
}

template <class T>
bool TwoThreeTree<T>::search23(const T info) {
  bool found;

  if (searchNode(info, root) != nullptr) {
    found = true;
  }
  else {
    found = false;
  }

  return found;

}

template <class T>
TwoThreeNode<T>* TwoThreeTree<T>::searchNode(const T info, TwoThreeNode<T> * node) {
  if(node == nullptr)
    return nullptr;
  if(isLeaf(node))
    return node;
  else if(checkTwoNode(node)) {
    if(info <= node->getSmall())
      return searchNode(info, node->getLeft());
    else
      return searchNode(info, node->getRight());
  }
  else if(checkThreeNode(node)) {
    if(info <= node->getSmall())
      return searchNode(info, node->getLeft());
    else if(info > node->getBig())
      return searchNode(info, node->getRight());
    else
      return searchNode(info, node->getMiddle());
  }
  return node;
}

template <class T>
void TwoThreeTree<T>::printAsc() {
  printAsc(root, 0);
  cout << "  " << endl;
}

template <class T>
void TwoThreeTree<T>::printAsc(TwoThreeNode<T> * node, int lv) {
  if(node == nullptr)
    return;
  if(isLeaf(node)) {
    if(checkTwoNode(node)) {
      cout << node->getSmall() << "  "<< flush;
    }
    else if(checkThreeNode(node)) {
      cout << node->getSmall() << "  " << node->getBig();
    }
  }
  else if(checkTwoNode(node)) {
    printAsc(node->getLeft(), lv);
    cout << node->getSmall() << "  "<< flush;
    printAsc(node->getRight(), lv);
  }
  else if(checkThreeNode(node)) {
    printAsc(node->getLeft(), lv);
    cout << node->getSmall() << "  "<< flush;
    printAsc(node->getMiddle(), lv);
    cout << node->getBig() << "  "<< flush;
    printAsc(node->getRight(), lv);
  }
}

template <class T>
void TwoThreeTree<T>::printDesc() {
  printDesc(root, 0);
  cout << "  " << endl;
}

template <class T>
void TwoThreeTree<T>::printDesc(TwoThreeNode<T> * node, int lv) {
  if(node == nullptr)
    return;
  if(isLeaf(node)) {
    if(checkTwoNode(node)) {
      cout << node->getSmall() << " "<< flush;
    }
    else if(checkThreeNode(node)) {
      cout << node->getBig() << " " << node->getSmall() << " ";
    }
  }
  else if(checkTwoNode(node)) {
    printDesc(node->getRight(), lv);
    cout << node->getSmall() << " "<< flush;
    printDesc(node->getLeft(), lv);
  }
  else if(checkThreeNode(node)) {
    printDesc(node->getRight(), lv);
    cout << node->getBig() << " "<< flush;
    printDesc(node->getMiddle(), lv);
    cout << node->getSmall() << " "<< flush;
    printDesc(node->getLeft(), lv);
  }
}


template <class T>
void TwoThreeTree<T>::fix(TwoThreeNode<T>* node) {
  if(isRoot(node)) {
    assignRoot(node->getMiddle());
    delete node;
  }
  else {
    bool threeKeys = false;
    TwoThreeNode<T>* parent = node->getParent();
    if(checkTwoNode(parent)) {
      TwoThreeNode<T>* sibiling = new TwoThreeNode<T>();
      if(parent->getRight() == node)
        sibiling = parent->getLeft();
      else
        sibiling = parent->getRight();
      if(parent->getRight() == node) {

        if(checkThreeNode(parent->getLeft())){
          threeKeys = true;
          T sibilingLower = sibiling->getSmall();
          T sibilingHigher = sibiling->getBig();
          T parentVal = parent->getSmall();
          T keys[3] = {sibilingLower,sibilingHigher,parentVal};
          order(keys,3);
          T low = keys[0];
          T mid = keys[1];
          T high = keys[2];
          node->setInfo(high);
          parent->deleteKeys();
          parent->setInfo(mid);
          sibiling->deleteKeys();
          sibiling->setInfo(low);


          if(!isLeaf(node)) {
            node->setRight(node->getMiddle());
            node->setMiddle(nullptr);
            node->setLeft(sibiling->getRight());
            node->getLeft()->setParent(node);
            sibiling->setRight(sibiling->getMiddle());
            sibiling->setMiddle(nullptr);
          }
        }
      }
      else {
        if(checkThreeNode(parent->getRight()))
        {
          threeKeys = true;
          T sibilingLower = sibiling->getSmall();
          T sibilingHigher = sibiling->getBig();
          T parentVal = parent->getSmall();
          T keys[3] = {sibilingLower,sibilingHigher,parentVal};
          order(keys,3);
          T low = keys[0];
          T mid = keys[1];
          T high = keys[2];
          node->setInfo(low);
          parent->deleteKeys();
          parent->setInfo(mid);
          sibiling->deleteKeys();
          sibiling->setInfo(high);

          if(!isLeaf(node)) {
            node->setLeft(node->getMiddle());
            node->setMiddle(nullptr);
            node->setRight(sibiling->getLeft());
            node->getRight()->setParent(node);
            sibiling->setLeft(sibiling->getMiddle());
            sibiling->setMiddle(nullptr);
          }
        }
      }
    }
    else if(checkThreeNode(parent)) {
      TwoThreeNode<T>* sibiling = new TwoThreeNode<T>();
      if(parent->getRight() == node) {
        if(checkThreeNode(parent->getMiddle())) {
          threeKeys = true;
          sibiling = parent->getMiddle();
          node->setInfo(parent->getBig());
          parent->setBig(sibiling->getBig());
          sibiling->deleteBig();
          if(!isLeaf(node)) {
            node->setRight(node->getMiddle());
            node->setLeft(sibiling->getRight());
            node->getLeft()->setParent(node);
            sibiling->setRight(sibiling->getMiddle());
            sibiling->setMiddle(nullptr);
          }
        }
      }
      else if(parent->getMiddle() == node) {
        if(checkThreeNode(parent->getLeft())) {
          threeKeys = true;
          sibiling = parent->getLeft();
          node->setInfo(parent->getSmall());
          parent->setSmall(sibiling->getBig());
          sibiling->deleteBig();
          if(!isLeaf(node)) {
            node->setRight(node->getMiddle());
            node->setLeft(sibiling->getRight());
            node->getLeft()->setParent(node);
            sibiling->setRight(sibiling->getMiddle());
            sibiling->setMiddle(nullptr);
          }
        }
      }
      else {
        if(checkThreeNode(parent->getMiddle())) {
          threeKeys = true;
          sibiling = parent->getMiddle();
          node->setInfo(parent->getSmall());
          parent->setSmall(sibiling->getSmall());
          sibiling->changeBigToSmall();
          if(!isLeaf(node)) {
            node->setLeft(node->getMiddle());
            node->setRight(sibiling->getLeft());
            node->getRight()->setParent(node);
            sibiling->setLeft(sibiling->getMiddle());
            sibiling->setMiddle(nullptr);
          }
        }
      }
    }
    if(!threeKeys) {
      TwoThreeNode<T>* sibiling = new TwoThreeNode<T>();
      if(checkTwoNode(parent)) {
        if(parent->getRight() == node) {
          sibiling = parent->getLeft();
          sibiling->setInfo(parent->getSmall());

          if(!isLeaf(node)) {
            sibiling->setMiddle(sibiling->getRight());
            sibiling->setRight(node->getMiddle());
          }
          parent->setMiddle(sibiling);
          parent->getMiddle()->setParent(parent);
          parent->setLeft(nullptr);
          parent->setRight(nullptr);
          parent->deleteKeys();
          delete node;
        }
        else {
          sibiling = parent->getRight();
          sibiling->setInfo(parent->getSmall());
          if(!isLeaf(node))
          {
            sibiling->setMiddle(sibiling->getLeft());
            sibiling->setLeft(node->getMiddle());
            sibiling->getLeft()->setParent(sibiling);
          }
          parent->setMiddle(sibiling);
          parent->getMiddle()->setParent(parent);
          parent->setLeft(nullptr);
          parent->setRight(nullptr);
          parent->deleteKeys();
          delete node;
        }
      }
      else if(checkThreeNode(parent)) {
        if(parent->getRight() == node) {
          sibiling = parent->getMiddle();
          sibiling->setInfo(parent->getBig());
          if(!isLeaf(node)) {
            sibiling->setMiddle(sibiling->getRight());
            sibiling->setRight(node->getMiddle());
            sibiling->getRight()->setParent(sibiling);
          }
          parent->setRight(sibiling);
          parent->getRight()->setParent(parent);
          parent->setMiddle(nullptr);
          parent->deleteBig();
          delete node;
        }
        else if(parent->getMiddle() == node) {
          sibiling = parent->getLeft();
          sibiling->setInfo(parent->getSmall());
          if(!isLeaf(node)) {
            sibiling->setMiddle(sibiling->getRight());
            sibiling->setRight(node->getMiddle());
            sibiling->getRight()->setParent(sibiling);
          }
          parent->setLeft(sibiling);
          parent->getLeft()->setParent(parent);
          parent->setMiddle(nullptr);
          parent->deleteSmall();
          parent->changeBigToSmall();
          delete node;
        }
        else {
          sibiling = parent->getMiddle();
          sibiling->setInfo(parent->getSmall());
          if(!isLeaf(node)) {
            sibiling->setMiddle(sibiling->getLeft());
            sibiling->setLeft(node->getMiddle());
            sibiling->getLeft()->setParent(sibiling);
          }
          parent->setLeft(sibiling);
          parent->getLeft()->setParent(parent);
          parent->setMiddle(nullptr);
          parent->deleteSmall();
          parent->changeBigToSmall();
          delete node;
        }
      }
      if(parent->noKeys()) {
        sibiling->setParent(parent);
        fix(parent);
      }
    }
  }
}

template <class T>
bool TwoThreeTree<T>::delete23(T info) {
  TwoThreeNode<T>* node = new TwoThreeNode<T>();
  node = findNodeToDelete(root, info);
  if(node) {
    TwoThreeNode<T>* leafNode = new TwoThreeNode<T>();
    if(!isLeaf(node)) {
      leafNode = getSucesorInorder(node);
      T swapVal = leafNode->getSmall();
      node->setSmall(swapVal);
    }
    else {
      if(node->getBig() == info) {
        node->deleteBig();
        return true;
      }
    }
    leafNode->deleteSmall();
    if(leafNode->noKeys()) {
      fix(leafNode);
    }
    return true;
  }
  else
    return false;
}

template <class T>
TwoThreeNode<T>* TwoThreeTree<T>::getSucesorInorder(TwoThreeNode<T>* node) {
  if (node) {
    TwoThreeNode<T> * workingNode = node->getLeft();
    if(workingNode){
      while (workingNode->getRight() != nullptr) {
        workingNode = workingNode->getRight();
      }
      return workingNode;
    }
    return nullptr;

  } else {
    return nullptr;
  }
}

template <class T>
TwoThreeNode<T>* TwoThreeTree<T>::findNodeToDelete(TwoThreeNode<T>* node, T info) {
  if(node == nullptr)
    return nullptr;
  if(isLeaf(node)) {
    if(checkTwoNode(node)) {
      if(node->getSmall() == info){
        return node;
      }
    }
    else if(checkThreeNode(node)) {
      if(node->getSmall() == info || node->getBig() == info) {
        return node;
      }
    }
    return nullptr;
  }
  else if(checkTwoNode(node)) {
    if(info == node->getSmall()) {
      return node;
    }

    if(info < node->getSmall())
      return findNodeToDelete(node->getLeft(), info);
    else
      return findNodeToDelete( node->getRight(), info);
  }
  else if(checkThreeNode(node))
{
    if(node->getSmall() == info || node->getBig() == info) {
      return node;
    }
    if(info < node->getSmall())
      return findNodeToDelete(node->getLeft(), info);
    else if(info > node->getBig())
      return findNodeToDelete(node->getRight(), info);
    else
      return findNodeToDelete(node->getMiddle(), info);
  }
  return nullptr;
}

template <class T>
bool TwoThreeTree<T>::findNode(TwoThreeNode<T>* node, T info) {
  if(node == nullptr)
    return false;
  if(isLeaf(node)) {
    if(checkTwoNode(node)) {
      if(node->getSmall() == info)
      {
        return true;
      }
    }
    else if(checkThreeNode(node)) {
      if(node->getSmall() == info || node->getBig() == info) {
        return true;
      }
    }
    return false;
  }
  else if(checkTwoNode(node)) {
    if(info == node->getSmall()) {
      return true;
    }

    if(info < node->getSmall())
      return findNode(node->getLeft(), info);
    else
      return findNode( node->getRight(), info);
  }
  else if(checkThreeNode(node)) {
    if(node->getSmall() == info || node->getBig() == info) {
      return true;
    }
    if(info < node->getSmall())
      return findNode(node->getLeft(), info);
    else if(info > node->getBig())
      return findNode(node->getRight(), info);
    else
      return findNode(node->getMiddle(), info);
  }
  return false;
}

template <class T>
bool TwoThreeTree<T>::isTwoTree() {
  return isTwoTree(root);
}

template <class T>
bool TwoThreeTree<T>::isTwoTree(TwoThreeNode<T>* node) {
  leafLevel.clear();
  getleafLevel(root);
  T cmp = leafLevel[0];
  bool leafs = true;
  for(int i=1; i<leafLevel.size(); i++) {
    if(leafLevel[i] != cmp)
      leafs = false;
  }
  return leafs;
}

template <class T>
void TwoThreeTree<T>::getleafLevel(TwoThreeNode<T>* node) {
  if(node == nullptr)
    return;
  if(isLeaf(node)) {
    leafLevel.push_back(getLevel(node));
  }
  else if(checkTwoNode(node)) {
    getleafLevel(node->getLeft());
    getleafLevel(node->getRight());
  }
  else if(checkThreeNode(node)) {
    getleafLevel(node->getLeft());
    getleafLevel(node->getMiddle());
    getleafLevel(node->getRight());
  }
}

template <class T>
void TwoThreeTree<T>::isLeaf() {
  isLeaf(root);
}

template <class T>
bool TwoThreeTree<T>::isLeaf(TwoThreeNode<T> * node) {
  if(node->getLeft() == nullptr && node->getMiddle() == nullptr && node->getRight() == nullptr)
    return true;
  else
    return false;
}

template <class T>
void TwoThreeTree<T>::ancestor(TwoThreeNode<T> * node) const {
  if (node) {
    cout << *node << " -> ";
    ancestor(node->getParent());
  }
}

template <class T>
int TwoThreeTree<T>::getHeight() const {
  return getHeight(root);
}

template <class T>
int TwoThreeTree<T>::getHeight(TwoThreeNode<T> * node) const {
  if (!node)
    return -1;
  return 1 + std::max(getHeight(node->getLeft()), getHeight(node->getRight()));
}

template <class T>
int TwoThreeTree<T>::getDepth() const {
  return getDepth(root);
}

template <class T>
int TwoThreeTree<T>::getDepth(TwoThreeNode<T> * node) const {
  if (node == nullptr) {
    return 0;
  }
  else {
    return getDepth(node->getParent())+1;
  }
}

template <class T>
int TwoThreeTree<T>::getLevel() const {
  return getLevel(root);
}

template <class T>
int TwoThreeTree<T>::getLevel(TwoThreeNode<T> * node) const {
  int level = 0;
  while (node != nullptr && node->getParent() != nullptr) {
    level++;
    node = node->getParent();
  }
  return level;
}

template <class T>
void TwoThreeTree<T>::order(T a[], int N) {

  int i, j, flag = 1;
  int temp;
  int numLength = N;
  for(i = 1; (i <= numLength) && flag; i++) {
    flag = 0;
    for (j=0; j < (numLength -1); j++) {
      if (a[j+1] < a[j]) {
        temp = a[j];
        a[j] = a[j+1];
        a[j+1] = temp;
        flag = 1;
      }
    }
  }
  return;
}

template<class T>
// HEIGHT: LONGEST PATH FROM THAT NODE TO A LEAF
bool TwoThreeTree<T>::hasPath(TwoThreeNode<T>*& root, vector<T>& arr, T x){
	if(root == NULL) return false;
	arr.push_back(x); //save the nodes value in vector
	if(x == x) return true;
	if(hasPath(root->left, arr, x) || hasPath(root->right, arr, x)) return true;
	arr.pop_back();
	return false;
}

template<class T>
void TwoThreeTree<T>::printHeight23(T x){
	TwoThreeNode<T> *y = root;
	vector<T> arr;
	int h = 1;
	cout << "Printing path: \n";
	if(hasPath(root, arr, x)){
		for(int i = 0; i < arr.size() - 1; ++i){
			cout << arr[i] << " -> ";
			h = (h + 4 * 3) * 4;
		}
		cout << arr[arr.size() - 1];
	} else
		cout << "There's no path of " << x << endl;
	cout << "\nHeight of node " << x << " is " << h << endl;
}

template<class T>
void TwoThreeTree<T>::printDepth23(T x){
	TwoThreeNode<T> *y = root;
	vector<T> arr;
	int d = 1;
	cout << "Printing path: \n";
	if(hasPath(root, arr, x)){
		for(int i = arr.size() - 1; i > 0 ; --i){
			cout << arr[i] << " -> ";
			d = (d + 4) * 5;
		}
		cout << arr[0];
	} else
		cout << "There's no path of " << x << endl;
	cout << "\nDepth of node " << x << " to root is " << d << endl;
}

template<class T>
void TwoThreeTree<T>::printLevel23(T x){
	TwoThreeNode<T> *y = root;
	vector<T> arr;
	int l = 1;
	cout << "Printing path: \n";
	if(hasPath(root, arr, x)){
		for(int i = arr.size() - 1; i > 0 ; --i){
			cout << arr[i] << " -> ";
			l = (l + 4) * 5;
		}
		cout << arr[0];
	} else
		cout << "There's no path of " << x << endl;
	cout << "\nLevel of node " << x << " is " << l + 1 << endl;
}
<file_sep>/Homework 5 - Computational Geometry/argo.cpp
#include "argo.h"
#include "ui_argo.h"

argo::argo(QWidget *parent) :
    QDialog(parent),
    ui(new Ui::argo)
{
    ui->setupUi(this);
}

argo::~argo()
{
    delete ui;
}
<file_sep>/Project 3 - Parallel vs Sequential/secuencial/sudoku.cpp
#include <iostream>
#include <vector>
#include <algorithm> // for count
#include <assert.h>
#include <time.h>
using namespace std;

// Possible values that can be entered in a cell
// Elimination
class PossibleValues{
  vector<bool> b; // Each boolean uses 1 bit, very optimal
public:
  PossibleValues(): b(9, true) {} //9 cells
  bool activeVal(int v) const   { return b[v - 1];  }
  void deleteVal(int v)            { b[v - 1] = false; }
  int numActiveVal()    const   { return count(b.begin(), b.end(), true); }  // Check how many values are on "true" (usable values)
  int valueInCell()     const   {
    // simply check if there's only one value in true, then that's the value for the cell
    // this returns an iterator to where the true value is positioned on
    vector<bool>::const_iterator it = find(b.begin(), b.end(), true);
    return 1 + (it - b.begin());
  }
  string str(int width) const;
};

// concatenate possible values
string PossibleValues::str(int width) const {
  string s(width, ' '); //this is simply for the printing part
  int j = 0;
  for(int i = 1; i <= 9; i++){
    if(activeVal(i)) s[j++] = ('0' + i);
  }
  return s;
}

class Sudoku {
  vector<PossibleValues> cells;
  // Groups (for lines, columns and subgrids) that will have to apply the rules
  // GropusOf: Which groups does a certain cell belong to
  // Neighbors: All of the cells a certain cell is related to
  static vector < vector <int> > groups, groupsOf, neighbors;
public:
  Sudoku(string s); //representation of sudoku
  static void initialize();

  PossibleValues possibleVal(int k) const { return cells[k]; } // know the possible values of k
  bool solved() const; // know if a sudoku is solved or not
  bool assign(int k, int val); // to cell k, assign value val, bool return value is to know if we have succeeded or failed
  bool deleteVal(int k, int val); // to cell k, delete value val, bool return value is to know if we have succeeded or failed
  void print(ostream& o) const;
  int lessPossibilites() const; //will return the value of the cell that has the less possibilites, when they have 2 or more possible values
};

vector < vector <int> > Sudoku::groups(27), Sudoku::groupsOf(81), Sudoku::neighbors(81);

void Sudoku::initialize() {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      const int k = i * 9 + j; //Getting the value of a cell
      const int g[3] = { i, 9 + j, 18 + (i/3)*3 + (j/3) }; // index of groups the k cell belongs to
      //filling the groups and groupsOf of a cell k
      for(int x = 0; x < 3; ++x) {
        groups[g[x]].push_back(k);
        groupsOf[k].push_back(g[x]);
      }
    }
  }

  for(int k = 0; k < 81; ++k) {
    for(int x = 0; x < 3; ++x) {
      const int g = groupsOf[k][x];
      for(int i = 0; i < 9; ++i) {
        const int k2 = groups[g][i];
        if(k2 != k) {
          neighbors[k].push_back(k2);
        }
      }
    }
  }

}

// using numActiveVal we can easily know if the sudoku has been solved or not. If, for each cell the numActiveVal = 1, then it is solved
bool Sudoku::solved() const {
  for(int k = 0; k < cells.size(); ++k){
    if(cells[k].numActiveVal() != 1){
      return false;
    }
  }
  return true;
}

bool Sudoku::assign(int k, int val) {
  //  cout << "Assign value (" << k << ", " << val << ")" << endl;
  for(int i = 1; i <= 9;  ++i) {
    if(val != i) {
      if(!deleteVal(k, i)) return false; // erase all the other values in the cell that are not the given value, if it cannot delete a value, return false --> there's an error
    }
  }
  return true;
}

bool Sudoku::deleteVal(int k, int val) {
  //cout << "Delete value (" << k << ", " << val << ")" << endl;
  if(!cells[k].activeVal(val)) {
    return true; // We can easily delete a value because it wasn't active
  }
  cells[k].deleteVal(val);

  const int N = cells[k].numActiveVal();

  if(N == 0) { // If there are 0 possible values --> error
    return false;
  } else if(N == 1) { // If there is only 1 possible values, delete the value in the neighbors
    const int v2 = cells[k].valueInCell();
    for(int i = 0; i < neighbors[i].size(); i++) {
      if(!deleteVal(neighbors[k][i], v2)) return false; // propagate the false values when something fails
    }
  }

  for(int x = 0; x < 3; x++) {
    const int g = groupsOf[k][x]; // the group we're currently analyzing
    int n = 0, k2;
    for(int i = 0; i < 9; i++) {
      const int kp = groups[g][i];
      if(cells[kp].activeVal(val)) {
        n++, k2 = kp;
      }
    }
    if(n == 0) {
      return false; // if a value has been deleted but it isn't present in any other of the neighbors, there's an error
    } else if (n == 1) { // simply assign a value if it's an onl value
      if(!assign(k2, val)) return false;
    }
  }

  return true;

}

int Sudoku::lessPossibilites() const {
  int kMin = -1, min;
  for(int k = 0; k < cells.size(); k++) {
    const int possNums = cells[k].numActiveVal();
    if(possNums > 1 && (kMin == -1 || possNums < min)) {
      min = possNums;
      kMin = k; // cell with less possibilites
    }
  }
  return kMin;
}

void Sudoku::print(ostream& o) const {
  int width = 2;
  for(int k = 0; k < cells.size(); ++k) {
    width = max(width, 1 + cells[k].numActiveVal());
  }
  string separator(3*width, '-');
  cout << endl;
  for(int i = 0; i < 9; i++) {
    if(i == 3 || i == 6) {
      cout << separator << "+-" << separator << "+-"<< separator << endl;
    }
    for(int j = 0; j < 9; j++) {
      const int k = i*9 + j;
      if(j == 3 || j == 6) {
        cout << "| ";
      }
      cout << cells[k].str(width);
    }
    cout << endl;
  }

}

Sudoku::Sudoku(string s): cells(81) { //initialize with default values
  int k = 0;
  for(int i = 0; i < s.size(); i++){
    if(s[i] >= '1' && s[i] <= '9') {
      if (!assign(k, s[i] - '0')){//reduce ASCII so we get a NUMBER
        cout << "Error trying to read the Sudoku. Check input" << endl;
        // we're checking in case we the input value doesn't follow the rules
      }
      k++;
    } else if (s[i] == '0' || s[i] == '.') {
      k++;
    }
  }
  assert(k == 81); //program will break if k != of 81
}

// This function is used to "guess" a value when there are multiple possibilites to choose from resulting in an unsolved Sudoku. It forms a "tree" os possibilites, erasing branches as soon as they aren't working
Sudoku *solve(Sudoku* S) {
  if(S == NULL || S->solved()) { // Base case, either it's solved or it's empty
    return S;
  }
  const int k = S->lessPossibilites();
  const PossibleValues pV = S->possibleVal(k);
  for(int i = 1; i <= 9; i++) {
    if(pV.activeVal(i)) {
      Sudoku *S1 = new Sudoku(*S); //Reference to a copy of a Sudoku
      if(S1->assign(k, i)) {
        Sudoku *S2 = solve(S1);
        if(S2 != NULL) {
          if(S2 != S1) delete S1; // the solution is another one, it's not S1
            return S2;
        }
      }
      delete S1; //the "tree" branch is not this one; erease it completely
    }
  }
  return NULL;
}

int main() {
  clock_t startTimer, endTimer;

  Sudoku::initialize();
  string s, line;
  while(getline(cin, line)) s += line; //reading from a file

  startTimer = clock();
  Sudoku *S = solve(new Sudoku(s));
  endTimer = clock();

  S->print(cout);

  double timeTaken = (double)(endTimer - startTimer)/(double)(CLOCKS_PER_SEC);
  cout << "\nTime taken by program is : " << timeTaken << " seconds\n";
}
<file_sep>/Homework 5 - Computational Geometry/prismarec.cpp
#include "prismarec.h"
#include "ui_prismarec.h"
#include <math.h>
#include <QMessageBox>

prismarec::prismarec(QWidget *parent):QDialog(parent), ui(new Ui::prismarec) {
    this->setFixedSize(521, 333); //Size of window
    ui->setupUi(this);
    xCentro = 345.0; // values so the first drawn figure is centered
    yCentro = 170.0;
    QTransform center;
    center.translate(xCentro,yCentro);
    vecTrans.push_back(center);
}

prismarec::~prismarec() {
    delete ui;
}


void prismarec::paintEvent(QPaintEvent *e) {
    QPainter painter(this);
    QPen pointPen(Qt::black);
    pointPen.setWidth(2);
    painter.setPen(pointPen);
    if (dibuja){
        for(int i=0; i<vecTrans.size(); ++i){
            painter.setTransform(vecTrans[i],true);
            drawPrismarec(painter);
        }
    }
}

void prismarec::drawPrismarec(QPainter &painter){
     //Base
     painter.drawLine(0,50,30,0);
     painter.drawLine(30,0,80,0);
     painter.drawLine(30,-150,30,0);
     painter.drawLine(50,50,80,0);

     // "Height"
     painter.drawLine(0,-100, 30,-150);
     painter.drawLine(50,-100, 80,-150);
     painter.drawLine(0, 50, 50, 50);
     painter.drawLine(0,-100, 50, -100);
     painter.drawLine(0, -100, 0, 50);
     painter.drawLine(50,-100, 50, 50);
     painter.drawLine(30,-150, 80,-150);
     painter.drawLine(80,-150, 80, 0);
}

void prismarec::on_dibujar_clicked() {
    vecTrans.clear();
    QTransform centro;
    centro.translate(xCentro,yCentro);
    vecTrans.push_back(centro);
    dibuja = !dibuja;
    update();
}

void prismarec::on_trasladar_clicked() {
    QString x = ui->boxXinicio->toPlainText();
    QString y = ui->boxYinicio->toPlainText();
     if(!x.isEmpty() && !y.isEmpty()) {
       int xS = x.toInt();
       int yS = y.toInt();
       QTransform t;
       t.translate(xS, yS);
       vecTrans.push_back(t);
     } else {
       QMessageBox msgBox;
       msgBox.setText("Please type in the values for x and y");
       msgBox.exec();
     }
     update();
}

void prismarec::on_zoom_in_clicked() {
    QTransform zIn;
    zIn.scale(2,2);
    vecTrans.push_back(zIn);
    update();
}

void prismarec::on_zoom_out_clicked() {
    QTransform zOut;
    zOut.scale(0.5,0.5);
    vecTrans.push_back(zOut);
    update();
}

void prismarec::on_rotar_clicked() {
    QString r = ui->boxGrados->toPlainText();
      if(!r.isEmpty()) {
        int rS = r.toInt();
        QTransform r;
        r.rotate(rS);
        vecTrans.push_back(r);
      } else {
        QMessageBox msgBox;
        msgBox.setText("Please type in the degree for rotation");
        msgBox.exec();
      }
    update();
}

void prismarec::on_vertical_clicked() {
    QTransform rv;
    rv.scale(1,-1);
    vecTrans.push_back(rv);
    update();
}

void prismarec::on_horizontal_clicked() {
    QTransform rh;
    rh.scale(-1,1);
    vecTrans.push_back(rh);
    update();
}
<file_sep>/Homework 5 - Computational Geometry/poligonos.cpp
#include "poligonos.h"
#include "ui_poligonos.h"
#include <QMessageBox>
#include <math.h>

Poligonos::Poligonos(QWidget *parent): QDialog(parent), ui(new Ui::Poligonos) {
    this->setFixedSize(521, 333); //Size of window
    ui->setupUi(this);
    xCentro = 345.0; // values so the first drawn figure is centered
    yCentro = 170.0;
    QTransform centro;
    centro.translate(xCentro,yCentro);
    vecTrans.push_back(centro);
}

Poligonos::~Poligonos() {
    delete ui;
}

void dibujarPoligono(int lados, QPainter & painter) {

    double radio = 100;
    double angulo = (double)360.0/(double)lados;

    int xi,yi,xf,yf;
    double val = M_PI / 180;
    angulo *= val;
    int a = 0;

    for(a = 1; a <= lados; a++) {
        xi = (radio * cos(angulo*a));
        yi = (radio * sin(angulo*a));

        xf = (radio * cos(angulo*(a+1)));
        yf = (radio * sin(angulo*(a+1)));

        painter.drawLine(xi, yi, xf, yf);
    }

}

void Poligonos::paintEvent(QPaintEvent *event) {
    QPainter painter(this);
    QPen pointPen(Qt::black);
    pointPen.setWidth(2);
    painter.setPen(pointPen);

    if (dibuja) {

        QString ladosStr = ui->boxXfin->toPlainText();

        if (!ladosStr.isEmpty()) {
            int lados = ladosStr.toInt();
            for(int i=0; i<vecTrans.size(); ++i) {
                painter.setTransform(vecTrans[i],true);
                dibujarPoligono(lados, painter);
            }
        }
    }
}

//Buttons...

void Poligonos::on_dibujar_clicked() {
    trans.dibujar(dibuja,vecTrans,xCentro,yCentro);
    update();
}

void Poligonos::on_trasladar_clicked() {
    QString xStr = ui->boxXinicio->toPlainText();
    QString yStr = ui->boxYinicio->toPlainText();
    QString x = ui->boxXinicio->toPlainText();
    QString y = ui->boxYinicio->toPlainText();
    if(!x.isEmpty() && !y.isEmpty()) {
       trans.trasladar(x, y, vecTrans);
       update();
    } else {
       QMessageBox msgBox;
       msgBox.setText("Please type in the values for x and y");
       msgBox.exec();
    }
}

void Poligonos::on_rotar_clicked() {
    QString gradosStr = ui->boxGrados->toPlainText();
    if(!gradosStr.isEmpty()) {
        trans.rotar(gradosStr, vecTrans);
        update();
    } else {
        QMessageBox msgBox;
        msgBox.setText("Please type in the degree for rotation");
        msgBox.exec();
    }
}

void Poligonos::on_zoom_out_clicked() {
    trans.zoomOut(vecTrans);
    update();
}

void Poligonos::on_zoom_in_clicked() {
    trans.zoomIn(vecTrans);
    update();
}

void Poligonos::on_horizontal_clicked() {
    trans.reflexHorizontal(vecTrans);
    update();
}

void Poligonos::on_vertical_clicked() {
    trans.reflexVertical(vecTrans);
    update();
}
<file_sep>/Exercises/Dynamic Programming/main.cpp
#include <iostream>
#include <chrono>
using namespace std;

int FibIterativo(int n){
  int suma, x, y;
  if(n <= 1)
    return 1;
  else {
    x = 1;
    y = 1;
    for(int i = 2; i < n; ++i){
      suma = x + y;
      y = x;
      x = suma;
    }
    return suma;
  }
}

int Fib(int n){
  if(n == 0 || n == 1){
    return 1;
  }
  else {
    return Fib(n - 1) + Fib(n - 2);
  }
  return -1;
}

int main(){
  int n, technique, answer;
  clock_t start, end;
  cout << "Input the value to calculate\n";
    cin >> n;
  cout << "1. Recursive Fibonacci\n2. Iterative Fibonacci\n";
    cin >> technique;

  switch(technique){
    case 1:
      {
        auto start = chrono::steady_clock::now();
        answer = Fib(n);
        auto end = chrono::steady_clock::now();
        cout << "Time taken by Recursive Fibonacci of " << n << " is \t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
        cout << "Fibonacci of: " << answer << endl;
      }
      break;
    case 2:
      {
        auto start = chrono::steady_clock::now();
        answer = FibIterativo(n);
        auto end = chrono::steady_clock::now();
        cout << "Time taken by Iterative Fibonacci of " << n << " is \t" << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms\n" << endl;
        cout << "Fibonacci of: " << answer << endl;
      }
      break;
  }
  return 0;
}
<file_sep>/Homework 5 - Computational Geometry/cubo.cpp
#include "cubo.h"
#include "ui_cubo.h"
#include <QPainter>
#include <QMessageBox>
#include <math.h>

cubo::cubo(QWidget *parent):QDialog(parent), ui(new Ui::cubo) {
    this->setFixedSize(521, 333); //Size of window
    ui->setupUi(this);
    xCentro = 345.0; // values so the first drawn figure is centered
    yCentro = 170.0;
    QTransform center;
    center.translate(xCentro,yCentro);
    vecTrans.push_back(center);
}

cubo::~cubo()
{
    delete ui;
}

void cubo::paintEvent(QPaintEvent *e){
    QPainter painter(this);
    QPen pointPen(Qt::black);
    pointPen.setWidth(2);
    painter.setPen(pointPen);
    if (dibuja){
        for(int i=0; i<vecTrans.size(); ++i){
            painter.setTransform(vecTrans[i],true);
            drawCubo(painter);
        }
    }
}

void cubo::drawCubo(QPainter &painter){
        painter.drawLine(-40, 40, 40, 40);
        painter.drawLine(-40, 40, -40, -40);
        painter.drawLine(40, 40, 40, -40);
        painter.drawLine(-40, -40, 40, -40);
        painter.drawLine(0, 0, 80, 0);
        painter.drawLine(0, 0, 0, -80);
        painter.drawLine(80, 0, 80, -80);
        painter.drawLine(0, -80, 80, -80);
        painter.drawLine(-40, 40, 0, 0);
        painter.drawLine(40, 40, 80, 0);
        painter.drawLine(-40, -40, 0, -80);
        painter.drawLine(40, -40, 80, -80);
}


void cubo::on_dibujar_clicked() {
    vecTrans.clear();
    QTransform centro;
    centro.translate(xCentro,yCentro);
    vecTrans.push_back(centro);
    dibuja = !dibuja;
    update();
}

void cubo::on_trasladar_clicked() {
    QString x = ui->boxXinicio->toPlainText();
    QString y = ui->boxYinicio->toPlainText();
     if(!x.isEmpty() && !y.isEmpty()) {
       int xS = x.toInt();
       int yS = y.toInt();
       QTransform t;
       t.translate(xS, yS);
       vecTrans.push_back(t);
     } else {
       QMessageBox msgBox;
       msgBox.setText("Please type in the values for x and y");
       msgBox.exec();
     }
     update();
}

void cubo::on_zoom_out_clicked() {
    QTransform zIn;
    zIn.scale(2,2);
    vecTrans.push_back(zIn);
    update();
}


void cubo::on_zoom_in_clicked() {
    QTransform zOut;
    zOut.scale(0.5,0.5);
    vecTrans.push_back(zOut);
    update();
}

void cubo::on_rotar_clicked() {
    QString r = ui->boxGrados->toPlainText();
      if(!r.isEmpty()) {
        int rS = r.toInt();
        QTransform r;
        r.rotate(rS);
        vecTrans.push_back(r);
      } else {
        QMessageBox msgBox;
        msgBox.setText("Please type in the degree for rotation");
        msgBox.exec();
      }
    update();
}

void cubo::on_vertical_clicked() {
    QTransform rv;
    rv.scale(1,-1);
    vecTrans.push_back(rv);
    update();
}

void cubo::on_horizontal_clicked() {
    QTransform rh;
    rh.scale(-1,1);
    vecTrans.push_back(rh);
    update();
}
<file_sep>/Homework 5 - Computational Geometry/prismatri.h
#ifndef PRISMATRI_H
#define PRISMATRI_H

#include <QDialog>
#include <QtGui>
#include <QtCore>
namespace Ui {
class PrismaTri;
}

class PrismaTri : public QDialog
{
    Q_OBJECT

public:
    explicit PrismaTri(QWidget *parent = 0);
    ~PrismaTri();

protected:
     void paintEvent(QPaintEvent *e);
     void drawPrismaTri(QPainter &painter);


private slots:
     void on_dibujar_clicked();
     void on_trasladar_clicked();
     void on_rotar_clicked();
     void on_zoom_in_clicked();
     void on_zoom_out_clicked();
     void on_horizontal_clicked();
     void on_vertical_clicked();

private:
    Ui::PrismaTri *ui;
    bool dibuja = false;

    double xCentro;
    double yCentro;

    QVector<QTransform> vecTrans;
};

#endif // PRISMATRI_H
<file_sep>/Project 1 - Balanced Trees/RBTNode.h
//RBTNode.h
enum RBTColor { Black, Red };

template<class KeyType>
struct  RBTNode
{
	KeyType key;
	RBTColor color;
	RBTNode<KeyType> * left;
	RBTNode<KeyType> * right;
	RBTNode<KeyType> * parent;
	RBTNode(KeyType k, RBTColor c, RBTNode* p, RBTNode*l, RBTNode*r) :
		key(k), color(c), parent(p), left(l), right(r) { };
};
<file_sep>/Homework 5 - Computational Geometry/dialog.h
#ifndef DIALOG_H
#define DIALOG_H

#include <QDialog>
#include "poligonos.h"
#include "arcos.h"
#include "cubo.h"
#include "cono.h"
#include "prismarec.h"
#include "prismatri.h"


namespace Ui {
class Dialog;
}

class Dialog : public QDialog
{
    Q_OBJECT

public:
    explicit Dialog(QWidget *parent = 0);
    ~Dialog();

private slots:
    void on_poligono_clicked();
    void on_arco_clicked();
    void on_cubo_clicked();
    void on_cono_clicked();
    void on_prismarec_clicked();
    void on_prismatri_clicked();
private:
    Ui::Dialog *ui;
};

#endif
<file_sep>/Homework 4 - Graph Processing/main.c.cpp
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <ctime>
#include <chrono>

using namespace std;
typedef PNGraph DGraph;

void GraphML(DGraph graph) {
	ofstream file ("wiki_vote.graphml");
	if (file.is_open()) {
		file << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n";
		file << "<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd\">\n";
		file << "<graph id=\"G\" edgedefault=\"directed\">\n";

		for (DGraph::TObj::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++)
			file << "<node id=\"" << NI.GetId() << "\"/>\n";

		int i = 1;
		for (DGraph::TObj::TEdgeI EI = graph->BegEI(); EI < graph->EndEI(); EI++, ++i)
			file << "<edge id=\"e" << i << "\" source=\"" << EI.GetSrcNId() << "\" target=\"" << EI.GetDstNId() << "\"/>\n";

		file << "</graph>\n";
		file << "</graphml>\n";
		file.close();
	}
}

void GEXF(DGraph graph) {
	ofstream file ("wiki_vote.gexf");
	if (file.is_open()) {
		file << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n";
		file << "<gexf xmlns=\"http://www.gexf.net/1.2draft\" version=\"1.2\">\n";
		file << "<graph mode=\"static\" defaultedgetype=\"directed\">\n";

		file << "<nodes>\n";
		for (DGraph::TObj::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++)
			file << "<node id=\"" << NI.GetId() << "\" />\n";
		file << "</nodes>\n";

		file << "<edges>\n";
		int i = 1;
		for (DGraph::TObj::TEdgeI EI = graph->BegEI(); EI < graph->EndEI(); EI++, ++i)
			file << "<edge id=\"" << i << "\" source=\"" << EI.GetSrcNId() << "\" target=\"" << EI.GetDstNId() << "\" />\n";
		file << "</edges>\n";

		file << "</graph>\n";
		file << "</gexf>\n";
		file.close();
	}
}

void GDF(DGraph graph) {
	ofstream file ("wiki_vote.gdf");
	if (file.is_open()) {
		file << "nodedef>id VARCHAR\n";
		for (DGraph::TObj::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++)
			file << NI.GetId() << "\n";

		file << "edgedef>source VARCHAR, destination VARCHAR\n";
		for (DGraph::TObj::TEdgeI EI = graph->BegEI(); EI < graph->EndEI(); EI++)
			file << EI.GetSrcNId() << ", " << EI.GetDstNId() << "\n";

		file.close();
	}
}

void JSON(DGraph graph) {
  ofstream file ("wiki_vote.json");
	if (file.is_open()) {
		file << "{ \"graph\": {\n";
		file << "\"nodes\": [\n";
		for (DGraph::TObj::TNodeI NI = graph->BegNI(); NI < graph->EndNI();) {
			file << "{ \"id\": \"" << NI.GetId() << "\" }";
			if (NI++ == graph->EndNI())
				file << " ],\n";
			else
				file << ",\n";
		}

		file << "\"edges\": [\n";
		for (DGraph::TObj::TEdgeI EI = graph->BegEI(); EI < graph->EndEI();) {
			file << "{ \"source\": \"" << EI.GetSrcNId() << "\", \"target\": \"" << EI.GetDstNId() << "\" }";
			if (EI++ == graph->EndEI())
				file << " ]\n";
			else
				file << ",\n";
		}
		file << "} }";
		file.close();
	}
}

int main() {
	DGraph graph = TSnap::LoadEdgeList<DGraph>("wiki-Vote.txt",0,1);

	cout << "\nThe Wiki-Vote dataset has been imported succesfully\nExporting...\n" << endl;
	cout << "Format\tExecution Time (ms)" << endl;
	for(int i = 0; i < 4; ++i) {
		switch(i){
			case 0:
			{
				auto start = chrono::steady_clock::now();
				GraphML(graph);
				auto end = chrono::steady_clock::now();
				cout << "GraphML\t     " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
			}
			break;
			case 1:
			{
				auto start = chrono::steady_clock::now();
				GEXF(graph);
				auto end = chrono::steady_clock::now();
				cout << "GEFX\t     " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
			}
			break;
			case 2:
			{
				auto start = chrono::steady_clock::now();
				GDF(graph);
				auto end = chrono::steady_clock::now();
				cout << "GDF\t     " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
			}
			break;
			case 3:
			{
				auto start = chrono::steady_clock::now();
				JSON(graph);
				auto end = chrono::steady_clock::now();
				cout << "JSON\t     " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
			}
			break;
		}
	}
	return 0;
}
<file_sep>/Homework 3 - Algorithm Design Techniques/driverTruck.cpp
/*
  <NAME>
  A01021698
  Exercise 1: Driver truck
  Technique: Greedy algorithm
    It makes a greedy choice when filling up the tank at the farthest reachable gas station
  Complexity: O(n) because there's only one for loop going through the n distances of the gas stations
*/
#include <iostream>
using namespace std;

int main() {
  int tank = 95, distanceTravelled = 0, refill = 0, n = 6;
  int gasStation [n]= {58, 49, 25, 78, 94, 76};

  cout << "\nCDMX                              Acapulco" << endl;
  cout << "|-----|-----|-----|-----|-----|-----|" << endl;
  cout << "0----58----107---132---210---304---380   km\n\n";

  cout << "Tank capacity: " << tank << endl << endl;
  int usedGas = tank;
  for(int i = 0; i <= n - 1; ++i){
      usedGas -= gasStation[i];
      distanceTravelled += gasStation[i];
      if(usedGas < gasStation[i + 1]){
          cout << "Stopping at gas station located at km " << distanceTravelled << endl;
          usedGas = tank;
          refill++;
      }
  }
  cout << "\nThe driver must stop to refill " << refill << " times"<< endl;
  refill = 0;
  return 0;
}
<file_sep>/Homework 5 - Computational Geometry/argo.h
#ifndef ARGO_H
#define ARGO_H

#include <QDialog>

namespace Ui {
class argo;
}

class argo : public QDialog
{
    Q_OBJECT

public:
    explicit argo(QWidget *parent = nullptr);
    ~argo();

private:
    Ui::argo *ui;
};

#endif // ARGO_H
<file_sep>/Project 2 - Graphs Algorithms/README.md
Busque en Internet las bibliotecas para la implementación de grafos (Boost Graph Library y SNAP) e implemente un programa que haciendo uso de cada biblioteca permita:
Insertar vértices en el grafo
Insertar arista en el grafo
Eliminar vértices del grafo
Eliminar aristas del grafo
Realizar un recorrido en profundidad (DFS)
Realizar un recorrido en amplitud (BFS)
Obtener el árbol de recubrimiento mínimo correspondiente utilizando el algoritmo de Prim
Obtener el árbol de recubrimiento mínimo correspondiente utilizando el algoritmo de Kruskal
Determinar la ruta mínima para llegar de un vértice origen a todos los demás vértices del grafo (Dijkstra)
Determinar la ruta mínima para llegar de cualquier vértice origen a todos los demás vértices del grafo (Floyd-Warshall)

Posteriormente modele en cada programa el grafo que aparece a continuación y mida los tiempos de ejecución de la implementación de cada algoritmo (de los anteriores) utilizando cada una de las bibliotecas tanto en su laptop como en una RPi. Para cada uno de los algoritmos utilizados, analice su complejidad temporal y espacial.

Finalmente, genere un reporte como resultado de la investigación donde analice los resultados obtenidos y en caso de haber diferencias entre los tiempos de ejecución utilizando una biblioteca u otra, realice una reflexión personal donde mencione con sus palabras cuáles son los factores  que ocasionan dichas diferencias de tiempo.

Como parte de la respuesta de este ejercicio debe incluir en el  reporte de investigación, lo siguiente:
Tabla con los tiempos de ejecución de cada algoritmo utilizado de cada biblioteca, tanto en la RPi como en la laptop / escritorio.
Para cada algoritmo, una gráfica comparativa con sus tiempos de ejecución en la RPi y en la laptop / escritorio para cada biblioteca.
Análisis e interpretación de los resultados (con sus palabras).
