Articulation Practice

One of the goals of this class is for you to be able to communicate precisely about the algorithm design process. This includes being able to formulate questions, rephrase and discuss material as well as help others understand any and all steps of the process. These activities help you take ownership of your learning and mastery of the material:

• Topic module reflections (at least 2)

• Learning pod engagement

• Lead a group module for your peers

You are responsible for at least two 3-5 minute topic module reflection for your peers. This should be done as a video recording; please make sure permissions are set so that (at least) anyone at MHC can view.

• Respect your peers and do not share with others not in the course. Sharing beyond the course is considered a violation of the Honor Code.

Submission process:

1. Post the video/link to the Ed Discussion forum under the appropriate topic for your peers to see.

2. Use the Gradescope assignment Topic module reflections to provide the URL; this is how we will give you feedback. When you "resubmit," your original  answers will  remain.
   Note that we are using this Gradescope assignment as our mechanism for feedback. We are unable to make "optional" points in Gradescope, but rest assured that we will adjust your points accordingly in your final grade calculation. Remember from the Syllabus, you must complete at least two reflections.

Use your time in a way that you feel will support your peers learning, which could be by:

• summarizing a concept, problem or definition

• walking through a simple example

• contextualizing material from the class in terms of a larger picture (e.g., the class as a whole, how it connects to your computer science journey or computer science in general or beyond)

• formulating a precise question to clarify material

• prompting the class to answer a simple question or pose specific questions

You will be graded on

• clarity of communication

• impact on your peers' learning

You will be working in "learning pods" of 3 to help support your learning. Be strategic about how you work together and how you approach the material. Here is some structure to guide your interactions:

• Use active listening (listen to understand) when trying to figure out where you or others are going wrong in a problem.

• Reflect back and synthesize: mirror what you heard to clarify your own understanding (and maybe theirs!).

• Step up, step back: be aware of when to take up space, and when to make room for more voices.

You will be assessed on:

• attendance and engagement with your learning pods

• serving as a facilitator (roughly once for each of 3 pods) 

  • at the end of the class, report out: what went well, what was bumpy and any remaining questions

  • depending on time constraints, the report may be posted to Ed in a written format

You will prepare and lead your peers through a topic module in groups of 3.

The topic module may take the form of:

• an activity to reinforce earlier material (such as solving recurrence relations or asymptotic analysis)

• a presentation of a more advanced algorithm -- specific suggestions listed on the form below

• leading a problem-solving session for a simpler problem that uses a design approach from class (e.g., drawn from sample interview questions)

Modules will take place during the last class meetings. 

• Each group will have ~20 minutes

Some suggested agendas that have worked in the past:

• 3-5 minute overview/intro, 5-10 minutes of problem solving/practicing the approach in groups/at the board, 3-5 minutes to debrief

• 5-10 minute presentation, followed by a 5 minute interactive quiz using something like kahoot, mentimeter, poll everywhere

• 15 minutes of presentation with quiz questions embedded throughout (using mentimeter or poll everywhere)

I’m also happy to brainstorm about the topic and how you might use class time best!

Requirements

Your module must:

• include a presentation of technical material

• contain an interactive component to engage your classmates

• have a follow-up multiple choice question for students to answer on the final exam, based on your lesson plan

You will be assessed on:

• the correctness and clarity of your materials

• the impact on student learning

• design of the exam question

By Tue 4/29: module materials

• Share a google drive folder with:

  • A google doc that contains:

    • Title of your module

    • Agenda/plan for your lesson

    • A multiple choice question + the solution to be included on the Final Exam.

      • Make sure the permissions are only shared with me :)

  • Material you’ll be using (slide deck, etc.) so I can post it to the web site.

  • Check that permissions for anything you'd like your peers to access are set to Mount Holyoke College or Anyone with the link.

Ideas for modules

• Finding counterexamples

  • One way researchers approach this is by developing a program that would start enumerating all instances and run each through the approach and through brute force. By comparing, they might find a counterexample. There is no guarantee here, since typically the universe of instances in infinite AND brute force generally cannot be run past a "small" value of n.

  • You could pick one of the problems we've seen (or any NP-complete problem). You could then implement brute force vs greedy and see if you find a counter-example. Some that we have seen:

    • Knapsack: greedy by value "density"

    • Princess Quest (Set Cover) 

    • Set Packing

    • Independent Set

  • The class time can be used to introduce/refresh the problem, and have the class execute the brute force and greedy approaches on an instance where greedy does work and on a counterexample (as found by your program).

• Learning new algorithms

  • You can walk through the Algorithm Design Process on a problem that we haven't covered (e.g., from Algorithm Design (K&T) text, from Algorithms (CLRS) text, from Computational Geometry text).

    • Prepare a presentation (slide deck or boardwork) to walk the class through Steps 0, 1 and 2 of the Algorithm Design process

    • Make a worksheet with instances of the problem for the class to practice Steps 0, 1 and 2

    • Give a high-level summary of Steps 3 and 4 (or ask the class to analyze the run time)

• Summarizing a topic from the course

  • Give a refresher on a topic by producing new instances/examples to work through.

  • Prepare a presentation (slide deck or boardwork) to remind the class of the topic.

  • Prepare a set of new instances that highlight notable features of the topic.

    • This might lend itself to a worksheet or Kahoot! for the class.

  • For example, maybe you want to focus more on Divide-and-conquer. You could try to find an example of an approach (that is not a clear O(n log n) or O(log n) closed form) or adapt/better-explain the Genetic Algorithms question from Homework 7. Then create a worksheet to help the class practice the analysis.

• (Re)framing a problem

  • Have fun by taking a problem from class or the book and turning it into a game (like Princess Quest). This could become part of a future offering of the course!

• Digging into an NP-complete problem

  • Choose an NP-complete problem that we did not cover and learn about the problem and how it is shown to be NP-complete.

  • Present the problem to the class and have them try it out on an instance to gain intuitions.

  • Present the reduction that shows it is NP-complete to the class and have them apply (some of, depending on time) it to the instance.