 Home  Sign up!  Projects  Seminars  Research Notes  Today's Lecture  About 
Atika ShirkotEmail atikashirkot@rediffmail.com
 Profile: I am a student in Bachelors of Computer Science at AIT in an exchange program with Tarleton State University, Texas. I am doing a course in C++ and MFC programming, designing MySQL and Oracle databases with PHP and ASP programming. I like programming , web designing and I am currently working on Theory of Computation. Prof. Ashay Dharwadker's Courses (2): Course  Semester  Grade   Information Systems  Fall 2003  View   Database Systems  Fall 2003  View  

Project ID: 19 Course: Database Systems Topic: Time_Table
 Description: Superna Sharma and I are currently working on creating a database that displays the courses for a student along with data like teachers,course numbers, etc. on being given the specific information(i.e course code etc).
The various MySQL queries used are given below :
mysql>create database Time_Table;
mysql>use Time_Table;
mysql>create table Course(C_Code char(20) not null,C_Name char(30),Credits int,Lecturer char(30),primary key (C_code));
You can refer to Superna's Project Report to find out about other tables and the various primary and foreign keys in them.
To insert values into the tables:
mysql>insert into Course values( "FSS 101",......);
To see the table :
mysql>select * from ____( give the table name );
To see all the tables : mysql> show tables;
To see only the fields:
mysql>describe ____(table name);
To delete a specific row or a specific column :
mysql> delete fields from tablename where _____;

Seminar ID: 9 Course: Information Systems Topic: Towers of Hanoi
 Description: This seminar on "Towers of Hanoi" was given by me along with Superna Sharma as my partner.Towers of Hanoi is basically a game which has a legend associated with it i.e." How can the hermits shift 64 discs from one peg (source) to the third peg (destination) and the day it is done the earth would come to an end." There are three pegs and the discs have to be moved from the first to the last one which is the destination keeping in mind the two rules that are: 1. not to keep the larger disc on the smaller one and 2.move a disc at a time. We showed how this can be done and the method used was "Recursion" the formula derived in general for n discs is 2^n1 . Along with this we showed them that this method is the optimal and proved it through Induction.We had also made an algorithm and program for this.We even showed that how much time the hermits would take to complete this and the process is still going on.I believe that the it was appreciated by the people and we hope to keep up their expections in our next seminar also that is linked to it "Complexity".

Research Note ID: 15 Course: Information Systems Topic: Working of Towers of Hanoi
 Description: The Recurrence Relation emerging out of the basic concept of Towers of Hanoi is :
Let T_{n } be the no. of steps for Towers of Hanoi with 'n' disks.
T_{n} = T_{n1} + 1 + T_{n1}
T_{n} = 2T_{n1} + 1
T_{n} = 2 (2T_{n2} + 1) + 1
T_{n} = 2^{2}T_{n2} + 2 + 1
T_{n} = 2^{2} (2T_{n3} + 1) + 2 + 1 ................. ................. ................... ...................
T_{n} = 2^{n1}T_{1} + 2^{n2} + ............................ + 2^{2} + 2 + 1
T_{n} = 1 + 2 + 2^{2} + ........................ + 2^{n1}  Eq. 1
Multiplying Eq. 1 by 2 :
2T_{n} = 2 + 2^{2} + ........................ + 2^{n1} + 2^{n}  Eq. 2
Subtracting Eq. 1 from Eq. 2 :
T_{n} = 2^{n}  1
Using Induction to show that this method is the optimal :
For N=1
T_{1}=2^{1}1=1......( algo is
optimal )
Assume algo is optimal for
N=1 , 2 , ....., K
For N = K + 1
Total moves = T_{K } + 1 + T_{K}
= 2^{K}  1 + 1 + 2^{K}  1
=2 * 2^{K}  1
=2^{K+1}  1
=T_{K+1}
Hence theTime Complexity of the Towers of Hanoi is 2^{n} from the eqn.
T_{n} = 2^{n}  1

Research Note ID: 32 Course: Database Systems Topic: Batcher's OddEven Merge Sort
 Description: This algorithm was designed by E.K.Batcher
The first and only criteria for this sorting algorithm is that the number of elements must be of the order of 2^{n}.
Now the steps involved in doing so are:
i)Divide the list of elements into 2 halves and sort them using any efficient recursive sorting algorithm.
ii)
Now swap the 2 halves.
iii)
Now take the elements in the odd and even positions resp. and sort them into 2 lists.
iv)
Now merge the 2 lists placing the elements of the odd positioned elements in the odd positions and resp. for the even positioned elements.
v)
Now except the first and last elements, compare and exchange(if required) pairs of consequtive evenodd elements(specifically in that order).
Note:
The Time complexity T(n) of this sorting algorithm is nlog(n).
SORTING NETWORKS:
Sorting networks are employed when we have to sort lists of some specific size. These are very simple devices that only do compare exchange operations.
eg. consider the below illustrated 4element sorting network.
c__.__ b ____ b__.__ a____a ____a
b____ c ____ c____ c__.__ c__.__b
d____ d__.__ a____ b____ b____c
a____ a____ d____ d____ d____ d
___________ ____________ _____
step1 step2 step3
A further indepth explaination will be provided in the course of the next few days. 

Last updated on Thursday, 20th November 2003, 05:32:43 PM.
Prof. Ashay Dharwadker

