Problems on Algorithms
          Second Edition
          Ian Parberry and William Gasarch
          July 2002
          Consisting of
          Problems on Algorithms, First Edition, by Ian
          Parberry, formerly published in 1994 by Prentice-
          Hall, Inc.
          Errata to the First Edition, published in 1998.
          Supplementary Problems, by William Gasarch.
          © Ian Parberry and William Gasarch, 2002.
                                          License Agreement
                       This work is copyright Ian Parberry and William Gasarch. All rights reserved. The authors offer
                       this work, retail value US$20, free of charge under the following conditions:
                       •   No part of this work may be made available on a public forum (including, but not limited to a
                           web page, ftp site, bulletin board, or internet news group) without the written permission of
                           the authors.
                       •   No part of this work may be rented, leased, or offered for sale commercially in any form or
                           by any means, either print, electronic, or otherwise, without written permission of the authors.
                       •   If you wish to provide access to this work in either print or electronic form, you may do so by
                           providing a link to, and/or listing the URL for the online version of this license agreement:
                                              http://hercule.csci.unt.edu/ian/books/free/license.html.
                           You may not link directly to the PDF file.
                       •   All printed versions of any or all parts of this work must include this license agreement.
                           Receipt of a printed copy of this work implies acceptance of the terms of this license
                           agreement. If you have received a printed copy of this work and do not accept the terms of
                           this license agreement, please destroy your copy by having it recycled in the most appropriate
                           manner available to you.
                       •   You may download a single copy of this work. You may make as many copies as you wish
                           for your own personal use. You may not give a copy to any other person unless that person
                           has read, understood, and agreed to the terms of this license agreement.
                       •   You undertake to donate a reasonable amount of your time or money to the charity of your
                           choice as soon as your personal circumstances allow you to do so. The author requests that
                           you make a cash donation to The National Multiple Sclerosis Society in the following amount
                           for each work that you receive:
                                •   $5 if you are a student,
                                •   $10 if you are a faculty member of a college, university, or school,
                                •   $20 if you are employed full-time in the computer industry.
                       Faculty, if you wish to use this work in your classroom, you are requested to:
                       •   encourage your students to make individual donations, or
                       •   make a lump-sum donation on behalf of your class.
                       If you have a credit card, you may place your donation online at:
                                               https://www.nationalmssociety.org/donate/donate.asp.
                       Otherwise, donations may be sent to:
                       National Multiple Sclerosis Society - Lone Star Chapter
                       8111 North Stadium Drive
                       Houston, Texas 77054
                       If you restrict your donation to the National MS Society's targeted research campaign, 100% of
                       your money will be directed to fund the latest research to find a cure for MS. For the story of Ian
                       Parberry's experience with Multiple Sclerosis, see http:// multiplesclerosissucks.com.
                 Problems on Algorithms
                                 by
                           Ian Parberry
                          (ian@ponder.csci.unt.edu)
                          Dept. of Computer Science
                          University of North Texas
                            Denton, TX 76203
                              August, 1994
                                                                                           Contents
                              Preface                                                                            ix
                              1 Introduction                                                                      1
                                  1.1  How to Use This Book                                                       1
                                  1.2  Overview of Chapters                                                       1
                                  1.3  Pseudocode                                                                 3
                                  1.4  Useful Texts                                                               4
                              2 Mathematical Induction                                                            8
                                  2.1  Summations                                                                 8
                                  2.2  Inequalities                                                              10
                                  2.3  Floors and Ceilings                                                       10
                                  2.4  Divisibility                                                              11
                                  2.5  Postage Stamps                                                            11
                                  2.6  Chessboard Problems                                                       12
                                  2.7  Fibonacci Numbers                                                         14
                                  2.8  Binomial Coefficients                                                       14
                                  2.9  What is Wrong?                                                            15
                                  2.10 Graphs                                                                    16
                                  2.11 Trees                                                                     17
                                  2.12 Geometry                                                                  18
                                  2.13 Miscellaneous                                                             19
                                  2.14 Hints                                                                     20
                                  2.15 Solutions                                                                 21
                                  2.16 Comments                                                                  23
                                                                                                                 iii