<< Chapter < Page Chapter >> Page >

Assignment problem

Assignment problem 1 - depth first search and the n-queens problem

Write recursive code to implement the N-Queen problem by using depth-first search. Make your code general enough to handle any arbitrary N. For testing purposes you might want to try N = 4, which is the smallest non-trivial problem.

Now use N = 8. Print out all the possible solutions. How many are there?

Modify your code to stop as soon as one solution is found. Run with N = 9, 10, 11, etc...

Assignment problem 2 - greedy search and the n-queens problem

Write code to implement the N-Queen problem by using greedy search. Make your code general enough to handle any arbitrary N. The code should terminate as soon as one solution is found.

For testing purposes you might want to try N = 4, which is the smallest non-trivial problem. Run with ever increasing N.

Assignment problem 3 - finding a maximum weight matching in a weighted bipartite graph

(From Wikipedia, the free encyclopedia)

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.

If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the Linear assignment problem. Commonly, when speaking of the Assignment problem without any additional qualification, then the Linear assignment problem is meant.

Formal mathematical definition

The formal definition of the assignment problem (or linear assignment problem) is

Given two sets, A and T, of equal size, together with a weight function C : A × T → R. Find a bijection f : A → T such that the cost function:

is minimized.

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

The problem can be expressed as a standard linear program with the objective function

subject to the constraints

for ,

for ,

for .

The variable xij represents the assignment of agent i to task j, taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent

Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.

Assignment problem 4 - stable marriage problem

(From Wikipedia, the free encyclopedia)

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

The Gale-Shapley algorithm involves a number of "rounds" (or "iterations") where each unengaged man "proposes" to the most-preferred woman to whom he has not yet proposed, and she accepts or rejects him based on whether she is already engaged to someone she prefers. If she is unengaged, or engaged to a man lower down her preference list than her new suitor, she accepts the proposal (and in the latter case, the other man becomes unengaged again). Note that only women can switch partners to increase their happiness.

Algorithm

function stableMatching {

Initialize all m M and w W to free

while free man m who still has a woman w to propose to {

w = m's highest ranked such woman

if w is free

(m, w) become engaged

else some pair (m', w) already exists

if w prefers m to m'

(m, w) become engaged

m' becomes free

else

(m', w) remain engaged

}

}

Using this algorithm to guarantee that:

  • Everyone gets married: Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have to have said yes.
  • The marriages are stable: Let Alice be a woman and Bob be a man. They are each paired/partnered/married, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.

Questions & Answers

Healthcare professionals often work in rotating shifts. Why is this problematic? What can be done to deal with potential problems?
Anna Reply
The core problem is the absence Good governance system
Waaya
ONLY BUDGET CONSUMING RATHER THAN WORKING GOOD HEALTH SERVICES FOR COMMUNITY BY LEADERS
Waaya
NO REALITY BUT THERE ARE FALSE BASED REALITY
Waaya
why is stress chronic?
Abhimanyu Reply
working conditions at work today
Namwanje Reply
working conditions at work
Namwanje
I work in Afghanistan. Work conditions are interesting. 😊
Jonah
what's it like where you work?
Jonah
and that's crazy jonah. stay safe e out there
queefburgler
thanks young King. Will do. what's goin on out there in you guy's parts of the world?
Jonah
who gets anxiety disorders and how common are they?
Karen Reply
I have generalized anxiety and I've had it for almost 12 years
Harley
I've had it for idk how long but I finally went and got diagnosed 3 years ago. it's pretty common actually
Shannon
I have anxiety with secondary depression, basically meaning my anxiety spirals into depression and depressive thoughts
Shannon
depression always start with anxiety......after some year when we are unable to tackle the anxiety....the anxiety converted into depression...b
Sahni
becoz in anxiety a person always unable to taking decision and adjustment with situation et all
Sahni
anxiety big ........ structure is as depression after some times years
Sahni
Do you mind if we begin a conversation?
Frank Reply
Not at all, how are you?
Shannon
abt what?
zaynab
I'm totally fine. What about you?
Frank
I'm good, just been studying.
Shannon
Oh,that's pretty good. What have you achieved in your studying?
Frank
what are you guys up to?
queefburgler
I just wanted to have a conversation.
Frank
hitting the books😁👋😂..have a great day everyone 🤗
Michelle
you too Michelle. currently I'm writing a lab report so you could say I'm studying too
queefburgler
Kind of like that. We are having a wonderful day, dude.
Frank
Where are you guys all from?
Frank
I stay in Dubai but originally from Somalia, east Africa
queefburgler
I kind of wanna go to the US after my bachelor's, kinda dont since you guys have that giant orange cheeto thing up in the oval office
queefburgler
But what are you working on?
Frank
currently? I'm doing an organic identification lab report (chemistry)
queefburgler
Unfortunately, i'm really bad at chemistry. Why do you like that? Is there anything that forces you to practice it more and more?
Frank
I'm going to work and then writing a paper for English...we got this...💪😃👍
Michelle
Hi! I'm french
Naomi
I'm from the US, And I wanna leave just because of the orange Cheeto dude
Marco
Oh,Bonjour. I know some words in french.
Frank
Can you help me master that language?
Frank
I'm from Texas currently attending hcc majoring psychology.
Pakayla
and lol Queef.. "the giant orange Cheeto..."
Pakayla
What's the difference between 9/11 and a cow?
Marco
the cow doesnt fly through skyscrapers?
queefburgler
You can't milk a cow for 18 years
Marco
solid.
queefburgler
hi can u eleborate it further?
LEARN Reply
can I get an explanation on the second requirement which was the use of repeatable stimuli?
Daniel Reply
what is psyche
EVANS Reply
psyche is the study of man, man as a being living in the over-world change, responding to thingsand events and other people.
ayman
bhvior n cogntnz....
Hunny
thnkng ptrnz
Hunny
psychology is the study of behavior and mental process
Arooj
something described in the state of a minds being
Carlnisha
That's true
Arooj
YES
ABIOLA
aoa arooj from whr u blong
Hunny
hi
Chandrakant
types of psychology
Clinton
is everyone here belongs to psychology related fields🤔
zaynab
Yes I am
Becca
yea
Odey
yes
JIGNA
behavioural psychology clinical psychology organisational psychology abnormal psychology counselling industrial psychology criminal psychology these all are types of psychology
JIGNA
is any one psychology student ?
JIGNA
i am a psych grad
Gel
Vague to the extent that it sounds like a rhetorical question
keenu
if you want to know the literal meaning of the word, look up Google. Or do provide more info so someone other than you could understand the word in the context that you've come across
keenu
Keenu, what are you talking about?
Becca
Hello I'm anis from Malaysia
Anis
I am strj
Satra
hi
Fred
hello Satra Joy
Fred
Hello
Satra
hey guys
Aditya
welcome everybody
ayman
u 2
Hunny
am in too
Pauline
Hello
Olukunle
Hello
Dungrani
Tell me some facts about developmental psychlogy
Hasham
what is educational psychology? tell me?
Sonai
What does psyche means? soul
Louisiana Reply
psychology= scientific study of the mind and behavior
Louisiana
Associated to outside stimuli or internal.
Rob
she is a goddess
Elizabeth
it is the study of human nature. it is the study of man, man as a being living in an over-changing world, responding to things and events and other people.
ayman
plz sujeest a book.psychological foundetion of education.
Sonai
Cognition is more about knowing. Learning, for instance, changes or at least has some effect on cognitive style. And Constructivism is more of a method or way to know and learn. This is the way I see these concepts. If you may please, tell me, have I got them correct?
Vijay Reply
you have to know the rules of life, follow the scientist and their theories. with that you can measure the truth by yourself. take care of you brother
Will
somebody hv any material related to CBT
Hunny
if hv kindly shr me plz
Hunny
you have everything on internet
Will
i want to understand by dscsn
Hunny
what is episodic memory?
Subhasmita Reply
i don't know
Trish
past memory
Trish
episodic memory is a collection of past personal experiences.
Preet
yes
Nazakat
Try to remember your first day in college(or anywhere). That is your episodic memory. If we discern its characteristics, then obviously its1) Autobiographical, 2)Explicit, meaning it can be expressed verbally, and 3)Retrievable, you can watch that scene on the screen inside your head anytime.
Vijay
that's interesting
Paveethra
yes it is.
mahendra
like watching a season of a show, except it's the show of your life.
Jonah
I just watched the show of my life!!! With deleted scenes(that helps) 🎃
Martin
What does merits mean
worthy or goodneas
Trish
integrity
Genata
merit /ˈmɛrɪt/ Learn to pronounce noun the quality of being particularly good or worthy, especially so as to deserve praise or reward. "composers of outstanding merit" synonyms:excellence, goodness, standard, quality, level, grade, high quality, calibre, worth, good, credit, eminence, worthin
Jonah
so, like a point system in which to grade or determine ones ability to be good or worthy. "Merit System" "Meritorial Award" "...he got it on his merits alone..." etc.
Jonah
look at it like Morale Credit
Jonah
its when credit is given for something you have done
Carlnisha
there is just one definition for psychology ?
TheReal Reply
Which one are you aware of? I'm aware of that psychology is the study of mind and behaviour?
Onesmo
yea thats the only definition that i found
TheReal
really
ravi
"Scientific" study of behaviour & mental processes..
ravi
Yes of course"scientific study" even the first definition is scientific but I'm wondering if "mental process is not included in the mind cause, mind is all about mental processes!
Onesmo
in general and what they teach in PSYC101 yes, psychology is the scientific study of behavior and mental processes, but as you go deeper, you will get more detailed definitions, for example cognitive psychology is the same definition plus emphasis in mental processes.
Mohammed
ok thanks guys
TheReal
Hlw, everyone. Nice to meet you guys. May I know that How to know about the psychological condition of any person ?
Sayantan Reply
like? you can know based on symptoms
john
actions
Amy
How can I determine, whether the person's intention are not good ?
Sayantan
basically you have to observe any person is he/she anxious or have any stress. for that you have to talk and make a good positive relation and being comfortable to person. you have to assist her personality. don't be judgemental. try to under stand her environment . don't be a emotional.
Nitin
cool, what if my opposite person acts moody....?
Sayantan
if you observe serious mood swings may be he/she suffer from some neurotic problem like bipolar.or may be some action affects negatively
Nitin
observation is very skilled task you can't just learned from a online platform. i just completed my Post graduation diploma in clinical psychology. but still i can't able to well define the mood of patients
Nitin
what's your opinion about the mood swings...? What are the causes (except periods of girls).
Sayantan
I agee on the bipolar, what kind of Moody?
Tina
moody means, suppose a person is talking softly with me but within a fraction of seconds he is starting reacting...
Sayantan
what type of mood swings anger-happy , normal-anger. extra energetic and low aur any other symptom
Nitin
normal- anger that generally causes due to frustration
Sayantan
and due to frustration emerged aggression
Sahni
How many types of characters, does humans have ?
Sayantan
types of characters or should you personality or temperament?
DHRUV
which one suits best ?
Sayantan
if personality, then how many types of personality are their in human
Sayantan
well there 5 basic types defined by terman though there are numerous types as per the different theorists over the time 1. Introversion 2. extraversion 3.agreeable 4. concitiousness 5.neuroticism.
DHRUV
these r 5 traits of personality
DHRUV
Basically I know about the first two. so what are the next 3
Sayantan
im very intrigued
Karena
How are you guys?
patwerking Reply
Alive and well.
Max
Nice. Where u from?
patwerking
Are u a boy or a girl?
patwerking
pakistan....vehari
Hunny
fin n u
Hunny
Hey
Anna
heloo
Sai
aoa
Hunny
How here can open new topic?
Anna
girl
Hunny
I am from India and u
Sai
want to talk abut negative thoughts abut self about others
Hunny
who
Hunny
ok
Sai
Have anyone worked in the field of mental health?
Gerald
m working at hsptl
Hunny
anyone is listng me
Hunny
hello everyone.. I have completed my master's in clinical psychology and have an internship experience in the field of mental health
Nirali
same here
Hunny
great
Nirali
how r u
Hunny
from where u r?
Hunny
Mumbai, India
Nirali
😯 woow
Khwabeeda
good
Dr
good
Hunny
want to visit india
Hunny
hey there (seniors) ..am an undergraduate student right now
Khwabeeda
oh nice
Nirali
aoa dr azeem
Hunny
from where u r dr azeem?
Hunny
🙂
Hunny
what do I have to do for becoming additional psychologist ? if any of you can suggest some key points
Khwabeeda
I am Ann from Russia. I am 28. :-) I am learning psychology by myself for prepare to enter at the university as a psychologist. I am looking for somebody who want to learn psychology together and discuss topics :-)
Anna
I am 17
Sai
If someone wants to study together and discuss topics, write briefly about yourself and share yours contacts please :)
Anna
I am 17
Sai
i want
Hunny
I am 17
Sai
hello my people
Samuel
m from pakistan...
Hunny
hey
Kanika
i want 2 learn how 2 deal with mently dsturbd prson
Hunny
anna
Samuel
i m 24
Hunny
hy
Hunny
anna....
Hunny
Yeah i want to learn that too
yaswanti
it's very interesting to see there brain function with their illness compare to a some what sane person 🤔
Gerald
how should i deal with somebody who is already too much disturbed with his past... that he doesn't pay attention to his present
yaswanti
Anna how are you
Samuel
also want to learn about brain parts their function n role of neurotransmitters
Hunny
hii
Yendluri
can anyone teach me human psychology
Yendluri
India Punjab Patiala pursuing MAPC IGNU through cc
rajesh
becoz I am going into that field
Yendluri
have u not any idea about human psychology
Hunny
u should go....
Hunny
what do u want to know about human psychology
yaswanti
yaswanti...how can u xplan it
Hunny
explain what...human psychology?
yaswanti
no no m asking about cognition
Hunny
completly how people judge and how I have to do it criminal psychology behaviour of humans so on,how to attract people towards our side during interview
Yendluri
a lot of it reiterating that things that have happened in the past is in the past and that we can't go back to change it however we can learn from it so we don't make the same mistakes over and the most important you'll have to find different ways of getting your message a cross.
Gerald
if you know iam glad to know
Yendluri
anyboby have mcqs relatd to psychology with answers for the preparation of compition papr
Hunny
Which exam r u preparing for?
yaswanti
is there anyone to help
Yendluri
4 the admission of ms clinical psychology
Hunny
i nd hlp kindly plz
Hunny
hlw
Sayantan
aoa
Hunny
sorry but i don't know have the MCQs
yaswanti
hmm...its ok dear
Hunny
I want to know how to deal with somebody with a horrible past... somebody full of complexes
yaswanti
Yaswanti Bura, horrible past mean ?
Sayantan
with full trust worthy...
Hunny
no dude , only trust is not the solution
Sayantan
hii. i am kanika from india and i am 18. i have opted for computer science course and want to learn psychology in my part time . can anybody help
Kanika
gee from the state's
Gerald
Horrible past here means...pat full of violence, drug addiction, bad company and loneliness
yaswanti
ok cool, first you have to know whether the person is extrovert or introvert.
Sayantan
according to me, generally people who are extrovert ,they suffer from bad company and loneliness while people who are introvert they goes for violence or drug addictions.
Sayantan
He's definitely an introvert...never shares his problems and acts like everything is fine when from inside he is full of complexes and doesn't trust people
yaswanti
he is addicted to drugs ?
Sayantan
I don't think so
Sayantan
Yes...he says it's a distraction but never mentions distraction from what...though i have a good idea what he's running from
yaswanti
What's your relationship with him ?
Sayantan
We know each other from a year and a half... he's my friend though he claims that I'm his best friend and i know more about him than anyone else
yaswanti
Your and his age ?
Sayantan
16 and...17 respectively
yaswanti
You told , you know lots of things about him than others, right ?
Sayantan
M from Nigeria l am undergraduate student
Zainab
aoa zainab...m sana from pakistan
Hunny
how far
Zainab
Yeah that's right i know more about him than others
yaswanti
I am in skull of community health ,I studies little in spychology
Zainab
Hey I am Tanin! From Bangladesh! I am studying Sociology, BSS Honours First Year..Social Pshychology is one of my major course. I am expecting that you guys will help me 🙂
Shanjida
cool, you know almost more than a half year, so when you first became his friend he was like this only ? or he suddenly changed ?
Sayantan
He has changed...remarkably...he loses his temper more, he more alone, sometimes when he is saying something it's like there's something else he wants to tell me from those lines but i can't grasp the idea, he's more lost now than he was when i met him...
yaswanti
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!





Source:  OpenStax, Data structures and algorithms. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10765/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?

Ask