 Home  Sign up!  Projects  Seminars  Research Notes  Today's Lecture  About 
Devina SibalEmail devinasibal@yahoo.com
 Profile: Sophomore student at AIT.
My Skills:
>Java
>C++
>IBM Assembly Language
>Adobe Photoshop
>Macromedia Flash
Prof. Ashay Dharwadker's Courses (3): Course  Semester  Grade   Algorithm Design  I  Fall 2002  View   Probability & Statistics  Spring 2003  View   Algorithm Design  II  Spring 2004  View  

Project ID: 47 Course: Algorithm Design  II Topic: Sorting Algorithms Visualization
 Description: In this project we have tried to implement the sorting techniques using different visualizations. I have made a visualization which shapes out like a spiral after the vector is sorted. The sorting method that is used is the Batcher's OddEven Merge Sort.
Other sorting methods could be used as well.
Team Manifesto
The first (and probably the most important) thing that any computer programmer learns are the various algorithms for SORTING data. They are absolutely critical for a complete understanding of the whole computer science field itself. But it can get quite confusing at times. Especially, when one wants to understand how each one of them works? Or, How each one of them is different from the other?
We think we have an answer to that. Suppose you wish to introduce somebody to the game of FOOTBALL. A verbal discription would not be very helpful. The best solution would be to show a visual of the football game to that person.
Same is the case with Sorting Methods. Through this project, we give a visual discription of the various Sorting Algorithms, with the aim of making learning easy and fun.
But the solution also gives rise to a more complex problem. How do we represent the sorting algorithms visually. The solution is to create unique visualization schemes to represent the status of data elements at various instances of time.
This method of representation gives rise to a more complex field in mathematics known as Dynamical Systems.
After the main idea of the project was concieved, the elements of the project were distributed to the various team members.
Team Members:
• Karan Sahni (Algorithms  Coding Sorting Algorithms into C++ Programs)
• Parul Yadav (Visualizations  Creating Visualization Schemes in OpenGL)
• Devina Sibal (Visualizations  Creating Visualization Schemes in OpenGL)
• Prakash (Win32 Integration  Integrating all components in Visual C++ Environment) 
Seminar ID: 44 Course: Algorithm DesignII Topic: Monty Hall Paradox
 Description: The Game:
Monty Hall's game show Let's Make A Deal took place sometime during the seventies. Imagine that the set of Monty Hall's game show has three closed doors. Behind one of these doors is a car; behind the other two are goats. The contestant does not know where the car is, but Monty Hall does.
The contestant picks a door and Monty opens one of the remaining doors, one he knows doesn't hide the car. If the contestant has already chosen the correct door, Monty is equally likely to open either of the two remaining doors.
After Monty has shown a goat behind the door that he opens, the contestant is always given the option to switch doors. What is the probability of winning the car if she stays with her first choice? What if she decides to switch?
To Switch or Not To Switch?
One way to think about this problem is to consider the sample space, which Monty alters by opening one of the doors that has a goat behind it. In doing so, he effectively removes one of the two losing doors from the sample space.
We will assume that there is a winning door and that the two remaining doors, A and B, both have goats behind them. There are three options:
1. The contestant first chooses the door with the car behind it. She is then shown either door A or door B, which reveals a goat. If she changes her choice of doors, she loses. If she stays with her original choice, she wins.
2.The contestant first chooses door A. She is then shown door B, which has a goat behind it. If she switches to the remaining door, she wins the car. Otherwise, she loses.
3. The contestant first chooses door B. She is then is shown door A, which has a goat behind it. If she switches to the remaining door, she wins the car. Otherwise, she loses.
Each of the above three options has a 1/3 probability of occurring, because the contestant is equally likely to begin by choosing any one of the three doors. In two of the above options, the contestant wins the car if she switches doors; in only one of the options does she win if she does not switch doors. When she switches, she wins the car twice (the number of favorable outcomes) out of three possible options (the sample space). Thus the probability of winning the car is 2/3 if she switches doors, which means that she should always switch doors  unless she wants to become a goatherd.
This result of 2/3 may seem counterintuitive to many of us because we may believe that the probability of winning the car should be 1/2 once Monty has shown that the car is not behind door A or door B. Many people reason that since there are two doors left, one of which must conceal the car, the probability of winning must be 1/2. This would mean that switching doors would not make a difference. As we've shown above through the three different options, however, this is not the case.

Seminar ID: 52 Course: Probability & Statistics Topic: The Prisoner's Dilemma
 Description: Cooperation is usually analyzed in game theory by means of a nonzerosum game called the "Prisoner's Dilemma" (Axelrod, 1984).
How did the game get its name?
The game got its name from the following hypothetical situation: imagine two criminals arrested under the suspicion of having committed a crime together. However, the police do not have sufficient proof in order to have them convicted. The two prisoners are isolated from each other, and the police visit each of them and offer a deal: the one who offers evidence against the other one will be freed. If none of them accepts the offer, they are in fact cooperating against the police, and both of them will get only a small punishment because of lack of proof. They both gain. However, if one of them betrays the other one, by confessing to the police, the defector will gain more, since he is freed; the one who remained silent, on the other hand, will receive the full punishment, since he did not help the police, and there is sufficient proof. If both betray, both will be punished, but less severely than if they had refused to talk. The dilemma resides in the fact that each prisoner has a choice between only two options, but cannot make a good decision without knowing what the other one will do.
The two players in the game can choose between two moves, either "cooperate" or "defect". The idea is that each player gains when both cooperate, but if only one of them cooperates, the other one, who defects, will gain more. If both defect, both lose (or gain very little) but not as much as the "cheated" cooperator whose cooperation is not returned. The whole game situation and its different outcomes can be summarized by a table given below, where hypothetical "points" are given as an example of how the differences in result might be quantified.
Action of A\ Action of B 
Cooperate 
Defect 
Cooperate 
Fairly good [+5] 
Bad [10] 
Defect 
Good[+10] 
Bad[10] 
Table 1: outcomes for actor A (in words, and in hypothetical "points") depending on the combination of A's action and B's action, in the "prisoner's dilemma" game situation. A similar scheme applies to the outcomes for B.
For simplicity we might consider the Prisoner's dilemma as zerosum insofar as there is no mutual cooperation: either each gets 0 when both defect, or when one of them cooperates, the defector gets + 10, and the cooperator  10, in total 0. On the other hand, if both cooperate the resulting synergy creates an additional gain that makes the sum positive: each of them gets 5, in total 10.
The gain for mutual cooperation (5) in the prisoner's dilemma is kept smaller than the gain for onesided defection (10), so that there would always be a "temptation" to defect. This assumption is not generally valid. Why?
The problem with the prisoner's dilemma is that if both decisionmakers were purely rational, they would never cooperate. Indeed, rational decisionmaking means that you make the decision that is best for you whatever the other actor chooses. Suppose the other one would defect, then it is rational to defect yourself: you won't gain anything, but if you do not defect you will be stuck with a 10 loss. Suppose the other one would cooperate, then you will gain anyway, but you will gain more if you do not cooperate, so here too the rational choice is to defect. The problem is that if both actors are rational, both will decide to defect, and none of them will gain anything. However, if both would "irrationally" decide to cooperate, both would gain 5 points and this is a fairly good decision.
This is realistic if we take into account the fact that the synergy usually only gets its full power after a longterm process of mutual cooperation. The prisoner's dilemma is meant to study shortterm decisionmaking where the actors do not have any specific expectations about future interactions or collaborations (as is the case in the original situation of the jailed criminals).

Seminar ID: 54 Course: Algorithm Design  II Topic: Fermat's Little Theorem
 Description: Fermat's little theorem states that if p is a prime number, then for any integer n, p divides n^{p}n. This means that if you take some number n, multiply it by itself p times and subtract n, the result is divisible by p.
A proof using necklaces
Here is an interesting proof of Fermat’s Little Theorem.
We demonstrate the proof for n=2 and p=3. The general proof is not much more difficult.
Given – beads of 2 different colors – Black beads and White beads.
We want to make necklaces out of these two (this number corresponds to n) colors consisting of a total of three beads (this number corresponds to p).
For each bead in the necklace we have two choices each. Thus, for 3 beads we have a total of 8 (i.e.2^3) choices and we can link them in any combination. But out of these 8 there are 2 monochrome necklaces that we will remove since their bead arrangement will be the same, having no different combinations.
Removing the monochrome from the set, we are left with (2^3 – 2) choices.
Claim = (2^3 – 2) is divisible by 3. (Although this is obvious, remember we are trying to give a general argument!)
We will break up the necklaces into classes consisting of 3 necklaces each.
E.g. taking a necklace of the combination BWW, we can rotate the beads around the necklace since they form closed necklaces. Hence we get a class {BWW, WBW, WWB}. Thus, 2^32 (multicolor) open necklaces make (2^32)/3 bracelets, each from 3 open necklaces. This shows that 3 divides (2^32). (Generalizing the above argument, p divides n^{p}n )
Hence Fermat’s Little Theorem is proved.

Seminar ID: 55 Course: Algorithm Design  II Topic: Knight’s Tour Problem
 Description: This problem asks you to place a knight any place you like on a chess board and then move it around the board so that you visit each position on the board exactly once. A reentrant tour requires that you are able to get back to the starting square with one more move.
This is an application of a Hamiltonian Path, a path that goes through every vertex of a graph exactly once.
Given a chessboard, make a graph G with vertices=squares and v_{i} and v_{j} are connected by an edge if and only if there is a possible knight move from square v_{i} to square v_{j}. Then a Reentrant Knight’s Tour on the chessboard = Hamiltonian Circuit.
What types of chessboards have Reentrant Knight’s Tours?
· No Reentrant Knight’s Tour for nodd.
· Always have a Reentrant Knight’s Tour for neven (n >= 6).

Research Note ID: 58 Course: Algorithm Design  II Topic: Sociable Numbers
 Description: A sociable number is a generalization of the concepts of amicable numbers and perfect numbers. A set of sociable numbers is an aliquot sequence, or a sequence of numbers, with each number being the sum of the factors of the preceding number, excluding the preceding number itself. In the case of sociable numbers, the sequence is cyclic (eventually returning to its starting point).
The period of the sequence, or order of the set of sociable numbers, is the number of numbers in this cycle.
Sociable numbers are similar to amicable numbers. A chain of numbers is sociable if the sum of the proper divisors of each number is the next number in the chain, the last number preceding the first. Poulet found the first two chains in 1918. The first chain contains five members, 12,496 > 14,288 > 15,472 > 14,536 > 14,264 > 12,496, while the second chain contains a remarkable 28 numbers.
These two chains were the only known sociable chains until 1969, when Henri Cohen used a computer to check all numbers below 60,000,000, and he discovered seven new chains of four links. More have been found since then. Curiously, no chains with just three links (which someone named "crowds") have been found.


Last updated on Tuesday, 27th April 2004, 08:16:17 PM.
Prof. Ashay Dharwadker

