|
Here are the questions if you can help i can send you the graphs needed
MCS 2534 Data Structures and Algorithm Design
Summer 2005
Midterm Take Home Exam
1. Chapter 2, Algorithm Design:
a. Discuss the meaning of the Big Oh notation. Cover the four cases defined by Big O, Omega, Theta, and Little o.
i. What is the significance of the positive constants used in the formal definition (e.g. ?There are positive constants, c & n such that T(N) >= cF(n) where N >= n0?)
ii. Show graphically (you can use graph of part iii)
iii. See the attached graph and answer the questions.
2. Chapter 3 ? Linked Lists, Stacks & Queues:
a. What is the Big Oh notation for stacks and queues?
3. Chapter 4, Trees:
a. How is the tree height related to running time for tree operations (give a general relationship).
b. What is the Big Oh for Binary Search Trees?
c. What is the basic reason for the Big Oh formula in part b? (develop a simple mathematical basis for this formula)
d. Discuss the affect that balance (or lack of) has on performance (Bog Oh) and why.
e. What is an AVL tree
i. What does it provide vs a BST?
ii. What is the affect on Big Oh vs a BST
f. Explain the basic idea of Splay Trees.
g. What do splay trees provide regarding running time (What is the Big Oh and why).
h. Discuss B- Trees
i. What is a B-Tree
ii. What is the basic idea behind a B-Tree
iii. What is the Big Oh notation
iv. Why use a B-Tree?
i. Balance the tree (attached) so it is AVL. You can use any method you want.
4. Chapter 5 ? Hashing
a. Explain the general idea behind hashing
b. What is the Big Oh for hashing?
c. What is a hashing function?
d. What are the tradeoffs among hashing functions?
e. If you use the table size as part of the hashing function, why should the table size be a prime number?
f. Give an example of a hashing function using table size.
g. Explain collisions.
h. Explain separate chaining
i. Explain Linear Probing
i. What is the basic idea?
j. What is the ?Primary Clustering Problem??
k. Explain Quadratic Probing.
i. What does it provide over linear probing?
l. See attached (5L) and answer questions
|