121x Filetype PDF File size 2.47 MB Source: home.cse.ust.hk
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
no reviews yet
Please Login to review.