CE2001/CZ2001 ALGORITHMS General Information of Individual Assignment - The assignment is an open-book individual assessment and will constitute 40% of final marks for the course. - Number of...

The assignment brief is on the first page, followed by 4 other questions


CE2001/CZ2001 ALGORITHMS General Information of Individual Assignment - The assignment is an open-book individual assessment and will constitute 40% of final marks for the course. - Number of questions: o There are 4 questions in total. - Deadline: o The deadline is at 6pm on 20 November 2020. o Late submission will NOT be accepted due to any reason and zero mark will be given. o You are suggested to submit earlier than the exact deadline to avoid heavy traffic at NTULearn in the last minute. - Submission: o Each student is required to submit a report (softcopy in a single pdf file) via NTULearn by the deadline. o The report should be typed in Arial Font 11 and with single line spacing and normal margin (Top and bottom 2.54cm, left and right 3.18cm). o The report should contain a cover page, specifying student’s full name, matric number, email, and the tutorial group. o The maximum length of the report is 4 pages, excluding the cover page. - Plagiarism: o Plagiarism is strictly prohibited. o Using online resources directly is considered plagiarism. o If the reports of two students are found similar (even just for a single question), both students will receive zero mark for the assignment, no matter who copies whom. Further academic disciplinary actions may be taken. Individual Assignment Q1: Are the following two graphs the same? Discuss whether the problem above is an NP, NP-hard, NP-complete or P class problem. (10 marks) Q2: As we know, the heuristic or approximation algorithms may not give an optimum solution to the problem but they are polynomial efficient. (a) Propose an approximation algorithm for travelling salesman problem (TSP) and discuss about its time complexity and limitation. (6 marks) (b) 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. (4 marks) Q3: Use the same versions of the sorting algorithms learnt from our lectures to solve the following questions. (a) 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. (6 marks) (b) An input array B contains 2k-1 distinct elements (k is a positive integer). All elements in B are arranged in ascending order. The constructHeap 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. (4 marks) Q4. Consider a weighted directed graph G with all edge weights greater than 10. Now we reduce the weight of every single edge in G by 4 and produce a graph G’ with all edge weights greater than 6. We then apply the Dijsktra’s algorithm on G’ and compute the shortest path from a source vertex s to every other vertex. Is the shortest path computed in G’ also a shortest path in G? If Yes, provide a proof. Note that you can directly utilize the proof of Dijsktra’s and don’t need to repeat its proof details. If No, provide a counter- example. (10 marks)