Advanced Programming, Fall 2014 HW3 - Heaps (Priority Queues), Data Streams, Simple Dijkstra. Due electronically on Blackboard on Tuesday Oct 14, 11:59pm. Include in your submission a report.txt and all python programs. Expected Amount of Work for an average student: 8-10 hours. Textbooks for References: [1] CLRS Ch. 6 (heapsort). 1. (taken from my first paper: see "Algorithm 1" in Huang and Chiang (2005).) Given two lists A and B, each with n integers, return a sorted list C that contains the smallest n elements from AxB: AxB = { (x, y) | x in A, y in B } i.e., AxB is the Cartesian Product of A and B. ordering: (x,y) < (x',y') iff. x+y < x'+y' or (x+y==x'+y' and y>> a, b = [4, 1, 5, 3], [2, 6, 3, 4] >>> nbesta(a, b) # algorithm (a), slowest [(1, 2), (1, 3), (3, 2), (1, 4)] >>> nbestb(a, b) # algorithm (b), slow [(1, 2), (1, 3), (3, 2), (1, 4)] >>> nbestc(a, b) # algorithm (c), fast [(1, 2), (1, 3), (3, 2), (1, 4)] Hint on (c): you can use Python's heapq module for priority queue. Filename: nbest.py 2. k-way mergesort (the classical mergesort is a special case where k=2). >>> kmergesort([4,1,5,2,6,3,7,0], 3) [0,1,2,3,4,5,6,7] What is the complexity? Write down the detailed analysis. Filename: kmergesort.py 3. Find the k smallest numbers in a data stream of length n (k<