Monte Carlo Optimization: Exam Timetabling

Patrick BuhagiarLeave a comment

The exam timetabling problem is a classic real life problem faced by all education institutions. When given a period of time, it is required to allocate all exams into specific timeslots without creating any collisions. There are many ways of implementing an exam timetabling algorithm, however one efficient way is to implement a Monte Carlo optimized Hyper-Heuristic algorithm. Hyper heuristics can be considered a type of nearest neighbour (or Greedy) algorithm with the only difference being that it seeks to automate the selecting process through machine learning.

Check out my GitHub for the implementation.

We are first required to define the necessary parameters and present them as a tuple in order to solve this algorithm. These are:

  • E →  The set of events
  • I →  The domain
  • K →  Constraints

E → Set of Events

In this case, the set of events are examinations. In the classic exam timetabling problem, for each exam we are required to define the set of all students which need to sit for the exam. Since this is a simple implementation, it is assumed that students in the same course do not have electives, therefore each student in the same course will sit for the same exam. In the programming implementation, each exam will list which courses are to sit for the exam.
A Course class and Exam class were created. The course class for this implementation contains the course name and number of students. The exam class on the other hand contains a list of courses that are to sit for the exam and the exam code.

Continue reading “Monte Carlo Optimization: Exam Timetabling” →

Remote File Memory Mapping

Patrick BuhagiarLeave a comment

The aim of this assignment was to implement an API which provides a number of calls allowing processes to memory map sections of a file located on a remote machine. Processes can then read and write to this memory area using the provided calls, with changes being propagated to the remote file by the library. Multiple processes from multiple client machines should be able to access and modify the same file on a remote machine. This was implemented in C on Ubuntu. Check out my Github for the full implementation.

REQUIREMENTS

The requirements consisted of a Client-Server model with:

  • The server having the ability to open a number of files (or section of files) on the machine using a file descriptor, and storing them in memory.
  • The client having the ability to demand that the server maps a particular file (or section of file) to memory.
  • The client having the ability to demand that the server unmaps a particular file (or section of a file) from memory.
  • The client having the ability to demand a part of the memory from the server.
  • The client having the ability to alter a part of the memory from the server.

Implementation

Continue reading “Remote File Memory Mapping” →

Sudoku Solver

Patrick BuhagiarLeave a comment

GitHub: https://github.com/PatrickBuhagiar/Sudoku-Solver

Given an initial Sudoku puzzle S0, we explore the state-space until we reach an end state Sn representing the solved puzzle. With the singleton technique, transitions between states will occur by looking up cells which only have one single candidate value.

The class Sudoku will represent the puzzle as a list of rows each containing a list of integers. Unknown cells are represented by the number 0.

class Sudoku(val grid: List[List[Int]]) {
    def row (row: Int): Set[Int] = ... 
    def column(column: Int): Set[Int] = ... 
    def block(block: Int): Set[Int] = ...
}

The row, column and block functions take an index as a parameter and return the content of the row, column or block respectively.

Continue reading “Sudoku Solver” →