1 Learning Outcomes
In this assignment you will demonstrate your understanding of dynamic memory allocation, linked data structures, and search algorithms. You will further extend your skills in program design and implementation.
2 The Story…
There are around 16 million credit cards on issue in Australia,1 and the number is over 1 billion worldwide.2 This is a goldmine for cybercriminals who make unauthorised payment to obtain goods or services (i.e., credit card fraud). Worldwide losses from card fraud is expected to reach US$31 billion in 2020.3 Banks and card companies are strongly motivated to develop anti-fraud technologies. They prevented two-thirds of the attempted card fraud in the UK in 2018,4 but this is a never-ending battle.
There are various anti-fraud algorithms. The core of those algorithms are rules and statistics (machine learning algorithms) to classify whether a transaction is abnormal and likely to be fraudulent. For example, a transaction well beyond the credit limit of a card is likely to be fraudulent, and so are two transactions of the same card issued at almost the same time but from two different cities.
3 Your Task
In this assignment, you will write a program to process credit card and transaction records and identify fraudulent transactions. Note that you do not need to be an anti-fraud expert to complete this assignment. You are given a list of credit card records and transactions to be processed in the following format.
3tu2iywy 10000 800 ceww0p66 150 100 v0xyil5t 3000 500 vb3dtxp0 5000 300 xnwxw8tl 2000 800 %%%%%%%%%% v5buvljyh0lg vb3dtxp0 2020:04:07:03:50:45 42 1yuy3noa2uxu xnwxw8tl 2020:04:08:04:16:20 729 gl3utnnwxf49 xnwxw8tl 2020:04:08:05:39:00 670 9mopqy3snk3h ceww0p66 2020:04:15:08:06:49 86 6hjqaydtmrq5 vb3dtxp0 2020:04:15:10:09:50 213 mlgtqk8oo74e ceww0p66 2020:04:15:13:45:29 95 u7s604f0u6bz xnwxw8tl 2020:04:22:15:30:43 799 2siil57yqe5k vb3dtxp0 2020:04:23:17:26:20 573 vzdg2z09t7zp v0xyil5t 2020:04:29:18:03:00 3489 n6lcvjyrhvwt 3tu2iywy 2020:04:29:23:07:00 4592
1 https://www.aph.gov.au/Parliamentary_Business/Committees/Senate/Economics/Credit_Card_Interest/Report/c02 2 https://wallethub.com/edu/cc/number- of- credit- cards/25532/
3 https://theconversation.com/credit- card- fraud- what- you- need- to- know- 78542
4 https://en.wikipedia.org/wiki/Credit_card_fraud
1
The input starts with a list of credit card records sorted by card ID. There are at least 1 and at most 100 cards. Each credit card occupies one line with three fields separated by a single space: unique card ID (8 alphanumeric characters; no uppercase letters), daily limit (the total amount that can be spent in a day; a positive integer), and transaction limit (the amount that can be spent in a transaction; a positive integer). The transaction limit does not exceed the daily limit.
The line “%%%%%%%%%%” indicates the end of credit card records and the start of transactions.
The transactions are sorted by date and time. Each transaction occupies one line with four fields separated by a single space: unique transaction ID (12 alphanumeric characters; no uppercase letters), card ID (8 alphanumeric characters; no uppercase letters; must have appeared in the card records), transaction date and time (with format year:month:day:hour:minute:second, two digits for each component), and trans- action amount (a positive integer, for simplicity). There is no given limit on the number of transaction lines.
You may assume that the input data is always in valid format. No input format validity checking is needed.
3.1 Stage 1 – Reading One Credit Card Record (Up to 4 Marks)
Your first task is to design a “struct” to represent a credit card record. You will then read in a credit card record from the input data, and output it in the following format.
=========================Stage 1========================= /* 25 ‘=’s each side */ Card ID: 3tu2iywy Daily limit: 10000 Transaction limit: 1000
3.2 Stage 2 – Reading All Credit Card Records (Up to 8 Marks)
Next, continue to read all credit card records. You need to design a proper data structure to store the records read. An array will do the job nicely. When this stage is done, your program should output: the total number of credit card records read, the average daily limit per card (up to two digits after the decimal point, by using “%.2f” in printf()), and the credit card with the largest transaction limit (if there is a tie, print the card with the smallest ID). The output of this stage based on the sample input is as follows.
=========================Stage 2========================= Number of credit cards: 5 Average daily limit: 4030.00 Card with the largest transaction limit: 3tu2iywy
3.3 Stage 3 – Reading the Transactions (Up to 12 Marks)
Your third task is to design a struct to represent a transaction, read in the transactions, store them in a linked data structure, and output their IDs. The output in this stage for the example above should be:
=========================Stage 3========================= v5buvljyh0lg 1yuy3noa2uxu gl3utnnwxf49
9mopqy3snk3h 6hjqaydtmrq5 mlgtqk8oo74e u7s604f0u6bz 2siil57yqe5k vzdg2z09t7zp n6lcvjyrhvwt
Hint: You may modify the linked list implementation in “listops.c” (link to source code available in lecture slides) to store the credit cards. You are free to use other linked data structures (queues, stacks, etc.) if you wish. Make sure to attribute the use of external code properly.
If you are unconfident with linked structures, you may use an array of struct’s to store the transactions, assuming at most 20 transactions. If you do so, the full mark of this stage will be reduced from 4 to 2.
2
3.4 Stage 4 – Checking for Fraudulent Transactions (Up to 15 Marks)
The next stage is to check whether a transaction may be fraudulent. You will go through the transactions. For each transaction, you need to check if it exceeds the transaction limit or the daily limit of the corre- sponding credit card.
You will use the binary search algorithm (Hint: You may use the “binary_search()” function, link to source code available in lecture slides, or “bsearch()” provided by “stdlib.h”) to look up the credit card ID of each transaction from the credit card records read in Stage 2. You may assume that all credit card IDs in the transactions can be found in the credit card records.
A sample output given the input example above is (note a final newline character ‘\n’ at the end): =========================Stage 4=========================
v5buvljyh0lg 1yuy3noa2uxu gl3utnnwxf49 9mopqy3snk3h 6hjqaydtmrq5 mlgtqk8oo74e u7s604f0u6bz 2siil57yqe5k vzdg2z09t7zp n6lcvjyrhvwt
IN_BOTH_LIMITS IN_BOTH_LIMITS IN_BOTH_LIMITS IN_BOTH_LIMITS IN_BOTH_LIMITS OVER_DAILY_LIMIT IN_BOTH_LIMITS OVER_TRANS_LIMIT OVER_BOTH_LIMITS OVER_TRANS_LIMIT
/* 86 + 95 > 150 */
/* 573 > 300 */ /* 3489 > 3000 and 500 */ /* 4592 > 800 */
Note also that you should only go through the transaction list once, that is, you need to design an algorithm with an O(nlogm) average time complexity for this stage, given n transactions and m credit card records. At the end of your submission file, you need to add a comment that states the average time complexity of your algorithm, and explains why it has that time complexity.
If the time complexity analysis is missing, or the average time complexity of your algorithm is higher than O(nlogm), the full mark of this stage will be reduced from 3 to 2.
Hint: To achieve the target time complexity, you may need to modify the credit card struct to store addi- tional information.
