algorithms exam
possible topics
- O(n) definition and measures
- P, NP, complexity classes
- trees and other data structures
- combinatorics
- sorting and searching
- heaps
- hashing
- queues and stacks
- graphs
- depth vs breadth tree search with stack vs queue for the fringe
- lossless compression: huffman and LZW
rules
- Given: Fri March 9 2007
- Due: midnight Fri March 16 2007
- Books and online resources are allowed (unless the question says otherwise) as long as you quote your sources explicitly.
- Don't ask other people for help.
- If a question isn't clear please ask for clarification.
- Your primary object should be to convince the readers that you understand the material, not just to get the right answer. Stating an answer without explaining where it came from is generally insufficient.
questions
1
Experimentally demonstrate the average big-O behavior of the following two problems, using randomly generated data. In other words, code each in a language of your choice, generate sample problems of different sizes n, collect data on how many steps each takes to accomplish (you can define a "step" in any reasonable way), and plot steps(n) vs n for both problems.
- The partition problem: given a multiset (a set-like construction that allows multiple copies of the same thing) of integers, is there a way to partition it into two parts such that the sum of integers in each part is the same.
- The convex hull problem: given a set of points (x[i], y[i]), find that list of points that's on the extreme outer "edge", which form a convex polygon containing all the other points.
2
For each of the two problems in question 1, explain whether the problem is in the complexity class P, NP, or some other. Be explicit as to why it does or does-not fit all the conditions necessary for membership. Discuss how your experimental results from question 1 fit into this story.
3
You are given a list N names and told that you'll need to search the list for a given name M times. The following techniques are suggested:
- a hash table
- a heap
- sequential search
- sorting followed by binary search
a) Discuss the time efficiency of these as N and M vary. Which would you suggest and why?
b) Implement one of these, including tests and docs.
c) Would your answer change if you need to change the list of names by adding and deleting students (P times, say) between searches?
4
Compare and contrast the LZW and Huffman coding methods of lossless data compression, including their strengths, weaknesses. Give an example of each algorithm applied to the same text string. (You can either do this by hand or code it; your choice.)
