Assignment 1 Solution

Problem 1

Goal

Get practice in decomposing a problem, creating a design for a program, and implementing and testing a program.


Background

Recommender systems use past behaviours of others to give you suggestions on what has worked for others in the past, based on your own current context. Amazon books, for example, looks at the set of books that you have already purchased and compares your reading list with the reading list of others. It then aggregates the purchases of others who also bought many of the same books as you and recommends to you those books from the aggregate that you haven’t already purchased. Typically, you don’t make a recommendation unless there is enough data to suggest that it’s a meaningful recommendation.

In this assignment, we will do a simpli ed version of a recommender system. In our case, you will be recommending courses to take at the university based on what other students have taken.


Problem

Design a class CourseSelector that collects data on which courses students have taken, and then allows a user to make queries about the data. You will be provided with a main program that will then let a user invoke the operations on the data.

Your class will read data from a    le, then allow a user to request the following three queries:

Recommend n courses based on a given list of courses

Print to a  le the number of students who have taken any pair of courses

Print to screen the number of students who have taken any pair of a given list of courses Speci cally, you will implement the following class:











1

c l a s s  C o u r s e S e l e c t o r  f
IMPLEMENT  / g
public
int  r e a d ( S t r i n g  f i l e n a m e )  f /

public
A r r a y L i s t <S t r i n g > recommend ( S t r i n g  taken ,

int
support ,

int
numRec )

    • /  IMPLEMENT  / g

public boolean showCommon( S t r i n g c o u r s e s ) f / IMPLEMENT / g public boolean showCommonAll ( S t r i n g f i l e n a m e ) f / IMPLEMENT / g

g

Descriptions of the methods follow below.


int read(String filename) The read method reads the contents of a le named filename to the object. Each line represents the courses a student has taken. The method returns the number of rows read in. The data should replace any data previously read into the class. Individual courses in a line are separated by spaces.


ArrayList<String> recommend(String taken, int support, int numRec) This method returns a list of numRec course recommendations given a list (taken) of courses already taken, separated by spaces. Only report courses if the recommendations are supported by at least support other students.

More speci cally, the recommend method should

    1. Find all of the students who have taken all of the same courses listed in taken.

    2. If there are at least support students who have taken all the courses, then

        (a) Find all of the courses these students have taken, not including the courses listed in taken.

        (b) For each of these courses, count the number of times they appear

        (c) Report back the  rst numRec most taken courses

If you don’t have enough students to make a recommendation, then return null.

If you do have recommendations to return, then the returned ArrayList should have at most numRec in it. The courses should be provided in descending order of frequency. Two courses with the same frequency can be in any order.

There is one situation where the ArrayList can have more entries: when you reach numRec entries and there are other courses with the same frequency that you haven’t reported. Rather than choose between which of these last courses to return, report all of the ones with that frequency.

For example, suppose that the outcome of computation 2c is the following list of courses:











2

Course
Number of students who have taken it


CSCI1100
12
CSCI2110
10
CSCI2112
8
CSCI2134
8
CSCI3110
5
CSCI3120
4



For 2 recommendations, return CSCI1100 and CSCI2110.

For 3 recommendations, return CSCI1100, CSCI2110, CSCI2112, and CSCI2134 (since the last two both have the same frequency).

For 5 recommendations, return CSCI1100, CSCI2110, CSCI2112, CSCI2134, and CSCI3110.


boolean showCommon(String courses) This method prints to the screen a 2d array with one row and column for each course in courses in the order in which they appear. The value in each entry is the number of students who have taken both courses. Return False if any errors were encountered and True otherwise.


boolean showCommonAll(String filename) This method prints to the le filename a 2d array with one row and column for every course that has been taken by any student, in order of course name. The value in each entry is the number of students who have taken both courses. Return False if any errors were encountered and True otherwise.

Both methods with this method name compute a pairwise popularity matrix. Pairs of courses that are both taken frequently shouldn’t be scheduled at the same time, so we want to know the pairs of courses that are both taken often.

The basic logic is as follows:

    1. Create a 2d array with one row and one column for each course that we are given.

    2. Consider the courses of each student in our system.

        (a) Find the rows/column number for each of the courses.

        (b) For each pair of courses, add 1 to the entry in the 2d array for the pair. Do not pair a course with itself.

    3. Print the resulting matrix.

When you print the matrix, you do not print the column names. For each row of the matrix, print the course name and then the integer from each column. Each of these bits to print will be separated by a tab character.

For example, suppose that we have entries for the following students in our system:

CSCI1110
CSCI2110
CSCI2122
CSCI2110
CSCI2112
CSCI2122  CSCI2134
CSCI1110
CSCI2134
CSCI3171
CSCI2141



If we asked for a matrix for all courses above, we would get the following output



3

CSCI1110
0
1
0
1
1
0
1
CSCI2110
1
0
1
2
1
0
0
CSCI2112
0
1
0
1
1
0
0
CSCI2122
1
2
1
0
1
0
0
CSCI2134
1
1
1
1
0
0
1
CSCI2141
0
0
0
0
0
0
0
CSCI3171
1
0
0
0
1
0
0


How to submit

Submit the .java le containing your CourseSelector class and any other supporting .java les to Brightspace.


Inputs

An input data le for your class will have one row for each student. One row consists of a set of course numbers (8 characters each), separated by spaces.

Each course number in the    le will be an alphanumeric string like CSCI3901.

You can assume that no student will have more than 10 courses provided in the le. The courses provided for a student are not necessarily provided alphabetically.

Example:

CSCI3901  CSCI5100

CSCI1110  CSCI2112  CSCI2110  CSCI2134  CSCI2141


Assumptions

You may assume that

Each line in the input  le will have at most 10 courses.

There are no spaces included in the course names in the input le or in the parameters provided to your methods.

File names will contain the full path to the  le, including any  le name extensions.


Constraints

Write your solution in Java. You are allowed to use data structures from the Java Collection Framework.

Course numbers are case insensitive.

If in doubt for testing, I will be running your program on timberlea.cs.dal.ca.  Correct operation of your program shouldn’t rely on any packages that aren’t available on that system.





4
Notes

You will be provided with a main class on the course web page that will give you an interface through which to invoke your class.

It is possible (and acceptable) to do this assignment with basic Java data types and ArrayLists. You are allowed to use or create more complex data types if you want.

The functionality of your assignment will be assessed based on the results of test cases. Conse-quently, code that doesn’t compile will not get marks for functionality.

You are permitted to create more than one class in support of your work.

I recommend thinking about how you want to store your data rst. Consider some of the built-in data types that do not worry about the size of the data. Next, design, code, and test functionality one method at a time. The showCommon/showCommonAll methods are likely easier to start with than the recommend method.

Look for common tasks that you can re-use between methods. Break these out as new private methods.

Document your code. If I hide the Java code, I should still get a reasonable sense of your method from the sequence of comments.

When testing, your methods will be invoked with error conditions. You are expected to handle these errors.

Review the test cases to identify special cases that you will want to consider in your work. Your class should never end by producing a Java error stack trace.

The marking scheme has no marks for time or space e  ciency.

Use the number of marks for the methods and the set of test cases as guides for how much time to devote to each method.

Recognize when you are spending time with no progress and ask for help before you nd yourself spending hours with no progress to show for the time.


Marking scheme (out of 30)

Code documentation { 3 marks

Program organization, clarity, modularity, style { 4 marks Ability to process le contents (read, write) { 5 marks

Working showCommon/showCommonAll methods { 8 marks Working recommend method { 10 marks

The majority of the functional testing will be done with an automated script, so stick to the input and output formats.


Test cases

Input Validation (usually looking for bad data and ensure you don’t crash)


5
Null value passed as  lename to read or showCommonAll

Empty string passed as  lename to read or showCommonAll

Courses separated by more than one space in read, recommend, showCommon Recommend method

{ taken value is null

{ taken value is an empty string { support value of -1

{ numRec value of -1

showCommon

{ courses parameter is null

{ courses parameter is an empty string

Boundary Cases (includes special or edge cases to consider)

Read method

{ File does not exist { Empty le

{ 1 line in the  le

{ Student has just 1 course { Student has 10 courses

Recommend method

{ taken parameter only has 1 course { support parameter is 0

{ support parameter is 1

{ support parameter is more than the number of students in the object { numRec parameter is 0

{ numRec parameter is 1

showCommon method

{ 1 course in taken list

{ There are no overlaps between any of the courses taken (each student only has 1 course) { Some pair of courses is only taken together once

{ Make the matrix from a single student

showCommonAll method { 1 student in the object

With 1 course With 10 courses


6

{ There are no overlaps between any of the courses taken (each student only has 1 course) { Some pair of courses is only taken together once

{ Make the matrix from a single student

Control Flow (think of it as \normal" cases for now)

Read method

{ Many student lines in the  le

{ Student has 4 courses (or a non-boundary number of courses)

Recommend method

{ taken parameter has 2 courses

{ taken parameter has all courses in it

{ taken parameter contains a course that no student has taken { support parameter is a reasonable positive integer

{ numRec parameter is a reasonable positive integer { Number of courses to recommend is below numRec { Number of courses to recommend is exactly numRec

{ Number of courses to recommend is greater than numRec and there are no ties at the numRec boundary

{ Number of courses to recommend is greater than numRec and there is a tie of courses to report at the numRec boundary

showCommon method

{ courses parameter comes in with 2 courses

{ courses parameter comes in with several courses

{ courses parameter comes in with a course that no student has taken

{ courses parameter has courses in a di erent order than what they were when read in and also not sorted alphabetically

{ Called with many students’ courses read into the object

showCommonAll method

{ call with many students loaded into the object, using a varying number of courses per student

{ courses were reported for students non-alphabetically

Data Flow (think of it as calling things in an unexpected order for now)

Read data into a new object

Read data into an object that already has data in it

Call showCommon or showCommonAll with no students read into the object

Call recommend, showCommon, or showCommonAll more than once on the same object



7