• If you have reviewed the textbook already, please pick up one sorting algorithm with time complexity of O(n) and discuss its performance. Since the algorithm runs faster than all comparison sorting algorithms, why comparison sorting algorithms are still used in some applications?

 

• Please briefly discuss the Quicksort algorithm shown in the textbook. What is the reason that it usually runs faster than other sorting algorithms with a time complexity of O(nlgn) (e.g., heap sort) in real world applications?

 

• Please briefly describe properties of the B-tree structure shown in the textbook. Why is it designed this way? What are the implications on operations such as insertion and deletion due to these properties?In addition, can you give some examples on real-world applications in which B-trees (or variants) might be used?

 

• In your own words, briefly discuss the TREE-DELETE algorithm used by binary search trees. Do you think there are alternative ways to implement this algorithm? In other words, are there other ways to maintain the properties of binary search trees when a node is deleted? Justify your answer.

 

• Please briefly introduce the ideas behind greedy algorithms. What are the hallmarks where greedy algorithms could be applied? How do these hallmarks differ from those used by dynamic programming techniques?

 

Please briefly introduce the dynamic programming technique. What do you think about its efficiency? What are the hallmarks where dynamic programming could be applied?