Algorithm Analysis & Abstraction

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

In simple terms, algorithms are sets of steps to complete a task.

In Computer Science, an algorithm is a process or set of rules to be followed in calculations or other problem-solving operations. 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.

The Ant and the Grasshopper: A Fable of Algorithms

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? It should be that you use an algorithm for making friends like Sheldon did on the Big Bang Theory or you have a ritual for brushing your teeth. 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 socks 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.


Why Should We Care About Algorithms?

Algorithms are solutions to problems. 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.

Assignment: Question for Thought 4.1

Directions: Algorithms have limits and there are some problems for which we do not have effective enough algorithms to solve. These are called intractable problems. Often intractable problems use a heuristic approach.

There are also problems that cannot be solved. 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.


Big O

Analyzing Algorithms

Algorithm Correctness

An algorithm's correctness refers to its accuracy and whether or not it contains errors. It is determined by mathematical reasoning rather than by testing. More than one correct algorithm can be created to solve a task. 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.

Algorithm Readability and Clarity

An important feature of any algorithm and program is how easy it is to read and follow. Clarity refers to how easy it is to understand. A computer program that is readable is clear. Readability is important to help programmers understanad a problem. Often times, the program's orginal programmer is not the same programmer as who makes changes and updates to it. Readability will impact the time and ability of the programmer to modify or correct the code. Features include variables and procedures (functions or methods) that are named according to their use and effective documentation of the program with comments in the code.

Algorithm Efficiency

The efficiency of algorthms deals with how long it will take to run and how much memory will be needed. Efficiency becomes especially important with extremely large data sets. While the time will vary based on the computer used, general rules are used to determine the efficiency of these 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 sorting sock algorithm is an example of a divide and conquer approach.

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. A navigaional algorithm would be an example and there can be many ways to get from point A to point B depending on the distance between those two points.

Searching

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. Did you know that when you seach using Google, you are actually searching Google's database where they have index and categorizes resources along with their location?

Google uses automated programs called spiders or crawlers, just like most search engines, to help generate its search results. Google has a large index of keywords that help determine search results. ... Google uses a trademarked algorithm called PageRank, which assigns each Web page a relevancy score.

A search engine spider does the search engine's grunt work: It scans Web pages and creates indexes of keywords. Once a spider has visited, scanned, categorized and indexed a page, it follows links from that page to other sites. The spider will continue to crawl from one site to the next, which means the search engine's index becomes more comprehensive and robust.J. Strickland, J. Donovan

You can learn more about Google's search engine by reading How Google Works by Jonathan Strickland and John Donovan.

Alogorithm Review

Quiz created by Shannon Anderson-Rush with GoConqr

Problem Solving

One of the most important skills you learn in your computer science courses is how to problem solve and the steps you use are an algorithm.

Problem solving in general consist of multiple steps:

Not every problem can be solved using an algorithm. Some problems may be unsolvable because there is no solution. Some problems can be solved but the solution takes an unreasonable amount of time. This is known as an intractable problem.

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.

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


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.

Assignment: Roberta Algorithm Assignment

Directions: You are working with a group of scientists who want to program a robot to perform a task. You have been assigned a robot named Roberta. Create a flowchart algorithm using www.gliffy.com, or any other free flowchart maker, to detail the steps Roberta must take to travel from your front door to the end of your street and return back to your front yard (or another path of your choice that involves at least 5 steps with at least 2 turns). After you have created the flowchart algorithm, save the flowchart as an image (screen shot or snip it tool). If you have problems saving the file as an image file, you may capture the screen and paste the image in a blank word processing document or embed the image into the assignment box. Save the document and submit your flowchart.


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.

What is the difference between an algorithm and pseudocode? An algorithm is a systematic logical approach used to solve problems in a computer while Pseudocode is the statement in plain English which may be translated later into a programming language (program). An algorithm is the semantic while the pseudocode is just a syntax of the communication about solving a problem.

Here is a couple of comparisons of an algorithm and the related pseudocode:

algorithm vs pseudocodealgorithm vs pseudocode

pseudocode

You do not need to be a programmer to understand this pseudocode. 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 without the stringent requirements of the programming syntax.

The examples 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


Activity: Question for Thought 4.2

Directions: "Once you have abstracted an object, it can be re-used. It can be modified to suit other situations." (Azagu, 2015). What are other examples of reducing a complex problem to produce a more manageable problem? Consider the ramifications (consequences) of your proposed reductions (e.g., the loss of accuracy in simulating movement through water as discussed in the Abstraction section of www.mrsrush.net). You must include at least one source with a parenthetical citation (look at the examples provided). 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