CST 370 – Homework 2

CST 370 –
Homework 2

How to turn in? 
•    Write your answer to the question 1 and 2 and submit it on the iLearn. Note that we accept only a PDF file. Do not submit a different file format. Also, don’t forget to write your name and class ID at the top of your homework document.
•    For the questions 3 and 4, you should submit two source programs (hw2_1.cpp and hw2_2.cpp) on the iLearn. Note that you can use the Java for the homework such as hw2_1.java and hw2_2.java.
•    Thus, you have to submit three files (one PDF file and two source files) on the iLearn.


1. Assume that you should search a number in a list of n numbers. How can you take advantage of the fact that the list is known to be sorted? Give separate answers for the following two cases. 

(a) A list represented in an array.

(b) A list represented in a linked list.



2. Assume that you have 10 identical-looking balls and a two-pan balance scale with no weights. One of the balls is a fake, but you don’t know whether it is lighter or heavier than the genuine balls, which all weigh the same. Describe your idea to determine in the minimum number of weighings whether the fake ball is lighter or heavier than the others. In the problem, you don’t need to identify the fake ball itself. It’s good enough for you to just say “It’s heavier or lighter”. Present the minimum number of weighings and your answer clearly.




 
===========================================================================

This is the HackerRank link: https://www.hackerrank.com/cst370-s20-hw2


3. Write a program called hw2_1.cpp (or hw2_1.java) that reads a positive integer number from a user and displays the reverse of the number. For the program, you can assume that the input number is in the range of the typical “int” data type.

Sample Run 0: Assume that the user typed the following number.

1234321

This is the correct output. 

1234321


Sample Run 1: Assume that the user typed the following number.

425

This is the correct output.

524


Sample Run 2: Assume that the user typed the following number.

1200

This is the correct output. Note that the reverse of 1200 is not 0021. It should be 21 because we should remove the leading zeros.

21




 
4. Write a program called hw2_2.cpp (or hw2_2.java) that reads two timestamps of two events from a user and displays the difference between the two timestamps. For the program, you can assume that each timestamp is composed of the hour (0 ~ 23), minute (0 ~ 59), and second (0 ~ 59) format. Your program should present the difference from the second event (= second timestamp) to the first event (= first timestamp). Note that the second event always happens after the first event and your program should display the time difference of the events.

Sample Run 0: Assume that the user typed the following two lines.

18:45:30
20:50:59

This is the correct output of your program.

02:05:29


Sample Run 1: Assume that the user typed the following two lines.

20:18:59
04:25:17

This is the correct output of your program.

08:06:18


Sample Run 2: Assume that the user typed the following two lines.

02:00:25
15:30:00

This is the correct output of your program.

13:29:35