University American U الشارقة 1997 ity of Sharjah الجامعة الأمان - CMP 340 – Design and Analysis of Algorithms Assignment #3 - Space-time tradeoffs - Trie Deadline: April 7th, 2024 Write a program for solving the coin collecting robot problem. You program should be able to read from a user-supplied file (as specified by the command line), a grid with coin placements, and print out the largest sum of money it can accumulate in addition to the steps the robot must perform. Assuming that the robot goes from the top-left corner to the bottom-right one, only Down and Right movements are allowed. The format of the input file is illustrated below: 4 6 // four rows and 6 columns 0 0 0 0 0 0 // one line of space-separated values for each row 0 0 3 000 0 0 0 1 0 0 1000 40 your program should produce for the above example: $ ./robot grid.txt 8: DRR DR DR R or any other valid sequence that produces the same value. Bonus 20% : If two or more sequences give the same solution, output the one that is alphabetically smaller. In the above example, other optimum sequences exist: RRDRDRDR RDRRDRDR RRDDDRDR etc. but none is smaller than “D RRDRDRR”. Delivarables: submit your work by e-mail to gbarlas@aus.edu. Name your file using your ID and the number of the assignment, e.g. 3648_ass3.zip You can work individually or in pairs.