CS301 Data Structures

Assignment No.3

Marks: 20

Deadline

Your assignment must be uploaded/submitted at or before 5/11/2016

Rules for Marking

It should be clear that your assignment will not get any credit if:

o The assignment is submitted after due date.

o The submitted assignment does not open

o The assignment is copied.

Objective

The objective of this assignment is to provide on hand experience of:

o Insertion & rotation and deletion in AVL Trees

o Huffman Encoding

Assignment

Question No: 1 Marks: 6+4

a) Show the result of inserting the values 11, 13, 24,26,30,40,58,10,8,7 into an

empty AVL Tree.

You are required to show each step of insertion and rotation in pictorial form.

b) Delete keys 13 and 26 from AVL tree constructed in part (a) and redraw tree after

each deletion.

Question No: 2 Marks: 2+4+2+2

Consider the following sequence:

joining different node to create new nodes

a) Draw frequency table

b) Create a Huffman tree

c) Determine the binary code for each character

d) Compare the Huffman encoded sequence with the encoding of sequence with

ASCII code.

Submit your all example of answer in .ccp file only.