Project 1 (v1.1)

 

Release: 21 Feb 2018 (Wed, Week 7)

Due: 7 Mar 2018 (Wed, Week 9) 23:30 hrs.

 

(Differences between this document & v1.0 are highlighted in yellow)

 

Please read:

 

Despite this being an individual assignment, you are allowed to discuss your IDEAS with your classmates. However, you are expected to come up with your implementation INDEPENDENTLY. Moreover, you should not show/distribute your CODE solutions to anyone explicitly (e.g. via email) or implicitly (e.g. post at a website for all to see). We will run your write-up through plagiarism checkers and will take disciplinary action against offenders.

 

Instructions:

 

• There are three questions in this project to be completed individually.
• Your team ID is your name (i.e. you are the only member in your team).
• You need to submit code for this exercise to red.smu.edu.sg, and a written component to the eLearn Assignment Folder. Read “Administrative Instructions” at the end of this document.

 

 

Q1: Simple Arithmetic

When adding two multi-digit numbers, children are taught to add from right-to-left one digit at a time. Many find the “carry” operation – in which a 1 is carried from one digit position to be added to the next – to be a significant challenge. Your job is to count the number of carry operations for adding a pair of integers so that educators may assess the difficulty.

Create a function with the following specification:

simple_arithmetic(num1, num2)

With the following parameters:

• num1, num2: Positive integers to be added together. Note that the number of digits for num1 and num2 might be different.

The function should return an integer, indicating the number of carry operations required for adding num1 and num2.

Here are some test cases:

# Test Case 1:

simple_arithmetic(123, 456)

=> 0

 

# Test Case 2:

simple_arithmetic(555, 555)

=> 3

 

# Test Case 3:

simple_arithmetic(9999, 9)

=> 4

 

 

Q2: Light Watcher

There are n light bulbs along a long corridor, where each bulb is independently controlled by a toggle switch. At the beginning of the day all light bulbs are at the off status. To begin the day, a light watcher would walk along the corridor back and forth n times and in the i ^th walk he toggles only the switches whose ID is divisible by i. He does not press any switch when coming back to his initial position. An i ^th walk is defined as going down the corridor (while toggling switches) and coming back again. After the light watcher finishes his daily routine, we want to know the status of any given light bulb. Write a function to answer that.

Create a function with the following specification:

light_watcher(n, j)

With the following parameters:

• n: The number of light bulbs along the corridor. Also the number of times the light watcher will walk.
• j: The light bulb ID (in the range of 1…n) which we would return the status for.

The function should return 0 if the status of light bulb j is off, and 1 if the status is on.

For example, the following table shows the statuses of each light bulb after each walk. Assume that n is 5 (there are 5 light bulbs with IDs 1, 2, 3, 4 and 5):

i th walk	Bulb IDb IDBulb ID
Value of i	1	2	3	4	5	Comments
0	0	0	0	0	0	All switches are “off” at first.
1	1	1	1	1	1	All switches are toggled since 1, 2, 3, 4, 5 are all divisible by 1.
2	1	0	1	0	1	Only bulbs 2 & 4 are toggled since only 2 & 4 are divisible by 2.
3	1	0	0	0	1	Only bulb 3 is toggled since only 3 is divisible by 3.
4	1	0	0	1	1	Only bulb 4 is toggled since only 4 is divisible by 4.
5	1	0	0	1	0	Only bulb 5 is toggled since only 5 is divisible by 5.

Therefore, we can use row i = 5  to answer the status of any bulb ID (from 1 to 5). So, according to the table above:

• light_watcher(5, 1) should return 1
• light_watcher(5, 2) should return 0
• light_watcher(5, 3) should return 0
• light_watcher(5, 4) should return 1
• light_watcher(5, 5) should return 0

Q3: Choosing Bin Colors

All townships around Singapore are now coming up with their own schemes for coloring recycling bins. The bins come in 5 different colors — red, orange, yellow, green and blue — and 5 types of waste have been identified for recycling — Plastic, Glass, Aluminum, Steel, and Paper. Obviously there has been no coordination between townships, so each township has allocated waste to bins in an arbitrary fashion.

The authority now wants to come up with a standardized color scheme for recycling bins by choosing the scheme adopted by one of the townships; however, it wants to minimize the impact caused. The impact due to the change in the coloring scheme is defined as the number of color-waste assignments that needs to be changed. For example, the following table contains two schemes and the chosen standard scheme:

	red	orange	yellow	green	blue
Standard Scheme	Plastic	Steel	Aluminum	Glass	Paper
Scheme A	Plastic	Glass	Steel	Aluminum	Paper
Scheme B	Paper	Glass	Steel	Plastic	Aluminum

 

The impact for choosing the above scheme for A and B will be 3 and 5 respectively. (For Scheme A, the following 3 colors are affected: orange, yellow and green. For scheme B, all 5 colors are affected).

Create a function with the following specification:

choose_scheme(schemes)

With the following parameter:

• schemes: A two-dimensional array containing color schemes used by all townships, where scheme[i][j] refers to the assignment of waste to color j for township i. The list of colors (red, orange, yellow, green, blue) are represented by j= 0, 1, 2, 3, 4. The value of scheme[i][j] refers to the type of waste assigned to color j for township i. The list of waste (Plastic, Glass, Aluminum, Steel, and Paper) are represented by values 0, 1, 2, 3, 4. For example, for the Schemes A and B from the table above, the array schemes will be:

schemes = [[0,1,3,2,4], [4,1,3,0,2]]

The output of the function is the index of the color scheme that would cause the least impact.

Here is one test case explained in detail:

schemes = [[0,1,3,2,4], [1,0,3,2,4], [0,1,3,4,2], [0,3,2,1,4]]

choose_scheme(schemes)

=> 0

 

 

The following table shows the impact caused for choosing each index as the standard scheme.

Selected standard scheme	Impact
	0	1	2	3	Total
0	0	2	2	3	7
1	2	0	4	4	10
2	2	4	0	4	10
3	3	4	4	0	11

 

 

Therefore, choosing scheme 0 as the standard scheme results in the least impact.

 

 

 

 

Administrative Instructions:

• To be submitted by the deadline:
  • At red.smu.edu.sg: rb, q2.rb and q3.rb. Email submissions will not be accepted.
  • At eLearn (folder: “Project 1”): A single Word/PDF write-up that describes your algorithms for all three questions. Your write-up must not exceed two A4 pages (excluding cover sheet or references, if any) – i.e., a total of two pages for all three question (not 6 pages). Include a brief explanation of your algorithms and an analysis of the complexity of your implementation. Use diagrams and code extracts in your explanation if preferred. Your explanation must match the code that you have submitted. Remember to include any references (with URLs if available) that you may have used.
• This project is worth 10% of your course grade, and will be marked upon a total score of 18 marks:
  • Q1 code: 4 marks
  • Q2 code: 4 marks
  • Q3 code: 8 marks
  • Q1-3 write-up: 2 marks

 

• Late submissions of either the write-up or code will be penalized:
  • Late by <=1 hour: 10% of your score
  • Late by <=1 day: 25% of your score
  • Late by >1 day: will not be accepted.
• smu.edu.sg will stop accepting submissions at the deadline. Please contact Mok (telegram: @Mokkie) if you are submitting code late.

 

 

END