Prof. Ashay Dharwadker's Courses (3):

Course	Semester	Grade	Add New Course
Algorithm Design - I	Fall 2002	View	Update Course
Probability & Statistics	Spring 2003	View	Update Course
Algorithm Design - II	Spring 2004	View	Update Course

Projects (1)

Other sorting methods could be used as well.

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.

Seminars (4)

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 zero-sum 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 one-sided 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 decision-makers were purely rational, they would never cooperate. Indeed, rational decision-making 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 long-term process of mutual cooperation. The prisoner's dilemma is meant to study short-term decision-making 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).

Research Notes (1)