powstik
Prove
LiveProof-of-Work · Oct–Nov: every verified proof counts. 35 days leftAll outcomes
Skills

Design and Analyse Algorithms (Part 2)

10 weeks · 2 milestones

Algorithms: Design and Analysis, Part 2 (Stanford on edX (free videos also at algorithmsilluminated.org)), then one project of your own. Part of the Varsity Curriculum: Computer Science.

Milestone map

Milestone map

2 milestones

Do the course work in public

4–8 weeks (4–8 hrs/week)

Take Algorithms: Design and Analysis, Part 2 for free and do the programming problems: greedy, dynamic programming, NP-hard heuristics. Keep everything in one public repo or notebook as you go. Certificates cost money. Audit is free; you never need the certificate here.

Proof required

Link your public repo or notebook with the programming problems: greedy, dynamic programming, NP-hard heuristics, and a screenshot or log showing the self-check passed.

What gets checked

  • Each implementation passes the test cases.
  • Running time is stated and matches.
  • Heuristics are compared with exact answers on small inputs.

Common mistakes

  • Copying posted answers: verifiers read the history.
  • Skipping the self-check, then asking for review too early.

Powstik Guide

A public repo or notebook with the programming problems: greedy, dynamic programming, NP-hard heuristics.

Steps

  1. Make a public repo or notebook first.
  2. Do one unit at a time and commit after each.
  3. Run the self-check: Run your code on the book site's test cases before the big inputs.
  4. Write a short README: what is here and how to run it.
  5. Ask three people who know the topic to check it.

Template

README
Course: Algorithms: Design and Analysis, Part 2 (Stanford on edX (free videos also at algorithmsilluminated.org))
What is here:
How to run it:
Self-check result:
What was hardest:

What gets sent back

  • No history, just one big upload.
  • Self-check not shown.
  • Code that does not run from the README.

Resources

Foundationstart here

Depthgo deeper

What a verifier looks for

  • Each implementation passes the test cases.
  • Running time is stated and matches.
  • Heuristics are compared with exact answers on small inputs.
  • Ask one question about a choice in the code; the answer should be clear.

You'll sign in first, then come straight back here.

Solve a hard problem well enough

1–3 weeks (5–8 hrs/week)

Use what you learned. Make a program that tackles an NP-hard problem on real data (a delivery route, a schedule) and compares two methods. Keep it small enough to finish in about two weeks.

Proof required

Link a program that tackles an NP-hard problem on real data (a delivery route, a schedule) and compares two methods, with a README that says how to run or read it.

What gets checked

  • Two methods are compared fairly.
  • Results are measured, not guessed.
  • Limits are stated.

Common mistakes

  • A project too big to finish.
  • A demo that only works on your machine.

Powstik Guide

A program that tackles an NP-hard problem on real data (a delivery route, a schedule) and compares two methods.

Steps

  1. Write one line: what it does and for whom.
  2. Build the smallest version that works.
  3. Test it on someone else's machine or with someone else reading it.
  4. Write the README.
  5. Ask three people to check it.

Template

README
What it does:
Who it is for:
How to run it:
What I would do next:

What gets sent back

  • Does not run from the README.
  • Not clearly the person's own work.
  • Claims more than it does.

Resources

Foundationstart here

Depthgo deeper

What a verifier looks for

  • Two methods are compared fairly.
  • Results are measured, not guessed.
  • Limits are stated.
  • Check that the work is the person's own.

You'll sign in first, then come straight back here.

Part of