Algorithms Q&a

This book contains more than three hundred questions on the design and analysis of algorithms. Also included are solutions or solution sketches to more than one hundred of these questions. Questions are classified as beginning, intermediate, and advanced. Covered topics include discrete math, program correctness, asymptotic growth of functions, recurrence relations, lower bound theory, average case analysis and randomized algorithms, divide and conquer algorithms, dynamic programming algorithms, greedy algorithms, computational geometry, string matching, graph and network algorithms, backtracking and branch and bound, algorithms in mathematics, and the theory of NP-completeness. There are some important points on certain language in the questions. The word ¡®describe¡¯ in a question that begins with ¡°Describe an algorithm for ¡­¡± should be taken to indicate that algorithms for the stated problem may be found in textbooks or other literature. The reader may wish to spend some time trying to design an algorithm from scratch, but not a lot. By contrast, a question of similar form that begins with ¡®Design¡¯ instead of ¡®Describe¡¯ should be taken to indicate that an algorithm of the desired characteristics should be designed from scratch. It goes without saying that a designed algorithm should be correct. If this is not easy to see in a particular case, give a proof. The word ¡®analyze¡¯ in a question should be taken to mean ¡°analyze running time asymptotically¡±. The phrase ¡°Exactly analyze¡± should be taken to mean ¡°analyze running time exactly, i.e., without ignoring constants¡±. In analyzing the running time of an algorithm that computes on numbers, remember to either explicitly assume that each number fits into a word of fixed size¨Cfor instance 32 bits¨Cor factor this into your analysis. This book is focused on questions and some solutions¡ªit is not a text on algorithms. It should be used in conjunction with a text on algorithms, and after the relevant topics have been understood. It will work well in the following situation. You are taking a course on algorithms and have attended some lectures on a certain topic (say divide and conquer algorithms). Use this book to practice the material by answering the questions. A related situation in which it will work well is practice for an exam on the topic (including master¡¯s or PhD qualifying exams). This book will also work well in problem-solving sessions lead by a teaching assistant in a course on algorithms. (Many schools use discussion or ¡°recitation¡± sessions, lead by teaching assistants, as adjuncts to the main lectures, to give the students more practice.) The teaching assistant could cover some of the answers in addition to the questions. The solution and solution sketches to about one-third of the questions are placed separately, in part 2 of the booklet. The author has been teaching a course on the design and analysis of algorithms, at various academic institutions, from 1993 to the present time.