The goals of this homework are to:
- allow you to (re)familiarize yourself with translating simple iterative procedures into loops and conditional statements
- help you get confidence with advanced control flows, such as recursions
- help you get confidence working with multiple components and integrating them in higher level functionality
Please keep track of how much time, in terms of number of hours, it takes you to solve each exercise, as we will ask you to provide us with this information.
The total number of points for this homework is 115. Of these, 15 are bonus points that can be counted toward future milestones where you do less well.
Please be mindful of the Collaboration Policy. If you have any questions regarding the assignment requirements, ask on the discussion group. If you have any doubts about whether it's appropriate to ask something, check with the course staff. You are allowed to use Web search to find answers to questions.
The deadline for this homework is November 5, 2010, at 23:59. Any assignments (or parts thereof) handed in late will not be considered.
In this assignment, we continue building parts of the Campus Buddy application. We first need to improve the functionality offered by the graph framework developed in Homework #2. We will then start working on modules concerning the schedule of the public transportation to the EPFL, and also on a recommendation system for EPFL courses.
The project skeleton can be downloaded here. The code is organized as follows:
- The epfl.sweng.graph package contains the full implementation of the previous homework, which is needed for Exercise 1.
- The epfl.sweng.graph.level package contains the code skeleton for the graph extensions that you will have to do for Exercise 1.
- The epfl.sweng.timetable package contains the skeleton needed for Exercise 2.
- The epfl.sweng.courses package contains the skeleton needed for Exercises 4, and, as a bonus, 5.
- The epfl.sweng package contains the skeletons for the three "high level" classes, which you will implement as the final results (the "external interface") of this assignment.
Exercise 1 (25 points)
In this exercise, we are extending the planar graph functionality from the second homework, in order to support multiple levels
. The EPFL plan
offers the possibility of showing the plan of each level in a building, so we also need to augment our graph representation of the campus with level information.
- First, have a look at the epfl.sweng.graph.level package. There, you will need to implement a Node derived class, called LevelNode, which contains x and y coordinates, as well as a level value. x and y should be floating point values, but the level must be a signed integer. (5 points)
- Second, you will need to implement a LevelNodeCostEvaluator class, extending the ICostEvaluator interface for the LevelNode class. Here, the cost between two adjacent nodes is computed as:
where the height between two adjacent levels is the constant LevelNode.LEVEL_HEIGHT. (5 points)
- Finally, based on this new graph structure, you will implement a basic EPFLMap class, which takes at construction time the graph representation of the campus map, and which offers three methods: two overloaded getMinDistance methods, and the getArrivalTime method. (15 points)
The first two methods compute the minimum distance between points on the map, while the third computes the arrival time at the destination node, given the current time, the starting coordinate, and the average speed of the person. The speed is measured as map units per second.
Note that, unlike the first method, the second and the third method take an arbitrary coordinate on the map, instead of a specific node in the graph. In this case, you will have first to "approximate" the arbitrary coordinate (x, y, level) to the nearest node in the graph, in terms of the metric described at point 2, and compute the distance as the sum between the distance to the nearest node, and the length of the shortest path between that node and the destination.
Exercise 2 (25 points + 5 bonus points)
The previous exercise solved an important task for us: now we can find out, from wherever we are in the campus, how much time it will take us to reach a certain point in the campus -- in particular, the EPFL metro station. We are now concerned with the schedule of the metro, to see what's the next metro we can catch, and thus we switch to the epfl.sweng.timetable package.
The basic abstraction we're using here is to encompass the metro events in a more general IEvent interface, which can represent any repeatable event that can be put in a time table. For instance, an IEvent could be something like "Wednesdays, at 13:15", while the getNextOccurrence method could return a specific moment in time, e.g. "Wednesday, October 20 2010, 13:15".
The events can be compared to each other (via the IComparable interface), in an absolute way. For instance, in the absolute orderings, Mon 12:05 < Mon 20:08 < Tue 00:00 < Sun 15:00.
- Have a look at the ITimeTableBuilder, and the ITimeTable interfaces, which describe the functionality of a time table object. Why did we split the functionality in two separate interfaces? (5 points)
- Implement the TimeTable class, extending both the ITimeTableBuilder, and the ITimeTable interface. The object should be capable of maintaining a set of events, and, given the current time, be able to find the moment of the event that will first happen next (for instance, the first metro to come next). (15 points)
- [Bonus] Implement the previous task in a more efficient way, through the use of binary search, instead of linearly traversing the list of events. The new class should be called TimeTableOptimized, and it should reside in the same package as the "standard" TimeTable. (5 bonus points)
- Finally, define the WeekTimeStamp class, described by a week day, and a particular time during the day (e.g. Monday, 13:54). Create then a MetroArrivalEvent class, implementing the IEvent interface, and which encapsulates a WeekTimeStamp object. (5 points)
Now, the TimeTable<MetroArrivalEvent>
class should be able to offer us all the information required for the EPFL metro station.
Hint: The java.util.Calendar class can be useful in manipulating dates. The general workflow is to construct a calendar object from a date representation (a Date object, or individual values for the date fields, for example), then perform all the required operations, and finally export back the result as a date object.
Exercise 3 (10 points)
In this exercise, we put the campus map and the metro schedule together, and offer the "next metro I can catch" service.
You need to implement the epfl.sweng.MetroScheduler class, which takes as inputs, at construction, an EPFLMap object, and a TimeTable<MetroArrivalEvent> object, together with the map point where the station is located.
You also have to implement the getNextMetro method, which takes as input the current location and speed of the student, and returns the time of the next metro that can be caught.
Exercise 4 (40 points)
We now move our focus towards a different problem, that some confused students have: what courses to pick? We want to do something useful in this regard, for the Campus Buddy app, so in this exercise you will create a course recommendation system, based on the EPFL course schedule, and the personal preferences/requirements of the student. Recommendation systems
are very complex in general, but we aim for a simple one. In the epfl.sweng.courses
package, you will need to follow the next steps:
- Implement the Interval<TimeStamp> class, which represents an interval between two fixed moments in time. This class also offers a static method for determining whether two time intervals overlap (in our case, adjacent intervals are considered non overlapping, e.g. [1, 3] and [3, 7]). (5 points)
- Analyze the ICourse, ICourseCatalog, and ICoursePreferences interfaces. What is the logic behind the separation of the course information into the three interfaces? Is there any mistake in how the separation was done? If it is, fix it. (4 points)
- For what we are concerned, the course preferences are expressed as a set of weights, one for each course in the catalog. A course with a larger weight will be more likely to be selected by the scheduler algorithm. A non-compulsory course with weight 0 (or negative) is not interesting to the student, and should not be taken into consideration when computing the solution.
We now write the epfl.sweng.CourseScheduler class, which takes as input an ICourseCatalog, together with an ICoursePreferences object, and returns a set of ICourse objects, representing a set of non-overlapping courses, such that all the compulsory courses are included, and the sum of all the weights of the courses is maximal.
Have a look at the CourseScheduler.CourseInfo nested class, which aggregates in a single object the course catalog information, and the student preferences regarding the course. The class fields are public -- does this break the encapsulation of the CourseScheduler class? Explain why or why not. (4 points)
- We implement the scheduling algorithm by backtracking through all the valid, non-overlapping course schedules, and choosing the one with the maximum amount of total weight. The CourseSchedulerBacktracker nested class computes the best schedule by doing a recursive backtracking.
First, write the recursive backtracking pseudocode for the missing computeBestSchedule method. How do you break the functionality of this method into multiple ones? (10 points)
Second, fully implement the computeBestSchedule method as Java code. (10 points)
- Now implement the CourseScheduler.scheduleCourses static method, which in turn should use the nested CourseSchedulerBacktracker class. (7 points)
Exercise 5 (10 bonus points)
Some lazy students decided that the lectures are the only relevant parts of the courses, so they would want a schedule in which only the lecture intervals are non-overlapping, and don't care about the other course intervals.
We will help them with this task by offering a new method in the CourseScheduler class -- scheduleCourseLectures -- with the same interface as the original one. For this exercise, the ICourse interface offers a function for retrieving only the lecture interval of the course (we assume that the lecture part is not split across multiple intervals).
- What pieces of code from the scheduleCourses method can be reused? Refactor out that functionality into a separate, static method. What visibility should the method have? (3 points)
- Create another inner class, LectureScheduler, with the same interface as the CourseSchedulerBacktracker, and use it in the scheduleCourseLectures method. (2 points)
- Implement the LectureScheduler functionality, which returns the set of courses with non-overlapping lecture intervals, such that the total weight of the courses is maximal. (5 points)
A strict requirement here is that the solution should be as fast as possible -- more precisely, a well known dynamic programming algorithm can solve the problem of weighted intervals scheduling in linear time. In order to get the points for this task, you need to implement this method.
Why didn't this method work in the previous case?
Deliverables for Homework #3
To hand in your assignments, you will use your SVN account. Below, SVNAccount stands for the actual path to your SVN account (e.g., https://svn.epfl.ch/svn/sweng2010-candea).
- You must place your answers in an SVNAccount/trunk/assignment3/answers.txt file.
- You must provide your Java source files in the SVNAccount/trunk/assignment3 folder, including the sources of the test classes. Failing to follow this file structure will result in losing all the points for this assignment.
- Your code should successfully compile on the BC machines, by running bash -c "/usr/bin/find -name
'*.java' | xargs javac". This command will search for all the Java files in the assignment directory, and will compile them with javac. If your files do not compile, you will lose all of the points for the code writing exercises that are affected by the compilation errors.
- You must write how much time (in hours) you spent solving each exercise in an SVNAccount/trunk/assignment3/timeSpent.txt file.
- You are strongly encouraged to commit your homework deliverables from the BC machines, since occasional network connectivity problems may prevent you from submitting from other locations.
Frequently Asked Questions
We will post questions & answers of general interest here, as they appear on the discussion group.
Q: Can I modify the provided code skeleton, in order to make the implementation easier?
A: For this assignment, for the first exercise only, you can adapt the reference implementation of the graph data structures to your own needs. We are providing it for your convenience, in the case you don't have a fully functional implementation of the second assignment.
Please also note that you can make interface changes only in the epfl.sweng.graph package, and not in epfl.sweng.graph.level or any other place in the code skeleton, unless otherwise requested by the homework statement.
Q: Can I make the LevelNode class be a descendant of GeoNode, in order to be able to use the A* goal searcher?
A: Yes, you can do that, since it doesn't break the LevelNode original interface specifications.