text:
\hypertarget{section}{%
\section{1}\label{section}}

\bibverse{1} Now in the first year of Cyrus king of Persia, that the
LORD's\footnote{1:1 When rendered in ALL CAPITAL LETTERS, ``LORD'' or
  ``GOD'' is the translation of God's Proper Name.} word by Jeremiah's
mouth might be accomplished, the LORD stirred up the spirit of Cyrus
king of Persia, so that he made a proclamation throughout all his
kingdom, and put it also in writing, saying, \bibverse{2} ``Cyrus king
of Persia says, `The LORD, the God+ 1:2 The Hebrew word rendered ``God''
is ``אֱלֹהִ֑ים'' (Elohim). of heaven, has given me all the kingdoms of
the earth; and he has commanded me to build him a house in Jerusalem,
which is in Judah. \bibverse{3} Whoever there is amongst you of all his
people, may his God be with him, and let him go up to Jerusalem, which
is in Judah, and build the house of the LORD, the God of Israel (he is
God), which is in Jerusalem. \bibverse{4} Whoever is left, in any place
where he lives, let the men of his place help him with silver, with
gold, with goods, and with animals, in addition to the free will
offering for God's house which is in Jerusalem.'\,''

\bibverse{5} Then the heads of fathers' households of Judah and
Benjamin, the priests and the Levites, all whose spirit God had stirred
to go up, rose up to build the LORD's house which is in Jerusalem.
\bibverse{6} All those who were around them strengthened their hands
with vessels of silver, with gold, with goods, with animals, and with
precious things, in addition to all that was willingly offered.
\bibverse{7} Also Cyrus the king brought out the vessels of the LORD's
house, which Nebuchadnezzar had brought out of Jerusalem, and had put in
the house of his gods; \bibverse{8} even those, Cyrus king of Persia
brought out by the hand of Mithredath the treasurer, and counted them
out to Sheshbazzar the prince of Judah. \bibverse{9} This is the number
of them: thirty platters of gold, one thousand platters of silver,
twenty-nine knives, \bibverse{10} thirty bowls of gold, four hundred and
ten silver bowls of a second kind, and one thousand other vessels.
\bibverse{11} All the vessels of gold and of silver were five thousand
and four hundred. Sheshbazzar brought all these up when the captives
were brought up from Babylon to Jerusalem.

\hypertarget{section-1}{%
\section{2}\label{section-1}}

\bibverse{1} Now these are the children of the province who went up out
of the captivity of those who had been carried away, whom Nebuchadnezzar
the king of Babylon had carried away to Babylon, and who returned to
Jerusalem and Judah, everyone to his city; \bibverse{2} who came with
Zerubbabel, Jeshua, Nehemiah, Seraiah, Reelaiah, Mordecai, Bilshan,
Mispar, Bigvai, Rehum, and Baanah.

The number of the men of the people of Israel: \bibverse{3} The children
of Parosh, two thousand and one hundred and seventy-two. \bibverse{4}
The children of Shephatiah, three hundred and seventy-two. \bibverse{5}
The children of Arah, seven hundred and seventy-five. \bibverse{6} The
children of Pahathmoab, of the children of Jeshua and Joab, two thousand
and eight hundred and twelve. \bibverse{7} The children of Elam, one
thousand and two hundred and fifty-four. \bibverse{8} The children of
Zattu, nine hundred and forty-five. \bibverse{9} The children of Zaccai,
seven hundred and sixty. \bibverse{10} The children of Bani, six hundred
and forty-two. \bibverse{11} The children of Bebai, six hundred and
twenty-three. \bibverse{12} The children of Azgad, one thousand and two
hundred and twenty-two. \bibverse{13} The children of Adonikam, six
hundred and sixty-six. \bibverse{14} The children of Bigvai, two
thousand and fifty-six. \bibverse{15} The children of Adin, four hundred
and fifty-four. \bibverse{16} The children of Ater, of Hezekiah,
ninety-eight. \bibverse{17} The children of Bezai, three hundred and
twenty-three. \bibverse{18} The children of Jorah, one hundred and
twelve. \bibverse{19} The children of Hashum, two hundred and
twenty-three. \bibverse{20} The children of Gibbar, ninety-five.
\bibverse{21} The children of Bethlehem, one hundred and twenty-three.
\bibverse{22} The men of Netophah, fifty-six. \bibverse{23} The men of
Anathoth, one hundred and twenty-eight. \bibverse{24} The children of
Azmaveth, forty-two. \bibverse{25} The children of Kiriath Arim,
Chephirah, and Beeroth, seven hundred and forty-three. \bibverse{26} The
children of Ramah and Geba, six hundred and twenty-one. \bibverse{27}
The men of Michmas, one hundred and twenty-two. \bibverse{28} The men of
Bethel and Ai, two hundred and twenty-three. \bibverse{29} The children
of Nebo, fifty-two. \bibverse{30} The children of Magbish, one hundred
and fifty-six. \bibverse{31} The children of the other Elam, one
thousand and two hundred and fifty-four. \bibverse{32} The children of
Harim, three hundred and twenty. \bibverse{33} The children of Lod,
Hadid, and Ono, seven hundred and twenty-five. \bibverse{34} The
children of Jericho, three hundred and forty-five. \bibverse{35} The
children of Senaah, three thousand and six hundred and thirty.

\bibverse{36} The priests: the children of Jedaiah, of the house of
Jeshua, nine hundred and seventy-three. \bibverse{37} The children of
Immer, one thousand and fifty-two. \bibverse{38} The children of
Pashhur, one thousand and two hundred and forty-seven. \bibverse{39} The
children of Harim, one thousand and seventeen.

\bibverse{40} The Levites: the children of Jeshua and Kadmiel, of the
children of Hodaviah, seventy-four. \bibverse{41} The singers: the
children of Asaph, one hundred and twenty-eight. \bibverse{42} The
children of the gatekeepers: the children of Shallum, the children of
Ater, the children of Talmon, the children of Akkub, the children of
Hatita, the children of Shobai, in all one hundred and thirty-nine.

\bibverse{43} The temple servants: the children of Ziha, the children of
Hasupha, the children of Tabbaoth, \bibverse{44} the children of Keros,
the children of Siaha, the children of Padon, \bibverse{45} the children
of Lebanah, the children of Hagabah, the children of Akkub,
\bibverse{46} the children of Hagab, the children of Shamlai, the
children of Hanan, \bibverse{47} the children of Giddel, the children of
Gahar, the children of Reaiah, \bibverse{48} the children of Rezin, the
children of Nekoda, the children of Gazzam, \bibverse{49} the children
of Uzza, the children of Paseah, the children of Besai, \bibverse{50}
the children of Asnah, the children of Meunim, the children of Nephisim,
\bibverse{51} the children of Bakbuk, the children of Hakupha, the
children of Harhur, \bibverse{52} the children of Bazluth, the children
of Mehida, the children of Harsha, \bibverse{53} the children of Barkos,
the children of Sisera, the children of Temah, \bibverse{54} the
children of Neziah, the children of Hatipha.

\bibverse{55} The children of Solomon's servants: the children of Sotai,
the children of Hassophereth, the children of Peruda, \bibverse{56} the
children of Jaalah, the children of Darkon, the children of Giddel,
\bibverse{57} the children of Shephatiah, the children of Hattil, the
children of Pochereth Hazzebaim, the children of Ami. \bibverse{58} All
the temple servants, and the children of Solomon's servants, were three
hundred and ninety-two.

\bibverse{59} These were those who went up from Tel Melah, Tel Harsha,
Cherub, Addan, and Immer; but they could not show their fathers' houses
and their offspring,\footnote{2:59 or, seed} whether they were of
Israel: \bibverse{60} the children of Delaiah, the children of Tobiah,
the children of Nekoda, six hundred and fifty-two. \bibverse{61} Of the
children of the priests: the children of Habaiah, the children of
Hakkoz, and the children of Barzillai, who took a wife of the daughters
of Barzillai the Gileadite, and was called after their name.
\bibverse{62} These sought their place amongst those who were registered
by genealogy, but they were not found; therefore they were deemed
disqualified and removed from the priesthood. \bibverse{63} The governor
told them that they should not eat of the most holy things until a
priest stood up to serve with Urim and with Thummim.

\bibverse{64} The whole assembly together was forty-two thousand and
three hundred and sixty, \bibverse{65} in addition to their male
servants and their female servants, of whom there were seven thousand
and three hundred and thirty-seven; and they had two hundred singing men
and singing women. \bibverse{66} Their horses were seven hundred and
thirty-six; their mules, two hundred and forty-five; \bibverse{67} their
camels, four hundred and thirty-five; their donkeys, six thousand and
seven hundred and twenty.

\bibverse{68} Some of the heads of fathers' households, when they came
to the LORD's house which is in Jerusalem, offered willingly for God's
house to set it up in its place. \bibverse{69} They gave according to
their ability into the treasury of the work sixty-one thousand darics of
gold,\footnote{2:69 a daric was a gold coin issued by a Persian king,
  weighing about 8.4 grams or about 0.27 troy ounces each.} five
thousand minas+ 2:69 A mina is about 600 grams or 1.3 U. S. pounds, so
5,000 minas is about 3 metric tonnes. of silver, and one hundred
priests' garments.

\bibverse{70} So the priests and the Levites, with some of the people,
the singers, the gatekeepers, and the temple servants, lived in their
cities, and all Israel in their cities.

\hypertarget{section-2}{%
\section{3}\label{section-2}}

\bibverse{1} When the seventh month had come, and the children of Israel
were in the cities, the people gathered themselves together as one man
to Jerusalem. \bibverse{2} Then Jeshua the son of Jozadak stood up with
his brothers the priests and Zerubbabel the son of Shealtiel and his
relatives, and built the altar of the God of Israel, to offer burnt
offerings on it, as it is written in the law of Moses the man of God.
\bibverse{3} In spite of their fear because of the peoples of the
surrounding lands, they set the altar on its base; and they offered
burnt offerings on it to the LORD, even burnt offerings morning and
evening. \bibverse{4} They kept the feast of booths, as it is written,
and offered the daily burnt offerings by number, according to the
ordinance, as the duty of every day required; \bibverse{5} and afterward
the continual burnt offering, the offerings of the new moons, of all the
set feasts of the LORD that were consecrated, and of everyone who
willingly offered a free will offering to the LORD. \bibverse{6} From
the first day of the seventh month, they began to offer burnt offerings
to the LORD; but the foundation of the LORD's temple was not yet laid.
\bibverse{7} They also gave money to the masons and to the carpenters.
They also gave food, drink, and oil to the people of Sidon and Tyre to
bring cedar trees from Lebanon to the sea, to Joppa, according to the
grant that they had from Cyrus King of Persia.

\bibverse{8} Now in the second year of their coming to God's house at
Jerusalem, in the second month, Zerubbabel the son of Shealtiel, Jeshua
the son of Jozadak, and the rest of their brothers the priests and the
Levites, and all those who had come out of the captivity to Jerusalem,
began the work and appointed the Levites, from twenty years old and
upward, to have the oversight of the work of the LORD's house.
\bibverse{9} Then Jeshua stood with his sons and his brothers, Kadmiel
and his sons, the sons of Judah, together to have the oversight of the
workmen in God's house: the sons of Henadad, with their sons and their
brothers the Levites.

\bibverse{10} When the builders laid the foundation of the LORD's
temple, they set the priests in their vestments with trumpets, with the
Levites the sons of Asaph with cymbals, to praise the LORD, according to
the directions of David king of Israel. \bibverse{11} They sang to one
another in praising and giving thanks to the LORD, ``For he is good, for
his loving kindness endures forever towards Israel.'' All the people
shouted with a great shout, when they praised the LORD, because the
foundation of the LORD's house had been laid.

\bibverse{12} But many of the priests and Levites and heads of fathers'
households, the old men who had seen the first house, when the
foundation of this house was laid before their eyes, wept with a loud
voice. Many also shouted aloud for joy, \bibverse{13} so that the people
could not discern the noise of the shout of joy from the noise of the
weeping of the people; for the people shouted with a loud shout, and the
noise was heard far away.

\hypertarget{section-3}{%
\section{4}\label{section-3}}

\bibverse{1} Now when the adversaries of Judah and Benjamin heard that
the children of the captivity were building a temple to the LORD, the
God of Israel, \bibverse{2} they came near to Zerubbabel, and to the
heads of fathers' households, and said to them, ``Let us build with you,
for we seek your God as you do; and we have been sacrificing to him
since the days of Esar Haddon king of Assyria, who brought us up here.''

\bibverse{3} But Zerubbabel, Jeshua, and the rest of the heads of
fathers' households of Israel said to them, ``You have nothing to do
with us in building a house to our God; but we ourselves together will
build to the LORD, the God of Israel, as king Cyrus the king of Persia
has commanded us.''

\bibverse{4} Then the people of the land weakened the hands of the
people of Judah, and troubled them in building. \bibverse{5} They hired
counsellors against them to frustrate their purpose all the days of
Cyrus king of Persia, even until the reign of Darius king of Persia.
\bibverse{6} In the reign of Ahasuerus, in the beginning of his reign,
they wrote an accusation against the inhabitants of Judah and Jerusalem.

\bibverse{7} In the days of Artaxerxes, Bishlam, Mithredath, Tabeel, and
the rest of his companions wrote to Artaxerxes king of Persia; and the
writing of the letter was written in Syrian and delivered in the Syrian
language. \bibverse{8} Rehum the chancellor and Shimshai the scribe
wrote a letter against Jerusalem to Artaxerxes the king as follows.
\bibverse{9} Then Rehum the chancellor, Shimshai the scribe, and the
rest of their companions, the Dinaites, and the Apharsathchites, the
Tarpelites, the Apharsites, the Archevites, the Babylonians, the
Shushanchites, the Dehaites, the Elamites, \bibverse{10} and the rest of
the nations whom the great and noble Osnappar brought over and settled
in the city of Samaria, and in the rest of the country beyond the River,
and so forth, wrote.

\bibverse{11} This is the copy of the letter that they sent: To King
Artaxerxes, from your servants, the people beyond the River.

i1\bibverse{12} Be it known to the king that the Jews who came up from
you have come to us to Jerusalem. They are building the rebellious and
bad city, and have finished the walls and repaired the foundations.
\bibverse{13} Be it known now to the king that if this city is built and
the walls finished, they will not pay tribute, custom, or toll, and in
the end it will be hurtful to the kings. \bibverse{14} Now because we
eat the salt of the palace and it is not appropriate for us to see the
king's dishonour, therefore we have sent and informed the king,
\bibverse{15} that search may be made in the book of the records of your
fathers. You will see in the book of the records, and know that this
city is a rebellious city, and hurtful to kings and provinces, and that
they have started rebellions within it in the past. That is why this
city was destroyed. \bibverse{16} We inform the king that if this city
is built and the walls finished, then you will have no possession beyond
the River. \bibverse{17} Then the king sent an answer to Rehum the
chancellor, and to Shimshai the scribe, and to the rest of their
companions who live in Samaria, and in the rest of the country beyond
the River: Peace. i1\bibverse{18} The letter which you sent to us has
been plainly read before me. \bibverse{19} I decreed, and search has
been made, and it was found that this city has made insurrection against
kings in the past, and that rebellion and revolts have been made in it.
\bibverse{20} There have also been mighty kings over Jerusalem who have
ruled over all the country beyond the River; and tribute, custom, and
toll was paid to them. \bibverse{21} Make a decree now to cause these
men to cease, and that this city not be built until a decree is made by
me. \bibverse{22} Be careful that you not be slack doing so. Why should
damage grow to the hurt of the kings? \bibverse{23} Then when the copy
of king Artaxerxes' letter was read before Rehum, Shimshai the scribe,
and their companions, they went in haste to Jerusalem to the Jews, and
made them to cease by force of arms. \bibverse{24} Then work stopped on
God's house which is at Jerusalem. It stopped until the second year of
the reign of Darius king of Persia.

\hypertarget{section-4}{%
\section{5}\label{section-4}}

\bibverse{1} Now the prophets, Haggai the prophet and Zechariah the son
of Iddo, prophesied to the Jews who were in Judah and Jerusalem. They
prophesied to them in the name of the God of Israel. \bibverse{2} Then
Zerubbabel the son of Shealtiel, and Jeshua the son of Jozadak rose up
and began to build God's house which is at Jerusalem; and with them were
the prophets of God, helping them.

\bibverse{3} At the same time Tattenai, the governor beyond the River,
came to them, with Shetharbozenai and their companions, and asked them,
``Who gave you a decree to build this house and to finish this wall?''
\bibverse{4} They also asked for the names of the men were who were
making this building. \bibverse{5} But the eye of their God was on the
elders of the Jews, and they didn't make them cease until the matter
should come to Darius, and an answer should be returned by letter
concerning it.

\bibverse{6} The copy of the letter that Tattenai, the governor beyond
the River, and Shetharbozenai, and his companions the Apharsachites who
were beyond the River, sent to Darius the king follows. \bibverse{7}
They sent a letter to him, in which was written: To Darius the king, all
peace.

i1\bibverse{8} Be it known to the king that we went into the province of
Judah, to the house of the great God, which is being built with great
stones and timber is laid in the walls. This work goes on with diligence
and prospers in their hands. \bibverse{9} Then we asked those elders,
and said to them thus, ``Who gave you a decree to build this house, and
to finish this wall?'' \bibverse{10} We asked them their names also, to
inform you that we might write the names of the men who were at their
head. \bibverse{11} Thus they returned us answer, saying, ``We are the
servants of the God of heaven and earth and are building the house that
was built these many years ago, which a great king of Israel built and
finished. \bibverse{12} But after our fathers had provoked the God of
heaven to wrath, he gave them into the hand of Nebuchadnezzar king of
Babylon, the Chaldean, who destroyed this house and carried the people
away into Babylon. \bibverse{13} But in the first year of Cyrus king of
Babylon, Cyrus the king made a decree to build this house of God.
\bibverse{14} The gold and silver vessels of God's house, which
Nebuchadnezzar took out of the temple that was in Jerusalem and brought
into the temple of Babylon, those Cyrus the king also took out of the
temple of Babylon, and they were delivered to one whose name was
Sheshbazzar, whom he had made governor. \bibverse{15} He said to him,
`Take these vessels, go, put them in the temple that is in Jerusalem,
and let God's house be built in its place.' \bibverse{16} Then the same
Sheshbazzar came and laid the foundations of God's house which is in
Jerusalem. Since that time even until now it has been being built, and
yet it is not completed.

i1\bibverse{17} Now therefore, if it seems good to the king, let a
search be made in the king's treasure house, which is there at Babylon,
whether it is so that a decree was made by Cyrus the king to build this
house of God at Jerusalem; and let the king send his pleasure to us
concerning this matter.''

\hypertarget{section-5}{%
\section{6}\label{section-5}}

\bibverse{1} Then Darius the king made a decree, and the house of the
archives, where the treasures were laid up in Babylon, was searched.
\bibverse{2} A scroll was found at Achmetha, in the palace that is in
the province of Media, and in it this was written for a record:
i1\bibverse{3} In the first year of Cyrus the king, Cyrus the king made
a decree: Concerning God's house at Jerusalem, let the house be built,
the place where they offer sacrifices, and let its foundations be
strongly laid, with its height sixty cubits\footnote{6:3 A cubit is the
  length from the tip of the middle finger to the elbow on a man's arm,
  or about 18 inches or 46 centimetres.} and its width sixty cubits;
\bibverse{4} with three courses of great stones and a course of new
timber. Let the expenses be given out of the king's house. \bibverse{5}
Also let the gold and silver vessels of God's house, which
Nebuchadnezzar took out of the temple which is at Jerusalem and brought
to Babylon, be restored and brought again to the temple which is at
Jerusalem, everything to its place. You shall put them in God's house.

i1\bibverse{6} Now therefore, Tattenai, governor beyond the River,
Shetharbozenai, and your companions the Apharsachites, who are beyond
the River, you must stay far from there. \bibverse{7} Leave the work of
this house of God alone; let the governor of the Jews and the elders of
the Jews build this house of God in its place. \bibverse{8} Moreover I
make a decree regarding what you shall do for these elders of the Jews
for the building of this house of God: that of the king's goods, even of
the tribute beyond the River, expenses must be given with all diligence
to these men, that they not be hindered. \bibverse{9} That which they
have need of, including young bulls, rams, and lambs, for burnt
offerings to the God of heaven; also wheat, salt, wine, and oil,
according to the word of the priests who are at Jerusalem, let it be
given them day by day without fail, \bibverse{10} that they may offer
sacrifices of pleasant aroma to the God of heaven, and pray for the life
of the king and of his sons. \bibverse{11} I have also made a decree
that whoever alters this message, let a beam be pulled out from his
house, and let him be lifted up and fastened on it; and let his house be
made a dunghill for this. \bibverse{12} May the God who has caused his
name to dwell there overthrow all kings and peoples who stretch out
their hand to alter this, to destroy this house of God which is at
Jerusalem. I Darius have made a decree. Let it be done with all
diligence. \bibverse{13} Then Tattenai, the governor beyond the River,
Shetharbozenai, and their companions did accordingly with all diligence,
because Darius the king had sent a decree.

\bibverse{14} The elders of the Jews built and prospered, through the
prophesying of Haggai the prophet and Zechariah the son of Iddo. They
built and finished it, according to the commandment of the God of
Israel, and according to the decree of Cyrus, Darius, and Artaxerxes
king of Persia. \bibverse{15} This house was finished on the third day
of the month Adar, which was in the sixth year of the reign of Darius
the king.

\bibverse{16} The children of Israel, the priests, the Levites, and the
rest of the children of the captivity, kept the dedication of this house
of God with joy. \bibverse{17} They offered at the dedication of this
house of God one hundred bulls, two hundred rams, four hundred lambs;
and for a sin offering for all Israel, twelve male goats, according to
the number of the tribes of Israel. \bibverse{18} They set the priests
in their divisions and the Levites in their courses, for the service of
God which is at Jerusalem, as it is written in the book of Moses.

\bibverse{19} The children of the captivity kept the Passover on the
fourteenth day of the first month. \bibverse{20} Because the priests and
the Levites had purified themselves together, all of them were pure.
They killed the Passover for all the children of the captivity, for
their brothers the priests, and for themselves. \bibverse{21} The
children of Israel who had returned out of the captivity, and all who
had separated themselves to them from the filthiness of the nations of
the land to seek the LORD, the God of Israel, ate, \bibverse{22} and
kept the feast of unleavened bread seven days with joy; because the LORD
had made them joyful, and had turned the heart of the king of Assyria to
them, to strengthen their hands in the work of God, the God of Israel's
house.

\hypertarget{section-6}{%
\section{7}\label{section-6}}

\bibverse{1} Now after these things, in the reign of Artaxerxes king of
Persia, Ezra the son of Seraiah, the son of Azariah, the son of Hilkiah,
\bibverse{2} the son of Shallum, the son of Zadok, the son of Ahitub,
\bibverse{3} the son of Amariah, the son of Azariah, the son of
Meraioth, \bibverse{4} the son of Zerahiah, the son of Uzzi, the son of
Bukki, \bibverse{5} the son of Abishua, the son of Phinehas, the son of
Eleazar, the son of Aaron the chief priest--- \bibverse{6} this Ezra
went up from Babylon. He was a skilled scribe in the law of Moses, which
the LORD, the God of Israel, had given; and the king granted him all his
request, according to the LORD his God's hand on him. \bibverse{7} Some
of the children of Israel, including some of the priests, the Levites,
the singers, the gatekeepers, and the temple servants went up to
Jerusalem in the seventh year of Artaxerxes the king. \bibverse{8} He
came to Jerusalem in the fifth month, which was in the seventh year of
the king. \bibverse{9} For on the first day of the first month he began
to go up from Babylon; and on the first day of the fifth month he came
to Jerusalem, according to the good hand of his God on him.
\bibverse{10} For Ezra had set his heart to seek the LORD's law, and to
do it, and to teach statutes and ordinances in Israel.

\bibverse{11} Now this is the copy of the letter that King Artaxerxes
gave to Ezra the priest, the scribe, even the scribe of the words of the
LORD's commandments, and of his statutes to Israel: \bibverse{12}
Artaxerxes, king of kings, To Ezra the priest, the scribe of the law of
the perfect God of heaven.

i1 Now \bibverse{13} I make a decree that all those of the people of
Israel and their priests and the Levites in my realm, who intend of
their own free will to go to Jerusalem, go with you. \bibverse{14}
Because you are sent by the king and his seven counsellors to enquire
concerning Judah and Jerusalem, according to the law of your God which
is in your hand, \bibverse{15} and to carry the silver and gold, which
the king and his counsellors have freely offered to the God of Israel,
whose habitation is in Jerusalem, \bibverse{16} and all the silver and
gold that you will find in all the province of Babylon, with the free
will offering of the people and of the priests, offering willingly for
the house of their God which is in Jerusalem. \bibverse{17} Therefore
you shall with all diligence buy with this money bulls, rams, and lambs
with their meal offerings and their drink offerings, and shall offer
them on the altar of the house of your God which is in Jerusalem.
\bibverse{18} Whatever seems good to you and to your brothers to do with
the rest of the silver and the gold, do that according to the will of
your God. \bibverse{19} The vessels that are given to you for the
service of the house of your God, deliver before the God of Jerusalem.
\bibverse{20} Whatever more will be needed for the house of your God,
which you may have occasion to give, give it out of the king's treasure
house.

i1\bibverse{21} I, even I, Artaxerxes the king, make a decree to all the
treasurers who are beyond the River, that whatever Ezra the priest, the
scribe of the law of the God of heaven, requires of you, it shall be
done with all diligence, \bibverse{22} up to one hundred
talents\footnote{7:22 A talent is about 30 kilograms or 66 pounds or 965
  Troy ounces} of silver, and to one hundred cors+ 7:22 1 cor is the
same as a homer, or about 55.9 U. S. gallons (liquid) or 211 litres or 6
bushels. of wheat, and to one hundred baths+ 7:22 1 bath is one tenth of
a cor, or about 5.6 U. S. gallons or 21 litres or 2.4 pecks. 100 baths
would be about 2,100 litres. of wine, and to one hundred baths of oil,
and salt without prescribing how much. \bibverse{23} Whatever is
commanded by the God of heaven, let it be done exactly for the house of
the God of heaven; for why should there be wrath against the realm of
the king and his sons?

i1\bibverse{24} Also we inform you that it shall not be lawful to impose
tribute, custom, or toll on any of the priests, Levites, singers,
gatekeepers, temple servants, or labourers of this house of God.

i1\bibverse{25} You, Ezra, according to the wisdom of your God that is
in your hand, appoint magistrates and judges who may judge all the
people who are beyond the River, who all know the laws of your God; and
teach him who doesn't know them. \bibverse{26} Whoever will not do the
law of your God and the law of the king, let judgement be executed on
him with all diligence, whether it is to death, or to banishment, or to
confiscation of goods, or to imprisonment. \bibverse{27} Blessed be the
LORD, the God of our fathers, who has put such a thing as this in the
king's heart, to beautify the LORD's house which is in Jerusalem;
\bibverse{28} and has extended loving kindness to me before the king and
his counsellors, and before all the king's mighty princes. I was
strengthened according to the LORD my God's hand on me, and I gathered
together chief men out of Israel to go up with me.

\hypertarget{section-7}{%
\section{8}\label{section-7}}

\bibverse{1} Now these are the heads of their fathers' households, and
this is the genealogy of those who went up with me from Babylon, in the
reign of Artaxerxes the king: \bibverse{2} Of the sons of Phinehas,
Gershom. Of the sons of Ithamar, Daniel. Of the sons of David, Hattush.
\bibverse{3} Of the sons of Shecaniah, of the sons of Parosh, Zechariah;
and with him were listed by genealogy of the males one hundred and
fifty. \bibverse{4} Of the sons of Pahathmoab, Eliehoenai the son of
Zerahiah; and with him two hundred males. \bibverse{5} Of the sons of
Shecaniah, the son of Jahaziel; and with him three hundred males.
\bibverse{6} Of the sons of Adin, Ebed the son of Jonathan; and with him
fifty males. \bibverse{7} Of the sons of Elam, Jeshaiah the son of
Athaliah; and with him seventy males. \bibverse{8} Of the sons of
Shephatiah, Zebadiah the son of Michael; and with him eighty males.
\bibverse{9} Of the sons of Joab, Obadiah the son of Jehiel; and with
him two hundred and eighteen males. \bibverse{10} Of the sons of
Shelomith, the son of Josiphiah; and with him one hundred and sixty
males. \bibverse{11} Of the sons of Bebai, Zechariah the son of Bebai;
and with him twenty-eight males. \bibverse{12} Of the sons of Azgad,
Johanan the son of Hakkatan; and with him one hundred and ten males.
\bibverse{13} Of the sons of Adonikam, who were the last, their names
are: Eliphelet, Jeuel, and Shemaiah; and with them sixty males.
\bibverse{14} Of the sons of Bigvai, Uthai and Zabbud; and with them
seventy males.

\bibverse{15} I gathered them together to the river that runs to Ahava;
and there we encamped three days. Then I looked around at the people and
the priests, and found there were none of the sons of Levi.
\bibverse{16} Then I sent for Eliezer, for Ariel, for Shemaiah, for
Elnathan, for Jarib, for Elnathan, for Nathan, for Zechariah, and for
Meshullam, chief men; also for Joiarib and for Elnathan, who were
teachers. \bibverse{17} I sent them out to Iddo the chief at the place
Casiphia; and I told them what they should tell Iddo and his brothers
the temple servants at the place Casiphia, that they should bring to us
ministers for the house of our God. \bibverse{18} According to the good
hand of our God on us they brought us a man of discretion, of the sons
of Mahli, the son of Levi, the son of Israel, namely Sherebiah, with his
sons and his brothers, eighteen; \bibverse{19} and Hashabiah, and with
him Jeshaiah of the sons of Merari, his brothers and their sons, twenty;
\bibverse{20} and of the temple servants, whom David and the princes had
given for the service of the Levites, two hundred and twenty temple
servants. All of them were mentioned by name.

\bibverse{21} Then I proclaimed a fast there at the river Ahava, that we
might humble ourselves before our God, to seek from him a straight way
for us, for our little ones, and for all our possessions. \bibverse{22}
For I was ashamed to ask of the king a band of soldiers and horsemen to
help us against the enemy on the way, because we had spoken to the king,
saying, ``The hand of our God is on all those who seek him, for good;
but his power and his wrath is against all those who forsake him.''
\bibverse{23} So we fasted and begged our God for this, and he granted
our request.

\bibverse{24} Then I set apart twelve of the chiefs of the priests, even
Sherebiah, Hashabiah, and ten of their brothers with them, \bibverse{25}
and weighed to them the silver, the gold, and the vessels, even the
offering for the house of our God, which the king, his counsellors, his
princes, and all Israel there present, had offered. \bibverse{26} I
weighed into their hand six hundred and fifty talents of
silver,\footnote{8:26 A talent is about 30 kilograms or 66 pounds or 965
  Troy ounces} one hundred talents of silver vessels, one hundred
talents of gold, \bibverse{27} twenty bowls of gold weighing one
thousand darics,+ 8:27 a daric was a gold coin issued by a Persian king,
weighing about 8.4 grams or about 0.27 troy ounces each. and two vessels
of fine bright bronze, precious as gold. \bibverse{28} I said to them,
``You are holy to the LORD, and the vessels are holy. The silver and the
gold are a free will offering to the LORD, the God of your fathers.
\bibverse{29} Watch and keep them until you weigh them before the chiefs
of the priests, the Levites, and the princes of the fathers' households
of Israel at Jerusalem, in the rooms of the LORD's house.''

\bibverse{30} So the priests and the Levites received the weight of the
silver, the gold, and the vessels, to bring them to Jerusalem to the
house of our God.

\bibverse{31} Then we departed from the river Ahava on the twelfth day
of the first month, to go to Jerusalem. The hand of our God was on us,
and he delivered us from the hand of the enemy and the bandits by the
way. \bibverse{32} We came to Jerusalem, and stayed there three days.
\bibverse{33} On the fourth day the silver and the gold and the vessels
were weighed in the house of our God into the hand of Meremoth the son
of Uriah the priest; and with him was Eleazar the son of Phinehas; and
with them were Jozabad the son of Jeshua, and Noadiah the son of Binnui,
the Levites. \bibverse{34} Everything was counted and weighed; and all
the weight was written at that time.

\bibverse{35} The children of the captivity, who had come out of exile,
offered burnt offerings to the God of Israel: twelve bulls for all
Israel, ninety-six rams, seventy-seven lambs, and twelve male goats for
a sin offering. All this was a burnt offering to the LORD. \bibverse{36}
They delivered the king's commissions to the king's local governors and
to the governors beyond the River. So they supported the people and
God's house.

\hypertarget{section-8}{%
\section{9}\label{section-8}}

\bibverse{1} Now when these things were done, the princes came near to
me, saying, ``The people of Israel, the priests, and the Levites have
not separated themselves from the peoples of the lands, following their
abominations, even those of the Canaanites, the Hittites, the
Perizzites, the Jebusites, the Ammonites, the Moabites, the Egyptians,
and the Amorites. \bibverse{2} For they have taken of their daughters
for themselves and for their sons, so that the holy offspring have mixed
themselves with the peoples of the lands. Yes, the hand of the princes
and rulers has been chief in this trespass.''

\bibverse{3} When I heard this thing, I tore my garment and my robe, and
pulled the hair out of my head and of my beard, and sat down confounded.
\bibverse{4} Then everyone who trembled at the words of the God of
Israel were assembled to me because of the trespass of the exiles; and I
sat confounded until the evening offering.

\bibverse{5} At the evening offering I rose up from my humiliation, even
with my garment and my robe torn; and I fell on my knees, and spread out
my hands to the LORD my God; \bibverse{6} and I said, ``My God, I am
ashamed and blush to lift up my face to you, my God, for our iniquities
have increased over our head, and our guiltiness has grown up to the
heavens. \bibverse{7} Since the days of our fathers we have been
exceedingly guilty to this day; and for our iniquities we, our kings,
and our priests have been delivered into the hand of the kings of the
lands, to the sword, to captivity, to plunder, and to confusion of face,
as it is this day. \bibverse{8} Now for a little moment grace has been
shown from the LORD our God, to leave us a remnant to escape, and to
give us a stake in his holy place, that our God may lighten our eyes,
and revive us a little in our bondage. \bibverse{9} For we are
bondservants; yet our God has not forsaken us in our bondage, but has
extended loving kindness to us in the sight of the kings of Persia, to
revive us, to set up the house of our God, and to repair its ruins, and
to give us a wall in Judah and in Jerusalem.

\bibverse{10} ``Now, our God, what shall we say after this? For we have
forsaken your commandments, \bibverse{11} which you have commanded by
your servants the prophets, saying, `The land to which you go to possess
is an unclean land through the uncleanness of the peoples of the lands,
through their abominations, which have filled it from one end to another
with their filthiness. \bibverse{12} Now therefore don't give your
daughters to their sons. Don't take their daughters to your sons, nor
seek their peace or their prosperity forever, that you may be strong and
eat the good of the land, and leave it for an inheritance to your
children forever.'

\bibverse{13} ``After all that has come on us for our evil deeds and for
our great guilt, since you, our God, have punished us less than our
iniquities deserve, and have given us such a remnant, \bibverse{14}
shall we again break your commandments, and join ourselves with the
peoples that do these abominations? Wouldn't you be angry with us until
you had consumed us, so that there would be no remnant, nor any to
escape? \bibverse{15} LORD, the God of Israel, you are righteous; for we
are left a remnant that has escaped, as it is today. Behold,\footnote{9:15
  ``Behold'', from ``הִנֵּה'', means look at, take notice, observe, see,
  or gaze at. It is often used as an interjection.} we are before you in
our guiltiness; for no one can stand before you because of this.''

\hypertarget{section-9}{%
\section{10}\label{section-9}}

\bibverse{1} Now while Ezra prayed and made confession, weeping and
casting himself down before God's house, there was gathered together to
him out of Israel a very great assembly of men and women and children;
for the people wept very bitterly. \bibverse{2} Shecaniah the son of
Jehiel, one of the sons of Elam, answered Ezra, ``We have trespassed
against our God, and have married foreign women of the peoples of the
land. Yet now there is hope for Israel concerning this thing.
\bibverse{3} Now therefore let's make a covenant with our God to put
away all the wives and those who are born of them, according to the
counsel of my lord and of those who tremble at the commandment of our
God. Let it be done according to the law. \bibverse{4} Arise, for the
matter belongs to you and we are with you. Be courageous, and do it.''

\bibverse{5} Then Ezra arose, and made the chiefs of the priests, the
Levites, and all Israel to swear that they would do according to this
word. So they swore. \bibverse{6} Then Ezra rose up from before God's
house, and went into the room of Jehohanan the son of Eliashib. When he
came there, he didn't eat bread or drank water, for he mourned because
of the trespass of the exiles. \bibverse{7} They made a proclamation
throughout Judah and Jerusalem to all the children of the captivity,
that they should gather themselves together to Jerusalem; \bibverse{8}
and that whoever didn't come within three days, according to the counsel
of the princes and the elders, all his possessions should be forfeited,
and he himself separated from the assembly of the captivity.

\bibverse{9} Then all the men of Judah and Benjamin gathered themselves
together to Jerusalem within the three days. It was the ninth month, on
the twentieth day of the month; and all the people sat in the wide place
in front of God's house, trembling because of this matter, and because
of the great rain.

\bibverse{10} Ezra the priest stood up and said to them, ``You have
trespassed, and have married foreign women, increasing the guilt of
Israel. \bibverse{11} Now therefore make confession to the LORD, the God
of your fathers and do his pleasure. Separate yourselves from the
peoples of the land and from the foreign women.''

\bibverse{12} Then all the assembly answered with a loud voice, ``We
must do as you have said concerning us. \bibverse{13} But the people are
many, and it is a time of much rain, and we are not able to stand
outside. This is not a work of one day or two, for we have greatly
transgressed in this matter. \bibverse{14} Now let our princes be
appointed for all the assembly, and let all those who are in our cities
who have married foreign women come at appointed times, and with them
the elders of every city and its judges, until the fierce wrath of our
God is turned from us, until this matter is resolved.''

\bibverse{15} Only Jonathan the son of Asahel and Jahzeiah the son of
Tikvah stood up against this; and Meshullam and Shabbethai the Levite
helped them.

\bibverse{16} The children of the captivity did so. Ezra the priest,
with certain heads of fathers' households, after their fathers' houses,
and all of them by their names, were set apart; and they sat down in the
first day of the tenth month to examine the matter. \bibverse{17} They
finished with all the men who had married foreign women by the first day
of the first month.

\bibverse{18} Amongst the sons of the priests there were found who had
married foreign women: of the sons of Jeshua, the son of Jozadak, and
his brothers: Maaseiah, Eliezer, Jarib, and Gedaliah. \bibverse{19} They
gave their hand that they would put away their wives; and being guilty,
they offered a ram of the flock for their guilt. \bibverse{20} Of the
sons of Immer: Hanani and Zebadiah. \bibverse{21} Of the sons of Harim:
Maaseiah, Elijah, Shemaiah, Jehiel, and Uzziah. \bibverse{22} Of the
sons of Pashhur: Elioenai, Maaseiah, Ishmael, Nethanel, Jozabad, and
Elasah. \bibverse{23} Of the Levites: Jozabad, Shimei, Kelaiah (also
called Kelita), Pethahiah, Judah, and Eliezer. \bibverse{24} Of the
singers: Eliashib. Of the gatekeepers: Shallum, Telem, and Uri.
\bibverse{25} Of Israel: Of the sons of Parosh: Ramiah, Izziah,
Malchijah, Mijamin, Eleazar, Malchijah, and Benaiah. \bibverse{26} Of
the sons of Elam: Mattaniah, Zechariah, Jehiel, Abdi, Jeremoth, and
Elijah. \bibverse{27} Of the sons of Zattu: Elioenai, Eliashib,
Mattaniah, Jeremoth, Zabad, and Aziza. \bibverse{28} Of the sons of
Bebai: Jehohanan, Hananiah, Zabbai, and Athlai. \bibverse{29} Of the
sons of Bani: Meshullam, Malluch, Adaiah, Jashub, Sheal, and Jeremoth.
\bibverse{30} Of the sons of Pahathmoab: Adna, Chelal, Benaiah,
Maaseiah, Mattaniah, Bezalel, Binnui, and Manasseh. \bibverse{31} Of the
sons of Harim: Eliezer, Isshijah, Malchijah, Shemaiah, Shimeon,
\bibverse{32} Benjamin, Malluch, and Shemariah. \bibverse{33} Of the
sons of Hashum: Mattenai, Mattattah, Zabad, Eliphelet, Jeremai,
Manasseh, and Shimei. \bibverse{34} Of the sons of Bani: Maadai, Amram,
Uel, \bibverse{35} Benaiah, Bedeiah, Cheluhi, \bibverse{36} Vaniah,
Meremoth, Eliashib, \bibverse{37} Mattaniah, Mattenai, Jaasu,
\bibverse{38} Bani, Binnui, Shimei, \bibverse{39} Shelemiah, Nathan,
Adaiah, \bibverse{40} Machnadebai, Shashai, Sharai, \bibverse{41}
Azarel, Shelemiah, Shemariah, \bibverse{42} Shallum, Amariah, and
Joseph. \bibverse{43} Of the sons of Nebo: Jeiel, Mattithiah, Zabad,
Zebina, Iddo, Joel, and Benaiah.

\bibverse{44} All these had taken foreign wives. Some of them had wives
by whom they had children.

max_stars_repo_name: bibliadelpueblo/BibliaLibre

max_issues_repo_name: bibliadelpueblo/BibliaLibre

max_forks_repo_name: bibliadelpueblo/BibliaLibre


text:
\section{Minimal System Requirements}
\label{requirements}

In order to install {\tt the system} you must have a Common Lisp running
on your machine.
Successful installations have been accomplished in KCL, AKCL, IBCL, DCL, LUCID.

ext: tex

max_stars_repo_name: getfol/GETFOL

max_stars_repo_licenses: DOC Unlicense

max_issues_repo_name: getfol/GETFOL

max_issues_repo_licenses: DOC Unlicense

max_forks_repo_name: getfol/GETFOL

max_forks_repo_licenses: DOC Unlicense


text:
\chapter{Introduction}
\newthought{Biological evolution is the change over time in the genetic composition of a population.} \cite{DobzhanskyBook} Our population is made up of a set of interbreeding individuals, the genetic composition of which is made up of the  genomes that each individual carries.  %While at first this definition of evolution seems at odds with the
%common textbook view of the evolution of phenotypes, such as the changing shape
%of finch beaks over generations, it is genetic changes that underpin these
%phenotypic changes.   \\
The genetic composition of the population alters due to the death of individuals or the migration of individuals in or out
of the population. If our individuals vary in the number of children they have, this
also alters the genetic composition of the population in the next generation.
Every new individual born into the population subtly changes the genetic
composition of the population. Their genome is a unique combination of their
parents' genomes, having been shuffled by segregation and recombination during
meioses, and possibly changed by mutation. These individual events seem minor at the level of the population, but it is the accumulation of small changes in aggregate across individuals and generations that is the stuff of evolution. It is the compounding of these small changes over tens, hundreds, and millions of generations that drives the amazing diversity of life that has emerged on this earth.\\

Population genetics is the study of the genetic composition of natural
populations and its evolutionary causes and consequences. Quantitative genetics is the study of the genetic basis of phenotypic variation and how phenotypic changes evolve over time. Both fields are closely conceptually aligned as we'll see throughout these notes. They seek to describe how the genetic and phenotypic composition of populations can be changed over
time by the forces of mutation, recombination, selection, migration, and
genetic drift.  To understand how these forces interact, it is helpful to
develop simple theoretical models to help our intuition. In these notes we will
work through these models and summarize the major areas of population- and quantitative-genetic
theory.\\

\marginnote{``All models are wrong but some are useful'' -
  \citet{box:79}.}  % https://en.wikipedia.org/wiki/All_models_are_wrong#Quotations_of_George_Box
% http://www.dtic.mil/dtic/tr/fulltext/u2/a070213.pdf

While the models we will develop will seem na\"{\i}ve, and indeed they are, they are
nonetheless incredibly useful and powerful. Throughout the course we will see
that these simple models often yield accurate predictions, such that much of our
understanding of the process of evolution is built on these models. We will
also see how these models are incredibly useful for understanding real patterns
we see in the evolution of phenotypes and genomes, such that much of our
analysis of evolution, in a range of areas from human medical genetics to conservation,
is based on these models. Therefore, population and quantitative genetics are key to
understanding various applied questions, from how medical genetics identifies
the genes involved in disease to how we preserve species from extinction. \\

Population genetics emerged from early efforts to
reconcile Mendelian genetics with Darwinian thought.\marginnote{See
\citet{provine:01} \cite{provine:01} for a history of early population
genetics.}
Part of the power of
population genetics comes from the fact that the basic rules of
transmission genetics are simple and nearly universal.  One of the truly remarkable things about population genetics is that
many of the important ideas and mathematical models emerged before the
1940s, long before the
mechanistic-basis of inheritance (DNA) was discovered, and yet the
usefulness of these models has not diminished. This is a testament to
the fact that the models are established on a very solid foundation,
building from the basic rules of genetic transmission combined with
simple mathematical and statistical models.

Much of this early work traces to the ideas of R.A. Fisher, Sewall Wright, and J.B.S. Haldane, who, along with many others, described the early principals and mathematical models underlying our understanding of the evolution of populations. Building on this conceptual fusion of genetics and evolution, there followed a flourishing of evolutionary thought, the modern evolutionary synthesis, combining these ideas with those from the study of speciation, biodiversity, and paleontology. In total this work showed that both short-term evolutionary change and the long-term evolution of biodiversity could be well understood through the gradual accumulation of evolutionary change within and among populations. This evolutionary synthesis continues to this day, combining new insights from genomics, phylogenetics, ecology, and developmental biology.

Population and quantitative genetics are a necessary but not sufficient description of evolution; it is only by combining the insights of many fields that a rich and comprehensive picture of evolution emerges.
\marginnote[-2cm]{
\begin{quote}
``\citet{DobzhanskyBook} once defined evolution as 'a change in the genetic
composition of the populations' an epigram that should not be
mistaken for the claim that everything worth saying about evolution is
contained in statements about genes''
\end{quote} -- \citet{lewontin01} }
We certainly do not need to know the genes underlying the displays of the birds of paradise to study how the divergence of these displays, due to sexual selection, may drive speciation. Indeed, as we'll see in our discussion of quantitative genetics, we can predict how populations respond to selection, including sexual selection and assortative mating, without any knowledge of the loci involved. Nor do we need to know the precise selection pressures and the ordering of genetic changes to study the emergence of the tetrapod body plan. We do not necessarily need to know all the genetic details to appreciate the beauty of these, and many other, evolutionary case studies. However, every student of biology gains from understanding the basics of population and quantitative genetics, allowing them to base their studies on a solid bedrock of understanding of the processes that underpin all evolutionary change.

%A full description of evolution only emerges from an understanding of the

%\ec{this is an awkward segway}
%Population geneticists can sometimes seem
%myopic in their focus on the nuts and bolts of evolution. The grandeur
%of evolution can sometimes seem a little lost in the simple models of
%population geneticists and in the field's obsession with genomic
%sequencing.

%The fact that many evolutionary principals are underpinned by
%population genetic models does diminish other
%areas of evolutionary study.

%We certainly do not need to know all of the genes underlying the
%displays of the bird of paradise's to study how the divergence of
%these displays due to sexual selection may drive speciation.
%Nor do we need know the precise selection pressures that drove
%to study the developmental mechanisms XXXX.
%Many of these aspects of any given things may be fundementally
%unknowable, and may often not be of primary interest to a given field
%of study.

%It is also not true that

max_stars_repo_name: emjosephs/popgen-notes

max_issues_repo_name: emjosephs/popgen-notes

max_forks_repo_name: emjosephs/popgen-notes


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                   File: OSAmeetings.tex             %
%                  Date: March 21, 2007  MSD          %
%                                                     %
%     For preparing LaTeX manuscripts for submission  %
%       submission to OSA meetings and conferences    %
%                                                     %
%       (c) 2007 Optical Society of America           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[letterpaper,10pt]{article}
\usepackage{osameet2}

%% standard packages and arguments should be modified as needed

\usepackage{amsmath,amssymb}
\usepackage{floatrow}
\usepackage[export]{adjustbox}

% \bibliography{paper}
% \bibliographystyle{osajnl}

%\usepackage[pdftex,colorlinks=true,bookmarks=false,citecolor=blue,urlcolor=blue]{hyperref} %pdflatex
\usepackage[colorlinks=true,bookmarks=false,citecolor=blue,urlcolor=blue]{hyperref} %latex w/dvips

\begin{document}

\title{Three-Dimensional Fluorophore Orientation Imaging with Multiview Polarized Microscopy}

\author{Talon Chandler,${}^{1,*}$ Min Guo,${}^2$ Shalin Mehta,${}^{1,3,4}$ Abhishek Kumar,${}^2$\\ Hari Shroff,${}^{2,5}$ Rudolf Oldenbourg,${}^{3,6}$ Patrick J. La Rivi\`ere${}^{1,5}$}

\address{${}^1$Department of Radiology, University of Chicago, Chicago, Illinois 60637, USA.\\ ${}^2$Section on High Resolution Optical Imaging, National Institute of Biomedical Imaging\\ and Bioengineering, National Institutes of Health, Bethesda, Maryland 20892, USA.\\ ${}^3$Bell Center, Marine Biological Laboratory, Woods Hole, Massachusetts 02543, USA.\\ ${}^4$(present address) Chan Zuckerberg Biohub, San Francisco, California 94158, USA.\\ ${}^5$Whitman Center, Marine Biological Laboratory, Woods Hole, Massachusetts 02543, USA.\\ ${}^6$Department of Physics, Brown University, Providence, Rhode Island 02912, USA.}
\email{${}^*$talonchandler@talonchandler.com} %% email address is required

\begin{abstract}
  \hspace{-0.75em} We show that polarized fluorescence microscopes make
  band-limited measurements in the angular frequency domain. We use this result
  to propose and demonstrate efficient algorithms for reconstructing
  three-dimensional fluorophore orientations from multiview polarized microscope
  data.
\end{abstract}
\vspace{0.03em}
\ocis{180.2520 Fluorescence microscopy, 260.5430 Polarization}
\vspace{-1em}
\section{Introduction}
Polarized fluorescence microscopes can measure the orientation of fluorophores
in live specimens\cite{weiss1999}. Unfortunately, existing techniques are
limited to imaging two-dimensional orientations, and attempts to generalize
these approaches to three-dimensional orientations have faced computational
difficulties. We propose the use of the spherical harmonics to simplify the
analysis of polarized fluorescence microscopes. In the same way that the Fourier
transform simplifies the analysis of spatial imaging systems, the spherical
Fourier transform simplifies the analysis of angular imaging systems.

\section{Theory}
Consider a small voxel that contains many non-interacting fluorophores. We define the
orientation distribution function $f(\hat{\mathbf{s}})$ as the number of
fluorophores per steradian oriented in a direction $\hat{\mathbf{s}}$. The goal
of polarized fluorescence microscopy is to estimate $f(\hat{\mathbf{s}})$ in
many voxels throughout a three-dimensional sample.

The forward model for an $N$-measurement polarized fluorescence microscope is
given by
\begin{align}
  g_i = \int_{\mathbb{S}^2}d\hat{\mathbf{s}}\ h_i(\hat{\mathbf{s}})f(\hat{\mathbf{s}})\hspace{1em}\text{for}\hspace{1em} i=1,\dotsc,N,
\end{align}
where $h_i(\hat{\mathbf{s}})$ is the kernel of the $i$th microscope
configuration, the integral is over the sphere $\mathbb{S}^2$, and $g_i$ is the
$i$th intensity measurement. Note that we are applying this forward model to
each voxel independently---we assume that there is no spatial blurring so the
signal from each voxel is independent. By discretizing $f(\hat{\mathbf{s}})$ and
expanding $h(\hat{\mathbf{s}})$ in terms of the spherical harmonics, we can
rewrite Eq. (1) as
\begin{align}
  \mathbf{g} = \Psi\hspace{0.1em}\mathbf{B}^+\mathbf{f},
\end{align}
where $\mathbf{f} = [f(\hat{\mathbf{s}}_1), \cdots, f(\hat{\mathbf{s}}_R)]^T$ is
a vector of $R$ samples of $f(\hat{\mathbf{s}})$; $\mathbf{B}$ is a matrix of
the spherical harmonics evaluated at the sample points,
$\mathbf{B}_{ij} = Y_j(\hat{\mathbf{s}}_i)$ where $Y_j$ is the $j$th spherical
harmonic; $\cdot^+$ is the Moore-Penrose pseudoinverse; $\Psi$ is a matrix of
the spherical harmonic coefficients of the kernels,
$\Psi_{ij} = \int_{\mathbb{S}^2}d\hat{\textbf{s}}\
h_i(\hat{\mathbf{s}})Y_j(\hat{\mathbf{s}})$; and
$\mathbf{g} = [g_1, \cdots, g_N]^T$ is a vector of the $N$ intensity
measurements.

The kernels for a wide class of polarized fluorescence microscopes have been
calculated previously\cite{chandler}. For many polarized fluorescence
microscopes the kernel can be expanded in terms of a small number of spherical
harmonics. If the kernel can be expanded in terms of $M$ spherical harmonics
then $\Psi$ is an $N\times M$ matrix and $\mathbf{B}^+$ only needs to be
calculated in the first $M$ columns. This simplification reduces Eq. (1) from
a set of integrals to an efficient series of matrix multiplications.

\section{Methods and Results}
We labeled the actin filaments of a fixed-cell sample with Alexa Fluor 488
Phalloidin and imaged the sample with an asymmetric 1.1/0.71 NA dual-view
inverted selective plane illumination microscope with orthogonal objectives
\cite{wu2017} and variable polarizers added to both illumination paths. The
dipole moment of Alexa Fluor 488 Phalloidin is known to align parallel to the
long axis of actin filaments, so this sample makes a suitable test specimen for
our reconstruction algorithm. We imaged the specimen volume eight times---two
views with four illumination polarization orientations each.

To reconstruct the orientation in each voxel we solved the following problem
\begin{align}
\mathbf{f^{\thinspace *}}= \underset{\mathbf{f}\in\{\mathbf{e}_i\}\ i = 0,\dotsc,R}{\text{argmin}}
\ \ ||\thinspace\mathbf{g} - \Psi\hspace{0.1em}\mathbf{B}^+\mathbf{f}\thinspace||_2^2,
\end{align}
where $\mathbf{e}_i$ is a vector with a one in the $i$th entry and zeros
elsewhere. By constraining $\mathbf{f}$ we are assuming that all of the
fluorophores in each voxel are oriented in the same direction---a reasonable
assumption for this sample.
\begin{figure}[htbp]
  \centering
  \includegraphics[width=16.cm, trim={0.1cm 1.3cm 0 0.5cm}]{figs/roi2/data.pdf}
  \caption{Fluorescence intensities of a small volume
    ($13.5\times 13.5\times 5.4\ \mu$m${}^3$) of a cell that was fixed, stained
    with Alexa Fluor 488 Phalloidin, and imaged in a dual-view microscope
    (diSPIM). The staining reveals two sets of actin bundles. Because
    fluorophores are aligned parallel to the bundles, their fluorescence
    intensities are modulated by the propagation direction and polarization of
    the excitation light. Bundles from bottom right to top left are highlighted
    for $x$-illumination and $z$-detection with
    $\phi_{\text{pol}} = 90^{\circ}$, while their intensities almost disappear
    for $z$-illumination and $x$-detection with $\phi_{\text{pol}} = 0^{\circ}$,
    which reveals the bundles running from bottom left to top right.}
\end{figure}

\begin{minipage}{.263\textwidth}
  \includegraphics[width=3.7cm, trim={0cm 0cm 0 0cm}, right]{figs/roi2/recon_color-min.png}
\end{minipage}% This must go next to `\end{minipage}`
\begin{minipage}{.639\textwidth}
  Fig. 2. Reconstruction of fluorophore orientations based on all intensity
    data shown in Fig. 1. Orientations are shown as short lines only in voxels
    whose fluorescence intensities surpassed a threshold. To highlight the two
    sets of actin bundles discussed in the caption of Fig. 1, we split the
    volume with a plane and colored the proximal voxels red and the distal
    voxels green. The reconstructed orientations approximately align with the
    long axes of the actin filaments as expected.
\end{minipage}
 \vspace{-1em}
{\footnotesize\bibliography{abstract}{}}
\bibliographystyle{osajnl}

\end{document}

max_stars_repo_name: talonchandler/polharmonic

max_issues_repo_name: talonchandler/polharmonic

max_forks_repo_name: talonchandler/polharmonic


text:
\section{Priority Queue}

\toclesssubsection{Introduction}

\begin{frame}{Priority Queue}{Introduction}
  \textbf{Definition:}
  \begin{itemize}
    \item<2->
      A priority queue saves a set of elements
    \item<3->
      Each element contains a key and a value like a map
    \item<4->
      There is a total order (like ${\color{Mittel-Blau}\leq}$) defined on the
      keys
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Introduction}
  \textbf{Definition:}
  \begin{itemize}
    \item<2->
      The priority queue supports the following operations:
  \end{itemize}
  \onslide<3->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{insert(key, value):}} &
    inserts a new element into the queue
  \end{tabular}
  \onslide<4->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{getMin():}} &
    returns the element with the smallest key\\
    {\color{Mittel-Blau}\texttt{deleteMin():}} &
    removes the element with the smallest key
  \end{tabular}
  \vspace{1.0em}
  \begin{itemize}
    \item<5->
      Sometimes additional operations are defined:
  \end{itemize}
  \onslide<6->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{changeKey(item, key):}} &
    changes the key of the element
  \end{tabular}
  \onslide<7->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{remove(item):}} &
    removes the element from the queue
  \end{tabular}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Introduction}
  \textbf{Special features:}
  \begin{itemize}
    \item<2->
      Multiple elements with the same key
      \begin{itemize}
        \item<3->
          No problem and for many applications necessary
        \item<3->
          If there is more than one element with the smallest key
          \begin{tabular}{ll}
            {\color{Mittel-Blau}\texttt{getMin():}} &
            returns just one of the possible elements\\
            {\color{Mittel-Blau}\texttt{deleteMin():}} &
            deletes the element returned by
            {\color{Mittel-Blau}\texttt{getMin}}
          \end{tabular}
      \end{itemize}
      \vspace{0.5em}
    \item<4->
      Argument of {\color{Mittel-Blau}\texttt{changeKey}} and
          {\color{Mittel-Blau}\texttt{remove}} operations
      \begin{itemize}
        \item<5->
          There is no \textbf{quick access} to an element in the queue
        \item<5->
          That is why {\color{Mittel-Blau}\texttt{insert}} and
          {\color{Mittel-Blau}\texttt{getMin}} return a reference
          (handle, accessor object)
        \item<5->
          {\color{Mittel-Blau}\texttt{changeKey}} and
          {\color{Mittel-Blau}\texttt{remove}} take this reference as argument
        \item<5->
          Therefore each element has to store its current position in the heap.
      \end{itemize}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\codeslide{python}{
\begin{frame}{Priority Queue}{Python}
  \vspace{-1.0em}
  \lstinputlisting[
    language=Python,
    basicstyle=\scriptesize,
    tabsize=4,
    style={python-idle-code},
    escapechar={@}
  ]{Code/PriorityQueue.py}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{java}{
\begin{frame}{Priority Queue}{Java}
  \lstinputlisting[
    language=Java,
    basicstyle=\scriptesize,
    tabsize=4,
    style={java-eclipse-code},
    breaklines=false,
    escapechar={@},
    emph={q,i1,i2},
    emphstyle=\color{java_variable}
  ]{Code/PriorityQueuePart1.java}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Java}
  \lstinputlisting[
    language=Java,
    basicstyle=\scriptesize,
    tabsize=4,
    style={java-eclipse-code},
    breaklines=false,
    escapechar={@},
    emph={q,i2,i3,i4},
    emphstyle=\color{java_variable}
  ]{Code/PriorityQueuePart2.java}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{cpp}{
\begin{frame}{Priority Queue}{C++}
  \lstinputlisting[
    language=C++,
    basicstyle=\small,
    tabsize=4,
    style={cpp-eclipse-code},
    breaklines=false,
    morekeywords={endl},
    escapechar={@}
  ]{Code/PriorityQueuePart1.cpp}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{C++}
  \vspace{-1.0em}
  \lstinputlisting[
    language=C++,
    basicstyle=\small,
    tabsize=4,
    style={cpp-eclipse-code},
    breaklines=false,
    morekeywords={endl},
    escapechar={@}
  ]{Code/PriorityQueuePart2.cpp}
\end{frame}
}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Application Example}
  \textbf{Example 1:}
  \begin{itemize}
    \item
      Calculation of the sorted union of $k$ sorted lists\\
      (multi-way merge or $k$-way merge)
  \end{itemize}
  \begin{figure}[!h]
    \begin{columns}
      \begin{column}[t]{0.5\linewidth}
        \begin{tabularx}{\linewidth}{c|X|X|X|X|X|}
          \cline{2-6}
          $L_1:$ & 3 & 5 & 8 & 12 & $\dots$\\
          \cline{2-6}
        \end{tabularx}
        \hfill\\[1.25em]
        \begin{tabularx}{\linewidth}{c|X|X|X|X|X|}
          \cline{2-6}
          $L_2:$ & 4 & 5 & 6 & 7 & $\dots$\\
          \cline{2-6}
        \end{tabularx}
      \end{column}
      \begin{column}[t]{0.5\linewidth}
        \begin{tabularx}{\linewidth}{c|X|X|X|X|X|}
          \cline{2-6}
          $L_3:$ & 1 & 10 & 11 & 24 & $\dots$\\
          \cline{2-6}
        \end{tabularx}
      \end{column}
    \end{columns}
    \hfill\\
    \onslide<2->
    $\underbrace{\hspace{\linewidth}}$\\[0.5em]
    \begin{tabularx}{\linewidth}{c|X|X|X|X|X|X|X|X|X|X|}
      \cline{2-11}
      $\Rightarrow R:$ & 1 & 3 & 4 & 5 & 5 & 6 & 7 & 8 & 10 & $\dots$\\
      \cline{2-11}
    \end{tabularx}
    \caption{3-way merge}
    \label{fig:priority_queue:three_way_merge}
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Application Example}
  \textbf{Example 1:}
  \begin{itemize}
    \item<2->
      Calculation of the sorted union of ${\color{Mittel-Blau}k}$ sorted lists\\
      (multi-way merge or ${\color{Mittel-Blau}k}$-way merge)
    \item<3->
      Runtime:
      ${\color{Mittel-Blau}N}$ = length of resulting list
      \begin{itemize}
        \item<4->
          Trivial:
          \begin{math}
            \Theta({\color{Mittel-Blau}N} \cdot {\color{Mittel-Blau}k})
          \end{math},
          minimum calculation $\Theta({\color{Mittel-Blau}k})$
        \item<5->
          Priority queue:
          \begin{math}
            \Theta({\color{Mittel-Blau}N} \cdot \log {\color{Mittel-Blau}k})
          \end{math},
          minimum calculation  $\Theta(\log {\color{Mittel-Blau}k})$
      \end{itemize}
  \end{itemize}
  \onslide<6->
  \textbf{Example 2:}
  \begin{itemize}
    \item<7->
      For example Dijkstra's algorithm for computing the shortest path (following lecture)
    \item<8->
      Among other applications it can be used for sorting
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Idea:}
  \begin{itemize}
    \item<2->
      Save elements as tuples in a binary heap
    \item<3->
      Summary from lecture 1 (\textit{HeapSort}):
    \begin{itemize}
      \item<3->
        Nearly complete binary tree
      \item<3->
        {\color{Mittel-Blau}Heap condition}:\\
        The key of each node ${\color{Mittel-Blau}\leq}$ the keys of the
        children\\
    \end{itemize}
  \end{itemize}
  \vspace{-0.5em}
  \onslide<2->
  \begin{figure}[!h]
    \begin{adjustbox}{height=0.3\linewidth}
      \input{Images/GenericHeap.tikz}%
    \end{adjustbox}
    \vspace{-0.75em}
    \caption{heap with 11 nodes}%
    \label{fig:priority_queue:impl_heap}%
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
 \onslide<1->
 \begin{figure}[!h]%
   \vspace{-1.5em}
   \begin{minipage}[b]{0.4\linewidth}%
     \input{Images/PriorityQueue/Heap.tikz}%
    \end{minipage}
    \hfill
    \begin{tabular}[b]{ccccc}
      {\color{Mittel-Gruen}0}&
      {\color{Mittel-Gruen}1}&
      {\color{Mittel-Gruen}2}&
      {\color{Mittel-Gruen}3}&
      {\color{Mittel-Gruen}4}\\
      \hline
      \multicolumn{1}{|c}{4, {\color{green2}B}}&%
      \multicolumn{1}{|c}{8, {\color{green2}M}}&%
      \multicolumn{1}{|c}{5, {\color{green2}A}}&%
      \multicolumn{1}{|c}{17, {\color{green2}Q}}&%
      \multicolumn{1}{|c|}{9, {\color{green2}H}}\\
      \hline
    \end{tabular}
    \vspace{-0.5em}
    \caption{min heap stored in array}%
    \label{fig:priority_queue:impl_min_heap}%
  \end{figure}%
 \vspace{-1.0em}
 \onslide<2->
  \textbf{Storing a binary heap:}
  \begin{itemize}
    \item<3->
      Number nodes from top to bottom and left to right starting with 0
      and store entries in array
    \item<3->
      Children of node ${\color{Mittel-Blau}i}$ are the nodes
      ${\color{Mittel-Blau}2\,i+1}$ and ${\color{Mittel-Blau}2\,i+2}$
    \item<3->
      Parent node of node ${\color{Mittel-Blau}i}$ is
      $\displaystyle {\color{Mittel-Blau}\mathrm{floor}((i-1)/2)}$
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Insertion}
  \textbf{Inserting an element:}
         {\color{Mittel-Blau}\texttt{insert(key, item)}}
           \begin{figure}[!h]
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap.tikz}%
    \end{adjustbox}
    \raisebox{3.0em}{
      \begin{math}
        \stackrel{
          \color{Mittel-Blau}\texttt{insert(1, {\color{green2}X})}
        }{\Rightarrow}
      \end{math}
    }\hspace{-1.5em}
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_Insert.tikz}%
    \end{adjustbox}
    %    \vspace{-0.5em}
    %    \caption{Inserting into the priority queue}%
    \label{fig:priority_queue:impl_insert}%
  \end{figure}%
  \begin{itemize}
    \item<2->
      Append the element at the end of the array
    \item<3->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      last index
    \item<4->
      Repair {\color{Mittel-Blau}heap condition}
      $\Rightarrow$ We will see later how to do this
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Returning the minimum:}
         {\color{Mittel-Blau}\texttt{getMin()}}
          \begin{figure}[!h]
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_Peek.tikz}%
    \end{adjustbox}
    \hspace{1.75em}\raisebox{3.0em}{
      $\stackrel{\color{Mittel-Blau}\texttt{getMin}}{\Rightarrow}$
      \hspace{1.75em}
      (4, {\color{green2}B})
    }
    \hfill
    %    \vspace{-0.5em}
    %    \caption{Returning the smallest element of the priotity queue}%
    \label{fig:priority_queue:impl_peek}%
  \end{figure}%
  \begin{itemize}
    \item<2->
      Else return the first element
    \item<3->
      If the heap is empty return {\color{Mittel-Blau}None}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Removing the minimum:}
         {\color{Mittel-Blau}\texttt{deleteMin()}}
           \begin{figure}[!h]
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_PrePop.tikz}%
    \end{adjustbox}
    \hspace{0.5em}\raisebox{3.0em}{
      $\stackrel{\color{Mittel-Blau}\texttt{deleteMin}}{\Rightarrow}$
    }\hspace{-1.5em}
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_PostPop.tikz}%
    \end{adjustbox}
    %    \vspace{-0.5em}
    %    \caption{Removing the smallest element of the priotity queue}%
    \label{fig:priority_queue:impl_pop}%
  \end{figure}%
   \begin{itemize}
    \item<2->
     Deleting the element with the lowest key
    \item<3->
      Swap the last element with the first element and shrink the heap by one
    \item<4->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      first index
    \item<5->
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Changing the key (priority):}
  {\color{Mittel-Blau}\texttt{changeKey(item, key)}}
  \begin{itemize}
    \item
      The element (queue item) is given as argument
    \item
      Replace the key of the element
    \item
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      element index and only in one direction (up / down)
    \item
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
    \begin{figure}[!h]
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PreChangeKey.tikz}%
      \end{adjustbox}
      \hspace{0.25em}\raisebox{3.0em}{
        $\stackrel{\color{Mittel-Blau}\texttt{changeKey}}{\Rightarrow}$
      }\hspace{-1.5em}
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PostChangeKey.tikz}%
      \end{adjustbox}
      %    \vspace{-0.5em}
      %    \caption{Changing the key of an element}%
      \label{fig:priority_queue:impl_change_key}%
    \end{figure}%
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Changing the key (priority):}
   {\color{Mittel-Blau}\texttt{changeKey(item, key)}}
     \begin{figure}[!h]
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PreChangeKey.tikz}%
      \end{adjustbox}
      \hspace{0.25em}\raisebox{3.0em}{
        $\stackrel{\color{Mittel-Blau}\texttt{changeKey}}{\Rightarrow}$
      }\hspace{-1.5em}
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PostChangeKey2.tikz}%
      \end{adjustbox}
      %    \vspace{-0.5em}
      %    \caption{Changing the key of an element}%
      \label{fig:priority_queue:impl_change_key2}%
    \end{figure}%
  \begin{itemize}
    \item<2->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      element index and only in one direction (up / down)
    \item<3->
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Removing an element:}
   {\color{Mittel-Blau}\texttt{remove(item)}}
     \begin{figure}[!h]
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PreRemove.tikz}%
      \end{adjustbox}
      \hspace{0.5em}\raisebox{3.0em}{
        $\stackrel{\color{Mittel-Blau}\texttt{remove}}{\Rightarrow}$
      }\hspace{-1.0em}
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PostRemove.tikz}%
      \end{adjustbox}
      %    \vspace{-0.5em}
      %    \caption{Removing a random element from the priotity queue}%
      \label{fig:priority_queue:impl_remove}%
    \end{figure}%
  \begin{itemize}
    \item<2->
      The element (queue item) is given as argument
    \item<3->
      Replace the element with the last element and shrink the heap by one
    \item<4->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      element index and only in one direction (up / down)
    \item<5->
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  \textbf{Repairing after modifying operations:}
  \begin{itemize}
    \item<2->
      The heap condition can be violated after using
      {\color{Mittel-Blau}\texttt{insert}},
      {\color{Mittel-Blau}\texttt{deleteMin}},
      {\color{Mittel-Blau}\texttt{changeKey}},
      {\color{Mittel-Blau}\texttt{remove}},
      but only at one known position with index ${\color{Mittel-Blau}i}$
    \item<3->
      Heap conditions can be violated in two directions:
      \begin{itemize}
        \item<4->
          Downwards:
          the key at index ${\color{Mittel-Blau}i}$ is not
          ${\color{Mittel-Blau}\leq}$ than the value of its children
        \item<5->
          Upwards:
          the key at index ${\color{Mittel-Blau}i}$ is not
          ${\color{Mittel-Blau}\geq}$ than the value of its parent
      \end{itemize}
    \item<6->
      We need two repair methods:
      {\color{Mittel-Blau}\texttt{repairHeapUp}},
      {\color{Mittel-Blau}\texttt{repairHeapDown}}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapDown:}}}
  \begin{itemize}
    \item<2->
      {\color{Mittel-Blau}Sift} the element until the
      {\color{Mittel-Blau}heap condition} is valid
      \begin{itemize}
        \item<3->
          Change node with child, which has the lower key of both children
        \item<4->
          If the {\color{Mittel-Blau}heap condition} is violated repeat for
          the child node
      \end{itemize}
  \end{itemize}
   \begin{figure}[!h]%
    \begin{columns}%
      \begin{column}{0.45\linewidth}%
        \begin{adjustbox}{width=\linewidth}%
          \input{Images/PriorityQueue/HeapRepairDown_First.tikz}%
        \end{adjustbox}%
      \end{column}%
      \begin{column}{0.45\linewidth}%
        \begin{adjustbox}{width=\linewidth}%
          \input{Images/PriorityQueue/HeapRepairDown_Second.tikz}%
        \end{adjustbox}%
      \end{column}%
    \end{columns}%
    \caption{repairing the heap downwards}%
    \label{fig:priority_queue:impl_repair_heap_down}%
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapDown:}}}
  \begin{itemize}
    \item
      {\color{Mittel-Blau}Sift} the element until the
      {\color{Mittel-Blau}heap condition} is valid
      \begin{itemize}
        \item
          Change node with child, which has the lower key of both children
        \item
          If the {\color{Mittel-Blau}heap condition} is violated repeat for
          the child node
      \end{itemize}
  \end{itemize}
  \begin{center}
    \begin{figure}[!h]%
      \begin{columns}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
              \input{Images/PriorityQueue/HeapRepairDown_Second.tikz}%
          \end{adjustbox}%
        \end{column}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairDown_Third.tikz}%
          \end{adjustbox}%
        \end{column}%
      \end{columns}%
      \caption{repairing the heap downwards}%
      \label{fig:priority_queue:impl_repair_heap_down2}%
    \end{figure}
  \end{center}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapUp:}}}
  \begin{itemize}
    \item<2->
      Change node with parent
    \item<3->
      If the {\color{Mittel-Blau}heap condition} is violated repeat for parent
      node
  \end{itemize}
  \begin{center}
    \begin{figure}[!h]%
      \begin{columns}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_First.tikz}%
          \end{adjustbox}%
        \end{column}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_Second.tikz}%
          \end{adjustbox}%
        \end{column}%
      \end{columns}%
      \caption{repairing the heap upwards}%
      \label{fig:priority_queue:impl_repair_heap_up}%
    \end{figure}
  \end{center}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapUp:}}}
  \begin{itemize}
    \item
      Change node with parent
    \item
      If the {\color{Mittel-Blau}heap condition} is violated repeat for parent
      node
  \end{itemize}
  \begin{center}
    \begin{figure}[!h]%
      \begin{columns}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_Second.tikz}%
          \end{adjustbox}%
        \end{column}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_Third.tikz}%
          \end{adjustbox}%
        \end{column}%
      \end{columns}%
      \caption{repairing the heap upwards}%
      \label{fig:priority_queue:impl_repair_heap_up2}%
    \end{figure}
  \end{center}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Priority Queue Item}
  \textbf{Index of a priority queue item:}
  \begin{itemize}
    \item<2->
      {\color{red}Attention:}
      for {\color{Mittel-Blau}\texttt{changeKey}} and
      {\color{Mittel-Blau}\texttt{remove}} the item has to \enquote{know} where
      it is located in the heap
    \item<3->
      Remember for {\color{Mittel-Blau}\texttt{repairHeapUp}} and
      {\color{Mittel-Blau}\texttt{repairHeapDown}}:\\
      update the index if moving an heap element
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\codeslide{python}{
\begin{frame}{Priority Queue}{Implementation - Priority Queue Item - Python}
  \lstinputlisting[
    language=Python,
    basicstyle=\scriptesize,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={PriorityQueueItem, __init__},
    emphstyle=\color{blue}
  ]{Code/PriorityQueueItem.py}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{java}{
\begin{frame}{Priority Queue}{Implementation - Priority Queue Item - Java}
  \lstinputlisting[
    language=Java,
    basicstyle=\scriptesize,
    tabsize=4,
    style={java-eclipse-code},
    breaklines=false,
    mathescape=true,
    emph={key, value, heapIndex},
    emphstyle=\color{java_static}
  ]{Code/PriorityQueueItem.java}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{cpp}{
\begin{frame}{Priority Queue}{Implementation - Priority Queue Item - C++}
  \lstinputlisting[
    language=C++,
    basicstyle=\small,
    tabsize=4,
    style={cpp-eclipse-code},
    breaklines=false,
    morekeywords={endl},
    escapechar={@}
  ]{Code/PriorityQueueItem.cpp}
\end{frame}
}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Complexity}
  \textbf{Summary lecture 1:}
  \begin{itemize}
    \item<2->
      A full binary tree with {\color{Mittel-Blau}$n$} elements has a {\color{Mittel-Blau}depth} of
      {\color{Mittel-Blau}$O(\log n)$}
    \item<3->
      The maximum distance from the root to a leaf can be
      $O(\log n)$ elements
    \item<4->
      Repairing the heap upwards and downwards:\\
      We have only one path to traverse: {\color{Mittel-Blau}$O(\log n)$}
  \end{itemize}
  \onslide<5->
  \textbf{Runtime for methods}
  \begin{itemize}
    \item<6->
      {\color{Mittel-Blau}\texttt{insert}},
      {\color{Mittel-Blau}\texttt{deleteMin}},
      {\color{Mittel-Blau}\texttt{changeKey}},
      {\color{Mittel-Blau}\texttt{remove}}:\\
      we have to repair the heap: {\color{Mittel-Blau}$O(\log n)$}
    \item<7->
      {\color{Mittel-Blau}\texttt{getMin}}:
      return the element at index 0: {\color{Mittel-Blau}$O(1)$}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Complexity}
  \textbf{Improvements (Fibonacci heaps):}
  \begin{itemize}
    \item<2->
      {\color{Mittel-Blau}\texttt{getMin}},
      {\color{Mittel-Blau}\texttt{insert}} and
      {\color{Mittel-Blau}\texttt{decreaseKey}}
      in amortized time of {\color{Mittel-Blau}$O(1)$}
    \item<3->
      {\color{Mittel-Blau}\texttt{deleteMin}}
      in amortized time {\color{Mittel-Blau}$O(\log n)$}
  \end{itemize}
  \hfill\\[0.5em]
  \onslide<4->
  \textbf{Practical experience:}
  \begin{itemize}
    \item<5->
      The binary heap is simpler: costs for managing the structure are low
    \item<6->
      The difference is negligible if the number of elements is relatively small
    \item<7->
      Example:
    \begin{itemize}
      \item
        For ${\color{Mittel-Blau}n = 2^{10}} \approx 1,000$, the
        {\color{Mittel-Blau}depth}
        $\log_2 n$ is only 10
      \item
        For ${\color{Mittel-Blau}n = 2^{20}} \approx 1,000,000$, the
        {\color{Mittel-Blau}depth}
        $\log_2 n$ is only 20
    \end{itemize}
  \end{itemize}
\end{frame}

max_stars_repo_name: TobiOnline/AlgoDat

max_issues_repo_name: TobiOnline/AlgoDat

max_forks_repo_name: TobiOnline/AlgoDat


text:
% This is a LaTeX tutorial by Overleaf titled [Free online introduction to LaTeX (part 3)](https://www.overleaf.com/learn/latex/Free_online_introduction_to_LaTeX_(part_3)).

\documentclass{beamer}
\usepackage{graphicx}

%\usetheme{Darmstadt}
%\usecolortheme{beetle}

\title{This is my slide!!!}
\author{Tran Phong Binh}
\institute{National Tsing Hua University}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

\begin{frame}
    \frametitle{Table of Contents}
    \tableofcontents
\end{frame}

\section{First section}
\begin{frame}
    \frametitle{This is the first slide of the first section baby!}
    \begin{itemize}
        \item Use \texttt{frametitle} to give the frame a title.
        \item Then add content to the frame.
        \item The source for this frame looks like \ldots
    \end{itemize}
\end{frame}

\section{Second section}
\begin{frame}
    \frametitle{First slide of the second section!!}
    \tableofcontents[currentsection]
\end{frame}

\begin{frame}
    \frametitle{Use of \texttt{column}s mate!!}
    \begin{columns}
        \begin{column}{0.4\textwidth}
            \begin{itemize}
                \item I should \emph{emphasize} that this is an \alert{important} point.
                \item The argument \ldots
                \item See also the \ldots
            \end{itemize}
        \end{column}
        \begin{column}{0.6\textwidth} % 20210614 0.4 + 0.6 = 1? any other possibilities?
        Second column's content here bitch.
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}
    \frametitle{Add some sexy pictures baby.}
    \begin{figure}
        \includegraphics[width=0.5\textwidth]{potato}
    \end{figure}
\end{frame}

\begin{frame}
    \frametitle{Wanna add tables?}
    \begin{table}
        \begin{tabular}{ |l|r|r| }
            \hline
            Item & Qty & Unit \$ \\
            \hline
            Widget & 1 & 199.99 \\
            Gadget & 2 & 399.99 \\
            Cable & 3 & 19.99 \\
            \hline
        \end{tabular}
        \caption{An ordinary table.}
    \end{table}
\end{frame}

\begin{frame}
    \frametitle{Use of \texttt{block}s bae.}
    \begin{block}{Interesting Fact}
    This is important.
    \end{block}
    \begin{alertblock}{Caution}
    This is really important!
    \end{alertblock}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item Can you feel the
        \pause \item anticipation?
    \end{itemize}
\end{frame}

\end{document}

max_stars_repo_name: phogbinh/latex

max_issues_repo_name: phogbinh/latex

max_forks_repo_name: phogbinh/latex