I teach a graduate class in algorithms. Students take this class primarily as a breadth requirement in grad school, and they are a mix of MS and Ph.D students in computer science. Most students taking the class have a CS background, but a few don't: instead, they have enough math background that I deem it permissible for them to take the class.
The class itself spends roughly a third of the time covering/reviewing what would be standard material in undergrad algorithms (basic algorithm design principles and methods for analyzing algorithms) and a third of time with more advanced material that is still core algorithms (flows, complexity theory, randomness) and a third with more advanced material (approximation algorithms, and advanced topics).
The main emphasis in the class (and the reason why I'm posting the question here) is an understanding how to reason formally about algorithm (as opposed to learning recipes, which is common in undergrad algorithms). Students are expected to write proofs, and understand how to apply imperfect design strategies to specific problems and generate provably correct algorithms. Students also do assignments and projects that involve programming, but this is not a central part of the course.
As is probably not surprising, understanding what constitutes a proof is a major issue for students.
Over the years, the class size has grown: partly because of the growth of the program and partly (I hope!) because of interest in the material. I started off some years ago with under 20 students, and now I'm upto 80 and counting.
This has forced many changes in the structure of my teaching. But I'm still in a "standard" lecture-style model, where I deliver lectures and assign homeworks.
What I'm thinking about doing is 'flipping' the class around to do something more interactive, especially to help students understand how to go about reasoning formally about algorithms. But at this size I'm not sure how possible this is.
So finally, my question:
are there good pointers on ways to flip a large grad class in a mathematical topic where the focus is on helping students assimilate algorithm design principles and understand how to reason about them ?