The University of Melbourne School of Computing and Information Systems COMP10002 Foundations of Algorithms Semester 1, 2020 Assignment 2 Due: 4pm Tuesday 2nd June 2020 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 1https://www.aph.gov.au/Parliamentary_Business/Committees/Senate/Economics/Credit_Card_Interest/Report/c02 2https://wallethub.com/edu/cc/number-of-credit-cards/25532/ 3https://theconversation.com/credit-card-fraud-what-you-need-to-know-78542 4https://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: 800 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 IN_BOTH_LIMITS 1yuy3noa2uxu IN_BOTH_LIMITS gl3utnnwxf49 IN_BOTH_LIMITS 9mopqy3snk3h IN_BOTH_LIMITS 6hjqaydtmrq5 IN_BOTH_LIMITS mlgtqk8oo74e OVER_DAILY_LIMIT /* 86 + 95 > 150 */ u7s604f0u6bz IN_BOTH_LIMITS 2siil57yqe5k OVER_TRANS_LIMIT /* 573 > 300 */ vzdg2z09t7zp OVER_BOTH_LIMITS /* 3489 > 3000 and 500 */ n6lcvjyrhvwt OVER_TRANS_LIMIT /* 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. 4 Submission and Assessment This assignment is worth 15% of the final mark. A detailed marking scheme will be provided on the Canvas. You need to submit your code in Grok Learning (https://groklearning.com) for assessment. Submission will NOT be done via the Canvas. Instead, you will need to: 1. Log in to Grok Learning using your student login details. 2. Navigate to the Assignment 2 module of our subject COMP10002 2020
S1: Foundations of Algorithms. 3. Place your code in the program.c tab window. 4. Compile your code by clicking on the Compile button. 5. Once the compilation is successful, click on the Mark button to submit your code. (You can submit as many times as you want to. Only the last submission made before the deadline will be marked.) 6. Two sample tests will be run automatically after you make a submission. Make sure that your submission passes these sample tests. 7. Two hidden tests will be run for marking purpose. Results of these tests will not be available until after the submissions are marked. You can (and should) submit both early and often – to check that your program compiles correctly on our test system, which may have some different characteristics to the lab machines and your own machines. 3 You will be given a sample test file test0.txt and the sample output test0-output.txt. You can test your code on your own machine with the following command and compare the output with test0-output.txt: mac: ./program < test0.txt /* Here ‘Note that we are using the following command to compile your code on the submission system (we name the source code file program.c). gcc -Wall -std=c99 -o program program.c The flag “-std=c99” enables the compiler to use a more modern standard of the C language – C99. To ensure that your submission works properly on the submission system, you should use this command to compile your code on your local machine as well. You may discuss your work with others, but what gets typed into your program must be individual work, not from anyone else. Do not give (hard or soft) copy of your work to anyone else; do not “lend” your memory stick to others; and do not ask others to give you their programs “just so that I can take a look and get some ideas, I won’t copy, honest”. The best way to help your friends in this regard is to say a very firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program that undertakes deep structural analysis of C code identifying regions of similarity will be run over all submissions in “compare every pair” mode. See https://academichonesty.unimelb.edu.au for more information. Deadline: Programs not submitted by 4pm Tuesday 2nd June 2020 will lose penalty marks at the rate of 2 marks per day or part day late. Late submissions after 4pm Friday 5th June 2020 will not be accepted. Students seeking extensions for medical or other “outside my control” reasons should email the lecturer at [email protected]. If you attend a GP or other health care professional as a result of illness, be sure to take a Health Professional Report form with you (get it from the Special Consideration section of the Student Portal), you will need this form to be filled out if your illness develops into something that later requires a Special Consideration application to be lodged. You should scan the HPR form and send it in connection with any non-Special Consideration assignment extension requests. Special consideration due to COVID-19: Please refer to the “Special Consideration” section in this page: https://students.unimelb.edu.au/student-support/coronavirus/information-for-all-students/ And remember, Algorithms are fun! c©2020 The University of Melbourne Prepared by Jianzhong Qi 4
