Cajic - An Illustrative Introduction to Algorithms

An Illustrative Introduction to Algorithms — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "An Illustrative Introduction to Algorithms" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

1234567...36

Copyright 2019 by Dino Cajic
All rights reserved. This book or any portion thereof may not be reproduced or used in any manner whatsoever without the express written permission of the copyright owner except for the use of brief quotations in a book review.

First Edition 2019

Contents

Chapter 0: Introduction

Let me make an educated guess: you learn best when the information is presented to you visually. Me too. This book is going to attempt to teach you a rather complex subject without the use of any words. Okay, maybe some words. Most illustrations will have an explanation attached to them. There are three approaches to reading this book:

Read about the algorithm online and then see if you can follow the traversal illustrated in this book.

View the algorithm in action by going through the chapter designated for the algorithm and then go online and read further about it.

Just view the algorithm as is outlined in this book. A significant amount of time was dedicated to make these algorithms easy to follow.

Not everything in this book is on algorithm traversal, however, everything is related to algorithms. Chapter 1 illustrates the Big O complexity for the algorithms we discuss in this book. It does so by showing the best (), average () and worst (O) time complexity. You may have encountered Big O notation, but a good portion of people have not encountered Big Omega () or Big Theta () notation. Chapters 2 and 3 are dedicated to introducing you to those topics.

A few other chapters are dedicated to data structures that you may need to know before proceeding to the specific algorithm that utilizes those data structures. The book is intended for first time learners as well as a reference guide for all programmers. The book does not contain any code since its readily available online. The goal of this book is to get you acquainted with the concept of each algorithm. If you can visualize it, you can code it.

Chapter 1: Big O Complexity

The graph is self-explanatory. Try to stick away from the algorithms that have a time complexity in red and attempt to stay with the ones in orange if you have no other choice. Yellow and green is where you would like to optimally reside. With some extra research, youll soon see that even O( n log(n) ) is good enough.

ALGORITHM	BEST	AVERAGE	BIG O
Binary Tree Search In-Pre-Post- Order	( n )	( n )	O( n )
Binary Search	( )	( log(n) )	O( log(n) )
Bubble Sort	( n )	( n )	O( n )
Breadth First Search (BFS)	( |V| + |E| )	( |V| + |E| )	O( |V| * |V| )
Depth First Search (DFS) Directed Graph	( |V| + |E| )	( |V| + |E| )	O( |V| + |E| )
Depth First Search (DFS) Undirected Graph	( |V| + |E| )	( |V| + |E| )	O( |V| + 2|E| )
Heap Sort	( n )	( n log(n) )	O( n log(n) )
Insertion Sort	( n )	( n )	O( n )
Kruskals Algorithm	( E log(E) )	( E log(E) )	O( E log(E) )
Merge Sort	( n log(n) )	( n log(n) )	O( n log(n) )
Prims Algorithm	( V log(V) )	( E log(V) )	O( V log(V) )
Quick Sort	( n log(n) )	( n log(n) )	O( n )
Selection Sort	( n )	( n )	O( n )

Chapter 2: Lower Bounds

What are the lower bounds of an algorithm? Instead of giving you a formal definition, lets look at weather. Most weather forecasters will provide you with the high and the low; the accurate temperature is somewhere in the middle. The high is your upper bound and the low is your lower bound. When relating this concept to algorithms, certain problems have provable lower bounds meaning that you will be incapable of providing a better answer than what was previously proven. For example, the minimum number of comparisons that you would need to sort 5 numbers is 7. Lets look at a few additional examples.

Example 1

You have 81 bottles of water. A bottle of water can be heavier than the others, lighter than the others, or equal in weight as the rest. What is the lower bound?

The formula to find the lower bounds of a problem is ceiling(log b n ) , where b is the number of possible outcomes and n is the number of possible answers. Most times b is going to be either 2 or 3. In the example above, you have 3 possibilities: heavier, lighter or equal. In most cases, the second variable, n , is more difficult to compute. In this example its straight forward: you have 81 bottles of water, so you have 81 possible answers. Well look at another example where its not so straight forward later.

ceiling(log81) = 4

Example 2

You flip a coin 64 times. What is the lower bound?

In this example, b would equal 2 since during each flip we get either heads or tails. The number of possible answers, n, is 128. Why 128? We flip the coin 64 times and during each flip we can get either heads or tails, so the possible number of answers is 128.

ceiling(log128) = 7

Example 3

Find the minimum number of comparisons required to sort 5 numbers. The difficulty increases here but its still not bad. Once you see this type of problem, you apply the same logic. There is a total of 5! or 120 possible outcomes. A binary sort tree will have 7 levels for the sorting procedure.

ceiling(logn!)

ceiling(log5!)

ceiling(log120) = 7

Chapter 3: Master Theorem

There are many times when you have to write a recurrence relation for a divide and conquer problem. The example below shows the recurrence relation for a binary search algorithm where you divide the problem by half and you accomplish a constant amount of work at each level:

T(n) = T() + O(1)

The general formula for the master theorem states that T(n) = aT()+ O(n c ) with T(0) = and T(1) = (1) . There are three conditions to the master theorem:

• If c < log b a, then T(n) = (n log b a )
• If c = log b a, then T(n) = (n c logn)
• If c > log b a, then T(n) = (n c )

Pretty simple. Lets look at a couple of examples.

Example 1

T(n) = T() + n
log 10/7 1 < n, therefore T(n) = (n)

Example 2

T(n) = 4T(n/3) + nlogn

Next page

1234567...36

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

Similar books «An Illustrative Introduction to Algorithms»

Look at similar books to An Illustrative Introduction to Algorithms. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.

Thomas H. Cormen

Introduction to Algorithms, Fourth Edition

Richard J. Lipton

Introduction to Quantum Algorithms via Linear Algebra, second edition

Unknown

Introduction to Algorithms The Computer Science of Human Decisions nodrm

Stephens

Essential algorithms: a practical approach to computer algorithms using Python and C#

Yang Hu

Graphic Go Algorithms: Graphically learn data structures and algorithms better than before

Luciano Manelli

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Sriraman Sridharan

Discrete Mathematics: Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography

Claus Matzinger

Hands-On Data Structures and Algorithms with Rust

Narasimha Karumanchi

Coding Interview Questions

Xin-She Yang

Nature-Inspired Optimization Algorithms

Robert Sedgewick

An Introduction to the Analysis of Algorithms

Rod Stephens

Essential Algorithms: A Practical Approach to Computer Algorithms

Discussion, reviews of the book An Illustrative Introduction to Algorithms and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.