Algorithm Analysis

Algorithms Defined | Problem Solving | Search Algorithms | Pseudocode | Abstraction | Review

Computational Fairy Tales

The Ant and the Grasshopper: A Fable of Algorithms

Big OWhat is an algorithm and why should I care? An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer. Another way to put it is an algorithm instructs the computer to carry out an individual task or function. Algorithms are especially important to computers because computers are really general purpose machines for solving problems. But in order for a computer to be useful, we must give it a problem to solve and a technique for solving the problem.

Through the use of algorithms, we can make computers "intelligent" by programming them with various algorithms to solve problems. Because of their speed and accuracy, computers are well-suited for solving tedious problems such as searching for a name in a large telephone directory or adding a long column of numbers. However, the usefulness of computers as problem solving machines is limited because the solutions to some problems cannot be stated in an algorithm. Much of the study of computer science is dedicated to discovering efficient algorithms and representing them so that they can be understood by computers. An algorithm can be thought of a mathematical method of solving problems both big and small.

Computer Scientists use 'Big O notation' to more accurately describe the performance or complexity of an algorithm, and you are likely to come across this notation very quickly when investigating the performance of algorithms. It characterizes the resources needed by an algorithm and is usually applied to the execution time required, or sometimes the space used by the algorithm.

 

An algorithm should have the following five characteristics:

Okay, now we now know what an algorithm is. The bigger question is why should we care?

Kevin Slavin argues that we're living in a world designed for -- and increasingly controlled by -- algorithms. In this riveting talk from TEDGlobal, he shows how these complex computer programs determine espionage tactics, stock prices, movie scripts, and architecture. Slavin also warns that we are writing code we can't understand with implications we can't control.

Common Programming Algorithms

The divide and conquer algorithm recursively breaks down a problem into two more sub-problems of the same or related type, and continues the process until those become simple enough to be solved directly.

The greedy algorithm always makes the choice that looks best at that moment. It makes a locally optimal choice (the solution that best fits the current stage of the problem rather than the overall problem) in the hope that this choice will lead to a globally optimal solution.

With the backtracking algorithm, a program solves problems by choosing candidates that build towards the overall solution and discards partial candidates. A maze uses backtracking.

The branch and bound algorithm finds the optimal solution to a problem by systematically identifying all solution candidates and then eliminating large subsets of those candidates by estimating lower and upper bounds for the problem. Branch and bound algorithms are reserved for optimization problems specifically discrete and combinational optimization.

Search Algorithms

Have you ever thought how amazing a search algorithm is? Okay, most of us take for granted that when we type a keyword into a search engine and hit the enter key, what follows is going to the answer to our query.

In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. When you use a search engine, like Google, you want the answer to your query, not trillions of webpages. Algorithms are computer programs that look for clues to give you back exactly what you want.

For a typical query, there are thousands, if not millions, of webpages with helpful information. Algorithms are the computer processes and formulas that take your questions and turn them into answers. Today Google's algorithms rely on more than 200 unique signals or "clues" that make it possible to guess what you might really be looking for. These signals include things like the terms on websites, the freshness of content, your region and PageRank. http://www.google.com/insidesearch/howsearchworks/algorithms.html

Google is always working to improve the quality, accuracy, and efficiency of their search engine.

   

   

Assignment: 10 Algorithms That Dominate Our World

Directions: Read the article "The 10 Algorithms That Dominate Our World" and answer the following questions in itsLearning.

Assignment: Algorithms in Your Life Discussion

Directions: How are algorithms a part of your life? Share your experiences with algorithms by thinking about algorithms that are a part of your daily life. Some algorithms might not be so obvious. Not sure where to start? You can get some inspiration by reading How Science can help you sort out your sock by Jordan Dunbar of BBS News. Post your answers in a thoughtful paragraph (~100 words) to the Algorithms in Your Life discussion board in itsLearning. Then continue the collaborative discussion by responding (meaningfully) to at least two classmates.

Assignment: Question for Thought 4.3

Directions: There are problems that cannot be solved and there are times when an algorithm cannot be written to solve a problem. There is no algorithm that can solve all cases of the problem. A decidable problem is one where an algorithm can be written that results in a "yes" or "no" for answer for inputs. In contrast, an undecidable problem does not have an algorithm that can give a correct "yes" or "no" for each instance. Share an example of a situation that cannot be solved with the use of an algorithm and explain why it cannot be solved with an algorithm. Your essay should be ~150 words and typed directly into the itsLearning textbox. Do not attach a separate document and be sure you proofread.

Alogorithm Review

Quiz created by Shannon Anderson-Rush with GoConqr

Problem Solving

Problem solving in general consist of multiple steps:

Christopher Steiner is the author of Automate This (2012) and $20 Per Gallon, a New York Times bestseller (2009). He is a cofounder at Aisle50, a Y Combinator company that sells grocery deals through the World Wide Web. Before starting Aisle50 in 2011, Steiner was a senior writer covering technology at Forbes magazine for seven years.

Advantages of Combining Algorithms

Practice: Rewriting Directions

Directions: Read the directions to get to John's house. Now rewrite the directions to John's House using structured English.

directions to John's house

Assignment: Origami Algorithms

Directions: Using one sheet of origami paper, create the animal or flower from the pictorial instructions you were given. Write instructions (steps) in words, to create your origami animal or flower. You cannot use any pictures or diagrams. Be exact and detailed. You may use "YouTube" videos to help you as long as you are not accessing written instructions (it's your job to create the algorithm).

origami


Flow Charts

What is a flow chart? A flow chart is a graphical or symbolic representation of a process. Each step in the process is represented by a different symbol and contains a short description of the process step. The flow chart symbols are linked together with arrows showing the process flow direction.

Sometimes it's more effective to visualize something graphically that it is to describe it with words. That is the essence of what flowcharts do for you. Flowcharts explain a process clearly through symbols and text. Moreover, flowcharts give you the gist of the process flow in a single glance. The following are some of the more salient reasons to use flowcharts.

The top five reasons to use flowcharts include:

The Top 5 Reasons To Use Flowcharts

Common Flowchart Symbols

Different flow chart symbols have different meanings. The most common flow chart symbols are:

playing board games to learn flowcharting

Assignment: Flowcharting with Board Games

Directions: Select a simple children's board game such as Sorry, Trouble, CandyLand or Chutes and Ladders. Create a flow chart, using the appropriate charting symbols, illustrating the decision making process required while playing the game.


Pseudocode

Algorithms can be expressed in many different languages - natural language (English), code, mathematics - all ranging from formal to informal syntax. When algorithms are being designed, they can be expressed in a notation, known as pseudocode, that is independent of any programming language. Pseudocode is, as the name implies, not real code, but it looks like code. It helps people to understand a problem domain or solution better without having to add all the baggage necessary when using a real language. In short: it is used only for illustrational purposes. Pseudocode is not an actual programming language. It contains well-defined structures that resemble programming languages, but these are not unique to one particular language.

pseudocode

You do not need to be a programmer to understand this code. When read aloud, it almost sounds like regular English. On the other hand, the logic and structure is starting to look a lot like code.

The example illustrates some of the basic aspects of pseudocode. First, every instruction is printed on a new line. The logic of the problem needs to be broken down into small steps that are very specific.

Second, pseudocode uses some key programming terms, such as 'if' and 'else.' The use of if-else is a fundamental construct in programming, known as a selection or decision statement. Based on a condition, only one of multiple options is carried out. Every programming language uses these types of if-else constructs. However, the details on exactly how this logic is implemented will vary among languages. When you are writing pseudocode, you don't worry about those differences and instead focus on the general logic.

Third, individual lines of pseudocode often start with action words that tell you to do something, as you might expect for a series of instructions. Verbs like 'print', 'read,' 'calculate' are common. These verbs correspond closely to commands in programming language, although the actual term may be different. Using Pseudocode to Map Code at Study.com

Statements Used in Pseudocode

Pseudocode is written in simple statements that fall under three basic categories:


Abstraction

abstract artModern systems are growing ever more complex, and the ability to use abstraction to reduce the complexity of interacting with these systems is critical to successful operation. Humans can manage only seven (plus or minus 2) pieces of information at one time.

An abstraction is a general and simplified representation of something. You use abstractions all the time, although you probably donít refer to them abstractions. You couldnít think or speak without abstractions. Words, ideas, concepts, maps, models, symbols are all examples of abstractions that we use every day to think about and talk about the world.

Our ideas and concepts are abstractions and formed through a process of leaving out details of the specific things that the idea represents and condensing information in order to focus on relevant aspects of the object or objects we are representing.

Some of the most abstract examples of abstractions are the words we use in our everyday language. For example, our concept of chair is general enough to represent any and all chairs. Unlike maps, models and floor plans, which have some visible similarities with the objects they represent, a word is completely abstract.

abstraction table

Slide Set created by Shannon Anderson-Rush with GoConqr

Activity: Map Activity

Directions: Add your name pin to your birth city/state†to the Google Map.


Birthday Map

Reflect on the following questions:

Slide Set created by Shannon Anderson-Rush with GoConqr

Assignment: Question for Thought 4.2

Directions: What are other examples of reducing a complex problem to produce a more manageable problem? Consider the consequences of your proposed reductions (e.g., the loss of accuracy in simulating movement through water). Post your response (~100 words) directly to the itsLearning textbox. Do not attach a separate document and be sure to proofread before posting.


Review

Flash Card Deck created by sarush with GoConqr

Resources

If you are having problems viewing this page, opening videos, or accessing the URLs, the direct links are posted below. All assignments are submitted in itsLearning. If you have having problems, contact Mrs. Rush through the itsLearning email client.

What is an algorithm and why should you care?: https://www.youtube.com/watch?v=CvSOaYi89B4

The Big Bang Theory - The Friendship Algorithm: https://www.youtube.com/watch?v=k0xgjUhEG3U

How algorithm shape our world: https://www.youtube.com/watch?v=ENWVRcMGDoU

Algorithms are taking over the world: https://www.youtube.com/watch?v=H_aLU-NOdHM

Improving the world's videos with algorithms: https://www.youtube.com/watch?v=lTjjV9xKYhk

Findable photos using data and algorithms: https://www.youtube.com/watch?v=o1mNf6_YqZM

The evolution of search: https://www.youtube.com/watch?v=mTBShTwCnD4

How Google makes improvements to its search algorithm: https://www.youtube.com/watch?v=J5RZOU6vK4Q

Algorithms in pseudocode and flow charts: https://www.youtube.com/watch?v=XDWw4Ltfy5w

Algorithm to Pseudocode to Code: https://www.youtube.com/watch?v=Q13YfIFSGmk

Programming Basics #36 Writing Pseudocode: https://www.youtube.com/watch?v=4G0EYfrrDT8

Credits

Flow Chart Example picture: www.abstractingcs.html

Abstract flower picture: http://www.bhmpics.com/view-flower_and_petals_abstraction-wide.html

Common Flowchart Symbols: http://www.breezetree.com/articles/what-is-a-flow-chart.htm


Transcript of this lesson