CST

---

Students learn important data structures in computer science and acquire fundamental algorithm design techniques to get the efficient solutions to several computing problems from various disciplines. Topics include the analysis of algorithm efficiency, hash, heap, graph, tree, sorting and searching, brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, dynamic programming, and greedy programming.

---

Prerequisite(s)/Corequisite(s): (Prereq: CST 238 and MATH 170 with a C- or better)
Typically Offered: Fall, Spring
Units: 4

---

/*
    * Title: main_hw5_1.cpp
    * Abstract: Write a C++ (or Java) program for hw5_1 to conduct heap operations. 
    The commands include “displayMax”( display root node if its a maxheap), “insert” (= insert a number to the heap and do the “heapify” to
adjust the heap), “deleteMax”( delete root node if its max heap, and then heapify to adjust), and “display” (= display all nodes in the heap on the screen).
    * Name: Ethan Bonavida
    * Date: 02-10-24  
    */

#include <iostream>
#include <string>
#include <vector>
using std::cout;
using std::cin;
using std::endl;

bool HeapIsHeap(std::vector<int>);
void Heapify(std::vector<int>&); // adjust the heap to a maxx heap based of given values
void Insert(int, std::vector<int>&);
void DeleteMax(std::vector<int>&); // max should just be the root node right?
void DisplayMax(int); // the heap should have root as max, just pass that.
void Display(std::vector<int>);

int main()
{

    int count_heap = 0, count_cmds = 0;    

    // get user input for heap
    cin >> count_heap;
    std::vector<int> user_heap(1,-1);

    for (int i = 0; i < count_heap; i++) {
        int temp_num = 0;
        cin >> temp_num;
        user_heap.push_back(temp_num);
    }

    // get user input for commands
    cin >> count_cmds;
    cin.ignore();
    std::vector<std::string> user_cmds(count_cmds);
    for (auto& it : user_cmds) {
        std::getline(cin, it);
    }

    // with input, first check if it is a heap?
    if (HeapIsHeap(user_heap)) {
        cout << "This is a heap." << endl;
    }
    else {
        cout << "This is NOT a heap." << endl;
    }

    // with input, heapify, make a max heap
    Heapify(user_heap);

    // now go through commands.
    for (std::string command : user_cmds) {        
        int insertion = -1;
        if (command.substr(0,1).compare("i") == 0) { // if its an insert, split
            insertion = std::stoi(command.substr(7, command.size() - 1)); // hopefully from the space to the end
            command = command.substr(0,6); // grab the insert            
        }

        if (command.compare("display") == 0) {
            Display(user_heap);
        }
        else if (command.compare("insert") == 0) { // hopefully split off from before, and insertion is correct value.
            Insert(insertion, user_heap);
        }
        else if (command.compare("displayMax") == 0) {
            DisplayMax(user_heap[1]); // root node is max, since its a heap
        }
        else if (command.compare("deleteMax") == 0) {
            DeleteMax(user_heap);
        }
        else {
            //something went wrong but do nothing?
        }
    }

    return 0;
}

// this should work for all cases?
bool HeapIsHeap(std::vector<int> _heap) {

    // if not heap
    for (int index = 1; 2 * index < _heap.size(); ) {
        // account for out loop.. 
        // if the number is bigger, than continue on looping through the heap
        if ( _heap[index] < _heap[2*index]) {
            return false;
        }
        else if (2 * index + 1 >= _heap.size()) { break; } // if there is only one child, account for it then break.
        else if ( _heap[index] < _heap[(2 * index) + 1]) {
            return false;
        }
        else {
            index++;
        }
    }
    // else, it is heap
    return true; 
}

void Heapify(std::vector<int>& _heap) {
    // algorithm for checking and creating a heap
    bool is_heap = false;
    int n = _heap.size()-1;

    for (int index =  n / 2; index >= 1; index--) {
        int key = index; int parent = _heap[key];
        is_heap = false;
        while (!is_heap && (2 * key) <= n) {
            int child_element = 2 * key;
            if (child_element < n) { // two children
                if (_heap[child_element] < _heap[child_element + 1]) { // get the biggest child value
                    child_element++;
                    }
            }
            if (parent >= _heap[child_element]) {
                is_heap = true; // the valid state of a max heap
            }
            else { // if its not a heap, swap the values to make it a heap.
                _heap[key] = _heap[child_element];
                key = child_element;
                _heap[key] = parent;
            }
        }

    }
}


void Insert(int _insertion, std::vector<int>& _heap) {
    // pushback the value
    _heap.push_back(_insertion);
    // heapify with new vector
    Heapify(_heap);
}

void DisplayMax(int max) {
    cout << max << endl; // just display the max and new line
}

void Display(std::vector<int> _heap) {
    std::string output = "";
    for (auto& it : _heap) {
        output += std::to_string(it);
        output += " ";
    }
    output = output.substr(3, output.size()-4); // ?
    cout << output << endl;
}

void DeleteMax( std::vector<int>& _heap) {
    // swap the root and last node. delete last node then heapify?
    _heap[1] = _heap[_heap.size() - 1];

    // delete last node
    _heap.pop_back();

    // heapify with new vector?
    Heapify(_heap);
}
                                    

/*
    * Title: main_hw5_3.cpp
    * Abstract: 3. Write a C++ (or Java) program for hw5_3 to simulate the operations of linear probing covered in the
lecture. For the sample operation, watch https://youtu.be/yAaUTDuiaqY
    * Name: Ethan Bonavida
    * Date: 02-13-24
    * references: ChatGPT (efficient prime algorithm)
    * https://codereview.stackexchange.com/questions/71212/find-smallest-prime-number-greater-than-given-n
    */

#include <iostream>
#include<string>
#include<vector>
using std::cout;
using std::cin;
using std::endl;

void Insert(int, std::vector<int>&, double&);
void TableSize(std::vector<int>);
int FindPrime(int);
bool IsPrime(int);

// GLOBALS
const double G_LOAD_FACTOR = 0.5;
const short int G_EMPTY_ENTRY = -1;

int main()
{

    int count_hash = 0, count_cmds = 0;
    double load_factor = 0.0;

    // get user input for hash table
    cin >> count_hash;
    std::vector<int> hash_table(count_hash, G_EMPTY_ENTRY); // initialize table with -1, no value


    // get user input for commands
    cin >> count_cmds;
    cin.ignore();
    std::vector<std::string> user_cmds(count_cmds);
    for (auto& it : user_cmds) {
        std::getline(cin, it);
    }

    // now go through commands.
    for (std::string command : user_cmds) {
        int insertion = -1;
        int searching = -1;
        int status = -1;
        if (command.substr(0, 1).compare("i") == 0) { // if its an insert, split
            insertion = std::stoi(command.substr(7, command.size() - 1)); // hopefully from the space to the end              
            Insert(insertion, hash_table, load_factor);
        }
        else if (command.substr(0, 1).compare("s") == 0) {
            searching = std::stoi(command.substr(7, command.size() - 1)); // grab the number from the space to the end
            //Search(searching, hash_table); // search for this key value from the table ( the index?)
            cout << searching << " ";
            bool search_found = false;
            for (int index = 0; index < hash_table.size(); index++) {
                if (hash_table[index] == searching) { // when found, mark true and break out.
                    search_found = true; 
                    break; 
                }
            }
            search_found ? cout << "Found" : cout << "Not found";
            cout << endl;
        }
        else if (command.substr(0, 1).compare("d") == 0) {
            status = std::stoi(command.substr(14, command.size() - 1)); // grab the number from the space to the end
            hash_table[status] == G_EMPTY_ENTRY ? cout << "Empty" : cout << hash_table[status];
            cout << endl;
            //cout << "Status: " << status << endl;
        }
        else if (command.compare("tableSize") == 0) {
            cout << hash_table.size() << endl;
        }
        else {
            //something went wrong but do nothing?
        }
    }

    return 0;
}

bool IsPrime(int _number) {
    // if divisible by the first important primes, then false
    if (_number % 2 == 0 || _number % 3 == 0 || _number % 5 == 0 ) {
        return false;
    }

    for (int i = 5; i * i <= _number; i += 6) {
        if (_number % i == 0 || _number % (i + 2) == 0) {
            return false;
        }
    }
    // if all else, then must be prime
    return true;
}

int FindPrime(int number) {
    bool found = false;

    while (!found) {
        number++;
        if (IsPrime(number)) {
            found = true;
        }
    }
    return number;
}

void Insert(int _insertion, std::vector<int>& _hash_table, double& _load_factor) {

    int key_size = _hash_table.size(); // original size
    int key_index = 0; // size is the has function key
    bool inserted = false;

    // increase load factor first to check if it overflows
    _load_factor += (1.0 / key_size);

    // maybe need to check load factor first. if this next insert goes over, need to rehashify
    if (_load_factor > G_LOAD_FACTOR) {
        // double the size, find nearest prime
        int prime_size = FindPrime((key_size * 2));
        std::vector<int> temp_hash_table(prime_size, G_EMPTY_ENTRY);
        int new_key_size = prime_size;
        _load_factor = 0.0; // reset the load factor
        // now go through and rehash
        for (int hash_index = 0; hash_index < key_size; hash_index++) {
            // when it is a valid number, rehash it with new size and new key
            if (_hash_table.at(hash_index) != G_EMPTY_ENTRY) {
                // create new key index based off new size
                key_index = _hash_table.at(hash_index) % new_key_size;
                // in new table, copy the value at this index, to the new index
                temp_hash_table.at(key_index) = _hash_table.at(hash_index);
                _load_factor += (1.0/ new_key_size);
            }
        }
        // new key size after rehashify
        key_size = new_key_size;      
        // copy over new table
        _hash_table = temp_hash_table;
    }
    // set key_index
    key_index = _insertion % key_size;

    while (!inserted) {
        if (_hash_table.at(key_index) == G_EMPTY_ENTRY) { // when the key index is null, or -1, insert the new value. otherwise, linear probe
            _hash_table.at(key_index) = _insertion;            
            inserted = true; // inserted something, so just leave?
            break; // or break?
        }
        else { // linear probe
            if (key_index < key_size) {
                key_index++; // increase the key
            }
            else {
                key_index = 0; // cycle back when its greater than the size;
            }
        }
    }
}