Recursion
Take-Home Lab #4 (CS1020 AY2010/11 Semester 2)
Date of release: 29 March 2011, Tuesday
Submission deadline:  3 April, Sunday 23:59hr
School of Computing, National University of Singapore

0 Introduction

Take-home labs are not graded and are for your own practice. Your lab tutor may discuss some of the exercises with you in odd weeks' lab sessions if necessary. Please take note of the following issues before attempting the labs:

• Please download skeleton files from CourseMarker for each exercise. Upon completing an exercise, please submit your program to CourseMarker so that your program can be evaluated by testing data planted in CourseMarker server.
  
  
• Use CourseMarker as a tool to verify the correctness of your code. Therefore, please focus on the feedback of "Dynamic Tests" only and ignore other portions such as "Features" and "Typography".
  
  
• Do not use CourseMarker as a debugging tool. For this lab, the maximum number of CourseMarker submissions in each exercise is set to 20. You should design your own testing data and test your program thoroughly before submitting to CourseMarker. This will help you in sit-in labs where you have no instant feedback from CourseMarker.
  
  
• You should use println() instead of print() for the last line of output your program generates.
  
  
• You should not create and use multiple instances of Scanner class (multiple scanner objects doesn't work with CourseMarker).
  
  
• You may assume that all input data are correct. Hence you do not need to do input data validation. This is always true throughout all take-home and sit-in labs unless otherwise specified in an individual exercise.
  
  
• You will be awarded 1 mark for this take-home lab, provided that (1) you have physically attended the lab session; (2) you have submitted all exercises before deadline; (3) you have shown genuine effort in your programs.
  
  
• Please use IVLE discussion forum as the media to discuss take-home labs. Raise your questions and discuss your problem solving approaches there if applicable. But do not post your solutions (partial or complete) in the forum.
  
  
• Please take care of the coding style of your programs as this is one of an evaluation criteria in each sit-in lab.

This lab requires you to do two exercises. You are advised to review the materials covered in lecture 8 recursion before attempting this lab assignment. You should not use syntax or constructs not yet covered in lectures.

1 Exercise 1: Top 2 Values

1.1 Learning objectives

• Recursion
• Logic thinking

1.2 Task statements

You are to Write a recursive method that finds the top 2 values in an unsorted array a[] of integers, where the array and its size are given as parameters. Note that the array may contain duplicate values.

Modify the skeleton file TopTwo.java for the above task.

Check sample runs for input and output format; submit your program through CourseMarker.

1.3 Sample runs

Four sample runs are shown below using interactive input (user's input shown in blue; essential output shown in bold purple).

$ javac TopTwo.java
$ java TopTwo
Enter the size of the array: 2
Enter array values: 5 11
top = 11, 2nd top = 5

Enter the size of the array: 6
Enter array values: 11 72 81 -108 81 14
top = 81, 2nd top = 81

Enter the size of the array: 6
Enter array values: 2 5 7 3 6 9
top = 9, 2nd top = 7

Enter the size of the array: 9
Enter array values: 2 5 7 9 10 5 10 3 10
top = 10, 2nd top = 10

1.4 Estimated development time

The time below is an estimate of how much time we expect you to spend on this exercise. If you need to spend a lot more time than this, it is an indication that some help (or more practice) might be needed.

• 80 minutes

1.5 For your own exploration

As the question is not easy, you are allowed to modify the skeleton file in any "unauthorized" way if you really can't figure out the idea of the designer. Discuss with your lab tutor for more.

2 Exercise 2: V Shape

2.1 Learning objectives

• Recursion
• Logic thinking

2.2 Task statements

Write a recursive method that print an input string in a reverse "V" shape and then a "V" shape as below:

• If the input string is "1234567" which has an odd number of characters, then the output is:

***4***
**3*5**
*2***6*
1*****7
1*****7
*2***6*
**3*5**
***4***

• If the input string is "abcdef" which has an even number of characters, then the output is:

**cd**
*b**e*
a****f
a****f
*b**e*
**cd**

Complete VShape.java for the above task.

Check sample run for input and output format; submit your program through CourseMarker.

2.3 Sample run

Two sample runs based on above sample1.data is shown below using interactive input (user's input shown in blue; essential output shown in bold purple).

$ javac VShape.java
$ java VShape
Enter a string: abcdef
**cd**
*b**e*
a****f
a****f
*b**e*
**cd**

Enter a string: bb
bb
bb

2.4 Estimated development time

The time below is an estimate of how much time we expect you to spend on this exercise. If you need to spend a lot more time than this, it is an indication that some help (or more practice) might be needed.

• 120 minutes

2.5 Important Note

You may find this exercise quite difficult. In that case, discuss with your lab tutor for ideas and approaches.