Source: Placement test of one of the Algorithmic Trading Firms coming to the campus. Also in UC Berkeley, Spring 2001 Final Exam for CS170 (Efficient Algorithms and Intractable Problems)
Problem: Pratik is organizing a mix tape for his sweetheart, Pratiksha. The tape will have her top N songs of all time. Pratik was going to determine the order of these songs on his own, but then Pratiksha found out about his little project. Being an obnoxiously demanding woman, she has now given Pratik a price function f which takes a pair of songs [si,sj] as input, and returns a real number that quantifies exactly how good song sj sounds after song si, in her opinion. (Note that f([si,sj]) may not be equal to f([sj,si]).)
Write an O(n^2*2^n) algorithm for Pratik that will determine a song order which maximizes the total transition goodness of the mix tape. (If the maximum is not achieved, Pratik will be dumped. :()
Posted by Nikhil Garg (Sophomore, CSE, IITD), Rajendran Thirupugalsamy (Research Assistant, Stony Brook University) and "Anonymous" in comments!!