Graduate Application Process
Welcome to the interview process for the Mu Lab! Aside from any possibly scheduled (remote) interviews with lab members, there are two key things that we ask you to do: review a paper and write some code.
Paper Review
Steps
- Pick any one of the papers below.
- Read through the paper.
- Write up 2-3 strengths, 2-3 weaknesses, and 1-2 “next steps” (i.e., future work) of the research. Note, weaknesses aren’t meant to include spelling errors or similar – rather, fundamental drawbacks of the approaches described.
Papers
- Modeling Blackbox Agent Behaviour via Knowledge Compilation
- Bayesian Inference of Linear Temporal Logic Specifications for Contrastive Explanations
- Planning for Goal-Oriented Dialogue Systems
- Learning Neural-Symbolic Descriptive Planning Models via Cube-Space Priors: The Voyage Home (to STRIPS)
- Efficient Multi-agent Epistemic Planning: Teaching Planners About Nested Belief
Assessment
There aren’t really any right/wrong answers here. We’re just looking to see how you read and critique. Also, we don’t assume that you will understand these papers fully – many require quite a depth and breadth of academic training (which, of course, you won’t have until you attend graduate school!).
Submission
Just send along your thoughts to christian.muise@queensu.ca.
Coding Exercise
You may perform the following in any language you’d like, but keep in mind that we’ll be looking to understand what it is you’ve done. I.e., code clarity will be quite valuable here. It is worth justifying all of your design decisions, especially for step 3 below.
Steps
- Pick one of the two problem settings below to implement, and a language to implement it in.
- Implement a naive version of the task using basic data structures, basic brute force techniques, etc.
- Implement a “smart” version using your best ideas.
- Compare the performance between the two. You should generate your own data to demonstrate interesting variations.
Project Topics
Tagged Document Lookup
Imagine you have a set of documents $D$ and a set of tags $T$ that can be associated with them. You can assume that $|D|$ is around $10^4$ to $10^5$ and $|T|$ is roughly 100. For each document $d \in D$, the tags for that document, $t_d \subseteq T$, has a size of roughly 2-7.
Unlike the normal document retrieval setting, we don’t want the set of documents that match a single given tag. Rather, given a set of tags $q \subseteq T$ (with $|q|$ anywhere from 10 to 40), we would like to return all documents that have all of their tags in the set:
$$query(D,T,q) = \lbrace d | t_d \subseteq q \rbrace$$
For this question, you don’t really need to be concerned with what’s in the documents, or what the tags actually are (treat $D$ and $T$ as just two sets of objects). The task for this problem is to implement the $query$ procedure.
Vacuum Search
Consider the setting where you have an autonomous vacuum cleaner operating in an extremely simplified view of the world: a 3x6 grid.
The goal of the vacuum is to clean the entire floor and go to the bottom left corner (the only cell guaranteed to not have an obstacle).
Your task is to come up with a search procedure that will vacuum the entire area. Some particulars:
About the world:
- Every cell in the 3x6 grid may or may not have dust.
- Some cells are obstacles, and the vacuum knows the locations of these obstacles.
About the vacuum, what it can do and what it can not do:
- The vacuum can move north, south, east, and west, and additionally suck (so 5 possible actions).
- When the vacuum performs a suck action, it will remove any dust that is there.
- When the vacuum moves, it either moves one cell in the appropriate direction (if it’s free) or remains stationary (if trying to move on an obstacle or into a wall).
Unfortunately, for this poor vacuum, all of the sensors are toast. There are no sensors to let the vacuum know if a move or suck action actually had an impact.
You are welcome to test in a variety of initial map configurations (i.e., with obstactles scattered about), and we’re interesting in (1) how you represent the state space of the search; (2) how the strategies are formed for settings with obstacles.
As a tip, if there were no obstacles, then the vacuum could localize itself by going west twice and south five times: no matter where it starts, it will wind up on the left wall first, and the bottom-left corner in the end.
Assessment
We are looking for code clarity, clear evaluation (for the final step), imagination with step 3, and overall correctness of the problem setting. If there is anything unclear with the description, please reach out – you are not being assessed on how well you can interpret our hastily written coding project ideas!
Submission
Host your code somewhere (GitHub is a good option), and share it with Prof. Muise (GitHub username: haz).