Saturday, October 17, 2009

Tutorial & Answers- Design and Analysis of Algorithms I

1.

a. Define the term Algorithm in your own words.

Algorithm is finite set of well defined instructions for accomplishing some task given an initial state that will terminate in a defined end state.

source:http://www.newworldencyclopedia.org/entry/Algorithm

b. What are the important properties of an algorithm?

  • Finiteness      :- an algorithm terminates after finite number of steps.
  • Definiteness  :-each step of algorithm is unambiguous.{ This means that actions specify by the steps cannot be interpreted in multiple ways & can be performed without any confusion. }
  • input              :-an algorithm accepts zero or more inputs.
  • output            :-it produces at least one output.
  • effectiveness :-it consists of basic instructions that are realizable.{ This means that the instructions performed by using the given input in a finite amount of time. }

source:http://www.newworldencyclopedia.org/entry/Algorithm

 

c. List the different way we can express an algorithm.

natural languages, pseudo codes, flow charts, and programming languages.

source:http://en.wikipedia.org/wiki/Algorithm#Expressing_algorithms

 

d. List the different classes of algorithms and give a short account on each of them including advantages and comparisons where relevant?

 

e. Why is the worst case complexity more important than the average case and the best case?

Because it give an assurance of the upper bound for how much of resources an algorithm would use

f. What is time complexity and what is space complexity, in computer science context?

  • The time complexity of a problem is the number of steps that it takes to solve an instance of problem as a function of the size of the input(n),using the most efficient algorithm.

         { R(n)=>T(n) where R(n):worst case steps T(n)=time complexity }

  • The space complexity of a problem is a related concept, that measures the amount of space, or memory required by the algorithm.

         Space complexity is also measured with Big O notation.

g. Define the terms efficient algorithm, inefficient algorithm and a correct algorithm.

  • efficient algorithm :For each “efficient” run-time there is a constant, k, such that the running time is at most n^k when n is large enough.
  • inefficient algorithm :For each “inefficient” run-time there is No constant, k, such that the running tine is at most n^k when n is large enough

          {Here we consider an algorithm with worst case run-time complexity of 2^n,3^n,4^n,n^logn}

  • correct algorithm :algorithm is correct if for each input it produces the correct output

h. Define the terms polynomial time complexity and non-polynomial time complexity.

  • Polynomial time complexity :There are problem f, fror which there is an algorithm a taking atmost n^k steps, an inputs of length n. i.e. f in T(n^k)
  • Non-polynomial time complexity :There are problem f, fror which there is not an algorithm a taking atmost n^k steps, an inputs of length n. i.e. f not in T(n^k)

i. Define the three complexity classes of algorithms.

j. Define the terms deterministic algorithm and non-deterministic algorithm.

k. Differentiate between a decision problem and an optimization problem.

2.

a. What is computational complexity?

b. Why is the `Big-O' Notation is useful?

c. What is meant by NP-completeness?

d. List down 5 problems that belong to the NP-Complete category.

3. A farmer has a goat, a wolf and cabbages. He is on the eastern shore of the river and has to take the goat, the wolf and the cabbages to the western shore. He has a boat where he can travel with only one other item. The rules are that he cannot leave the cabbage along with the goat, and he cannot leave the goat alone with the wolf.

If you were to apply the Alpha-Beta Pruning method, the Branch and Bound Algorithm or the Backtracking Algorithm, which will give you a faster solution?

4. Write a recursive algorithm for merge sort in pseudo code together with the pseudo code for the merging operation.

Friday, October 16, 2009

Tutorial - Design and Analysis of Algorithms II

1.) Greedy Algorithms works by making the decision that seems most promising at any moment; it never reconsiders this decision, whatever situation may arise later.
Consider the problem of "Making Change".
Coins that are available are:
· dollars (100 cents)
· quarters (25 cents)
· dimes (10 cents)
· nickels (5 cents)
· pennies (1 cent)
Problem  :  Make a change of a given amount using the smallest possible number of coins.
Example  :  
Make a change for $2.89 (289 cents), here n = 2.89 and the solution contains 2 dollars, 3 quarters, 1 dime and 4 pennies. The algorithm is greedy because at every stage it chooses the largest coin without worrying about the consequences. Moreover, it never changes its mind in the sense that once a coin has been included in the solution set, it remains there.
Design an algorithm to solve the above problem using the greedy strategy.
2.) A thief robbing a store can carry a maximum weight of W in his knapsack. There are n items, and the ith item weighs wi and is worth vi dollars. What items should the thief take in order make the maximum money out of them?
There are two versions of this problem:
Fractional knapsack problem: The setup is same, but the thief can take fractions of each item, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.

0-1 knapsack problem: The setup is the same, but the items may not be broken into smaller pieces, so the thief may decide either to take an item or to leave it (binary choice) behind.
Fractional knapsack problem
· Exhibit greedy choice property.
        => Greedy algorithm exists.
· Exhibit optimal substructure property.
0-1 knapsack problem
· Does not Exhibit greedy choice property.
        => No greedy algorithm exists.
· Exhibit optimal substructure property.
· Only dynamic programming algorithm exists.
Design a Greedy algorithm solution and a Dynamic programming solution to the fractional knapsack problem and the 0-1 knapsack problem respectively.
3.) Does backtracking make an algorithm non-deterministic? Explain your answer.
4.) Design an algorithm using backtracking, to position n queens on an n x n chess board so that no two queens threaten the others.
Input: positive integer n
Output: all possible ways n queens can be placed on an n x n chess board so that no two queens threaten each other. Each output consists of an array of integers ‘col’ indexed from 1 to n, where col[i] is the column where the queen in ith row is placed.

5.) Design an algorithm for the breadth first search using the branch and bound approach.

Thursday, October 15, 2009

Tutorial-Server side Web Programming(CS310)

 

  1. Create a web page as the home page for the Department of Statistics and Computer Science.

    image

    • You may use your own creative ideas to create the web page
    • Use an External Cascading Style Sheet to apply the style properties.
    • When the user move the mouse pointer over a menu option it should be emphasized with different styles. (use: hover element).
    • Insert images of the University Logo and the department into your web page.
    • In the area for News
      •   Should display the Headings of the latest news regarding the academic
        work of the department as hyperlinks.
      • When click on the hyperlinks should open a page with more details of the
        particular news.
  2. Create a Web page which contains a map which shows the separation of provinces of Sri Lanka. When the user clicks on a particular region of a province on the map some
    details of that province should be visible.
    Hint: use HTML Image Maps. i.e. Map element and Image element with the usemap attribute.
  3. Use JavaScript to create a web page that gets five numbers from the user and prints them in ascending or descending order in the same page. The user should also be given the option to choose the sorting method, ascending or descending.
  4. Design the following simple calculator using JavaScript. You should avoid invalid user inputs to the program. image
  5. Using any graphics software, create a menu bar as follows. Include it in a web page
    and provide links to programs, courses, faculty, research and department of Computer
    Science and Engineering using image maps. image
  6. Create a web page that users can input their Date of Birth in the format given below.image
    • Validate the input using JavaScript. You should consider all possible inputs that can be invalid for a Date of Birth. 
    • When the entered value is invalid and valid it should be displayed to the user
      as shown below.

image

Hint: Use innerText property to display the message.

Wednesday, October 14, 2009

Answer-Server side Web Programming tute1-Q1

Answer for Question 1:
<html>
<head>
    <title>Home Page</title>
        <style>
          .gray{background-color:#CCCCCC;font-weight:bold;}
          .white {color: #FFFFFF;}
          table{border:#000000; border-style:groove;}
          .style1 {font-size: 12px; font-weight:bold;}
        </style>
</head>
<body>
    <table border='1' width="100%">
        <tr>
           <td  width="75%" height="69" colspan="3">
            <h1 align="center" style="vertical-align:middle">UNIVERSITY OF PERADENIYA</h1>   
           </td>
           <td width="25%" bgcolor="#CCCCCC" >
             <span class="white"><a href="directory.html" class="white">Directory</a>|<a href="contact.html" class="white">Contact Us</a>|<a href="serch.html" class="white">Search</a></span> </td>
        </tr>
        <tr>
           <td colspan="4">
             <strong>Faculty of Science           </strong></td>
        </tr>
        <tr>
           <td colspan="4">
             <strong>Department of Statistics &amp; Computer Science </strong></td>
        </tr>
        <tr >
           <td width="15%" bgcolor="#FFFFFF">
            <span class="gray">Naviagation</span><br>
            <a href=".html">Home</a><br>
            <a href=".html">Staff</a><br>
            <a href=".html">Student</a><br>
            <a href=".html">Publication</a><br>
            <a href=".html">Research</a><br>
            <a href=".html">Awards</a><br>
            <span class="gray">Courses</span><br>
            <a href=".html">Computer Science</a><br>
            <a href=".html">Statistics</a><br>
            <span class="gray">Online</span><br>
            <a href=".html">Course Materials</a><br>
            <a href=".html">Notices</a><br>
            <a href=".html">Forums</a><br>
            <a href=".html">FAQ</a><br>
            <a href=".html">Problem Reporting</a><br>
            <span class="gray">Services</span><br>
            <a href=".html">SSDAS</a><br>
            <span class="gray">Other</span><br>
            <a href=".html">Contact</a><br>           </td>
           <td ><img src="home.jpg" width="100%" height="100%"></td>
           <td width="35%" colspan="2" valign="top" >
                <span class="gray">news</span></td>
        </tr>
        <tr>
           <td colspan="2"><p><strong>University of Peradeniya</strong></p>
           <p>&nbsp;</p>
           <p>&nbsp;</p></td>
           <td rowspan="2" colspan="2" valign="top"><p class="style1">Department of Statistics &amp; Computer Science<br>
           University of Peradeniya<br>Peradeniya<br>
           Sri Lanka </p>
           </td>
        </tr>
        <tr >
           <td height="54" colspan="2"><strong class="style1">Copyright&copy;,Department Of Statistics &amp; Computer Science,University of Peradeniya.All rights reserved.</strong></td>
        </tr>
    </table>
</body>
</html>
OUTPUT:

UNIVERSITY OF PERADENIYA

Directory|Contact Us|Search
Faculty of Science
Department of Statistics & Computer Science
Navigation
Home
Staff
Student
Publication
Research
Awards
Courses
Computer Science
Statistics
Online
Course Materials
Notices
Forums
FAQ
Problem Reporting
Services
SSDAS
Other
Contact

news
University of Peradeniya


Department of Statistics & Computer Science
University of Peradeniya
Peradeniya
Sri Lanka
Copyright©,Department Of Statistics & Computer Science,University of Peradeniya.All rights reserved.

ORIGINAL OUTPUT:
image