computer Science -- Data Structures and algorithms

SECTION 1. Algorithm Analysis [1 pt per prompt = 12 points]

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.

*Answer:

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.

*Answer:

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

*Name:

*Name:

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

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

*Example Algorithms: ________ vs.______________

*Reason:

*Example Data Structures: _________vs.____________

*Reason:

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

*Algorithm for solving/finding:

*Algorithm for solving/finding:

SECTION 2. Sorting [2pts per prompt = 10 points]

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."

*Answer: This is

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.”

*Answer: This is

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

*Answer: This is

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."

*Answer: This is

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

*Answer: This is

SECTION 3. Object-Oriented Programming [2pts per prompt = 16 points]

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

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 (HW4)[1 pt per prompt = 5 points]

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 [2pts per prompt = 4 points]

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)[1 pt per blank = 4 points]

*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 [1pt per prompt = 3 points]

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 [2pts per prompt = 6 points]

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?

*Implication on (1):

*Question answered:

================== THE END ===================================================