﻿ C/C++ - 硕博编程辅导/课程/代码/程序/it/cs/code/java/python/c/c++/人工智能/深度学习/R/算法/web/app/assignment辅导|原创|加急|硕士|博士|985高校|欧洲美国常青藤名校

# 北美代写,Homework代写,Essay代寫-准时✔️高质✔最【靠谱】

CSc 345: Homework Assignment 4

Assigned: Monday July 26 2021 Due: 5:00PM, Friday August 6 2021 Clear, neat and concise solutions are required in order to receive full credit so revise your work carefully before submission, and consider how your work is presented. If you cannot solve a particular problem, state this clearly in your write-up, and write down only what you know to be correct. For involved proofs, first outline the argument and then delve into the details. 1. (10pts) Give a θ(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself. 2. (10pts) Suppose that we are storing a set of n keys into a hash table of size m. Show that if the keys are drawn from a universe U with |U| > nm, then U has a subset of size n consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is θ(n). 3. (10pts) What is the difference between the binary-search-tree property and the min-heap property (see page 153)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Show how, or explain why not. 4. (10pts) Write the TREE-PREDECESSOR procedure. 5. (10pts) Consider a binary search tree T whose keys are distinct. Show that if the right subtree of a node x in T is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x. (Recall that every node is its own ancestor.) 6. (10pts) An alternative method of performing an inorder tree walk of an n-node binary search tree finds the minimum element in the tree by calling TREE-MINIMUM and then making n ? 1 calls to TREE-SUCCESSOR. Prove that this algorithm runs in θ(n) time. 7. (10pts) We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm? 1 8. (10pts) Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees? 9. (10pts) Let (u, v) be a minimum-weight edge in a connected graph G. Show that (u, v) belongs to some minimum spanning tree of G. 10. (10pts) Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is nonhamiltonian.    