Download Notebook

Homework 5¶

Due Tuesday, November 10th 2020 at 11:59 PM.¶

Problem 0 (C++). Homework Workflow [10 pts]

Problem 1 (C++). Templated Linked List [40 pts]

Problem 2 (C++). Templated Binary Search Tree [50 pts]

Follow the Problem 2 instructions. Implement a templated Binary Search Tree based off of the Problem 1 Linked List template.

We will be using an autograder for this homework. Please don't change the specified function signature.

Problem 0: Homework Workflow¶

Once you receive HW4 feedback, you will need to merge your HW4-dev branch into master.

You will earn points for following all stages of the git workflow which involves:

3pts for merging HW4-dev into master
5pts for completing HW5 on HW5-dev
2pts for making a PR on HW5-dev to merge into master

Problem 1: Linked List¶

A singly linked list can be implemented by nodes. Each node has 2 properties: a head and a tail. The head is the element held by the first node in the list. The tail is the rest of the list, which is a reference to the next node.

The code provided in linked_list.hpp is a partially implemented singly linked list. It consists of one class: LinkedList is a node that holds an element. In this problem, you will finish the implementation of this class. To name a node LinkedList is a bit confusing, but as we will see, although the LinkedList is implemented as a node, it behaves as if it is a whole list.

Start by copying the template code linked_list.hpp. For this exercise, you will implement all the sections with comments:

#ifndef LINKED_LIST_HPP
#define LINKED_LIST_HPP

/* system header files */
#include <iostream>

/* namespace */
using namespace std;

/* ========================== */
/* Templated Class Definition */
/* ========================== */
template <class T>
class LinkedList {
  private:
      T data;
      LinkedList *next;

  public:
    /* Constructor */
    LinkedList(T data, LinkedList *next){
        //TODO: assign data
        //TODO: assign next
    }

    /* getters */
    T getData(){//TODO}
    LinkedList* getNext(){//TODO}

    /* setters */
    void setData(T data){//TODO}
    void setNext(LinkedList *next){//TODO}

    /* member functions */
    void prepend(LinkedList **head_ref, T new_data);
    void append(LinkedList **head_ref, T new_data);
    T summation();
    T minimum();
    template <typename FUNC> LinkedList* forEach(FUNC f);
    template <typename FUNC> LinkedList* reduceRight(FUNC f);
    void printList();
};


/* -------------------------------------------------------------------------- */
/* Class LinkedList<T> Member Function Implementations:                       */
/* NOTE: Putting implementation inside header file for templated classes.     */
/*      See why: https://isocpp.org/wiki/faq/templates#templates-defn-vs-decl */
/* -------------------------------------------------------------------------- */

/* =============================================== */
/* LinkedList<T>::prepend                          */
/*    Inserts a new node on the front of the list. */
/* =============================================== */
template <class T>
void LinkedList<T>::prepend(LinkedList **head_ref, T new_data){
    /* 1. allocate node */
    //TODO

    /* 2. move the head to point to the new node */
    //TODO
}

/* ============================================= */
/* LinkedList<T>::append                         */
/*    Inserts a new node at the end of the list. */
/* ============================================= */
template <class T>
void LinkedList<T>::append(LinkedList **head_ref, T new_data){
    /* 1. allocate node */
    //TODO

    /* 2. save head_ref for step 4 */
    //TODO

    /* 3. If the Linked List is empty, then make the new node as head */
    //TODO

    /* 4. Else traverse until the last node */
    //TODO

    /* 5. Change the next of last node */
    //TODO

    return;
}

/* ============================================= */
/* LinkedList<T>::summation                      */
/*    Computes summation of data in linked list. */
/* ============================================= */
template <class T>
T LinkedList<T>::summation(){
    return (next == nullptr) ? (data) : (data + next->summation());
}

/* =================================================== */
/* LinkedList<T>::minimum                              */
/*    Computes the minimum element in the linked list. */
/* =================================================== */
template <class T>
T LinkedList<T>::minimum(){
    if(next == nullptr) return data;
    return std::min(data,next->minimum());
}

/* =============================================== */
/* LinkedList<T>::forEach                          */
/*    Applies the function f to each data in list. */
/* =============================================== */
template <typename T>
template <typename FUNC>
LinkedList<T>* LinkedList<T>::forEach(FUNC f){
    //TODO
}

/* =============================================== */
/* LinkedList<T>::reduceRight                      */
/*    Applies the function f to each data in list. */
/* =============================================== */
template <typename T>
template <typename FUNC>
LinkedList<T>* LinkedList<T>::reduceRight(FUNC f){
    //TODO
}

/* ============================= */
/* LinkedList<T>::printList      */
/*    Displays each node's data. */
/* ============================= */
template <class T>
void LinkedList<T>::printList(){
    LinkedList *node = this;
    while (node != nullptr) {
        cout << node->getData() << " ";
        node = node->getNext();
    }
    cout << "\n";
}

#endif /* LINKED_LIST_HPP */

Part A [15 points]:¶

Please implement the constructor, getter, and setter methods. These functions save or return the private data stored in the class: T data; LinkedList *next.
Please implement the append method in the LinkedList class. It returns a LinkedList where a node holding the object val is appended.

Hint: This function is not recursive. You will make a new node, updating its data and next pointer, and resetting the previous node's next pointer.

In contrast to the Python version, we are making this linked list mutable such that we keep track of the head of the list through reference. When we prepend a node, we update the LinkedList head pointer. To see a demonstration of the expected behavior, see demo.cpp.

Please implement the prepend method in the LinkedList class.

Part B [5 points]:¶

We want to be able to conveniently apply a function to all elements in this list.

Please implement the forEach method in the LinkedList class.
The forEach method takes a function FUNC f as an argument, and returns a LinkedList (or nullptr) in which the element e in the list is mapped to fun(e). For example:

/* header files */
#include "linked_list.hpp"

template<typename T>
T square(T a){
    return a*a;
}

int main(){
    LinkedList<int> *list = nullptr;
    list->prepend(&list, 5);
    list->prepend(&list, 2);
    list->prepend(&list, 3);
    list->append(&list, 1);
    list->append(&list, 7);

    LinkedList<int> *new_list = list->forEach(square<int>);
    cout << "Original List: "; list->printList();
    cout << "forEach  List: "; new_list->printList();

    return 0;
}

Output:

Original List: 3 2 5 1 7
forEach  List: 9 4 25 1 49

Note: In the above example, forEach is not modifying the values in the LinkedList list. It is returning a new LinkedList new_list.

Part C [10 points]:¶

If we look at the logic of summation and minimum, we will notice that they are quite similar. Both are first reducing the tail of the list into an intermediate result and then combining the head with the intermediate result. The difference between summation and minimum lies in what this combining function is. For summation, two elements are combined by the function:

int combine(int a, int b){
    return a+b;
}

(We don't really have this function in our code, but its logic is used in summation.)

For minimum, two elements are combined by the hypothetical function:

int combine(int a,int b){
    return (a < b) ? a:b;
}

Please implement the reduceRight method in the LinkedList class. This method requires a function FUNC f as an argument. reduceRight will first reduce the tail of the list into an intermediate result by applying f to the tail nodes. Then, f should be applied to the head and the intermediate result to combine them.

For Example:

/* header files */
#include "linked_list.hpp"

template <typename T>
LinkedList<T>* smaller(LinkedList<T> *a, LinkedList<T> *b){
    return (a->getData() < b->getData()) ? a:b;
}

template<typename T>
T square(T a){
    return a*a;
}

int main(){
    LinkedList<int> *list = nullptr;
    list->prepend(&list, 5);
    list->prepend(&list, 2);
    list->prepend(&list, 3);
    list->append(&list, 1);
    list->append(&list, 7);

    LinkedList<int> *reduced  = list->reduceRight(smaller<int>);
    cout << "Original List: "; list->printList();
    cout << "Reduced  List: " << reduced->getData() << "\n";

    return 0;
}

Output:

Original List: 5 2 3 1 7
Reduced  List: 1

Part D [10 points]:¶

For this problem, copy the following code longest_sentence.cpp:

/* header files */
#include "longest_sentence.hpp"

LinkedList<std::string> *getListOfSentences(const char *filename){
    LinkedList<std::string> *list = nullptr;
    std::string line;

    std::ifstream ifs(filename);
    if (ifs.is_open() == false) {
        std::cerr << "Couldn't open file..." << std::endl;
        return nullptr;
    }

    while(std::getline(ifs,line)) {
        findAndReplaceAll(line,"...","|"); // avoid ellipsis issue
        findAndReplaceAll(line,".","|");
        findAndReplaceAll(line,"!","|");
        findAndReplaceAll(line,"?","|");
        findAndReplaceAll(line,"\" ","");

        std::istringstream p(line);
        while (std::getline(p, line, '|')) {
            list->append(&list, line);
        }
    }
    return list;
}


template <typename T>
LinkedList<T>* get_longest_sentence(LinkedList<T> *a, LinkedList<T> *b){
    //TODO: use countWords to test longest sentence

    //TODO: return "List" containing longest sentence
}

int main(void){
    LinkedList<std::string> *list_of_sentences = getListOfSentences("swansway-chapter1.txt");

    //TODO: Use reduceRight method -- pass in get_longest_sentence function

    //TODO: Output longest sentence and length

    return 0;
}

Marcel Proust is known for writing long sentences. The swansway-chapter1.txt contains the first chapter of Remembrance of Things Past. The function getListOfSentences will preprocess this file and return a LinkedList of all sentences in this chapter.

Please implement longest_sentence which returns the number of words in the longest sentence. You can assume that anything delimited by a space is a word.

Note: getListOfSentences reads text from swansway-chapter1.txt. You should have the text file in your HW5-final/ directory.

Hint: Use the reduceRight method that you implemented.

Deliverables¶

linked_list.hpp
longest_sentence.hpp
longest_sentence.cpp

Problem 2: Binary Search Tree¶

A binary search tree (BST) is a binary tree in which:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.

The code below is a partially implemented binary search tree. BSTNode is a node in the binary search tree. It contains a key-value pair and has references to its child nodes. BSTTable is the binary search tree itself. It holds a reference to the root node of the tree and contains methods that manipulate the nodes. Each child of the root node and its child should be a BSTNode. A BSTTable can be used as a table to store key-value pairs. Our implementation will only be able to handle the case when the keys are comparable to each other. Simple client code of BSTTable looks like this:

BSTTable<std::string> *greektoroman = new BSTTable<std::string>();
greektoroman->put("Athena",    "Minerva");
greektoroman->put("Eros",      "Cupid");
greektoroman->put("Aphrodite", "Venus");
greektoroman->display();
cout << greektoroman->get("Eros") << "\n";

and will return

(Aphrodite,Venus) (Athena,Minerva) (Eros,Cupid) 
Cupid

In this problem, we will implement the get and put method of BSTTable.

#ifndef BINARY_SEARCH_TREE_HPP
#define BINARY_SEARCH_TREE_HPP

/* system header files */
#include <iostream>

/* namespace */
using namespace std;

/* ============================ */
/* Templated BSTNode Definition */
/* ============================ */
template <class T>
class BSTNode {
  public:
    T key, value;
    BSTNode *left, *right;

    /* Constructors */
    BSTNode(T key, T value) : left(nullptr),right(nullptr) {
        //TODO: assign key
        //TODO: assign value
    }
    BSTNode(T key, T value, BSTNode *left, BSTNode *right){
        //TODO: assign key
        //TODO: assign value
        //TODO: assign left
        //TODO: assign right
    }
};

/* ============================= */
/* Templated BSTTable Definition */
/* ============================= */
template <class T>
class BSTTable {
  private:
    BSTNode<T> *root;

    /* private methods */
    BSTNode<T>* insert(BSTNode<T> *node, T key, T value){
        //TODO: insert new node into table
    }
    BSTNode<T>* search(BSTNode<T> *node, T key){
        //TODO: return node containing the key
    }

    void inorder(BSTNode<T> *node){
        if (node != nullptr) {
            inorder(node->left);
            cout << "(" << node->key << "," << node->value << ") ";
            inorder(node->right);
        }
    }
  public:
    /* Constructors */
    BSTTable() : root(nullptr) {}

    /* class methods */
    void put(T key, T val){
        //TODO: insert new node and update root
    }

    T get(T key){
        //TODO: return value corresponding to BSTNode with key
    }

    void display(){
        inorder(root);
        cout << "\n";
    }
};
#endif /* BINARY_SEARCH_TREE_HPP */

Part A [15 points]:¶

The put method inserts a key-value pair into the BSTTable. It delegates the function call to insert.

Please implement the public method put and the private method insert. The insert method takes a node, a key, and a val as its arguments. node is the root of the subtree into which the key-value pair is to be inserted. After the insertion, the root of this subtree may change. The insert method should return the new root of this subtree. If the key was already in the BSTTable, then the value of the corresponding node should be updated.

Note: We assume all the keys are of the same type and are comparable to each other with >, < and ==. So if all your keys are strings, they will be ordered lexicographically. If all your keys are numbers, they will be ordered from the smallest to the largest. Here is an example:

BSTTable<std::string> *greektoroman = new BSTTable<std::string>();
greektoroman->put("Athena",    "Minerva");
greektoroman->put("Eros",      "Cupid");
greektoroman->put("Aphrodite", "Venus");
greektoroman->display();

Output:

(Aphrodite,Venus) (Athena,Minerva) (Eros,Cupid)

Part B [15 points]:¶

The get method returns the value with the corresponding key. It delegates the function call to search.

Please implement the public method get method and the private method search. The search methods takes a node and a key as arguments. It will search for a node with the same key under the subtree whose root is node. If there is such a node, return the val of this node. The get method should raise an error if no such node is found.

Deliverables¶

binary_search_tree.hpp

In [ ]: