CS 610 – 104 Homework 4 Spring 2017 Note: All homework assignments are to be completed individually. No group work is allowed. This homework is due at the beginning of class on the assigned due date. To receive any credit for your submission you must show all work. 1.) (5 pts) Using the abstract operations defined for the List ADT, write an algorithm to count the number of elements that fall between a range of [low, high] inclusive in an unsorted List ADT S. 2.) (5pts) Using the abstract operations defined for the Tree ADT, write an abstract level pseudocode algorithm CountExternal(T, v) to count the number of external nodes in a Tree T. 3.) (5 pts) Assume that a Tree ADT stores numerical values. Write an algorithm TreeMax(T, v, max) that returns the largest value in a Tree ADT T. 4.) (5 pts) Using the abstract operations defined for the Tree ADT, write an algorithm isTernaryTree(T, v), which returns a Boolean value indicating if the Tree ADT T is a proper ternary tree. A proper ternary tree is a tree where each node has three children or no children. 5.) (5 pts) Using the abstract operations defined for the Binary Tree ADT, write an algorithm cousins(T, v) that returns the cousins (i.e., nodes with the same grandparent) of a given node v in a proper binary tree ADT T, if they exist. The cousins can be returned as an array. 6.) (10 pts) Using the abstract operations defined for the Binary Tree ADT, write an algorithm to determines if two Binary Trees, T1 and T2, are equal. A binary tree is considered equal if the structure is the same and the values stored at the same location in the trees are the same. For (2)-(6) analyze the order if the running time if the Tree/Binary Tree is implemented using a linkednode data structure where each node has a direct link to its children and (i) has a link to its parent and (ii) does not have a link to its parent.