TEMASEK POLYTECHNIC

SCHOOL OF INFORMATICS & IT

AY2018/2019 OCTOBER SEMESTER (LEVEL 1)
DATA STRUCTURE AND ALGORITHM (CIT1C14)

PROJECT 1 (80%)

This is an individual assignment. Your submission must not contain any plagiarized materials
and source code.

Objectives
This assignment requires students to put into practice the various topics covered so far in data
structures and algorithms.

PART A (50%)

Start: Week 2 Due: 11 Dec 2018, 12 noon

1. Inverse Insertion Sort (4%)

Recall how the Insertion Sort works. It starts from the left of the list and sorts up to
where the counter is. Modify the Insertion Sort such that it starts from the right of the
list and sorts until where the counter is.

def insertionSort(list):
for index in range(1, len(list)):

currentvalue = list[index]
position = index

while position > 0 and list[position - 1] > currentvalue:

list[position] = list[position - 1]
position = position - 1

list[position] = currentvalue

list = [88, 90, 5, 19, 23, 41, 2, 83, 60]

insertionSort(list)
print(list)

2. Search Algorithms (8%)

Consider the following array:

12B 6D 4C 8D 34A 18C 78D 10A 9B 17E 55A

Note : A, B, C, D and E refer to one of the last five digits of your student’s admin
number. For example, the last five numerical digits are 32605, so A = 3, B = 2, C = 6, D
= 0 and E = 5.
 a. Show with the aid of a series of diagrams to search for the number 177 using Binary
Search algorithm. Do note that calculation of middle for each iteration at each step
should be shown.

b. Analyse the efficiency of Sequential Search and Binary Search algorithms. No

coding or illustration with program is needed.

3. Mystery Gift Vending Machine (10%)

There is a mystery gift vending machine in Wonder Mall which dispenses a random
gift upon receipt of payment in cash.

Write a prototype program (in Python) that will simulate the mystery gift vending
machine using stack data structure. No other data structures is allowed for this
question.

The program will have a stack data structure with 8 gifts pushed to it as below.

No. Gifts
1 iPhone XS
2 Wireless Headphones
3 Stuffed Bunny Toy
4 Nike Cap
5 Silver Heart Pendant
6 Happy Birthday Photo Frame
7 Gadget Key Chain
8 Smart Watch

The vending machine will display the list of gifts so as to attract buyers.

Upon receiving payment, it will generate and display 3 different random gifts. This is
to create suspense and excitement.

After which, it will dispense the mystery gift which is 1 of the 3 gifts displayed earlier.

At the end of the game, it will display the remaining gifts in the machine in the same
order as before.

Use logic compound statement learnt in LOMA to construct the condition for
generating 3 different random numbers. Use sequence and recursion learnt in LOMA
to construct an appropriate loop that allows the machine to dispense the mystery gift
and displays the remaining gifts in the machine.

Sample Output:
~ Mystery Gift Vending Machine ~
1 - iPhone XS
2 - Wireless Headphones
 3 - Stuffed Bunny Toy
4 - Nike Cap
5 - Silver Heart Pendant
6 - Happy Birthday Photo Frame
7 - Gadget Key Chain
8 - Smart Watch

You will get one of these gifts below.

Nike Cap
Stuffed Bunny Toy
Wireless Headphones

Your gift is Wireless Headphones!

Here are the remaining gifts.

1 - iPhone XS
2 - Stuffed Bunny Toy
3 - Nike Cap
4 - Silver Heart Pendant
5 - Happy Birthday Photo Frame
6 - Gadget Key Chain
7 - Smart Watch

4. National Data Analytics Challenge (8%)

National Data Analytics Challenge is conducted annually to recognise and award

individuals who excel in the area. It consists of preliminary and final rounds. During
preliminary round, those who scored at least 50% will qualify for the final round. The
participants in the final round will be awarded the following medals based on their
individual scores.

Score range (%) Medal

80 to 100 Gold
60 to 79 Silver
40 to 59 Bronze

Your program will do the following:

a. Add 10 participants’ names to a queue on a first-come-first-served basis.
b. During preliminary round, display the name of each participant from the queue
and generate a random number, score1 which can be 0 to 100 inclusive and
that will be the score for this round. Display the score next to the participant’s
name. If the score is 50 and above, add the participant’s name to another
queue named “finalQ”.
c. During final round, display the name of each participant from the “finalQ”
queue and generate a random number, score2 which can be 0 to 100 inclusive
and that will be the score for this round. Display the score and the medal if
there is any next to the participant’s name.
d. After the final round, display the following statistic:
 • average/mean score (to one decimal point) for preliminary round
• percentage of participants (to one decimal point) getting into final
round
• number of participants getting a medal

This question requires logic, and sequence and recursion learnt in LOMA and statistics
in DANA.

Sample Output:
Preliminary round starts ...

Participant #1: Ada - 8

Participant #2: Bala - 44
Participant #3: Chloe - 48
Participant #4: Dylan - 82
Participant #5: Elvin - 30
Participant #6: Fadhilah - 58
Participant #7: Gwendolyn - 73
Participant #8: Hakim - 58
Participant #9: Ian - 76
Participant #10: Jeremy - 38

Final round starts ...

Participant #1: Dylan - 41 - Bronze

Participant #2: Fadhilah - 21
Participant #3: Gwendolyn - 14
Participant #4: Hakim - 10
Participant #5: Ian - 93 - Gold

The average/mean score for preliminary round is 51.5.

The percentage of participants getting into final round is 50.0.

The number of participants getting a medal is 2.

5. Conversion Using Recursion (6%)

Modify the following Bubble Sort code such that it uses recursion and achieves the
same output as its other counterpart.

Run the list at the end of the code to ensure that your program works.

This question requires logic, and sequence and recursion learnt in LOMA.

def bubbleSort(list):
for i in range(len(list)-1,0,-1):
for j in range(i):
if list[j] > list[j+1]:
 temp = list[j]
list[j] = list[j+1]
list[j+1] = temp

list = [72, 56, 93, 8, 22, 41, 88, 23, 60]

bubbleSort(list)
print(list)

Do note that your function should only take in a list and the size of the list as
parameters.

***** End of Project 1 Part A *****

Part A Status Report (5%)

The status report must be typed-written using Microsoft Word with 1 inch margin all round,
portrait, Times New Roman font, size 12, single line spacing. Proper English MUST be used for
the writing of report.

Write a short summary of the final state of your assignment in a file called
Status_<YourName>_<AdminNumber>.doc.
E.g. Status_LimChuKang_1809115J.doc.

Your report should include the following:

• The assumptions made.
• Any question you did not complete with reasons for not completing the questions.
• Any problems you encountered while doing the assignment and how you go about
resolving them.
• Any improvements / additional features attempted. Explain the rationale of having
them. No marks will be given if you did not provide any convincing reason for having
the improvements / additional features.

Marking Scheme for assignment submission

Total: 50%

Part A %
1. Inverse Insertion Sort 4
2. Search Algorithms 8
3. Mystery Gift Vending Machine 10
4. National Data Analytics Challenge 8
5. Conversion Using Recursion 6
Programming Style (Documentation/Comments) 3
Additional features/ Efficient code 6
(One additional feature be awarded 1 mark)
Report 5
Total 50
Deliverables

There are a total of THREE items which you need to submit as follows:

1) An individual, typewritten report satisfying the following criteria:

a) Status Report with its cover page as shown in Appendix 1, which can be found at the
end of this assignment specification.

b) All answers are accompanied by detailed computations and workings (e.g. tables,
diagrams, etc.). Include answers for Q2.

2) Program/Coding files

3) A signed declaration of work originality bearing your signature in hardcopy

Method of Submission

The report and the program/coding files must be compressed into a .zip file and labeled as
[your_matric_no].zip. (E.g. 1801234A.zip). Please do not use other file compression methods
(e.g. rar).

This zip file must be submitted electronically to TP-LMS before the deadline.

Penalty

You will be penalised for the following:

syntax, link and runtime errors (so test early and test often!)

lack of comments and missing header comments

poor programming styles (including indentation, variable naming etc.)

poorly written/formatted status report

late submission

plagiarised or copied work.

Penalty for Late Submission Without Valid Reasons

late and <1 day : 10% deduction from absolute mark given for the component
late>=1 and <2 days : 20% deduction from absolute mark for the component
late>=2 days : No marks awarded
Note that “day” includes non-working days (Sat, Sun and public holidays).
General MC/LOA is NOT considered as valid reason for extended assignment submission.

***** End of Project 1 *****

 Appendix 1: Report Template

Temasek Polytechnic
School of Informatics & IT

Diploma in [Your Diploma Name]

AY 2018/2019 October Semester

Data Structures and Algorithms (DSAG)

CIT1C14
Project 1 Part A Report

Name (As in Class Register)

Matric Number
Tutorial/Lab Group
Introduction

This section should include:

1. Can your code be executed without error? If not, state the errors.
2. What grade do you think you should deserve? State your reason.
3. What could you have done to achieve better grade?

Assumptions

This section should include your assumptions made for your solutions and reason why you
need such assumptions.

Additional features

This section should include:

1. What are the additional features?
2. Are they useful?
3. How to test them?

Include the solutions for Q2

Process and steps to complete the project

This section should include:

1. How did you start the project? When? Did you make any plan?
2. How did you do? State steps or processes went through.
3. How to improve in the future? What are the steps and processes that you want to
know more?

Problem faced and solution

This section should include:

1. State any problem you have encountered
2. Explain how you managed to solve them.
3. What did you learn from these problems?

References

This section should include:

1. State clearly if you use any references to complete this assignment: Book? Website?
Note? Tutorials?
2. State clearly if you receive help from any of your friend or classmate (who are they?
What kind of help?)
3. State clearly which lecturer/tutor did you come for help? Are they helpful?
 Appendix 2

Declaration of Work Originality

Diploma in Information Technology

Diploma in Cybersecurity & Digital Forensics
Diploma in Game Design & Development
Diploma in Big Data & Governance
Diploma in Business Intelligence & Analytics
Diploma in Financial Business Informatics

Data Structures and Algorithms (CIT1C14)

AY2018/2019 Oct Semester

Practical Class: P0X

Submitted by:
<Matric number of student > <Full name of student>

Date: <signing date in dd /mm/yyyy format>

“By submitting this work, I am / we are declaring that I am / we are the originator(s) of
this work and that all other original sources used in this work has been appropriately
acknowledged.

I / We understand that plagiarism is the act of taking and using the whole or any part of
another person’s work and presenting it as my/ our own without proper
acknowledgement.

I / We also understand that plagiarism is an academic offence and that disciplinary action
will be taken for plagiarism.”

Name and Signature of student: ……………………………………