CS201 Assignment No. 2 Announced

Assignment No. 02

Semester: Spring 2011

CS201: Introduction to Programming

Total Marks: 20

Due Date:02/05/2011

Assignment:

Problem Statement: Sorting two matrices  

You are required to write a program which takes two 3x3 matrix A and B containing 09 elements each and sort all these 18 elements in descending order and put it in one dimensional array and then display it.

Follow the following steps to code this program

1. Take two two-dimensional arrays as A[3][3]and B[3][3] and  one-dimensional array C[] to keep the result.

2. Prompt the user to enter the elements of first matrix

3. Prompt the user to enter the elements of second matrix

1. Now take first element of first matrix and check in both matrix weather it is greatest or any other number is the greatest and put the greatest number at the first index of the one dimensional array. Follow this procedure for other elements and at the end one dimensional array would be in descending order

2. Display this one-Dimensional sorted array on the screen

Following is the sample program structure

   2 3 5               2 8 7

A= 6 5 9             B= 0 1 1

   1 0 2                4 7 9

Output should be like this

Please enter the Elements of First Matrix:

Please enter the Elements of second Matrix:

 Sorted Values from Both the Matrices are:             

    -------------------------------------------

     9 9 8 7 7 6 5 5 4 3 2 2 2 1 1 1 0 0

    ------------------------------------------

CS402 Assignment No. 2 solution

Theory of Automata (CS402)

Assignment No.2

Deadline

Your assignment must be uploaded before or on 27th April, 2011

Rules for Marking

It should be clear that your assignment will not get any credit if:

• The assignment is submitted after due date

• The assignment is copied

Objectives

Objective of this assignment is to make students able to understand the following concepts,

• Finite Automata

• Transition Graph

• Generalized Transition Graphs

• Kleene’s Theorem Part III

Question No.1

Finite Automata

Consider the Language L of Strings, defined over Σ = {a, b}, staring and ending with same letter. The RE of language is: (a+b) +a (a + b)*a + b (a + b)*b. Draw the FA of given Language.

Question No.2

Transition Graph

Draw the TG for the language L of strings, defined over Σ = {a, b} in which if a occur it is in the form of aaa and that ends in two or more b’s.

Some example strings are:

bb , bbb , bbbbb , … , aaabb , aaabaaabb , baaabaaabb , baaabaaabbbb ,

bbbaaabaaabbbb , …

Question No.3

Transition Graph

Draw the TG for the language L of strings, defined over Σ = {a, b}, beginning and ending in same letters. The language L may be expressed by RE a(a + b)*a + b(a + b)*b.

Question No.4

Generalized Transition Graphs

Consider the language L of strings, defined over Σ = {a,b}, accepting all strings without double “b”. Draw the GTG for the above stated language.

[Hint: First make RE of the language].

Question No.5

Kleene’s Theorem Part III

Let r1 = (a + b)*a and the corresponding FA1 be

Find out the FA corresponding to r1+ r2

How to Make FA using Word:

You can view the video file

http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.00.zip

to see how to make FA in MS Word.

Important Note:

While attempting any question always remember the following points:

o Where OR is used in the description of a language it means that expressions on both sides of ‘OR’ are parts of the language.

o Where NOT is used in the description of the language it means that language includes all strings except described in the ‘NOT’ condition, for example language NOT starting with a, means all strings not having a in the start (you have to evaluate yourself what kinds of strings are these).

Assignment Uploading Instructions:

o Upload single word file having solutions for all questions.

:::::::::::::::::::::::::::::::::::::::::::::::

Solution: