Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

CS614. Advanced Algorithms. L18 Quiz.

CS614. Advanced Algorithms.

L18 Quiz

Back to the course page

Problem 1. 3-Hitting Set

Obtain an algorithm for 3-Hitting Set running in time 2.4656knO(1)2.4656^k n^{\mathcal{O}(1)}2.4656knO(1) using iterative compression.

Problem 2. d-Hitting Set

Generalize the algorithm from the previous problem to obtain an algorithm for ddd-Hitting Set running in time ((d−1)+0.4656)knO(1)((d-1)+0.4656)^k n^{\mathcal{O}(1)}((d−1)+0.4656)knO(1).


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×