Description
If you have any questions, please post to the Moodle discussion forum on Assignment 1.
• General Instructions
• Problem 1: Large Numbers Addition (50 marks)
• Problem 2: STL – Log Analyzer (45 marks)
Total marks: 100 marks
• 5 marks for proper code comments, indentation and use of functions
• 95 marks for program correctness
A maximum of 5 marks will be deducted if you fail to follow the submission instructions strictly.
General Instructions
Read the instructions in this document carefully.
In this assignment you will solve TWO problems and a tester would automatically test your submitted program. So if your submitted files and program outputs do not conform to our instructions given here, your programs cannot be evaluated and you will risk losing marks totally.
We will also use additional test cases when marking your submission.
Input and output format
How to use the sample test cases
Testing against the sample test cases is important to avoid making formatting mistakes. The additional test cases for grading your work will be of the same formats as the sample test cases.
Coding environment
You must make sure that your program can compile, execute and generate the required outputs on our standard environment, namely, the gcc C++11 environment we have on the CS Linux servers (academy*).
Make sure the following compilation command is used to compile your programs:
As a programmer/developer, you should always ensure that your code can work perfectly as expected on a target (e.g., your client’s) environment, not only on yours.
Submission
Name your C++ programs as in the following table and put them together into one directory.
Late submission
Evaluation
Academic dishonesty
Getting help
You are not alone! If you find yourself stuck on something, post your question to the course forum. We want this assignment to be rewarding and instructional, not frustrating and demoralizing. But we don’t know when or how to help unless you ask.
Please be careful not to post spoilers. Please don’t post any code that is directly related to the assignments to the discussion forums or share your work to any public domain. However you are welcome and encouraged to discuss general ideas on the discussion forums.
Problem 1: Large Numbers Addition
This problem is an extension of the tutorial problem in Module 8.3 on large number comparisons.
The largest integer that can be stored using a 32-bit int data type is 2,147,483,647. In this question, you are going to implement addition of two arbitrarily large numbers using linked lists.
A large integer is to be stored in your program as follows. Starting from the least significant digit, an integer n is segmented into chunks of 3 digits. The value of the chunk with the least significant digits is stored in the first node and that of the most significant digits is stored in the last node, so that the linked list in reverse will give the original integer n. Here are some examples:
Input:
• Your program should accept an expression a + b from the user, which is an addition of two large numbers a and b .
Output:
• First two lines of output print the linked list storing the two input large numbers to be added.
• The third line of output prints the linked linked list storing the sum of the two numbers.
• The fourth line of output prints the sum in its conventional form.
Requirements:
• You should assume that the input integers are of arbitrarily number of digits. In other words, you cannot simply store the input numbers in any integer or string types.
• You should start with the solution program largenum.cpp of the tutorial problem and modify the code from there. Then the use of dynamic array to handle the arbitrary long input would have been done for you.
• Remember to name your submission as 1.cpp .
• Modify the code so it first creates two linked lists for the input numbers, then performs the addition which creates a third linked list storing the sum.
• Addition is done by adding the values stored in the nodes of the two linked lists that correspond to the same decimal places, and propagating the carry digit (if there is any) to the addition of the next nodes storing the value of the more significant digits.
• You are not allowed to use STL containers (e.g., vectors) or other external libraries.
• You are allowed to reuse/modify functions in the sample programs build_list_forward.cpp , build_list_backward.cpp ,
build_list_sorted.cpp , build_list_reverse.cpp and largenum.cpp of Module 8.3 whenever appropriate.
Sample Test Cases
User inputs are shown in blue.
1_1
1_2
1_3
Problem 2: STL – Log Analyzer
You are provided with a template program 2.cpp . Complete the program and the program will read and process a web log data file from user input ( cin ). The program will then print out the 5 most popular pages, and the 5 most active users and the corresponding pages they have visited.
The log file consists of records of three types, each record occupies exactly one line. Here is the format of these three types of record:
Page record: PAGE <page id> <page url>
User record: USER <user id>
Visiting record: VISIT <page id>
A page record represents a page on the web server. A user record represents a user that accesses the system. A visiting record represents a visit by the user indicated by the most recent user record. Here is a sample data file:
You can assume the followings regarding the data file:
• The data file always consists of the three types of records only
• The page ids are unique across all PAGE records
• The user ids are unique across all USER records
• The page ids are unique across all VISIT records of a user
• VISIT records will only appear after the first USER record
• The page id in a VISIT record appears only after its corresponding PAGE record
• There will be at least 5 users and 5 pages
The followings have been implemented for you:
• A Page structure, each Page object consists of the id, path and a counter to count the number times it is being visited
ids
You are required to complete the missing functions in the template program to make it work.
Note: The functions Page() and User() in the structs Page and User above are called struct constructors. Refer to Module 10 “C Programming (Part 3)” for the discussion on the struct constructor functions. It works the same in C++.
Sample Test Cases
You are provided with 4 sample test cases. We will use the first test case and detail the test run below.
Assume we have input2_1.txt in the current directory. If we run the program like this (assuming that we are working on Linux):
The program will print:
The output format is explained as the below:
• Each line of the “5 most popular pages” is in the format of
“visit_counter:page_path”. E.g., 36:/msdownload .
• A line of an active user is in the format of “number_of_pages_visisted:user_id”.
E.g., 23:10068 .
• A line of an active user’s visit is in the format of “- page_path”. E.g.,
– /activeplatform .
Note:
• If two pages are equally popular, the pages are ordered lexicographically by the path.
• If two users visit the same number of pages, the users are ordered by their id ascendingly.
• The list of pages a user visit must be printed in lexicographical ascending order.
• You can choose not to use the provided template program and implement in your own way. However, your program must contain the provided Page and User structures and use STL vectors for storage.
• Once again, you MUST use STL vectors in your program. Your program will be checked and your score will be 0 if we find that you use traditional arrays to store pages and users in your implementation.
