ActuallyAnAgenda

Inspiration

Our project was inspired by the ever increasing difficulty of time-management and being able to properly concentrate on your tasks, especially under the current pandemic. While there are scheduling and planning apps out there, many of them rely on the user to manually create their own entries for when they would like to work on a project or assignment, potentially either giving themselves too much of a challenge or not being able to properly manage breaks and stress. This is where we got our inspiration - what if we created a program that did that for you?

What it does

Most of us would like to be more productive with our time but have a long list of tasks we need to complete. Our project; ActuallyAnAgendaAgain aims to solve this by automatically turning a to-do list of your tasks into a fully-fledged schedule using dynamic programming with your events and breaks to optimize your productivity. This is all done in our easy to use Android app that interfaces with our algorithm. Personal preferences can be set in the app like break durations, work times, and meal times so our algorithm can create a schedule just for you.

How we built it

For the gist of our project, we used Android studio as a front-end with SQLite as a database that would store your tasks and generated schedule while you closed the app. We utilized a series of advanced algorithms in order to generate such schedule that will be described in the following Algorithm section.

Challenges we ran into

By far, the hardest part of our project was actually coming up with an efficient algorithm that would solve our task. A simple brute-force algorithm that attempts to generate, while it may work for one or two tasks, may end up taking literal centuries to complete for more than that. There were several accommodations we had to make, but we ended up creating a method that runs on O(N * K^2) time, where K is roughly proportional to the number of hours in total in the to-do list, and N is proportional to the time from now, to the final due-date on the to-do list. We brainstormed several different methods, ranging from a basic heuristic that would attempt to evenly distribute break time, to an advanced algorithm called "Convex Hull Trick", or CHT for short that at the time, we didn't know how to properly use. The whole process required a lot of thinking, and eventually we settled on a "Cost" formula that would attempt to accurately measure how difficult a schedule would be for the user to follow using the sum of the least squares residuals.

The biggest realizations we ended up making were how to simplify the problem down to a binary strings of 1s and 0s, representing the latest possible times for the user to complete their tasks, that we would then be able to figure out a dynamic programming algorithm from there in order to optimize it.

Algorithm

To begin, our algorithm firstly the timeline from when the schedule is created upto the final due-date into 15-minute intervals. We would begin by figuring out a valid schedule that would shove the work times into the latest intervals possible. This is a rather simple algorithm that only involves a simple sorting of the tasks by due date, traversing them in reverse order, and assigning each interval directly preceding a due date of a project to working on that project until it is done. If the intervals directly preceding such due date are already full (working on a different project), it moves the pointer left until it reaches an empty interval with no current tasks. If at any point the current interval is in the past, it is impossible to create a schedule under any circumstance.

Next, we removed all intervals that corresponded to sleep times, meal times, and specific designated events, as well as intervals in the past and intervals in the far future (past all due dates). This would leave us with essentially a string of 1s and 0s, where each 1 represented a 15 minute interval of work, and each 0 represented a 15 minute break.

The hard part here comes in optimizing this schedule further, where we opted on attempting to minimize a cost that represented the sum of (Break/Session Time - Optimal Break and Session Time)^2, where each break/session time is represented by a consecutive substring of 0s or 1s within the full string. There was an observation we made that moving any of such 1s to the left would always return a valid schedule in every circumstance, which we used to our advantage.

In order to do this, we utilized a dynamic programming algorithm which initially ran at a bad time complexity, but was then further optimized to get rid of a nested loop using Convex Hull Trick to query the minimum point on a series of parabolas. This dynamic programming algorithm would essentially traverse the string in reverse, and simulate adding a series of substrings of 0s and 1s at a time. We essentially have a 3D dynamic programming array where dp[index][number of ones used so far][last digit used] memoizes the minimum cost possible at the current substring [index, length of string), containing a specific number of ones used so far, as well as the digit at index. To make sure that ones are never moved to the right, we keep track of a suffix array.

To actually fill in this table, the property dp[i][j][0] = dp[a][j][1] + (a-i-k)^2 was utilized, which essentially states that adding (a-i) zeroes to the left of the most optimal substring [a, length of string) where S[a] = 1 will increase the cost by (a-i-optimal break time)^2. The additional property dp[i][j][1] = dp[a][b][0] + (a-i-k)^2 was also utilized, which essentially states the same thing, but adding (a-i) ones instead where S[a] = 0. While we originally used a nested loop to iterate through all values of a from i to the length of the string, we realized that this would be incredibly inefficient, and opted to optimize it further using convex hull trick, by treating each index dp[a][j][1] as a parabola that had it’s vertex at y = dp[a][j][1] and x = (a-k). This would allow us to query and update each row of the dp table in O(N) time, without requiring a nested loop.

From there, we keep track of a separate array storing where that optimal parabola came from, and use backtracking to generate an optimized string of ones and zeroes which would then be utilized to store the most optimal 15 minute intervals of breaks and work periods.

What we learned

We learned a lot about Android Studio. We’ve never used it before, and even learning the basics, such as the palettes or the design editor of the xml file was overwhelming at first. However, through practice, we were able to gain more insight into different techniques in order to make our app more interactive, such as employing a variety of different palettes such as Calender View or List View, or importing unique colour schemes and images.

What's next for ActuallyAnAgendaAgain

We plan on adding more functionality, such as connectivity with Google Calendar, notifications, more personalized options.

While the schedule generation is really all that is necessary, we also plan on adding quality of life features, such as being able to add and modify tasks once you get new projects that do not rely on completely regenerating the schedule, as well as having lenience, such as if the user misses a task and wants to add it back to the schedule.

One thing we planned on adding but didn’t have the time to was a learning algorithm that adapted to the user’s habits and adjusted the preferences overtime in order to ensure that they work more efficiently, taking constant user input on how productive they felt after a work session and how much work they actually got done.

Built With

• android-studio
• convex-hull-trick
• java
• sqlite