5
$\begingroup$

I teach 3rd-year algorithms for CS majors at a Canadian university and it always seems a fair number of students arrive not really understanding basic things like breadth-first search. This year I'm planning to give them a homework assignment on the first day that's due a week later so we can have it marked and returned before the end of the first two weeks, which is the deadline for them to drop the course and get their money back.

For the assignment, I'm asking them to write a program that reads a 3 x 3 grid of numbers representing a puzzle with 8 sliding tiles numbered 1 to 8 and an empty space (shown as 0 on the grid), and prints the minimum number of moves needed to reach that configuration from the starting configuration or "unreachable" if that configuration is unreachable. (The starting configuation has 1, 2, 3 in the top row, 4, 5, 6 in the next row, and 7, 8 and the empty space 0 in the bottom row, and a move consists of sliding a tile that's horizontally or vertically adjacent to the empty space, into the empty space.) I'm telling them to use breadth-first search and they can use C, C++ or Java (or any other language the TAs and markers are ok with).

I'm pretty sure some of them are going to complain that I'm being really mean by giving them an assignment on the first day. Given that they're they've already spent two years (and usually $50K+ on tuition) in a university CS major, I think being able to do this assignment is a necessary (not sufficient) condition for even starting 3rd-year algorithms.

Am I being unreasonable?

(I'm posting this a month in advance so I can change my plans if Stackexchange says I really am mean; otherwise, I can show complaining students that at least Stackexchange backs me up. :)

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ Your question would be more on topic on cseducators.stackexchange.com $\endgroup$
    – Nathaniel
    Commented Apr 8 at 17:08
  • $\begingroup$ It's a SIGCSE question but I'd like a SIGACT perspective. $\endgroup$
    – Travis
    Commented Apr 8 at 17:19
  • $\begingroup$ I think it's an interesting problem to be honest, that might be quite widespread. I don't work at a university myself, but I've also noticed quite a lot of students in 3rd or 4th year at the university I graduated from not understanding the core algorithm basics. And I've heard complaints from a lot of senior devs that a lot of graduates these days don't have a good grasp on basics either. I'm not aware of what could be causing the issue though. $\endgroup$
    – Minko_Minkov
    Commented Apr 9 at 8:52
  • $\begingroup$ As a former (not very good) student at ETHZ from back before Gulf War 1, this sounds good to me and actually not at all complicated. Can they use Prolog (or Picat?) though, much easier to handle and with none of the ceremonial mystery of the "classic languages". (To be fair, Prolog was still a mystery to me at semester 6, but then again, teaching resources were hard to come by) $\endgroup$
    – David Tonhofer
    Commented Apr 9 at 18:09
  • 1
    $\begingroup$ As a student, I would say the hard thing about this exercise is not the breadth-first search at all but rather how to design an efficient state representation that allows identifying adjacent-to-empty tiles to move and that can be used as a node in the search graph (i.e. as a hash map key). Lots of things to go wrong there that have nothing to do with the graph algorithm. Unless "design data structure for representing state" was meant to be a major part of the exercise? $\endgroup$
    – Bergi
    Commented Apr 10 at 9:57

3 Answers 3

Reset to default
4
$\begingroup$

I am a teacher in 2nd year in a generalist scientific formation for engineers, and I would expect my students to be able to do that in less than one hour after one semester, so I think this is perfectly reasonable.

Also I always give homework assignment on the first day each year.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks! I would up-vote your answer but apparently I "need at least 15 reputation" to do that. $\endgroup$
    – Travis
    Commented Apr 8 at 20:55
  • $\begingroup$ @Travis thanks, you can still accept the answer (if you consider that it answered your question, of course). $\endgroup$
    – Nathaniel
    Commented Apr 8 at 21:13
  • $\begingroup$ @Travis as an advanced homework, you can ask to do the same thing on a 4×4 grid (though a BFS would not work). $\endgroup$
    – Nathaniel
    Commented Apr 8 at 22:26
  • $\begingroup$ I might leave that for the end of the course. :o) $\endgroup$
    – Travis
    Commented Apr 8 at 23:10
  • $\begingroup$ "Less than one hour" is 100% reaching unless you want randomly glued illness-inducing code that falls over for random edge cases (unless minimalist work in Prolog or Picat?). Happy to report that writing this in Dart (a language I am not yet knowledgeable in) I have succeeded in writing the breadth-first search, a large-ish page of unit tests, and experimented with a number of design choices, but it took 3 days or so. Problem is small enough that one doesn't even need iterative deepening. The max depth to solution is 30 moves, at which point it seems nearly whole state space has been searched. $\endgroup$
    – David Tonhofer
    Commented Apr 25 at 22:33
4
$\begingroup$

I see three issues that are going to come up for you:

  1. Undergraduate courses in Canada do not have entrance exams. If you expect and encourage students to drop the course because they did not complete a first week assignment, they will rightfully be upset. You are likely to get extension requests or late submissions, and possibly complaints to the department. I would run this by your undergrad chair with all the specifics about how you will present it.
  2. Your problem is too well known. Searching for "8 puzzle" autocompletes to many versions of solutions, and "8 puzzle breadth" or "8 grid breadth" would allow anyone to solve this assignment, regardless of background knowledge, in whatever language they want. The assignment doesn't do what you want it to do. If you believe your students are incapable of looking up a solution and simultaneously do not have the background knowledge for the course, you should ask yourself how they completed the prerequisites.
  3. You are teaching in one month in Canada, which means you have a spring/summer session. These students are typically retaking the course, and will be especially annoyed that it is starting very differently than the main session version. It's unlikely they have the option to drop and take this again at another time - it may be a prerequisite for their 4th year courses starting the September. This is particularly true for international students on time limited visas.

I don't expect you will get support from the university. They will let you do it (this is the understanding of "academic freedom" in Canada), but you are interfering with their main business by trying to get under-prepared students a refund on their tuition. They'll just let you drown in antagonistic students and poor SETs.

It's truly not your responsibility to correct the issue that CS students are under-prepared for upper year courses. Not a bug, etc. You can help them fill in their gaps by suggesting that if they can't solve this in a short amount of time, they will need to catch up and suggest some resources to do so, but telling them to quit if they can't solve a well-known problem will just encourage them to submit the well-known solutions, and has the side effect of showing them how easy it is to cheat for the rest of the term.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ I may be wrong, but as I understood, OP is doing that so that students realize by themselves that they are lacking/not interested, not to encourage them to drop or give a mandatory assignment. If they want to cheat, well, that's their problem (and their money) since this would not be an exam. $\endgroup$
    – Nathaniel
    Commented Apr 9 at 20:49
  • 2
    $\begingroup$ @Nathaniel: after $50K and 2 or 3 years, interest is not related to enrollment. Under-prepared students in over-enrolled programs don't have an issue realizing their problem, they have an issue solving it. From their perspective, they have fulfilled their end of the deal by paying tuition and attending classes - learning is not part of getting a degree. If it is entirely optional, I don't think he would be worried that students think he is "mean." We also would not call that an assignment, just homework. $\endgroup$
    – Zack Wolske
    Commented Apr 9 at 21:08
  • $\begingroup$ I would go to our undergrad chair, but he teaches the 2nd-year course that feeds into mine and we've already clashed (mainly over how much students should know at the end of 2nd year). I would feel slightly worse about doing this except that algorithms is somehow not a mandatory course for getting a CS degree at my university; students can avoid it by switching to Bacherlor of Applied Computer Science. Here's the assignment (with obvious uni-identifying terms rather pointlessly blanked): dropbox.com/scl/fi/5vqzk4qi3rn9lp34wi7di/… . $\endgroup$
    – Travis
    Commented Apr 10 at 21:17
2
$\begingroup$

8-Puzzle is a classic textbook problem that has been used both in many standard algorithm design books as well as in classical AI books such as Artificial Intelligence: A Modern Approach, by Russell and Norvig. I have done a fair amount of experimentation with the problem myself, both as a research problem and as a standard assignment design around it. One thing I can assure you is that handing out the problem as a coding exercise is very reasonable. But let me give you a heads up (you may already know): a straight-forward application of BFS to 8-Puzzle can quickly exhaust the system memory (even with good implementation) for instances that require more than 15 (say) steps to solve. It would be wiser to stick to instances that require fewer steps to solve so that they take less time and space to terminate.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ This is a reason I would either avoid this exercise, or at least give the same warning to the students and provide several tests that they can safely apply. $\endgroup$
    – Ben I.
    Commented Apr 9 at 11:02
  • $\begingroup$ One thing I did last time, first check if the heuristic distance (manhattan) is less than 10, then only try to solve it; otherwise, take another random state to start with. $\endgroup$
    – codeR
    Commented Apr 9 at 12:14
  • $\begingroup$ One way to reduce the memory requirement of BFS is to make some of the tiles identical; for example, an 8-puzzle with 4 red tiles and 4 blue tiles doesn't have enough states for memory to be a problem. The downside of this is that most ways to do make some tiles identical will also mean that there are no unreachable configurations. (But we're also not testing unreachable configurations if we're only testing ones with short solutions.) $\endgroup$
    – Misha Lavrov
    Commented Apr 9 at 15:43
  • 4
    $\begingroup$ I don't really understand your answer. There are roughly $180$ thousand different configurations for the 8-puzzle which is ok for a BFS considering memory. I have done some tests, and I have no problems finding the distance to the solved configuration for ALL the solvable configurations, in less than a second, without any special optimization. $\endgroup$
    – Nathaniel
    Commented Apr 9 at 16:06
  • $\begingroup$ For an unsolvable start state, you have to explore half of all possible states (9!/2), which would take significant time and space. Of course, it depends on the platform and language capabilities. Is your implementation available on a public repository? I would like to see that maybe I was doing something wrong and I can learn something from it. :) $\endgroup$
    – codeR
    Commented Apr 11 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.