a greedy algorithm is proposed for the given problem. Give a simple counterexample for each of them to show that the proposed greedy algorithm does not always return the optimal solution (this is algorithm queations)

This question is to be attempted individually. In each of the following, a greedy algorithm is proposed for the given problem. Give a simple counterexample for each of them to show that the proposed greedy algorithm does not always return the optimal solution. You should give an example input, state the solution returned by the greedy algorithm on that input, and another solution that is better than the greedy solution for that input. (a) Input: An undirected complete graph G (i.e. there is an edge (with weight) between any two vertices in the graph); a starting vertex s and a destination vertex t in G. Problem: Find a path that begins at s, ends at t, and visits every other vertex in G exactly once, and such that the total weight of this path is as small as possible. Algorithm: Let u be the current vertex (which initially is s). Find the minimum-weight edge among all edges (u, v) where v is neither t nor any vertex already visited. Add this edge to the path, and update the current vertex to v. Repeat this until t is the only vertex not yet visited. At this point add the edge from the current vertex to t as the final edge of the path. [10 marks] (b) Input: A set Y of youtube channels, a set P of people and a and a set of pairs (Yi, Pj) indicating person p; subscribed channel yi. Problem: Choose a subset Y' of youtube channels from Y so that everyone in P sub- scribes to at least one channel in Y', and that the number of channels in Y' is as small as possible. Algorithm: Repeatedly add to Y' the channel that would give the largest number of 'new subscribers (i.e. those who did not subscribe to any channel already in Y'), until everyone in P has subscribed something in Y'. [10 marks) (c) Input: A set of objects, each with a weight between 0 and 1. Problem: Put all objects into a number of containers, where each container can hold objects of total weight at most 1, and such that the number of containers used is minimised. Algorithm: Sort all objects in decreasing order of weights. For each object in this sorted order, among all existing containers that would fit this object, put it into the one with the largest total weight of objects already in there. If no existing container can fit this object in, put it into a new container. [10 marks] 1 Question 2 (70 marks) This question can be attempted in groups. A fundamental problem in machine learning and data analytics is to partition or classify objects in a 'natural way based on their distances to each other. In this question, you are given an integer N, and n points x1, x2, ..., In in a horizontal line. We want to partition the n points into N groups so that intuitively within each group the points are 'close together. The following is an example of what may be a good way of partitioning the following n = 8 points into N = 3 groups, and what may be a bad way: 1 2 3 6 8 12 13 15 Good? Bad? More precisely, each point x; is a number on the x-axis. To measure how 'good' a partitioning is, we define the error of a group of points Xp, Xp+1,...,xq to be (Ip H)2 + (1 p+1 u)? + ... + ({q H)2 where u = (xp + Xp+1+...+xg)/(q- p+1) is the average of the points. Our objective is to find the optimal way of partitioning the points into N groups so that the sum of errors of all groups is minimised. For example, the 'bad' way of partitioning for the above example gives an error of: Group 1: average = (1+2)/2 = 1.5, error = (1 - 1.5)2 + (2 - 1.5)2 = 0.5. Group 2: average = (3+6+8+12)/4 = 7.25, error = (3 7.25)2 + (6 7.25)2 + (8 7.25)2 + (12 - 7.25)2 = 42.75. Group 3: average = (13+15)/2 = 14, error = (13 14)2 + (15 14)2 = 2. Total error = 0.5 + 42.75 + 2 = 45.25. We divide the points in such a way that only consecutive points (along the line) may fall into the same group. (a) Design an efficient algorithm for this problem. You should: (the following is described in terms of the design of a dynamic programming algorithm, since you almost certainly should use it) In plain English or using some mathematical notation, give a recursive formulation of the problem. (Hint: one possible approach is to define F(i,k) to be the error of the optimal partition of the first i points x1,...,x; into k groups, where i