Reading 04: Bit Manipulation, Dynamic Programming

Everyone:

Next week, we will work on problems related to the following problem solving techniques:

  1. Bit Manipulation: This technique takes advantage of the bit representation of an integer to compactly store information using bitwise logical operations.

  2. Dynamic Programming: This is a problem solving technique that can be viewed as a combination of complete search (correctness) and greedy algorithms (efficiency).

Both of these techniques will come in handy for solving Challenge 10, Challenge 11, and Challenge 12.

Reading

The readings for this week are:

  1. Competitive Programmer's Handbook

    • Chapter 7 Dynamic Programming

    • Chapter 10 Bit manipulation

  2. A graphical introduction to dynamic programming

Optional

Quiz

Once you have done the readings, answer the following Reading 04 Quiz questions:

Submission

To submit you work, follow the same process outlined in Reading 01:

$ git checkout master                 # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

$ git checkout -b reading04           # Create reading04 branch and check it out

$ cd reading04                        # Go into reading04 folder
$ $EDITOR answers.json                # Edit your answers.json file

$ ../.scripts/submit.py               # Check reading04 quiz
Submitting reading04 assignment ...
Submitting reading04 quiz ...
      Q1 0.50
      Q2 1.00
      Q3 0.50
      Q4 0.50
      Q5 0.50
      Q6 1.00
   Score 4.00

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 04: Done"    # Commit work

$ git push -u origin reading04        # Push branch to GitLab

Remember to create a merge request and assign it to the instructor.