University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
Department of Computer Science
My Home Page
Course Page
CSC 477/677 Assignment 4
Due date: Wednesday, October 2, 2013, 2:30 PM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
-
using the frequencies of the uses of letters in English given by
Wikipedia,
constuct an optimal prefix code for the first thirteen letters of
the Roman alphabet, namely "a" through "m."
Use Huffman's algorithm.
-
Find the minimum spanning tree of
this weighted graph
Using Kruskal's algorithm. Show the steps.
Same graph in pdf format.
-
Show that the worst case time complexity for Shell sort is
Θ(n2) if the gap sequence consists of powers of 2.
Hint: Consider the input list:
NAOBPCQDRESFTGUHVIWJXKYLZM
-
The median problem is to identify the median item in a list of items.
The BFPRT algorithm, also known as the Median of medians algorithm,
solves the median problem in O(n) time.
In special cases, the median problem can be solved faster.
For example, if the input list is given as a sorted array,
the median problem can be solved in O(1) time.
Suppose the input consists of two sorted arrays of items, whose total length
is n. How fast can you solve the median problem in this special case?
Example: if the input consists of the arrays
ABDGHIJLPQ
and
CEMNTVXYZ
then the median item is L.
-
Suppose a graph G is represented as an
edge list.
Describe an algorithm which uses Kruskal's algorithm, or uses union/find
directly, to decide whether G is connected.
Back to
Course Page