GROUP ASSIGNMENT PROPOSAL

TECHNOLOGY PARK MALAYSIA

CT077-3-2 DSTR

DATA STRUCTURES

APD2F2106CS(IS)

HAND OUT DATE: 13 – DECEMBER - 2021

HAND IN DATE: 21 – FEBRUARY - 2022

WEIGHTAGE: 50%

Brian Lamri See TP056199

Ong Chong Xian TP055766
Sim Yoke Shin TP059851
Introduction
This proposal documents the proposed system design for the inventory management system
for Grandplex Cinema. The system design will centre around two main components which
are the inventory and transactions of the cinema. The inventory will include items sold in the
cinema from movie tickets and movies to food and beverage as well as movie merchandises.
Information stored in the inventory the product name, price, stock quantity and other relevant
information. Other than that, the records of transaction would also be stored and managed in
the system. Information such as the total paid price, product purchased, purchased quantity
and purchase time and date will be recorded for every transaction.

Data Structure
Array
The development team chose array as the data structure to store data for the inventory
component in the proposed system. This decision was based on the consideration that action
performing insertion or removal of item from the inventory will be less frequent compared to
accessing items from the inventory. Since the array data structure allow random access of
element in the array in constant time when the address of the element was known, it was a
suitable data structure for the implementation of inventory which would be frequently
accessed to get or change the quantity value. To achieve time complexity of constant time,
O(1) when accessing an element in the array, the address of the products would match the
product ID, eg: P00001 is first element of the array etc. Implementation of sorting algorithm
in arrays would also be easier for the development team.
Quick sort
The development team propose to implement quick sort algorithm to sort data stored in the
array data structure. Quick sort is a divide and conquer algorithm which solves a problem by
dividing the problem into smaller sub problems and further divide the problem until the base
case was reached. The main idea of quick sort is the array will be partitioned recursively. One
element in the array will be chosen to be the pivot and elements greater than the pivot will
move to the right side of the pivot while elements smaller than the pivot will move to the left
side of the pivot. The two groups of sub elements were then partitioned within themselves
repeatedly until the base case was reached where only one element was left.

The best and average time complexity of quick sort is O(nLogn) while the worst time
complexity could be O(n2 ). The worst case would happen if the pivot chosen each time was
the smallest or largest value in each recursive call however it rarely happens and can be
avoided by randomizing the choice of pivot. Quick sort is suitable for sorting array as it is an
in-place sort which does not require additional storage unlike merge sort. It is also cache
friendly where it has good locality of reference where it accesses the memory block of the
array using the pointers. It being tail recursive allows tail call optimization to be done to
further improve the computational complexity.
Doubly Linked list
Next, the team opted for doubly linked list as the data structure to implement the transactions
component of the proposed system. This choice was made because linked list allow insertion
of element at constant time where a new node can be directly inserted at the head or the tail
of the list. Insertion of new elements would happen more frequently in the case of the cinema
transactions record whenever a purchase happens and new transactions detailing the purchase
details will be saved. Using a doubly linked list would also improve the flexibility of the
development process and make the implementation of the data structure easier for the team as
the pointer to the previous and next node can be utilized to traverse the linked list in both
directions.
Merge sort
Merge sort is another divide and conquer algorithm. It divides the input array into two halves
and call recursively for the two halves until the base case was reached and then merge the
two sorted halves into the original size.

Its time complexity for all three worst, average and best case are O(nLogn). This sorting
algorithm is useful for sorting linked list. Since linked list allow element to be inserted in the
middle of the list in O(1) time, the merge operation of merge sort can be implemented with
better time complexity and without extra space unlike arrays where time complexity for
insertion of elements is O(n) in the worst case. Even though linked list has a high time
complexity of accessing elements in the links (O(n) in worst case), it was less relevant in
merge sort operation as the algorithm accesses data sequentially and the need of random
access is low.
System Design and Workflows
Add product
addProduct()

Start

Print ͞Please
enter the
Product id͟

Read Input

Print ͞The input

If Product id
Yes product id has exist
exist?
please again.͟

No

Print ͞Please
enter the
Product Name͟

Read Input

Print ͞Please
enter the
Category͟

Yes
Read Input

Print ͞Please
enter the
Supplier͟

Read Input

Print ͞Please
enter the Price͟

Read Input

Print ͞Please
enter the Cost͟

Read Input

Print ͞Please
enter the
Quantity͟

Read Input

Add another
Save Product Info
product?

No

End
Display product

Start

Print
inventory list

Print ͞Enter
product id to No
view product
info͟

Read Input

If product id
exist?

Print ͚product info͛

by product id

Print ͞Enter
0 to exit
1 to back to
main menu͟

Read Input

End
Product search

Start

Print ͞Enter
keyword to No
search͟

Read Input

If similar word
exist?

Yes

Print ͚product info͛

Print ͞Enter
0 to exit
1 to back to
main menu͟

Read Input

End
Category filter
Filter Product()

Start

Print
inventory list

Print ͞Filter product by:

0-category, 1-price, 2-
quantity͟

Read Input

Input = 0 OR 1
OR 2?

0 2
1

Print ͞Select product Print ͞Enter

category to filter: Print ͞Enter price quantity range
1.Movie range to filer. to filer.
2.Food and beverage Max: ͟ Max: ͟
3. Movie merchandise͟

Read max Read max

price quantity
Read
1
category

Print ͞Min: ͟ Print ͞Min: ͟

If product
category equal Read min Read min
category price quantity

yes

Print product
no If product price smaller than If product price smaller than
max price and greater than max quantity and greater than
yes min price min quantity

yes
yes

Print product
no Print product
no
Remaining
product not
filtered yes yes

Remaining
product not Remaining
filtered product not
filtered

no

no
no

Print ͟Enter
1 to filter Input equals 1 or
Read input 0 End
again, 0 to 0
exit͟
Update product

Start

Print ͞Enter
the product
id to select
which item
to edit͟
No

Read Input

Is product exist?

Yes

Print ͞Please
enter the
Product Name͟

Read Input

Print ͞Please
enter the
Category͟

Read Input

Print ͞Please
enter the
Supplier͟

Read Input

Print ͞Please
enter the Price͟

Read Input

Print ͞Please
enter the Cost͟

Read Input

Print ͞Please
enter the
Quantity͟

Read Input

Update Product Info

End
Sort Product

sortProduct()

Start

Print
inventory list

Print ͞Sort product by:

0-category, 1-product
name, 2- quantity͟

Read Input

Print ͞Invalid input!

Input = 0 OR 1
No please enter number Ϭ-
OR 2?
Ϯ͘ ͟

Yes

Print inventory list

Input = 0 Yes
No sort by category
Yes

Input = 1
Yes
No

Print inventory list Print inventory list

sort by quantity sort by product name

Want to sort product

in other way?

No

End
Delete product

Start

Print ͞Enter
the product
id to select
which item
to delete͟

No

Read Input

Is product exist?

Yes

Print ͚product info͛

Print ͞Do you

confirm this is
the item you
wish to delete 0-
yes, 1-no.͟

Read Input

End
Add purchase
addPurchase()

Start

Print ͞Please
enter the
Purchase id͟

Read Input

Print ͞The input

If Purchase id
Yes product id has exist
exist?
please again.͟

No

Print
Inventory

Print ͞Please
enter the
Product id͟

Read Input

Yes

No

Print ͞The input

If Product id
No product id does not
exist?
exist please again.͟

Yes

Print ͞Please enter

the Quantity͟

Read Input

Add another
Save Purchase
product into
Details
cart?

No

Do you confirm to place

order?

Yes

Print Ā Please enter

buyer nameā

Read input

Count Total Price

Print Total Price

Save Purchase
Record

End
View purchase

ViewPurchase()

Start

Read Purchase
Record

Print Purchase
Record

Print ͞Enter
0 to exit
1 to back to
main menu͟

Read Input

End
Sort purchase

sortPurchase()

Start

Print purchase
record

Print ͞Sort purchase

record by:
0-purchase id , 1- total
price͟

Read Input

Print ͞Invalid input!

Input = 0 OR 1? No please enter number 0
or ϭ͘ ͟

Yes

Print purchase record

Input = 0 Yes Yes
sort by purchase id

No

Print purchase record

sort by total price

Want to sort
purchase record in
other way?

No

End
Purchase detail
Work Breakdown Structure

Task Brian Lamri See Ong Chong Xian Sim Yoke Shin
TP056199 TP055766 TP059851

Documentation 80% 10% 10%

Flowchart 20% 40% 40%