Description
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 may add your own functions wherever appropriate for better program
modularity.
• 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
12345678 + 1009
678 -> 345 -> 12 -> NULL
9 -> 1 -> NULL
687 -> 346 -> 12 -> NULL
12346687
1_2
999999999 + 99
999 -> 999 -> 999 -> NULL
99 -> NULL
98 -> 0 -> 0 -> 1 -> NULL
1000000098
1_3
12345678 + 21474000083647
678 -> 345 -> 12 -> NULL
647 -> 83 -> 0 -> 474 -> 21 -> NULL
325 -> 429 -> 12 -> 474 -> 21 -> NULL
21474012429325
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 User record: USER
Visiting record: VISIT 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:
PAGE 1288 /library
PAGE 1282 /home
USER 20686
VISIT 1288
VISIT 1282
USER 20687
VISIT 1288
In this case, we have 2 pages ( /library and /home ) on the server. Two users have
accessed the server, one (#20686) visiting 2 pages ( /library and /home ) and the other
(#20687) visiting 1 page ( /library ).
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
struct Page {
int id;
string path;
int counter;
Page(int id, string path) {
this->id = id;
this->path = path;
counter = 0;
};
};
• A STL vector for organizing the Page objects
vector pages;
• A User structure, each User object consists of the id and the pages the user
visited
struct User {
int id;
vector visits;
User(int id) {
this->id = id;
};
void add_visit(int page_id) {
…
};
int size() const {
return visits.size();
};
void print_visits() {
…
}
};
• A STL vector for organizing the User objects
vector users;
• A function to overload < operator for the comparison of 2 pages based on their
ids
bool operator<(const Page & a, const Page & b) {
return (a.id < b.id);
};
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):
$ g++ -pedantic-errors -std=c++11 2.cpp -o 2
$ ./2 < input2_1.txt
The program will print:
*** 5 most popular pages ***
36:/msdownload
32:/ie
17:/products
17:/search
13:/sitebuilder
*** 5 most active users ***
23:10068
– /activeplatform
– /activex
– /automap
– /frontpage
– /gallery
– /ie
– /intdev
– /isapi
– /java
– /msdownload
– /musicproducer
– /office
– /promo
– /sbnmember
– /search
– /sitebuilder
– /spain
– /vbasic
…
[snipped]
…
11:10019
– /athome
– /clipgallerylive
– /games
– /isapi
– /kb
– /logostore
– /msdownload
– /msoffice
– /ntserver
– /products
– /search
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.
