Assignment

SECTION 1. Algorithm Analysis

TO DO WELL: Before you work on this section, write down what W(N) means, and the F(N)s of sorting and searching.

1) What is the purpose of using asymptotic notation such as O, Omega and Theta instead of using the exact number of comparisons done by a sorting algorithm?

i.e. why do we use O(n^2) instead of saying 2n^2 + 3n + 4

*Because we are only interested in

2) Computing the Average time complexity for a real-world problem is difficult. Explain why by referring back to the formula for computing A(n). Why?

3) Your friend is very excited about having found a sorting algorithm that sorts in much less than W(n) = Theta(N^2)comparisons even though it corrects only one bad pair per comparison. He thinks this is the fastest sort ever and that he will get a Ph.D. tomorrow. Please teach him why he is wrong.

4) Your friend says she can find a comparison based algorithm that searches for an element in an ordered list in much less than W(N) = Theta(log N). Please teach her why she is wrong.

5) Name 2 Divide and Conquer algorithms we studied in this class.

6) Describe 2 Space vs. Time decision cases we discussed in this class.

In what ways can each be called Space vs. Time?

7) Name 2 greedy algorithms we have learned in this class.

SECTION 2. Sorting

Your mean employer has five sorting programs. But they are labeled by their descriptions - no names.

Read each label then say which of the following it is:

Heap Sort
Insertion Sort
Merge Sort
Quick Sort
Radix Sort

1) "I am a good choice if you want consistent theta(nlogn) time and have lots of space."

2) "Although I take O(n^2) time in the worst case, on the average

I only use theta(nlogn) and I do not need as much space as another divide and conquer algorithm."

3) "I use theta(nlogn) time in the worst case. The data structure I use is also useful for efficiently implementing priority queues."

4) "Even though my average complexity is theta(n^2), I am a good choice if you want to sort small files, or large files that are very nearly in order."

5) "I am a good choice if you want to quickly sort a large number of K digit numeric IDs."

SECTION 3. Object-Oriented Programming

TO DO WELL: Before you work on this section, re-read the notes.

1) (inheritance), we placed data members of the base class in protected. Why did we do that? Answer each separately.

*Why not private?

*Why not public?

2) You had to overload = to make it work with slists.

*We had to overload=. What's wrong with the one provided by C++?

*We had to overload==. What's wrong with the one provided by C++?

3) Why did you have to write a copy constructor for linked lists?

Also, give two cases in which your copy constructor is automatically invoked in relation to calling regular functions.

*What's wrong with the one provided by C++?

*Invoked when:

*Invoked when:

4) Why is it useful to use virtual functions with inheritance and pointers? Explain using the Animals array which contains pointers to Dog and Cat objects with a virtual function Speak.

*The stated combinations allows

SECTION 4. Binary Search Trees

void BST::traverse(Vertex *V) // post order traversal recursively
{
if (V != NULL)
{
traverse(V->Left);
traverse(V->Right);
cout << V->elem << endl;
}
}

1) Modify the above slightly (just re-order) to do the Depth First traversal recursively. What is this traversal called?

*Code:

*Name of the traversal: ____________ order traversal.

2) Why would we want to balance search trees?

(i.e. What is wrong with unbalanced trees?)

What were the two ways (from our notes) of having a balanced search tree?

*Why:

*Way1:

*Way2:

SECTION 5. GRAPHS: Islands and Bridges

800 islands are connected with many two-way bridges (i.e. lines, not arrows).

You know the cost of maintaining each bridge.

You want to minimize the total maintenance cost by eliminating some bridges while leaving all the islands connected.

1) What algorithm would you use to solve this problem? (Algorithm for finding what?)

*Algorithm for finding:

2) How many bridges will you end up with if you used this algorithm?

*Give the Formula where N = 800:

SECTION 6. ENCYPTION and BIG DATA (from Notes-14)

*Fill in the blanks in the following:

Encryption in essential in cybersecurity.

Using RSA, if people want to send messages to Mary, they have to use her ______ encryption key. She uses her ______ decryption key to decode them.

_______ numbers play an important role in constructing these keys.

The computer can use big training data to learn to identify or classify things.

By analyzing a vast number of examples labeled with their categories, the computer will learn to place unlabeled ones into these categories. This area of Artificial Intelligence is called _________ learning.

SECTION 7. MEMORY

1) What are garbage cells? i.e. What kind of cells are they and why do they happen? (Recall that there are 3 kinds of cells and garbage cells are just one of them)

*What are they?

*Why do they happen?

2) Which garbage collection method from the notes worked incrementally and also prevented dangling pointers?

*Method:

SECTION 8 NP vs. P Consulting Job

1) Your boss says "I want you to find the shortest path that passes through all the Mars alien bases. The objective is to infect each base and thus you cannot return to the same base ever again. I want an algorithm to do it in Polynomial time."

*What would you say to him? Explain why:

2) 10 years from today, while sleeping, you find a polynomial time algorithm for bin packing. Congratulations!! What implication does this have on your answer to the question above? What famous question have you answered to make you rich?