Wednesday, August 17, 2011
DAA Assignment Questions
Question 1
Consider the algorithm :
Algorithm mystery(n)
//Input : A non negative integer
s<-0
for i<-1 to n do
s<-s+i
return s
a) What does this algorithm compute ?
b)What is its basic operation ?
c)How many times is the basic operation executed ?
d)What is the efficiency class of the algorithm ?
e)Suggest an improvement if possible.
Question 2
Consider the following recursive algorithm
ALGORITHM S(n)
//Input: A positive integer n
//Output: The sum of the first n cubes
if n = 1 return 1
else return S(n - 1) + n * n * n
a. Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed.
b. How does this algorithm compare with the straightforward non-recursive algorithm for computing this sum?
Question 3
How many comparisons will be made by the Brute Force technique for each of the following cases :
1) Binary text of 1000 zeros.
Patterns:
a) 00001 b) 10100 c) 10001
Question 4
Consider the problem of counting in a given text , the no. of substrings that start with 'a' and end with 'b'.Design a Brute Force algorithm for this problem and determine its efficiency class
Consider the algorithm :
Algorithm mystery(n)
//Input : A non negative integer
s<-0
for i<-1 to n do
s<-s+i
return s
a) What does this algorithm compute ?
b)What is its basic operation ?
c)How many times is the basic operation executed ?
d)What is the efficiency class of the algorithm ?
e)Suggest an improvement if possible.
Question 2
Consider the following recursive algorithm
ALGORITHM S(n)
//Input: A positive integer n
//Output: The sum of the first n cubes
if n = 1 return 1
else return S(n - 1) + n * n * n
a. Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed.
b. How does this algorithm compare with the straightforward non-recursive algorithm for computing this sum?
Question 3
How many comparisons will be made by the Brute Force technique for each of the following cases :
1) Binary text of 1000 zeros.
Patterns:
a) 00001 b) 10100 c) 10001
Question 4
Consider the problem of counting in a given text , the no. of substrings that start with 'a' and end with 'b'.Design a Brute Force algorithm for this problem and determine its efficiency class
Sunday, August 14, 2011
Thursday, August 11, 2011
Monday, August 8, 2011
Wednesday, May 11, 2011
Sunday, May 8, 2011
Saturday, April 30, 2011
mini project submission date
B21- EVALUATION ON THURSDAY(5TH MAY)-10:30 to 12:30pm
B12 & B11 - EVALUATION ON THURSDAY(5TH MAY)- 2 to 5pm
B22- EVALUATION ON MONDAY(9TH MAY).timings to be decided
B12 & B11 - EVALUATION ON THURSDAY(5TH MAY)- 2 to 5pm
B22- EVALUATION ON MONDAY(9TH MAY).timings to be decided
Sunday, April 24, 2011
LAB SCHEDULE
java :B1-28/4 B2-29/4
MP: B11-26/4 B12-3/5
B21-28/4 B22-5/4
B22-DBMS LAB on 26/4
B21-DBMS LAB on 3/5
B12-DBMS LAB on 30/4
B11-DBMS LAB on 6/5
ROLL NOS.
B11- 55 TO 71
B12- 72 TO 87
B21- 88 TO 104
B22- 105 TO 281
MP: B11-26/4 B12-3/5
B21-28/4 B22-5/4
B22-DBMS LAB on 26/4
B21-DBMS LAB on 3/5
B12-DBMS LAB on 30/4
B11-DBMS LAB on 6/5
ROLL NOS.
B11- 55 TO 71
B12- 72 TO 87
B21- 88 TO 104
B22- 105 TO 281
phone no list
4th SEMESTER B-Section TEACHERS CONTACT DETAILS
SUJATA MA'AM 9448744540
SHANTHI MA'AM 9901659271
SMITHA MA'AM 9980250304
VIJAYA SIR 9535680918
CENITTA MA'AM 9738891473
SUJATA MA'AM 9448744540
SHANTHI MA'AM 9901659271
SMITHA MA'AM 9980250304
VIJAYA SIR 9535680918
CENITTA MA'AM 9738891473
Tuesday, April 19, 2011
example of 4nf
Multivalued dependencies
If the column headings in a relational database table are divided into three disjoint groupings X, Y, and Z, then, in the context of a particular row, we can refer to the data beneath each group of headings as x, y, and z respectively. A multivalued dependency X →→ Y signifies that if we choose any x actually occurring in the table (call this choice xc), and compile a list of all the xcyz combinations that occur in the table, we will find that xc is associated with the same y entries regardless of z.
A trivial multivalued dependency X →→ Y is one in which Y consists of all columns belonging to X. That is, a subset of attributes in a table has a trivial multivalued dependency on the remaining subset of attributes.
A functional dependency is a special case of multivalued dependency. In a functional dependency X → Y, every x determines exactly one y, never more than one.
[edit] Example
Consider the following example:
Pizza Delivery Permutations
Restaurant Pizza Variety Delivery Area
A1 Pizza Thick Crust Springfield
A1 Pizza Thick Crust Shelbyville
A1 Pizza Thick Crust Capital City
A1 Pizza Stuffed Crust Springfield
A1 Pizza Stuffed Crust Shelbyville
A1 Pizza Stuffed Crust Capital City
Elite Pizza Thin Crust Capital City
Elite Pizza Stuffed Crust Capital City
Vincenzo's Pizza Thick Crust Springfield
Vincenzo's Pizza Thick Crust Shelbyville
Vincenzo's Pizza Thin Crust Springfield
Vincenzo's Pizza Thin Crust Shelbyville
Each row indicates that a given restaurant can deliver a given variety of pizza to a given area.
The table has no non-key attributes because its only key is {Restaurant, Pizza Variety, Delivery Area}. Therefore it meets all normal forms up to BCNF. If we assume, however, that pizza varieties offered by a restaurant are not affected by delivery area, then it does not meet 4NF. The problem is that the table features two non-trivial multivalued dependencies on the {Restaurant} attribute (which is not a superkey). The dependencies are:
• {Restaurant} →→ {Pizza Variety}
• {Restaurant} →→ {Delivery Area}
These non-trivial multivalued dependencies on a non-superkey reflect the fact that the varieties of pizza a restaurant offers are independent from the areas to which the restaurant delivers. This state of affairs leads to redundancy in the table: for example, we are told three times that A1 Pizza offers Stuffed Crust, and if A1 Pizza starts producing Cheese Crust pizzas then we will need to add multiple rows, one for each of A1 Pizza's delivery areas. There is, moreover, nothing to prevent us from doing this incorrectly: we might add Cheese Crust rows for all but one of A1 Pizza's delivery areas, thereby failing to respect the multivalued dependency {Restaurant} →→ {Pizza Variety}.
To eliminate the possibility of these anomalies, we must place the facts about varieties offered into a different table from the facts about delivery areas, yielding two tables that are both in 4NF:
Varieties By Restaurant
Restaurant Pizza Variety
A1 Pizza Thick Crust
A1 Pizza Stuffed Crust
Elite Pizza Thin Crust
Elite Pizza Stuffed Crust
Vincenzo's Pizza Thick Crust
Vincenzo's Pizza Thin Crust
Delivery Areas By Restaurant
Restaurant Delivery Area
A1 Pizza Springfield
A1 Pizza Shelbyville
A1 Pizza Capital City
Elite Pizza Capital City
Vincenzo's Pizza Springfield
Vincenzo's Pizza Shelbyville
In contrast, if the pizza varieties offered by a restaurant sometimes did legitimately vary from one delivery area to another, the original three-column table would satisfy 4NF.
Ronald Fagin demonstrated that it is always possible to achieve 4NF
If the column headings in a relational database table are divided into three disjoint groupings X, Y, and Z, then, in the context of a particular row, we can refer to the data beneath each group of headings as x, y, and z respectively. A multivalued dependency X →→ Y signifies that if we choose any x actually occurring in the table (call this choice xc), and compile a list of all the xcyz combinations that occur in the table, we will find that xc is associated with the same y entries regardless of z.
A trivial multivalued dependency X →→ Y is one in which Y consists of all columns belonging to X. That is, a subset of attributes in a table has a trivial multivalued dependency on the remaining subset of attributes.
A functional dependency is a special case of multivalued dependency. In a functional dependency X → Y, every x determines exactly one y, never more than one.
[edit] Example
Consider the following example:
Pizza Delivery Permutations
Restaurant Pizza Variety Delivery Area
A1 Pizza Thick Crust Springfield
A1 Pizza Thick Crust Shelbyville
A1 Pizza Thick Crust Capital City
A1 Pizza Stuffed Crust Springfield
A1 Pizza Stuffed Crust Shelbyville
A1 Pizza Stuffed Crust Capital City
Elite Pizza Thin Crust Capital City
Elite Pizza Stuffed Crust Capital City
Vincenzo's Pizza Thick Crust Springfield
Vincenzo's Pizza Thick Crust Shelbyville
Vincenzo's Pizza Thin Crust Springfield
Vincenzo's Pizza Thin Crust Shelbyville
Each row indicates that a given restaurant can deliver a given variety of pizza to a given area.
The table has no non-key attributes because its only key is {Restaurant, Pizza Variety, Delivery Area}. Therefore it meets all normal forms up to BCNF. If we assume, however, that pizza varieties offered by a restaurant are not affected by delivery area, then it does not meet 4NF. The problem is that the table features two non-trivial multivalued dependencies on the {Restaurant} attribute (which is not a superkey). The dependencies are:
• {Restaurant} →→ {Pizza Variety}
• {Restaurant} →→ {Delivery Area}
These non-trivial multivalued dependencies on a non-superkey reflect the fact that the varieties of pizza a restaurant offers are independent from the areas to which the restaurant delivers. This state of affairs leads to redundancy in the table: for example, we are told three times that A1 Pizza offers Stuffed Crust, and if A1 Pizza starts producing Cheese Crust pizzas then we will need to add multiple rows, one for each of A1 Pizza's delivery areas. There is, moreover, nothing to prevent us from doing this incorrectly: we might add Cheese Crust rows for all but one of A1 Pizza's delivery areas, thereby failing to respect the multivalued dependency {Restaurant} →→ {Pizza Variety}.
To eliminate the possibility of these anomalies, we must place the facts about varieties offered into a different table from the facts about delivery areas, yielding two tables that are both in 4NF:
Varieties By Restaurant
Restaurant Pizza Variety
A1 Pizza Thick Crust
A1 Pizza Stuffed Crust
Elite Pizza Thin Crust
Elite Pizza Stuffed Crust
Vincenzo's Pizza Thick Crust
Vincenzo's Pizza Thin Crust
Delivery Areas By Restaurant
Restaurant Delivery Area
A1 Pizza Springfield
A1 Pizza Shelbyville
A1 Pizza Capital City
Elite Pizza Capital City
Vincenzo's Pizza Springfield
Vincenzo's Pizza Shelbyville
In contrast, if the pizza varieties offered by a restaurant sometimes did legitimately vary from one delivery area to another, the original three-column table would satisfy 4NF.
Ronald Fagin demonstrated that it is always possible to achieve 4NF
Thursday, April 14, 2011
Wednesday, April 13, 2011
Tuesday, April 12, 2011
important
i have decided the following lab schedule for dbms :
B22-DBMS LAB on 26/4
B21-DBMS LAB on 3/5
B12-DBMS LAB on 29/4
B11-DBMS LAB on 6/5
if u r not satisfied with this proposal, u can messg me a better one by 9pm today ; the majority satisfaction will be taken into account as the final decision.
i have decided the above considering that no student should have more than 2 lab exams in a week.
JAVA & MP are already finalized.
java :B1-28/4 B2-29/4
MP: B11-26/4 B12-3/5
B21-28/4 B22-5/4
plz get ur bus xerox to class tomorrow.
B22-DBMS LAB on 26/4
B21-DBMS LAB on 3/5
B12-DBMS LAB on 29/4
B11-DBMS LAB on 6/5
if u r not satisfied with this proposal, u can messg me a better one by 9pm today ; the majority satisfaction will be taken into account as the final decision.
i have decided the above considering that no student should have more than 2 lab exams in a week.
JAVA & MP are already finalized.
java :B1-28/4 B2-29/4
MP: B11-26/4 B12-3/5
B21-28/4 B22-5/4
plz get ur bus xerox to class tomorrow.
Monday, April 11, 2011
Thursday, April 7, 2011
Wednesday, April 6, 2011
Sunday, April 3, 2011
Friday, April 1, 2011
Thursday, March 31, 2011
notice
students will receive 3 marks for Q1-(i) if they have written the ans as " not in bcnf " in the 2nd sessional of rdbms.
Wednesday, March 30, 2011
Friday, March 25, 2011
imp stuff
java end sem lab exam
B1 BATCH-28TH APRIL
B2 BATCH-29TH APRIL
wanna remind that classes on monday start @ 9 and not 8.
mini project to be submitted on 1st week of MAY. ma'am will decide the date and notify later. last working day b4 end sems is 12th may(thursday).
22nd april is a holiday on account of GOOD FRIDAY.
a request to all of u ; plz circulate messages to ur friendz so that no one is at loss specially for the morning class cancellation. or read notices here........if there is any morning class cancld i'll notify here as well b4 6:30 am of that day.i regret for the inconvenience caused 2day. i don't know why some of u didn't receive the msg yesterday.
maths assignment 2 to be submitted on monday only during 10:30 to 11:30 prp class
mode of submission of synopsis for miniproject :(any 1 of the two)
hard copy: in 2-3pm rdbms class to me on monday
soft copy: email it to Vijaya sir. sir's id- arjun.connects@gmail.com
before 1:30pm on monday
do u want a class party? pratan wants to organize it.if u r interested, plz contact him @ 9535617107
thanks for ur support.
regards,
rajat
B1 BATCH-28TH APRIL
B2 BATCH-29TH APRIL
wanna remind that classes on monday start @ 9 and not 8.
mini project to be submitted on 1st week of MAY. ma'am will decide the date and notify later. last working day b4 end sems is 12th may(thursday).
22nd april is a holiday on account of GOOD FRIDAY.
a request to all of u ; plz circulate messages to ur friendz so that no one is at loss specially for the morning class cancellation. or read notices here........if there is any morning class cancld i'll notify here as well b4 6:30 am of that day.i regret for the inconvenience caused 2day. i don't know why some of u didn't receive the msg yesterday.
maths assignment 2 to be submitted on monday only during 10:30 to 11:30 prp class
mode of submission of synopsis for miniproject :(any 1 of the two)
hard copy: in 2-3pm rdbms class to me on monday
soft copy: email it to Vijaya sir. sir's id- arjun.connects@gmail.com
before 1:30pm on monday
do u want a class party? pratan wants to organize it.if u r interested, plz contact him @ 9535617107
thanks for ur support.
regards,
rajat
Tuesday, March 15, 2011
Monday, March 14, 2011
syllabus for 2nd sessional
rdbms- lesson 2,7
flta- lesson 5,6
java -threads,i/o,applets
mp- interrupts(excluding hardware part and software applications)
refer xerox for 8254A modes,bios 10h, interrupt int 21h,dma,basic 8086 config ,dma,min and max modes
interfacing-till before handshake application(examples).
programs from files,strings & interrupts are there
flta- lesson 5,6
java -threads,i/o,applets
mp- interrupts(excluding hardware part and software applications)
refer xerox for 8254A modes,bios 10h, interrupt int 21h,dma,basic 8086 config ,dma,min and max modes
interfacing-till before handshake application(examples).
programs from files,strings & interrupts are there
Friday, March 11, 2011
java
topics like datainputstream,pushbackreader are also there 4r the sessionals, though it's not covered in the slides
2nd sessional time table
17/3-flta-10:30am
17/3-prp-3:30pm
18/3-rdbms-10:30pm
18/3-mp-3:30pm
19/3-java-3:30pm
rooms 4r b sec--AB5-308,310
17/3-prp-3:30pm
18/3-rdbms-10:30pm
18/3-mp-3:30pm
19/3-java-3:30pm
rooms 4r b sec--AB5-308,310
notice
CALL FOR VOLUNTEERS...for DSY...a Microsoft Event...
Venue-AB-5, Room-306
Time:5pm-6pm
Date:11th March 2011...
Certificates will be provided from Microsoft...
Call 8088752191 for further queries...
Venue-AB-5, Room-306
Time:5pm-6pm
Date:11th March 2011...
Certificates will be provided from Microsoft...
Call 8088752191 for further queries...
Wednesday, March 9, 2011
Sunday, March 6, 2011
Saturday, February 19, 2011
1st sessnl java syllabus
JAVA syllabus- lesson 1(The History and Evolution of Java) to lesson 10(Exception Handing )
notice
Dear students,
A knowledge sharing session is scheduled by CISCO on Monday 28th February 2011
from 4.00 PM to 7.00 PM. The topics to be covered are
1.Advance Switching
2.Data Centre Technology “ Load balancers “
3.Voice over IP Technology
This is open to the second year as well as third year students of CSE, IT, E&E and
E&C branches of engineering. The interested students of CSE Department who are
willing to attend the session are suppose to register to the link given as ‘click here to
register’.
http://csemitmanipal.blogspot.com
A knowledge sharing session is scheduled by CISCO on Monday 28th February 2011
from 4.00 PM to 7.00 PM. The topics to be covered are
1.Advance Switching
2.Data Centre Technology “ Load balancers “
3.Voice over IP Technology
This is open to the second year as well as third year students of CSE, IT, E&E and
E&C branches of engineering. The interested students of CSE Department who are
willing to attend the session are suppose to register to the link given as ‘click here to
register’.
http://csemitmanipal.blogspot.com
Wednesday, February 16, 2011
Monday, February 14, 2011
Saturday, February 12, 2011
portion for sessional - prp & dbms
dbms- db system concepts by korth,sudarshan......
5th edition
entire lesson 1(introduction),lesson 3 (sql)& lesson 6(db design & er models) excluding 1.7(object-based & semi-structured db),1.10(data mining & analysis),1.13(history of db),6.10(other aspects of db) & 6.11(uml). chapter 2 is not there for this test.
(as per Archana mam who takes C sec ).
prp -everything is there before "2 & higher dimensional random variable".
5th edition
entire lesson 1(introduction),lesson 3 (sql)& lesson 6(db design & er models) excluding 1.7(object-based & semi-structured db),1.10(data mining & analysis),1.13(history of db),6.10(other aspects of db) & 6.11(uml). chapter 2 is not there for this test.
(as per Archana mam who takes C sec ).
prp -everything is there before "2 & higher dimensional random variable".
Tuesday, February 8, 2011
Friday, February 4, 2011
Tuesday, February 1, 2011
Saturday, January 29, 2011
Wednesday, January 26, 2011
Tuesday, January 25, 2011
attendance status : java & flta
https://docs.google.com/leaf?id=0B2SPc_81I6KiMGVhMmJhN2MtNTZlMy00MmM2LTljY2MtYTY5MzNjMDI5YzYz&hl=en
FOR THEORY CLASSES IT IS OUT OF 8.
FOR LAB OUT OF 2.
FOR THEORY CLASSES IT IS OUT OF 8.
FOR LAB OUT OF 2.
Friday, January 21, 2011
Subscribe to:
Posts (Atom)