Algorithms - Ch 1 Foundations

Late post b/c vacation and stuff, but I'm back now.

One of my algorithm books came in today.  I decided to order two, one for my class coming up this quarter, and another that I found regarded as the standard in the field.

Algorithm Design: Foundations, Analysis, and Internet Examples 

Introduction to Algorithms 
Introduction to Algorithms just came in and so far it a pretty good read.  It comes across very accessible to newbies like myself, but has a rigor and complexity to it still.  For the next couple of weeks, I think I will focus on burning through the first few chapters of this book, which will help me with my class this quarter.  I'll probably still work on Java projects, but I think that it will be a side thing I do in my spare time for now.

Ch 1 - Foundations

1.1 Role of Algorithms in Computing

Algorithms take an input and produces a set of output.  An algorithm is a sequence of steps that transform the input into output.

Take for example one of the most basic types of algorithms, which would be sorting.  It takes an input of some list and gives the the same list, but in a specified order.

The type of data structures that you use can play a major role in the performance of your algorithms.  Each data structure has its own properties and it is important to know the strengths and limitations of each data structure.

Hard Problems (or NP-Complete) - There are such problems today that we are unable to find an efficient solution for currently. 
  1. No one has proven there are no efficient solutions
  2. If an efficient solution exists for one of them, then there must be an efficient solution for all of them.
  3. NP-Complete problems are similar to some problems are have been solved, but not exactly the same.
The most common example of this taught is the "traveling salesman", where a salesman must find the shortest path to to reach each of his destinations and back home.  This problem has yet to be solved because every possible path between destinations would have to be checked to make sure that it is in fact the shortest path. That does not mean that this problem cannot be solved, but currently there is no algorithm that will be able to find the definite shortest path in a timely manner.  What we do have is what we call an "approximation algorithm", which allows us to find a solution that should be close the the shortest path, but may not actually be the shortest path, in a timely manner.

Comments

Popular posts from this blog

Uncle Bob's Clean Architecture

C4 Model: Describing Software Architecture

Running RabbitMQ with Docker