Tutorial & Answers-Design Patterns(CS407)

1. Software designing is hard and good designing is even hard. Explain why?       In this Problem we are asked two things.1) Why Hard  2) What is good design  According to the Design Patten book by gang of four

Designing object-oriented software is hard, and designing reusable object-oriented software is even harder. You must find pertinent objects, factor them into classes at the right granularity define class interfaces and inherited hierarchies, and establish key relationships among them. Your design should be specific to the problem at hand but also general enough to address future problems and requirements. You also want to avoid redesign, or at least minimize it. Experienced object-oriented designers will tell you that a reusable and flexible design is difficult if not impossible to get "right" the first time. Before a design is finished, they usually try to reuse it several times, modifying it each time.

Yet experienced object-oriented designers do make good designs. Meanwhile new designers are overwhelmed by the options available and tend to fall back on non-object-oriented techniques they've used before. It takes a long time for novices to learn what good object-oriented design is all about. Experienced designers evidently know something inexperienced ones don't. What is it?

2. Discuss the following statements.                                                                                        (a) Following design rules and guidelines may not produce good designs.
(b) Software development is a team work than an individual work.

3. (a) What does mean by the pattern selection problem?.                                      Pattern selection problem is How we select the best pattern to our software design 
(b) Do you think that existing pattern organizations address this problem? Justify
your answer.
4. In a certain organization, employees are allowed to access information objects,
but the direct access may cause several problems. Therefore, it is required to
solve this problem by applying a design pattern. Suggest an appropriate design
patterns to achieve this task. Describe your method in terms of class diagram.
For simplicity consider only one information object that consists of the following
interface:

Constructor(….)
Create()
Delete()
Update()
calTotal()
displayInfo()

5. There are two design patterns that can be applied in designing variants of an
algorithm that can be interchanged independently. What are those patterns?
Explain how you could use these patterns to design elementary sorting algorithms.

6. Some of the existing design patterns are large in scale whereas some others are small in scale. If any small-scale pattern addresses a sub-problem of a large scale pattern, the first one can be used to complement the second. Do you think that the Factory Method pattern complements the Strategy pattern? If not explain why. If yes, explain how you could use them in designing an application that traverse a Binary search Tree by using one of the four traversal methods: pre-order, in-order, post-order and level order traversals. Description should be provided by means of a class diagram or by means of a code in any object oriented programming language.

7. State and discuss the two Adapter patterns. You should explain the advantages and disadvantages of each pattern when applying to solve a candidate problem.

8. There are two patterns with similar solution structures. State those two patterns and explain how they differ.

9.Assume that you have an application with two sets of objects so that the states
of many objects depend on the state of another object. Do you think that you can design such a system with patterns? If so propose suitable pattern(s) for this task. Demonstrate the application of the proposed patterns by means of class diagram and code fragments.

10 .(a) Give a brief account of each of the following:

i) Creational patterns

creational design patterns are design patterns that deal with object creation mechanisms, trying to create objects in a manner suitable to the situation. The basic form of object creation could result in design problems or added complexity to the design. Creational design patterns solve this problem by somehow controlling this object creation.

ex:Abstract Factory ,Factory Method,Prototype,Singleton

ii) Structural patterns

structural design patterns are design patterns that ease the design by identifying a simple way to realize relationships between entities.

ex:Adapter,Composite,Facade,Proxy,Bridge

iii) Behavioral patterns

behavioral design patterns are design patterns that identify common communication patterns between objects and realize these patterns. By doing so, these patterns increase flexibility in carrying out this communication.

ex:Integrator,Strategy,Template method

Source:-http://en.wikipedia.org/wiki/Design_pattern_(computer_science)

(b) Discuss the statement “Pattern descriptions are informal and ambiguous”.
Describe how such informal descriptions effect on optimal usage of patterns.
Can you suggest a solution for this problem? Explain how your method assists
users.

Prolog Exercising control (AI,CS409)

Code window

 

steps

Prolog Examples II(AI,CS409)

Towers of Hanoi Problem

you have N rings of increasing size and three pegs. Initially the three rings are
stacked in order of decreasing size on the first peg. You can move them between pegs but you must never stack a big ring onto a smaller one. What is the sequence of moves to move from all the rings from the first to the the third peg.

answers:

hanoi( N ):- 
      move( N, left, middle, right ).
move(1,X,Y,_) :-
      write('Move top disk from '),
      write(X),
      write(' to '),
      write(Y),
      nl.
move(N,X,Y,Z) :-
      N>1,
      M is N-1,
      move(M,X,Z,Y),
      move(1,X,Y,_),
      move(M,Z,Y,X).

Find Factoria (N!) of a number

factorial(0, 1).                                          % Factorial of 0 is 1.
factorial(N, FactN) :-
    N > 0,                                                      % N is positive
    Nminus1 is N - 1,                                  % Calculate N minus 1
    factorial(Nminus1, FactNminus1), % recursion
    FactN is N * FactNminus1.                % N! = N * (N - 1)!

Prolog Examples (AI,CS409)

monkeys banana problem

There is a monkey at the door into a room. In the middle of the room a banana is hanging from the ceiling. The monkey is hungry and wants to get the banana, but he cannot stretch high enough from the floor. At the window of the room there is a box the monkey may use.

The monkey can perform the following actions: 

Walk on the floor
Climb the box
Push the box around (if it is already at the box)
Grasp the banana if standing on the box directly under the banana. 

Answers code:

move(state(middel, onbox, middle, hasnot),
grasp,
state(middle, onbox, middle, has)).
move(state(P, onfloor, P, H),
climb,
state(P, onbox, P, H)).
move(state(P1, onfloor, P1, H),
push(P1, P2),
state(P2, onfloor, P2, H)).
move(state(P1, onfloor, B, H),
walk(P1, P2),
state(P2, onfloor, B, H)).
canget(state(_,_,_,has)).
canget(State1) :-
move(State1, Move, State2),
canget(State2).

 

Prolog Examples (AI,CS409)

monkeys banana problem

There is a monkey at the door into a room. In the middle of the room a banana is hanging from the ceiling. The monkey is hungry and wants to get the banana, but he cannot stretch high enough from the floor. At the window of the room there is a box the monkey may use.

The monkey can perform the following actions: 

Walk on the floor
Climb the box
Push the box around (if it is already at the box)
Grasp the banana if standing on the box directly under the banana. 

Answers code:

move(state(middel, onbox, middle, hasnot),
grasp,
state(middle, onbox, middle, has)).
move(state(P, onfloor, P, H),
climb,
state(P, onbox, P, H)).
move(state(P1, onfloor, P1, H),
push(P1, P2),
state(P2, onfloor, P2, H)).
move(state(P1, onfloor, B, H),
walk(P1, P2),
state(P2, onfloor, B, H)).
canget(state(_,_,_,has)).
canget(State1) :-
move(State1, Move, State2),
canget(State2).

 

Prolog Examples (AI,CS409)

monkeys banana problem

There is a monkey at the door into a room. In the middle of the room a banana is hanging from the ceiling. The monkey is hungry and wants to get the banana, but he cannot stretch high enough from the floor. At the window of the room there is a box the monkey may use.
The monkey can perform the following actions: 
Walk on the floor
Climb the box
Push the box around (if it is already at the box)
Grasp the banana if standing on the box directly under the banana. 
Answers code:
move(state(middel, onbox, middle, hasnot),
grasp,
state(middle, onbox, middle, has)).
move(state(P, onfloor, P, H),
climb,
state(P, onbox, P, H)).
move(state(P1, onfloor, P1, H),
push(P1, P2),
state(P2, onfloor, P2, H)).
move(state(P1, onfloor, B, H),
walk(P1, P2),
state(P2, onfloor, B, H)).
canget(state(_,_,_,has)).
canget(State1) :-
move(State1, Move, State2),
canget(State2).

Prolog Introduction-I(AI ,CS409)

 

  Hi guys after very long time I’m posting for this blog because My Computer so speed to do blogging or web developing [you know what i mean:) ].

  Any way I came to know this SW with AI lecture  series.First I thought it will be boring one as it has text editor with hard compiling manner but after doing some exercise it makes some sense. That would be the reason why I’m posting this to encourage people to use it.

Before the Starting this use following link download it.It’s come under lesser GNU public license  freely available with SWI-Prolog site and nearly 8Mb.Also don’t forget to check the version before download it’s compatible to your PC.

http://www.swi-prolog.org/download/stable 

 

When you open swi-prolog you can see window like above but when you click on menu item you might get some doubts because it’s refer some menu item for different purpose ex:-Run menu not involve for executing program.

First we need to create new file (extension will be .pl) by file->new then it will open some editor and after editing  save it(it appears as save buffer; Ctrl+S works).

Prolog has its roots in formal logic, and unlike many other programming languages, Prolog is declarative: The program logic is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a query over these relations.

There are some basic rules.

after every line finish with full stop(.)

define thing. 

to declare thing use following format declare_what(thing) 

male(nimal). 

this means "Nimal is a male" is true.we can write this one as 

male(Nimal):-true.

After saving this have to compile that by file->consults and then open source file then it gives message then type above formula then check it replies true.

1 ?- % j:/Documents and Settings/common/My Documents/Prolog/Ex1.pl compiled 0.00 sec, 136 byte

1 ?- male(nimal).

true . 

2 ?- male(namal).

false .

For the time being I stop this if you interested check part II(if not you have to best things happen last)  :)

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.

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 i^th item weighs w_i and is worth v_i 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 x_i of item i, where 0 ≤ x_i ≤ 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 i^th row is placed.

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

Tutorial-Server side Web Programming(CS310)

 

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

   

   • 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.
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.
6. Create a web page that users can input their Date of Birth in the format given below.
   • 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.

Hint: Use innerText property to display the message.

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: