Tasks
Q1: Array Application Programming: - A tiny programming project
mimicking Lotto’s award checking system
(1) Function 2: This function has an interface where a player can check his/her winning
status (i.e., whether or not he/she is a lotto winner, of any class): When the player inputs
his ID number, say, k (1 k n), this function checks whether or not the player wins the
lotto, and print the following: Your Tasks:
Design algorithms and/or write Python code/s to implement the above tiny “lotto”
system. For practice purpose, you may assume n = 1000.
The system starts with the initialization stage. It generates the winning number
sequence (and stores them in the array WinNum[0…5]), and all players’ game -
numbers (and stores them in the array lotto[0…n -1][0…5]). A pre -processing step
follows to sort array WinNum[0…5] and the game -numbers for each player (see
below further requirement). After that, the system waits for user’s input to do either
Function 1 or 2 (as described above).
Further requirements are:
a) Sorting (as in pre-processing stage):
To reduce the searching costs, all arrays must be sorted in the initialization
stage. For practice purpose, you are requested to
i). use Insertion-sort algorithm to sort the array WinNum[0…5]; and
ii). use Merge-sort algorithm to sort the game-numbers for each player, that
is, sort array lotto[i -1] [0…5]) for i = 1, 2, …, n;
b) Searching (as in Function 1):
Develop an algorithm to do Function 1: You may use binary-search or
linear-search algorithm (or develop your own algorithm) as a part of your
algorithm. For each payer i, determine if he/she is a winner. This can be done
by searching each data item x ϵ lotto[i-1][0…5] from array WinNum[ ], and then
further determine how many components of lotto[i-1][ ] match that of
WinNum[ ]. By this way you can not only determine if the play i is a winner but
also determine which class of winner he/she is, if any.
And finally, collate data from this process and complete the Winners
statistics table.
c) Player’s wining status check (as in Function 2):
i). You are requested to design an algorithm, CommonValue (A, B), that
compares the two sorted integer arrays A and B and returns the
number of values that are contained in both arrays (i.e., common
values of A and B). For example, if A[ ] = {2, 5, 7, 9, 10} and B[ ] = {7, 8,
10, 16, 22, 31, 44}, the execution of CommonValue(A, B) would return
2, as two values (i.e., 7, 10) are contained in both A and B.
(Hint: modify the array-merge-algorithm (see Module 3) to complete the
al gorithm, whic h c ompares eac h pair of c omponents, one from eac h array, and
increment the count if the two components/values are equal)
ii). Complete Function 2 by using the above
CommonValue( ) algorithm.
For an input value k, this function calculates the
number of game numbers of player k (i.e., that
contained in the WinNum[ ]) thus to determine if
player k is a game winner (and for yes, which
class of winner). This calculation task can be
completed by calling CommonValue(lotto[k-1],
WinNum).
Once done, you may print/display the related
output as described in Function 2.
d) Algorithm analysis:
Analyse the CommonValue algorithm that you developed
for Function 2 (in above step c) i) and c) ii)), using big-O
notation.