Describe Linked-lists, what operations you like to make for Linked-lists?

Algorithms

Final Exam, Spring 2016

Name________________________ SSN________________________

1. Describe Linked-lists, what operations you like to make for Linked-lists?

2. Write a C++ function for calculating the recursive function: f(0)=f(1)=1, and f(n)=f(n-1)+ f(n-2).

3. Quad-tree is often used in GIS systems for spatial data.
If you have an 1024×1024 array that stores {0,1} image. If you are asked to save the image in a quad-tree structure, one can reach a leaf (meaning no further dividing action is needed) if the represented square are all “1.” (1) What is the possible height of the quad tree? (2) What is the time complexity of the process if you have NxN array? (You need to first build a recurrence equation.) Prove your answer.

4. Describe the minimum spanning tree. What algorithm you want to use to find a minimum spanning tree? What is the time complexity?

5. The depth-first search algorithm is a fundamental algorithm for graphs. It can be used to design an algorithm that decides if a graph G contains a cycle. Describe the cycle-finding algorithm. What is the time complexity?

6. (Review 🙂 Given a set of numbers: A = <3, 41, 52, 26, 38, 57, 9, 49>. Use both merge-sort and quick-sort to sort the array. Show each detail steps. How many “comparisons” for each algorithm? What is the complexity of merge-sort? Prove it.