SULIT
Second Semester Assessment
2019/2020 Academic Session
CPT212 – Design and Analysis of Algorithms
Online Case Study
Release Date: 6th July 2020 (12:00am) Due Date: 19th July 2020 (11:59pm)
Objectives
This project evaluates your capability in applying algorithms in practical applications. You must choose appropriate algorithms or techniques for the given case studies, execute or trace those algorithms to find solutions, and discuss your findings.
This is an individual project whereby each student must submit ONE report. There is no need to submit program codes.
Instructions
1. You are given THREE (3) different case studies to examine. For each case study, there will be a problem that needs to be solved using one of the algorithms or techniques that you have learned in CPT212.
2. You are required to investigate various algorithms or techniques to solve the problem and choose one. You will need to provide strong justifications for your choice.
3. You will then need to discuss the solutions that you have found by providing appropriate examples and experimental results.
4. You may use algorithms discussed in CPT212 or other algorithms that you have found elsewhere.
5. Please refer to marking rubrics for more details.
Report Specifications
There is no specific format for the report, but it MUST contain the following information:
a. Font: Times New Roman (10), Single-Spacing (1.0)
b. Content:
a. Case Study I
b. Case Study II
c. Case Study III
c. You may add pseudocodes or diagrams to support your explanations
d. Maximum number of words: 1500 (500 words per case study). There is a penalty of 1% per word exceeding 1500.
Eve operates a chain of pharmacies throughout Malaysia. Each of her employees are assigned ID numbers that consists of numbers and characters. Several samples are given below:
AA00000001
AA00000002
.
.
.
ZZ99999999
Eve wants to map her employee IDs to their e-mail addresses to be stored in a hash table. Several samples are given below:
Employee ID Employee Email Address
AA00000001 bob@gmail.com
AA00000002 brad@hotmail.com
.
.
.
ZZ99999999 zainor@yahoo.com
How can Eve efficiently store all her employee information in a hash table that has a fixed length?
Bob owns a company with several office buildings in several cities. He wants to connect those office buildings with phone lines. The phone company charges different amounts of money to connect different pairs of cities. The phone lines will be constructed along valid roads in Penang. The charge is RM100 per kilometer.
Bob’s offices are located at Bayan Lepas, George Town, Gelugor, Balik Pulau and Bayan Baru.
Help Bob find a way to minimize the cost of setting up the phone network for his company.
Tip: You may use Google Maps to assist you in finding the distances between the various offices.
Alice is a programmer working in a country with limited internet bandwidth. She wishes to apply text compression to reduce the size of her work so they can be sent to her colleagues while using up minimal bandwidth. She has a choice between sending pseudocodes or her actual C++ source codes. However, she is not sure of which type of text compression method to use.
Help Alice decide on a text compression method to use. Also, help her determine whether it is more efficient to send compressed pseudocodes or the compressed C++ source code (assuming they have the same number of characters).
Rubric (100%) – LO3/PO3
Category Weak (0-3%) Average (4-6%) Good (7-10%)
Algorithm/Technique
Investigation and
Justification (Case Study I) Incorrect or unsuitable algorithm/technique selected for the given problem Suitable
algorithm/technique
selected with some justification or reasoning for selection Suitable
algorithm/technique
selected with strong justification or reasoning for selection
Experimental
Results/Examples (Case
Study I) Invalid examples provided for the given problem Simple examples provided for the given problem Detailed examples provided for the given problem
Analysis/Discussion (Case Study I) Incorrect results or lack of discussion Results are correct with some discussion being provided Results are correct and an in-depth discussion that indicates a deep understanding of the
problem being solved
Algorithm/Technique
Selection and Justification
(Case Study II) Incorrect or unsuitable algorithm/technique selected for the given problem Suitable
algorithm/technique
selected with some justification or reasoning for selection Suitable
algorithm/technique
selected with strong justification or reasoning for selection
Experimental
Results/Examples (Case
Study II) Invalid examples provided for the given problem Simple examples provided for the given problem Detailed examples provided for the given problem
Analysis/Discussion (Case
Study II) Incorrect results or lack of discussion Results are correct with some discussion being provided Results are correct and an in-depth discussion that indicates a deep understanding of the
problem being solved
Algorithm/Technique
Selection and Justification
(Case Study III) Incorrect or unsuitable algorithm/technique selected for the given problem Suitable
algorithm/technique
selected with some justification or reasoning for selection Suitable
algorithm/technique
selected with strong justification or reasoning for selection
Experimental
Results/Examples (Case
Study III) Invalid examples provided for the given problem Simple examples provided for the given problem Detailed examples provided for the given problem
Analysis/Discussion (Case
Study III) Incorrect results or lack of discussion Results are correct with some discussion being provided Results are correct and an in-depth discussion that indicates a deep understanding of the
problem being solved
Overall Report Poorly written and difficult to understand, with more than 20 identifiable
grammatical/spelling errors Decently written and easy to understand, with 10-20
identifiable
grammatical/spelling errors Well-written, clear, and precise, with less than 10 identifiable
grammatical/spelling errors
GET ANSWERS / LIVE CHAT