MTH251: As We Know, the Heuristic or Approximation Algorithms may not Give an Optimum Solution: Data Structures and Algorithms I Assignment, SUSS, Singapore

Q1: Are the following two graphs the same?

Discuss whether the problem above is an NP, NP-hard, NP-complete, or P class problem.

Q2: As we know, the heuristic or approximation algorithms may not give an optimum solution to the problem but they are polynomial efficient.

• Propose an approximation algorithm for travelling salesman problem (TSP) and discuss its time complexity and limitation.
• Give two example inputs, in which the algorithm in (a) gives the best and not-the-best solutions, respectively. The number of nodes should be between six and eight.

Q3: Use the same versions of the sorting algorithms learned from our lectures to solve the following questions.

• Consider a hybrid sorting algorithm that combines Mergesort with Insertion Sort. It uses Mergesort until the number of elements in the input becomes smaller than or equal to 8, after which it switches to Insertion Sort. What is the number of key comparisons performed by this hybrid sorting algorithm in the best case when running on an input array of size n? Briefly justify your answer. You could assume n = 2k, for some integer k > 3.
• An input array B contains 2`-1 distinct elements (k is a positive integer). All elements in B are arranged in ascending order. The construct Heap algorithm in Heapsort is applied to B to construct a maximizing heap. Analyze how many key comparisons are performed in this heap construction. Your result must be in terms of k.