Using Big O notation for proofs.

Use only the definition of O(f(n)) to prove that the following statements are true: 1. (6n^3*log n + 1)/2n +1000 = O(1) 2. nlog n + n^3/2 = O(n^3/2) Please view the attachment below for the full question.

Constructing an optimal Huffman code and tree.

Suppose characters a, b, c, d, e, f, g, h, i, j, k have probabilities 0.01, 0.03, 0.03, 0.05, 0.05, 0.07, 0.09, 0.12, 0.13, 0.20, 0.22, respectively. Construct an optimal Huffman code and draw the Huffman tree. Use the following rules: a. Left: 0, right: 1 b. For identical probabilities, group them from the left to right. What is the average code length?

Working with the binary search tree and complete tree and proving that it can be done for an arbitrary number of nodes.

Give an example of a binary search tree which is a complete tree. Can it be done for an arbitrary number of nodes? Prove your answer.

Writing a linear-time boolean function for a HEAP structure.

Write a linear-time Boolean function HEAP(T:BINARY_TREE) which returns TRUE is T is a heap, i.e., it is partially ordered. Assume that T is represented using pointers to left and right children. Prove that the time is really linear.

Showing how AVL trees are formed. Attachments in Word.

AVL trees are a good implementation of binary search trees. Show (step by step) the AVL trees formed by inserting the numbers 3, 11, 2, 9, 8, 12, 10, 5, 4, 7, 6, 1, 13.