ALGORITHMS!

Today was great - pure computer science. The lesson, led by Krista, was on algorithms, one of the most central of concepts. She began by introducing what an algorithm is and how we as computer scientists characterize their goodness. The students were then given an exercise: given a set of n integers, devise an algorithm that computes the largest number that is a function of the integers using only simple arithmetic operations. This is not easy! I was impressed with the solutions and how the students came up with their algorithms.

Next, the "Stable Matching" problem was presented, in terms of medical students being matched to hospitals for residency. This is a non-trivial problem to understand, never mind to devise an algorithm that produces an optimal (most stable) matching. Within a few minutes of having first seen this problem, some of the students already had at least some ideas on a possible algorithm. Krista then presented the optimal algorithm, and led a discussion. The students were clearly engaged - based on their questions and responses - despite the complexity of the topic. They had to deal with concepts such as termination, running time, proving correctness, fairness, stability, etc.

Finally, the students were taught about "big-Oh" as a way of characterizing running time, and this was applied to different sorting algorithms. The students then went to the lab where Krista went over Java code for various sorting algorithms and showed how they work in detail. The students were asked to modify the algorithms to achieve improvements in running time.

What was taught today is typically material that students are exposed to well into a university-level class on algorithms over a number of lectures, and it was by far the most advanced material covered in our thread. It was a classic and well-executed lesson by "Professor" Krista, and I could only admire the students' participation and willingness to try to understand this difficult subject matter.