Practicing Running Time Analysis of Recursive Algorithms - Softcover

Pevac, Irena

Softcover

ISBN 10: 1539088863 ISBN 13: 9781539088868

Publisher: CreateSpace Independent Publishing Platform, 2016

Synopsis

Educators teaching Algorithms and students taking the course consider running time analysis of recursive algorithms one of the most difficult topics in the course. The limited number of examples in the textbooks is not sufficient to grasp the topic for most of the learners. This text is designed to help students learn time performance analysis. It may be helpful for instructors teaching those courses as well by providing them a poll of test questions, or helping those to create projects that are variations of existing examples. The book provides 60 examples. They are grouped into decrease-by-constant, decrease-by-constant-factor, divide-and-conquer, and general-decrease type. Each example has a description of the problem, recursive algorithm implemented in Java, and full running time analysis consisting of problem size, basic operation, recurrence, and detailed derivation of solution for the recurrence. Most of the examples were given to students on tests, final exams, or were part of the assigned projects. The last chapter of the book provides templates for the following seven basic complexity categories: log n, n, n log n, n squared, n cubed, a raised to the power of n , and n!, together with a list of possible variations for each template that do not affect their asymptotic performance. In addition, we provide list of problems to illustrate each of the templates.

About this title

About the Author

Irena Pevac is a professor of computer science at Central Connecticut State University. She has over twenty years of experience teaching Algorithms in undergraduate and graduate level courses. Other computer science courses that she taught are: introductory programming courses, data structures, database, artificial intelligence, theory of computation, and theoretical computer science. She published four books and over 40 papers in journals and conference proceedings. The domain of her research publications includes automata and formal languages, computability, artificial intelligence, theorem proving, database design, algorithm time performance, and teaching.

Edition details

• Publisher: CreateSpace Independent Publishing Platform
• Publication date: 2016
• ISBN 10: 1539088863
• ISBN 13: 9781539088868
• Binding: Paperback
• Language: English
• Number of pages: 100