# Tag Info

37

Similar to @Vince, I think it's a good practice to do both. I don't really agree with the cooking recipe analogy, though. Pseudocode describes that the algorithm does, without going into detail how you do it. I think perhaps a better analogy: Pseudocode: you need to put an egg into the flour mixture Actual code: pick up an egg, crack it open on the side of ...

26

Actually I am of the opinion that you should not present your own code, but rather get the students to implement the algorithms you teach them, which you give in pseudocode, and give them the freedom to choose any one of a fixed set of languages that you are familiar with, such as C++/Java/Python. Really, the only way students can truly understand an ...

12

Back around 1985, Susan Merritt created an Inverted Taxonomy of Sorting Algorithms. The idea is that to sort an array you have two phases, the split phase and the join phase. She divided the various algorithms into two types easy split/hard join and hard split/easy join varieties. Merge sort is of the former type. Quick sort is the latter. But all sorts, ...

9

Actually, the code is terrible, but I don't think its purpose is to illustrate a stack so much as to illustrate in a very rudimentary way how heap allocation works. (Worse than "terrible", it isn't "pythonic"). But you are wrong about the efficiency. Only the initialize function is O(n). Push an pop are O(1) as should be obvious. But no serious code ...

7

The simplest example that still bears enough complexity to show what's going on is probably merge sort. It's no coincidence that this algorithm is the classical example to begin explaining the divide and conquer technique. I am not sure at what level you teach, but your students should be comfortable with both recursion and inductive proofs before venturing ...

6

Buffy is provably correct (no risk needed!) that it is impossible to do it with automated code analysis, as this is an attempt to figure out when a program will finish (i.e. the halting problem.) You can get a very good guess, however, by using a few (very) differently sized input data sets, run the program on each one multiple times, and observe the ...

6

Pseudocode helps a lot by removing anything unnecessary, and focusing entirely on the algorithm, which can already be hard to understand as is. It's also faster to express ideas : if a student wants to write a different algorithm than the one you taught them, it can be really cumbersome if they have to deal with every details of Java. As others said, it's ...

5

One of the key points here is that you are teaching to future engineers, even if at academic level. The very nature of engineering is solving problems by implementing a solution. Therefore I think that presenting the pseudocode is useful to give your student the correct theoretical POV to frame the problem, BUT showing them an actual, working ...

4

I'll accept a bit of risk here, but claim that this isn't possible in general unless the student writes very naive code. But in the courses for which you want to use it, that doesn't seem likely. Imagine a linear algorithm implemented as two nested loops. The outer loop depends on the "n" that you are interested in, say the length of an array. The inner ...

4

Rosen, Discrete Mathematics and its Applications, Sec. 8.3, says: This problem arises in many applications such as determining the closest pair of airplanes in the air space at a particular altitude being managed by an air traffic controller.

3

These sorts of patterns are a bit tricky in real life. In nice easy computer-science land, every step is the same, just smaller. Merge sort is clearly the ultimate easy example of this. In real life, we tend to break things up along useful lines. If we're sorting change, we first divide the coins up by denominations, then total up each denomination ...

3

How about Huffman encodings? Given a text that uses an alphabet of $n$ unique characters, how can we uniquely encode the alphabet so that the text uses the smallest amount of bits? More formally for Huffman encodings (as formulated by Tardos & Kleinberg in their book Algorithm Design): Given an alphabet and a set of frequencies for letters, we ...

3

First, if you aren't taking a course, get a good book that has a lot of exercises. Use the exercises to guide your learning. Try to find a way to get some feedback on your attempts. The way you learn just about anything deeply is to get a lot of reinforcement and feedback. On the other hand, it is seldom necessary with today's languages and libraries to ...

3

Neither alone is enough for a good dish. I'd go with pseudo code in the lecture, and use homework to give students practice in turning pseudo code into real code. Using pseudo code in the lecture has the pragmatic reason that pseudo code is, by nature, somehow vague. You want to use it as a tool to be able to concisely state ideas that still contain all ...

3

This answer is a complement to Buffy's and is more oriented towards future applications of autograding. The description of the assignment gave me the impression that your autograder is rather lazy. Instead of checking whether the functions the students have written are correct it executes a bunch of operations and compare a checksum of the result. ...

3

Based on clarification in comments, Algorithms 4th ed. by Sedgewick and Wayne seems to meet your criteria. The book itself doesn't seem to have an official PDF version (I haven't searched for unofficial ones of dubious provenance), but the code is available both at the linked page and on Github, and includes solutions to selected exercises.

3

There are a number of sites with challenges- once you complete a challenge you can often view other solutions, and many of these sites (not all) support multiple languages. CodingBat HackerRank Rosalind The Python Challenge TopCoder Project Euler Coding Chef Even the "Python Challenge" tasks can be solved with another language since all you are looking ...

2

In fact you are adressing an important issue: You were learning concepts, but you are unable to transfer the concepts to real world problems. This is a major issue in many higher education scenarios and e.g. my students always complain, that they do not find the answers to my question in the course material. Of course they don't, otherwise I would not have ...

2

Late answer: I agree greatly with @igordsm's response above (emphasize unit testing with more detailed feedback, not just a "pass/fail" output), so this should be considered in support of that. I agree with the comment by @pojo-guy that the specification seems "unnecessarily convoluted and artificial". Having read the specifications for the 1st and 4th ...

2

One nice problem that I found is: Given n segments in 2D Euclidean space, find two segments that intersect. Seek for $O(n \cdot log(n))$ solution. https://cp-algorithms.com/geometry/intersecting_segments.html

2

I see two very different reasons to use pseudo-code. First, being precise. You want to describe an algorithm in details, without being dependent of the particularities of some programming language. That's the way algorithms are presented in the CS literature. Maybe you avoid a language war, but then, you are dependent of the particularities of your ...

2

The key to learning this, or much of anything, is reinforcement and feedback. Reinforcement comes from doing exercises and solving problems in a course like this and the book has plenty of mid chapter and end chapter exercises and problems. You can do a lot of these. All of them may be asking too much, but you want to be able to answer any of them. Getting ...

2

A loaf of bread, a knife, a jar of peanut butter and a jar of jelly. Write an algorithm to build a PB&J. Have one of the kids follow the literal direction written by a different kid. This project have been a favorite starter for algorithms for 30 years.

2

The Sedgwick resource is excellent. Besides online chapter summaries and code examples, it has a corresponding Coursera class with videos and grades exercises.

1

Another one is the following job scheduling problem: N jobs are arriving with priorities: priority_1 arrival_time_1 execution_time_1 priority_2 arrival_time_2 execution_time_2 ... priority_N arrival_time_N execution_time_N The arriving jobs are queued. When the CPU can process the next job, he will pick the one that has already arrived and has the ...

1

MergeSort is fairly easy to implement in Python and it's a straightforward divide-and-conquer algorithm. You keep splitting the collection in half until it is in trivial-to-sort pieces. This splitting reduces sorting from O(n^2) to O(nlog(n)). Second example: computing integer powers. if the power is even, square base and integer divide exponent by 2. ...

Only top voted, non community-wiki answers of a minimum length are eligible