CS 215 Design and Analysis of Algorithms Module 1 PDF

CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS MODULE 1 Introduction Module Overview: This module will lay down the basic foundation of algorithms and its properties as well as review the basic mathematical background needed for a...

CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS MODULE 1 Introduction Module Overview: This module will lay down the basic foundation of algorithms and its properties as well as review the basic mathematical background needed for algorithm analysis that will be introduced in the next module. It will also discuss briefly the role of algorithms in computing and present that syntax that will be used in this course to describe algorithms. This module is divided into three lessons: Lesson 1: Algorithms and Its Properties Lesson 2: Mathematical Tools in Analysis Lesson 3: Recursion Module Outcomes: At the completion of this module, you should be able to:  describe the behaviour of an algorithm;  perform the standard techniques for algorithm analysis; and  demonstrate how recursion works. 11  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS Lesson 1 Lesson Title: Algorithm and Its Properties Learning Outcomes: At the completion of this lesson, you should be able to:  describe the behaviour of an algorithm. Time Frame: 1 week Introduction You have reached the first stop of this course pack. In this lesson, we will look at the definition of algorithm and its properties. We will try a couple of card tricks that will help you understand the concept of an algorithm. We will also cover some applications of algorithms. Are you ready? Activity Imagine that I am shuffling a deck of playing cards. I deal out single cards, left to right into three piles of 7 cards, all face up and visible. For the purpose of illustration, assume that the figure below is already the result of doing the steps mentioned. 12  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS I want you to mentally select one of the cards and I will try to reveal the card you have selected. You must not tell me which card it is, but I want you to tell me the pile it is in. Have you selected your card? Since it is difficult to demonstrate this trick like this, let’s assume again that the card you selected is Ace of Clubs in the middle of the pile. If you are to replicate this card trick to others, you must not do this because the idea is to pretend that you are reading their mind and you are going to tell them the card they are thinking of. I will now collect up the cards, and deal them out a card at a time left to right into three (3) piles for three times. For every time I deal the cards, you must tell me the pile your card is in. Let’s assume again that below are the results of dealing the cards three additional times but this must be done with all the cards face up and visible. In the second deal, Ace of Clubs is still in the middle of the pile. In the third deal, Ace of Clubs is in the first pile and in the middle row. Finally, in the fourth and last deal, Ace of Clubs is already in the middle. You can now declare that you have already revealed the chosen card. 13  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS Analysis Let’s look at the “mechanics” of the trick. 1. How do you make it work? 2. Does this trick reveal the correct chosen card all the time? 3. Why does it work? Abstraction The card trick, which is named the “21-Card Trick ”, is really simple. All you have to do is make sure you always put the pile your volunteer selects carefully between the other two piles and deal the pack as above. Keep doing this for every time you deal the cards and after the fourth deal the middle card of the middle pile is the chosen card, which you can reveal as you see fit. The steps that you go through to get the 21-Card Trick to work guarantee that you will always reveal the chosen card. Hence, it works all the time as long as you follow the steps. These steps are also similar to the way that a computer steps through its instructions in a software program. In fact, all the computers do is follow instructions, which are algorithms that programmers 14  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS work out for them. The idea is that if computers follow the algorithm then they will always complete their task. In short, every program you have ever used is working the same way as an oversized magic trick. What is an Algorithm? An algorithm is a well-defined sequence of steps that solves a particular problem in a finite amount of time. “A problem can have many algorithms.” An algorithm is a sequence of computational steps that transform the input into the output. It is a tool for solving a well-specified computational problem. The algorithm describes a specific computational procedure for achieving that input/output relationship. What are the properties of Algorithms? 1. It must be correct. 2. It must be composed of a series of concrete steps. 3. It must be composed of a finite number of steps. 4. There can be no ambiguity as to which step will be performed next. 5. It must terminate. Here is the 21-Card Trick Algorithm: 1. Let a volunteer shuffle a pack of cards. 2. Deal out single cards, left to right intro three piles of seven cards, all face up and visible. 3. Let the volunteer mentally selects one of the cards and let him/her tell you the pile the card is in. 4. Repeat the following three times: 4.1 Collect the cards and ensure you always put the pile your volunteer selects between the other two piles and deal the pack as above. 5. On the fourth deal, the middle card of the middle pile is the chosen card. 15  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS How do we make sure that our algorithm is correct? Perform a series of tests by following the algorithm lots of times with different test cases To make sure that the 21-Card Trick algorithm is correct, we could do the trick plenty of times and check if it works every time. Yet the question is “how many times would we need to do the magic trick to be safe?” To be sure, we would have to try it out with every possible set of 21 cards, in all possible starting positions, checking for every card the person might have thought of. This is a lot of work, right? Hence, testing programs exhaustively is not practical. The rule is, if the program works each time then it is assumed that it works in the cases that were never tried. Computer scientists use the techniques of design, analysis, and experimentation. To design means to create algorithms; and to analyse entails examining algorithms and problems mathematically. In analysis, for example, it is possible to arrive at the following conclusions: o “Algorithm A1 is more efficient than algorithm A2” o “Problem P1 is not solvable but Problem P2 is solvable” o “Problem P3 is solvable but intractable” (i.e., requires too much time/resources to be of practical value) Lastly, experimentation means implementing systems and studying the resulting behaviour. In this course, you will be able to cover all these three techniques. Practical applications of algorithms are ubiquitous and include the following examples: The Internet, which enables people all around the world to quickly access and retrieve even large amount of information are capable of: o Finding good routes from the source host to the destination host using a clever algorithm o Finding pages quickly through Search engines about a particular information and rank the retrieved results using well-studied algorithms 16  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS The Human Genome Project – involves sophisticated algorithms that can: o Identify all the approximately 100,000 genes in the human DNA o Determine the sequences of approximately 3 billion chemical base pairs that make up the human DNA o Store all the derived information in databases o Develop tools for data analysis Other applications of algorithms abound in e-Commerce where public-key cryptography and digital signatures based on numerical algorithms and number theory are used. Algorithms are also used in manufacturing and other commercial enterprises whenever they need to allocate scarce resources in the most beneficial way using linear programming. It is also used to solve problems in market forecasting, weather prediction, logistics set-up, fraud detection, encryption, cancer detection, games, and a lot of real-world applications. 17  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS Let us now focus our attention to the syntax that will be used for this course. To describe algorithms in this course, we will follow the format below:  Algorithm Title  Input  Output  Body o Write in pseudo code (actual code is acceptable also) o Use of indentation o Keywords: if-then-else, while, for, repeat-until, do-while, return o Special symbols  Operators and other symbols Assignment operation  Equality = Comments // Empty Set  or { } There exists; for some  For all  Floor function  Ceiling function  Absolute value or set cardinality || Other math symbols , , , , ,  18  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS Here is an example of an algorithm to find the largest element in an array using the syntax notation above: ALGORITHM: MaxArrayElement INPUT: Array of A of n integers OUTPUT: Integer k such that A[i] = k i  {1,2,…,n} and A[j]  k j  {1,2,…,n} BODY: Max  A for i  2 to n if A[i] > max then max  A[i] return max Application (Let’s Do It!) 1. I want you to perform this another card trick called “Are you a psychic? ” with a friend or in front of an audience at home. You give them a pile of ten cards and tell them that they’re going to try to make a pair without looking at any of them. The cards are separated into two piles and then the spectator mixes them up a little under your direction. You discard the top two cards on each pile. You work through the piles that way, mixing and discarding until there are only two cards left. To the volunteer’s astonishment, the last two cards are a pair. They are psychic. As their jaw drops you show them that they are even better than they thought. It turns out every eliminated pair of cards match in value too. Mechanics: Before you start, get the Ace to the five of hearts and the Ace to five of spades out of the pack. Set them up in one pile in the order red 1-5 cards then black 1-5. Spread the cards in your hand and have the spectator point to the back of any card. Split the pack at that point and place the top pile at the bottom of the pack. Repeat this until they are happy the cards are well mixed. Deal the top five cards onto the table, reversing 19  CS 215 – DESIGN AND ANALYSIS OF ALGORITHMS their order. Place the remaining un-dealt cards in a second pile beside them. This keeps their order the same. You explain that as there are 5 cards in each pile you will give them 4 moves to test their psychic powers. A move involves taking the top card on one of the piles and placing it on the bottom of the same pile. They can, for example, do all 4 moves on one pile, 2 on each, or 3 on one and 1 on the other. It is their choice, their intuition, remembering that their aim is to be left with two matching cards. Once the 4 moves are made, remove the top card on each pile and place them aside, face down. Point out that it does not matter what they are because they are being discarded. Now there are 4 cards in each pile. Offer the spectator 3 moves, make those 3 swaps and then remove the top two cards from the piles. Keep doing this giving them one less move than the number of cards. Eventually you are left with two single cards and they will match, and so will all the other pairs discarded. Were you able to follow the steps correctly? Try writing a simplified algorithm for this card trick. 2. Write an algorithm that returns the third maximum element of an array using the syntax described in the preceding example. Closure Well done! You have just finished Lesson 1 of this module. Should there be some parts of the lesson which you need clarification, don’t hesitate to send me a message. Now if you are ready, please proceed to Lesson 2 of this module which will discuss the mathematical tools in analysis. 20