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. ...continues

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.

Proving a problem is NP - complete by reduction from Vertex-cover.

Please see the attachment below for the complete question. We need to prove that the problem is NP -complete by reduction from Vertex-cover. Problem :- Given a collection of sets { S1, S2 ,..., Sn} and a positive integer K. Does there exist a set T with at most K elements such that T disjoint Si not-equalto empty , 1<=i<=n ...continues

Understanding a binary search.

What is a binary search, and how does it work?

Prove a tautology using truth tables.

Show that [(a OR b) AND (a IMPLIES c) AND (b IMPLIES c)] IMPLIES c) is a tautology, using truth tables.

Determining the greatest common divisor using the Euclidean Algorithm.

How do I use the Euclidean Algorithm for determining the greatest common divisor of two integers?

Writing regular expressions describing languages of strings.

Write a regular expression describing the language of strings that do not begin with the pattern 110. The language consists of 0s and 1s.