Reading 03: Complete Search, Bit Manipulation, Greedy Algorithms

Everyone:

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

1. Complete Search: This involves trying out every possibility and testing them. Although brute-force search may feel wrong, sometimes the most straightforward solution is the best one. To perform a "complete search" we will need the ability to generate each combination and the ability to perform backtracking.

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

3. Greedy Algorithms: This is a problem solving approach where we attempt to find a global optimum by always making the locally optimal choice. That is, greedy algorithms take advantage of certain problem features to avoid searching every possibility in order to find an optimal solution.

Both of these techniques will come in handy for solving Challenge 07, Challenge 08, and Challenge 09.

Reading¶

The readings for this week are:

1. Competitive Programmer's Handbook

   • Chapter 5 Complete Search
   • Chapter 6 Greedy Algorithm
   • Chapter 10 Bit manipulation

Quiz¶

Once you have done the readings, answer the following Reading 03 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 GitHub

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

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

$ ../.scripts/check.py                # Check reading03 quiz
Checking reading03 quiz ...
      Q1 0.50
      Q2 0.50
      Q3 0.50
      Q4 1.00
      Q5 0.50
      Q6 0.50
      Q7 0.50
   Score 4.00 / 4.00
  Status Success

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

$ git push -u origin reading03        # Push branch to GitHub