/* ***************************************************************************** * Name: * NetID: * Precept: * * Partner Name: * Partner NetID: * Partner Precept: * * Hours to complete assignment (optional): * **************************************************************************** */ Programming Assignment 6: WordNet /* ***************************************************************************** * Describe concisely the data structure(s) you used to store the * information in synsets.txt. Why did you make this choice? **************************************************************************** */ /* ***************************************************************************** * Describe concisely the data structure(s) you used to store the * information in hypernyms.txt. Why did you make this choice? **************************************************************************** */ /* ***************************************************************************** * Describe concisely the algorithm you use in the constructor of * ShortestCommonAncestor to check if the digraph is a rooted DAG. * What is the order of growth of the worst-case running times of * your algorithms as a function of the number of vertices V and the * number of edges E in the digraph? **************************************************************************** */ Description: Order of growth of running time: /* ***************************************************************************** * Describe concisely your algorithm to compute the shortest common ancestor * in ShortestCommonAncestor. For each method, give the order of growth of * the best- and worst-case running times (as a function of the number of * vertices V and the number of edges E in the digraph)? * * If you use hashing, assume the uniform hashing assumption so that put() * and get() take constant time per operation. * * Be careful! If you use a BreadthFirstDirectedPaths object, don't forget * to count the time needed to initialize the marked[], edgeTo[], and * distTo[] arrays. **************************************************************************** */ Description: running time method best case worst case -------------------------------------------------------- length() ancestor() lengthSubset() ancestorSubset() /* ***************************************************************************** * Known bugs / limitations. **************************************************************************** */ /* ***************************************************************************** * Describe whatever help (if any) that you received. * Don't include readings, lectures, and precepts, but do * include any help from people (including course staff, lab TAs, * classmates, and friends) and attribute them by name. **************************************************************************** */ /* ***************************************************************************** * Describe any serious problems you encountered. **************************************************************************** */ /* ***************************************************************************** * If you worked with a partner, assert below that you followed * the protocol as described on the assignment page. Give one * sentence explaining what each of you contributed. **************************************************************************** */ /* ***************************************************************************** * List any other comments here. Feel free to provide any feedback * on how much you learned from doing the assignment, and whether * you enjoyed doing it. **************************************************************************** */