CSI5100 Programming Languages Homework 2

Homework 2

• This homework is an individual assignment. For your homework to be marked, please pack the source code into a zip archive labeled with your student ID (e.g., 2018010201.tar.gz) and submit it in the provided report section on LearnUs.
• Please provide a README.txt file that contains the commands how to build and run your programs. Please state the operating system (Windows, Linux, macOS) in your README.txt file.
• Please make sure that when your archive is extracted, the files appear as follows (for programing problem p4, the choice of file names is up to you): ./2018010201/README.txt ./2018010201/p1/factorial.scm ./2018010201/p2/ackerman.scm ./2018010201/p3/allzero.scm ./2018010201/p4/v1/ ... ./2018010201/p4/v2/ ... ./2018010201/p4/v3/ ... ./2018010201/p4/v4/ ... • The documentation of your code should be done in form of comments. Please be verbose with your comments, i.e., thoroughly explain your ideas how you have implemented the programs. Not providing comments will decrease your score.

  Programming Problems

  1. Define a factorial function in Scheme and execute it with (factorial 6).
  2. Define the Ackermann function in Scheme and execute it with (A 3 2). See http://en. wikipedia.org/wiki/Ackermann_function for a definition of the Ackermann function.
  3. Define a Scheme function “allzero” that takes a list of integers, applies a function that converts an integer to true if the integer is zero and to false otherwise, and reduces the resulting list to a single true/false by conjunction. To keep your code compact, use higherorder Scheme functions whenever possible. The result should be: (allzero ’(1 0 0)) ⇒ #f and (allzero ’(0 0 0)) ⇒ #t.
  4. Solve the following programming problem in three languages . Two languages you must select from the following four programming languages: Ada, Scala, Scheme or Python 3. For the third language you have free choice. Your program should read a sequence of n integers from the commandline and output a not necessarily contiguous subsequence that is as long as possible, and in which the elements are monotonically increasing from left-to-right. For example, if the input sequence is 19 3 11 7 15 12 4 12 8 16 then one possible output would be 3 7 15 16 There are several other possible outputs, all of length 4: 3 4 8 16 3 4 12 16 3 7 8 16 3 7 12 16 3 11 12 16 3 11 15 16

There are several possible solutions to this problem, the most obvious one being perhaps a doubly recursive function that takes O(2n ) running time. More efficient solutions use dynamic programming. It is sufficient to use the “obvious” solution, as the focus is on comparing languages. CourseNana.COM

Please note that there are open-source implementations available for all of the above mentioned languages. For Scheme, I suggest to use Racket (see https://racket-lang. org/, which was used with the examples in the lecture slides on functional programming. If you find it hard to install a particular language implementation on your computer, please post on LearnUs. CourseNana.COM