text:
# Project 5: Integrals

## Instructions

Use Winplot, Google Docs, and possibly Microsoft Excel/Google Spreadsheets to create a document with two problems on it.

## Problem 1 - Approximating Areas

Consider the function $$y = 0.1 x^3 - \cos(x^2) - 0.5x + 2$$ on $$[-2,3]$$.

Use Winplot to create a graph of the curve on the interval. Include the graph in the document.

Use Winplot to complete this table.

Method 2 5 10 100 1000
Left endpoint
Midpoint
Right endpoint
Trapezoidal
Parabolic
Random

## Problem 2 - Web Pages

The instructor has a school website that receives thousands of hits each day. The hits column represents the number of hits (in thousands of hits per day) for that day.

 Date Hits Nov 1 Nov 5 Nov 8 Nov 17 Nov 18 Nov 21 Nov 30 43.398 71.863 43.841 60.835 77.347 70.385 36.982

Use the information to estimate the number of hits during the month of November 2013 using the five approaches given in the table. You may want to use a spreadsheet to speed up the calculations, although the data points are limited enough that you could do it by hand.

Method Estimate Relative Error
Left endpoints
Right endpoints
Trapezoids
Minimums
Maximums

The total count for the month was 1714.325 thousand hits (1.714 million). The relative error is usually given as a percent. You take the estimate minus the actual value and then divide by the actual value. Finally, convert that into a percent.

## Additional Notes

• Add your names at the top of the document under the title.
• To submit the assignment, click the Share button in Google Docs and change it so that anyone with the link can view the results. Then copy the share link and email it to the instructor at james@richland.edu with an appropriate subject and the names of the people in the group. Only one person per group needs to submit the project.

## Winplot Tips

### Equa Menu

• Use implicit to graph an implicit equation. Sometimes, implicit graphs have a problem displaying if you change the zoom or arrow around to change the viewing. A workaround is to edit the graph in the inventory and then change the color.
• The inventory has a derive button that will graph the derivative of the selected function. The graph button will show or hide a graph, so a good way to make matching graphs is to sketch the function and derivative to make sure both are going to fit reasonably well on in the viewing window and then show one while hiding the other when you copy and paste the graph.

### One Menu

• Use Measurement / Integrate to determine the areas. After setting it up, click on Definite to obtain the estimates.

format: plain


text:
## Calculus (3rd Edition)

(a) $1.0508$ (b) $1.0513$
Since $$r=0.05$$ (a) The rate is compounded three times ($M=3$), continuously, so we have \begin{aligned} P(t)&=P_{0}\left(1+\frac{r}{M}\right)^{M t}\\ &= \left(1+\frac{0.05}{3}\right)^{3} \\ &\approx 1.0508 \end{aligned} (b) The rate is compounded continuously, so \begin{aligned} P&=P_{0} e^{r t} \end{aligned} Thus, the yearly multiplier is: $$e^{r}=e^{0.05} \approx 1.0513$$


text:
## Textbooks & Solution Manuals

Find the Source, Textbook, Solution Manual that you are looking for in 1 click.

## Tip our Team

Our Website is free to use.
To help us grow, you can support our team with a Small Tip.

## Holooly Tables

All the data tables that you may search for.

## Holooly Help Desk

Need Help? We got you covered.

## Holooly Arabia

For Arabic Users, find a teacher/tutor in your City or country in the Middle East.

Products

## Textbooks & Solution Manuals

Find the Source, Textbook, Solution Manual that you are looking for in 1 click.

## Holooly Arabia

For Arabic Users, find a teacher/tutor in your City or country in the Middle East.

## Holooly Help Desk

Need Help? We got you covered.

## Q. 14.6.3

(Cambridge University Engineering Tripos: Preliminary Examination for Part I (1975).) Figs. 14.6-7(a) and (b) show respectively the dimensions of a propped uniform cantilever and its cross-section.
(a)  Determine the plastic moment of resistance of the beam section if the yield stress of the material is 250 N/mm2 in tension and in compression.
(b)  If the load W may be applied at any position within the span, determine the minimum value of W that will cause collapse.
(c)  If the load W is removed just after the formation of the collapse plastic hinges, sketch the shapes of the bending moment and shear force diagrams after the removal of the load.

## Verified Solution

(a)The neutral axis divides the cross section into two parts of equal area as in Fig. 14.6-8(a)

$\qquad \begin{matrix}\text{ Therefore }: \ \text{Lever arm } \ & =(10+5)/2=7.5 \ mm \\ \text{Plastic moment } \ M_{p} & =10\times 10\times 250\times 7.5 \\ \quad & = \underline{0.188\ kN\ m } \\ \end{matrix}$

(b) Consider the mechanism in Fig. 14.6-8(b), where the position of the plastic hinge B is defined by the variable x.
The work equation is

$\qquad W(xL\phi )=M_{p} \left( \frac{\phi }{1-x} +\frac{x\phi }{1-x} \right)$

or

$\qquad W = \frac{1+x}{x(1-x)}\frac{M_{p}}{L}$

We do not know the value of x, but we do know that the required value of x is such as to make W a minimum.

$\hspace{5em} \frac{dW}{dx}=0\ gives\ x^{2}+2x-1=0$

Therefore   x = 0.414

and            W=730 N

(c) In the absence of external applied load, the beam is acted on by support reactions only (see Fig. 14.6-8(c)).

Suppose the (unknown) support reactions are M and R. The only possible
shape of the bending moment diagram is a triangle (Fig. 14.6-8(d)); the only possible shape of the shear force diagram is a rectangle (Fig. 14.6-8(e)).


text:
## The Annals of Probability

### Some Remarks About the Convolution of Unimodal Functions

Bela Uhrin

#### Abstract

In the note a new class of functions called $\alpha$-quasi-concave is introduced and it is proved that the convolution of two unimodal functions each having some additional concavity properties belongs to this class. Other results concerning the convolution of unimodal functions are also studied and the extensions of some of them are also given in the paper.

#### Article information

Source
Ann. Probab., Volume 12, Number 2 (1984), 640-645.

Dates
First available in Project Euclid: 19 April 2007

Permanent link to this document
https://projecteuclid.org/euclid.aop/1176993312

Digital Object Identifier
doi:10.1214/aop/1176993312

Mathematical Reviews number (MathSciNet)
MR735860

Zentralblatt MATH identifier
0554.60028

JSTOR


text:
# How to tune an FM transmitter to a specific frequency?

I am planning to organise a simple fox hunt, a family event. This includes building a transmitter. I am currently considering the following schematics:

Both target the 88-110 MHZ band, but that range of frequencies requires licensing. I live in Ireland and according to the local rules the following bands seem to be available:

• 26.957 – 27.283 MHz (no further requirements)
• 40.660 – 40.700 MHz (no further requirements)
• 49.82 – 49.98 MHz, 10 mW ERP, no other requirements
• 169.4 - 169.475 MHz, 500 mW ERP, Duty cycle < 10% Max 50 kHz channel spacing
• 433.050 – 434.790 MHz, 10 mW ERP, Duty Cycle ≤ 10 %

This is how I understand the document https://www.comreg.ie/media/dlm_uploads/2015/12/ComReg0271R9.pdf

Now, from the list above 169 MHz range seems to be the closest to 110 MHz. My plan is to first build the transmitter within the 88-110 MHz range, verify using common radio receiver that it works and then tune up to 169 MHz.

I assume that if I play with the coil inductor (add or remove turns) and/or capacitor the shift from 110 to 169 MHZ will be possible. I found a surprisingly affordable frequency counter on Amazon and hope it will help me to validate the frequency (so that I do not skip to 200 MHz). https://www.amazon.co.uk/gp/product/B01B3ZCP3U/

Would that work? Is this how tuning is normally done?

EDIT: The desired communication distance is up to 100-200 meters from the fox box in a park (within line of sight).

• If you have a few Euros to spare, you can get a comercial FM band transmitter. The ones with 50 nW EIRP are license-free in Europe and this might be enough for a foxhunt. They're cheaper than making on on your own and have a battery included. – AndrejaKo Mar 7 '18 at 9:30
• @AndrejaKo well, on the other hand, 50 nW + Free Space Path Loss with a path coefficient that incorporates Irish weather (i.e. spherical accumulations of water in the air in a steady downwards movement) means you'd need pretty low-noise receivers pretty soon, unless that fox hunt is very locally limited. What about simply getting a SRD handset? – Marcus Müller Mar 7 '18 at 9:35

I will assume you will get the legal issues sorted so I will address the circuit itself.

If you look at the second circuit you referenced, you will find L1 and VC1 in parallel. These form a tuned circuit that sets the output frequency of the transmitter (ignore the polarity symbol on VC1, it is a remnant of the circuit editor on this site):

simulate this circuit – Schematic created using CircuitLab

The formula for the resonant frequency of this circuit is:

$$Frequency=\frac{1}{2\pi\sqrt{LC}} \tag 1$$

where Frequency is in Hertz, L is the inductance in Henries and C is the capacitance in Farads.

In your case you may find it helpful to solve equation 1 for LC:

$$LC=\left(\frac{1}{Frequency*2\pi}\right)^2 \tag 2$$

where resonance is achieved by any combination of inductance and capacitance where their product equals the right side of equation 2.

So with L1 = 0.1 $\mu$H, VC1 would need to be set to about 26 pF to hit the middle of the FM band (98 MHz).

If you wish to adjust the output frequency to ~170 MHz, VC1 would need to be set to approximately 9 pF according to equation 1. But the recommended capacitor for VC1 probably will not go that low so select a different variable capacitor that can be adjusted to this value; or place a 10 pF capacitor in series with VC1; or use a 10 pF fixed capacitor instead of VC1 and simply stretch or compress the windings of L1 a bit to adjust the frequency. Your frequency counter will make this a straight forward process.

As the capacitor value gets quite small, the circuit may not behave as expected due to stray capacitance. You can overcome this by reducing the inductance value. For example, 4 turns of wire wound on a 0.25 inch form and spaced out to make a coil that is about 0.5 inches long will form an inductance of ~0.04 $\mu$H. A 22 pF capacitor in parallel with this will get you into the 170 MHz range.

The circuit will be sensitive to the presence of your hand or any metal tools. You can make the inductor adjustment with a small wooden stick to avoid this problem. A stiff piece of plastic (e.g from a plastic milk jug) can serve as a poor man's adjustment tool for the variable capacitor.

• Also: 9pF is really little, even compared to capacitances of PCB traces. You won't be able to reliably make this work on a breadboard thingie! – Marcus Müller Mar 7 '18 at 15:33
• @MarcusMüller I edited my answer to address your concern. – Glenn W9IQ Mar 7 '18 at 18:37

not quite sure what to say about "how is it normally done":

"how it can be done" depends on the transmitter architecture you're using, and any non-my-first-diy-fm-transmitter will be a bit more complex in the way they generate the RF oscillation :)

However, the principle for many of these will be the same: you change an energy-storing element (either a capacitor or an inductor (coil)); you measure what that does to your operating frequency, and with that info calibrate the frequency scale on your device.

Regarding legality:

Can't really comment qualifiedly, have measured none of these circuits, but "1 General Information" demands

All radio and telecommunications terminal equipment must comply with the essential requirements and other relevant provisions of the R&TTE Directive before being placed on the market or put into service in Ireland.

That requires suppression of out-of-band spurs as well as sufficient stability to be sure that your transmitter doesn't drift away from the frequencies it's allowed on. The latter might be a real problem: Your circuit is pretty temperature-dependent and will generally tend to drift (which is why real-world transmitters typically a bit more complex). However, nothing says it's impossible to make, by carefully trimming, and pampering your circuit, to make it stable enough.

Whether your location application or your transmit power is legal in your band: I honestly have no idea, and would have to read that document in full. You also have zero means to measure emitted power, raising completely different questions regarding legality than frequency!

Regarding band selection:

I think table 1 is pretty clear here, the band between 169 and 173 MHz can only be used with very low duty cycles, your transmitter must be off for 99% of time. I doubt this is optimal for fox hunting, unless you have extensively clever receiver design (as in, a computer-aided TDMA system. Not happening.). So, 169 MHz is right out.

Your best bet is the 173.2375 – 173.275 MHz band, where no duty cycle restrictions apply. However, that band is only 37.5 kHz wide. This means your transmitter needs to be pretty frequency-exact. I predict that this will be a major obstacle when employing such simple, uncompensated circuits – any temperature, supply voltage, antenna condition change (rain, potentially wind, close large objects moving) will influence the operation frequency.

So, if you really want to build a transmitter yourself instead of eg. buying a cheap SRD handset that you can program to that frequency you should probably stay away from instructables.com, and the other websites you're using, and would need to aim for more advanced circuits.

Personally, I'm a computer person (in fact, I'm a Software Defined Radio person, where we control such parameters in software). I'd frankly directly go for something that a manufacturer has calibrated and with which I can talk to digitally and simply tell it what frequency to synthesize. Now, that would require a relatively large engineering effort for you to build – cannot recommend. Annoyingly, most cheaply available programmable oscillators end at 150, 165 or 170 MHz. Just below what you need...

• Thanks! I will look into buying a ready-made transmitter indeed. Regarding power and harmonics: would the proposed designs be that strong to cause problems? I thought the signal would die off at, let's say, 300 meters and therefore nobody will be offended if the transmission is already within a shared-use band. – Alexander Churanov Mar 7 '18 at 12:00
• About R&TTE, it's now in final stages of being replaced with RED. RED has some exceptions, if a small number of devices will be produced, as far as testing is concerned. – AndrejaKo Mar 7 '18 at 12:28

Let me chime in, as I am in Ireland, and have at least some knowledge of the regulations. However I can see at other answers have already addressed this, so I am not going to repeat this.

Let me give you a solution for your family-day-fox-hunt

• 100 mW EIRP TX
• legal
• cheap
• unlimited FREE RX devices for your family memembers

If it is just for the family fun day (and lets forget about the fun building electronic circuits) you can do the following:

• get a cheap/old Wifi router
• most of them run on 9V or 12V, so you can run it on a battery of some sort
• some you can turn down the power output if you want to make it challenging
• get mobile phones and install a "Wifi tracking or finder app"
• configure the Wifi router with a recognizable SSID
• hide the Wifi router where you have your family day.
• try to find it with phones....

Lots of fun, everyone has a phone, so you have not only solved the TX problem, you have given everyone a method of RX, for all ages !

Building transmitters if fun, and this is probably something where you could say: "we have all done it". The frequency which is most versatile to experiment with is 87-108 MHz, which is the FM broadcast band. You will need to experiment with filtering and the like. And with a max ERP of 50 nW there is not much of a range.

You do have to start somewhere when you want to do this, but it will be a while before you can build a transmitter with larger power output, which can be used for your intended family day. (as other answers have already covered this)

[EDIT after reading some more documents about the legality]

I was surprised about the frequency ranges mentioned, hence my edit here.

It seems to me that most of the frequencies you are listing have a very specific license exemption, e.g. cordless phones, baby monitors, radar-to-wall, and other applications.

I would strongly advice to stay away from those "seems to be good to use" frequencies. These frequencies are NOT for "Private Mobile Radio" (PMR for short). The license exempt allocations for PMR are:

• 434.04 – 434.79 MHz (10 mW)
• 446.00 - 446.10 MHz (500 mW) channelized
• 446.10 - 446.20 MHz (500 mW) channelized digital only

However for those license exempt frequencies there are actually type-approval requirements in the appropriate legistlation.

The relevant documents can be found on Electronic Irish Statute Book:

• S.I. 93 of 1998
• S.I. 405 of 2005
• S.I. 160 of 2006

Clearly stipulating that the equipment used for those need to be "type approved", and will bring a extensive list of requirements for such approval.

Furthermore, Document 06/47R stipulates the following:

All radio and telecommunications terminal equipment must comply with the essential requirements and other relevant provisions of the R&TTE Directive before being placed on the market or put into service in Ireland.

Which was already mentioned in another answer, this will bring requirements in regards to spurious emissions and harmonics.

Under Irish legislation (The Wireless Telegraphy Acts 1926 - 1988), all apparatus for Wireless Telegraphy requires a licence unless that apparatus has been specifically exempted from licensing under Irish legislation by means of an Exemption Order.

Which comes down to "you may not own a tranmitter, unless licensed, or unless license exempt" And we already know that the license exempt equipment need to be type approved.

So your options are getting narrower once you start reading the detail of the legislation.

The PMR devices (properly type approved and license exempt) are widely available in many stores around Ireland. They are called PMR446 devices, and sold as "walkie-talkie". These will have a 500 mW output and can be loads of fun. Some of them have microphone inputs where you can feed it with a signal of some sort.

Conclusion

For a "family day of fun in the park" and therefore in a public place, I would higly recommend you stick to type-approved equipment, or the Wifi I mentioned before.

Personal Opinion

Don't let this stop you from experimenting, there are some good answers here which can get you going in building simple transmitting circuits. Just don't expect to build anything with large power output and be sure you are able to measure and adjust/filter spurious emissions and harmonics... this will be a learning journey.

I believe that many experimenters do so in the 87-108 MHz FM broadcast band, and keep the power output under 50 nW. This I mention above as well. Technically speaking this license exemption for Short Range Devices, also need type approval, and also a CE mark certification. But I could not find any other frequency allocation for such experimentation.

I am not even sure if there is an allocation you could "officially" use for experimentation.

Did I built transmitters in that frequency range?

Yes I did, learned a lot, had some fun. But never with large power, and never used them for "public" functions/family-days-in-the-park.

• Thank you so much for suggesting the idea! A report on how it went: purchased 4 routers (€2 each) and battery boxes to produce 12 volts (€3-7 each). Built 2 Faraday Cage boxes out of food packaging cardboard and cooking foil, left 1 side open. Used the WiFi Sonar app, direction was detected by the sound (higher pitch — more power) after rotating the box few times. The game was fun! Downsides: routers ran out of power within few minutes during test. Purchased most expensive Energiser batteries (36 AA = €48), lasted for few more minutes (10-20 minutes total play time). – Alexander Churanov Apr 23 '18 at 15:01
• I am glad you had a good day with some fun radio games ! – Edwin van Mierlo Apr 24 '18 at 10:55

As buying everything pre-made would take away the fun of building something yourself, I'd propose to look into kits which you can at least assemble yourself. The transmitter is the one on which legal restrictions apply, so that one might be a good candidate for getting it pre-made, or in kit form. If you want help, get in touch with a local ham radio club. Your mileage may vary, but quite certainly there's someone very eager to help you out if you want to make frequency and/or power measurements. Just sent them an email and ask, you might be surprised. Helping others (or elmering) is supposed to be highly valued among hams (as is building things yourself). Or maybe someone has an ardf transmitter that you can lend, and build your own receiver for.


text:
# Properties

 Label 420.2.l.c Level $420$ Weight $2$ Character orbit 420.l Analytic conductor $3.354$ Analytic rank $0$ Dimension $8$ CM no Inner twists $2$

# Related objects

## Newspace parameters

 Level: $$N$$ $$=$$ $$420 = 2^{2} \cdot 3 \cdot 5 \cdot 7$$ Weight: $$k$$ $$=$$ $$2$$ Character orbit: $$[\chi]$$ $$=$$ 420.l (of order $$2$$, degree $$1$$, minimal)

## Newform invariants

 Self dual: no Analytic conductor: $$3.35371688489$$ Analytic rank: $$0$$ Dimension: $$8$$ Coefficient field: 8.0.386672896.3 Defining polynomial: $$x^{8} - x^{6} - 2 x^{5} + 2 x^{4} - 4 x^{3} - 4 x^{2} + 16$$ Coefficient ring: $$\Z[a_1, a_2, a_3]$$ Coefficient ring index: $$2^{2}$$ Twist minimal: yes Sato-Tate group: $\mathrm{SU}(2)[C_{2}]$

## $q$-expansion

Coefficients of the $$q$$-expansion are expressed in terms of a basis $$1,\beta_1,\ldots,\beta_{7}$$ for the coefficient ring described below. We also show the integral $$q$$-expansion of the trace form.

 $$f(q)$$ $$=$$ $$q -\beta_{3} q^{2} + \beta_{2} q^{3} + ( 1 - \beta_{4} - \beta_{6} ) q^{4} + ( -1 + \beta_{1} + \beta_{3} + \beta_{4} + \beta_{7} ) q^{5} + ( 1 + \beta_{1} + \beta_{5} ) q^{6} - q^{7} + ( 1 - \beta_{1} + \beta_{2} - \beta_{3} + \beta_{5} - \beta_{7} ) q^{8} + ( \beta_{1} - \beta_{3} + \beta_{4} + \beta_{6} + \beta_{7} ) q^{9} +O(q^{10})$$ $$q -\beta_{3} q^{2} + \beta_{2} q^{3} + ( 1 - \beta_{4} - \beta_{6} ) q^{4} + ( -1 + \beta_{1} + \beta_{3} + \beta_{4} + \beta_{7} ) q^{5} + ( 1 + \beta_{1} + \beta_{5} ) q^{6} - q^{7} + ( 1 - \beta_{1} + \beta_{2} - \beta_{3} + \beta_{5} - \beta_{7} ) q^{8} + ( \beta_{1} - \beta_{3} + \beta_{4} + \beta_{6} + \beta_{7} ) q^{9} + ( \beta_{1} + \beta_{2} + 2 \beta_{3} + \beta_{4} - \beta_{5} + \beta_{6} + \beta_{7} ) q^{10} + ( -\beta_{2} + \beta_{6} ) q^{11} + ( 1 + \beta_{1} + \beta_{2} + \beta_{3} + 2 \beta_{4} - \beta_{5} + \beta_{7} ) q^{12} + ( 2 \beta_{1} - \beta_{2} + 2 \beta_{3} - \beta_{6} ) q^{13} + \beta_{3} q^{14} + ( 2 - \beta_{1} - \beta_{2} + \beta_{3} - \beta_{4} + \beta_{7} ) q^{15} + ( -1 + 2 \beta_{1} + \beta_{4} - \beta_{6} ) q^{16} + ( 2 \beta_{1} - \beta_{2} - 2 \beta_{3} + \beta_{6} ) q^{17} + ( 2 + \beta_{1} + \beta_{3} - \beta_{4} - \beta_{5} - \beta_{6} + 2 \beta_{7} ) q^{18} + ( -2 \beta_{4} - 2 \beta_{7} ) q^{19} + ( 1 + \beta_{1} - \beta_{2} - \beta_{3} + \beta_{5} + 2 \beta_{6} + \beta_{7} ) q^{20} -\beta_{2} q^{21} + ( -1 - \beta_{1} - \beta_{2} - \beta_{5} + \beta_{7} ) q^{22} + ( -2 \beta_{2} - 2 \beta_{4} - 2 \beta_{6} - 2 \beta_{7} ) q^{23} + ( 1 + 2 \beta_{1} - 2 \beta_{3} - \beta_{4} + \beta_{6} ) q^{24} + ( -3 - 2 \beta_{1} - 2 \beta_{3} - 2 \beta_{4} - 2 \beta_{7} ) q^{25} + ( 1 - \beta_{1} + \beta_{2} + 2 \beta_{4} - \beta_{5} + 2 \beta_{6} - \beta_{7} ) q^{26} + ( 1 + \beta_{1} + \beta_{3} - \beta_{4} + 2 \beta_{5} + \beta_{7} ) q^{27} + ( -1 + \beta_{4} + \beta_{6} ) q^{28} + ( 2 \beta_{1} - \beta_{2} + 2 \beta_{3} - \beta_{6} ) q^{29} + ( -3 - 2 \beta_{1} + \beta_{2} - \beta_{3} + \beta_{4} + \beta_{6} + \beta_{7} ) q^{30} + ( 4 \beta_{1} + 2 \beta_{2} + 4 \beta_{3} + 2 \beta_{4} + 2 \beta_{6} + 2 \beta_{7} ) q^{31} + ( 3 + \beta_{1} + \beta_{2} + \beta_{3} - \beta_{5} - \beta_{7} ) q^{32} + ( -3 - \beta_{1} + \beta_{3} - \beta_{4} - \beta_{6} - \beta_{7} ) q^{33} + ( 5 - \beta_{1} - \beta_{2} - 2 \beta_{4} - \beta_{5} - 2 \beta_{6} + \beta_{7} ) q^{34} + ( 1 - \beta_{1} - \beta_{3} - \beta_{4} - \beta_{7} ) q^{35} + ( 3 - 2 \beta_{1} + 2 \beta_{2} - 2 \beta_{3} - \beta_{4} + 2 \beta_{5} + \beta_{6} ) q^{36} + ( -2 - 2 \beta_{1} - 2 \beta_{3} - 4 \beta_{7} ) q^{37} + ( 2 - 2 \beta_{1} - 2 \beta_{2} - 2 \beta_{3} + 2 \beta_{5} - 2 \beta_{7} ) q^{38} + ( 3 - 3 \beta_{1} + \beta_{3} - \beta_{4} - 2 \beta_{5} - 3 \beta_{6} + \beta_{7} ) q^{39} + ( 1 + 2 \beta_{3} + \beta_{4} - 2 \beta_{5} - \beta_{6} + 4 \beta_{7} ) q^{40} + ( 2 - 2 \beta_{4} + 2 \beta_{7} ) q^{41} + ( -1 - \beta_{1} - \beta_{5} ) q^{42} + ( 2 - 2 \beta_{1} + 2 \beta_{2} + 2 \beta_{3} - 2 \beta_{6} ) q^{43} + ( -2 - 2 \beta_{1} - 2 \beta_{4} ) q^{44} + ( -4 + 2 \beta_{2} + 4 \beta_{3} + 2 \beta_{4} - 2 \beta_{5} + \beta_{6} ) q^{45} + ( -4 \beta_{1} - 2 \beta_{3} - 4 \beta_{7} ) q^{46} + ( -\beta_{2} - \beta_{6} ) q^{47} + ( 7 - \beta_{1} - \beta_{2} - \beta_{3} - 2 \beta_{4} + \beta_{5} - 2 \beta_{6} + \beta_{7} ) q^{48} + q^{49} + ( -2 \beta_{1} - 2 \beta_{2} + \beta_{3} - 2 \beta_{4} + 2 \beta_{5} - 2 \beta_{6} - 2 \beta_{7} ) q^{50} + ( 1 + \beta_{1} + \beta_{3} - \beta_{4} + 2 \beta_{5} - 3 \beta_{6} + \beta_{7} ) q^{51} + ( -2 + 2 \beta_{1} - 4 \beta_{2} - 4 \beta_{3} - 2 \beta_{4} ) q^{52} + ( -2 - 4 \beta_{2} + 4 \beta_{6} ) q^{53} + ( \beta_{1} + 3 \beta_{2} + 4 \beta_{3} + 5 \beta_{4} - \beta_{5} + \beta_{6} + 3 \beta_{7} ) q^{54} + ( -2 + \beta_{2} + 2 \beta_{4} - \beta_{6} - 2 \beta_{7} ) q^{55} + ( -1 + \beta_{1} - \beta_{2} + \beta_{3} - \beta_{5} + \beta_{7} ) q^{56} + ( -4 - 2 \beta_{3} + 2 \beta_{4} - 2 \beta_{5} - 2 \beta_{6} ) q^{57} + ( 1 - \beta_{1} + \beta_{2} + 2 \beta_{4} - \beta_{5} + 2 \beta_{6} - \beta_{7} ) q^{58} + ( 2 \beta_{1} + 2 \beta_{2} + 2 \beta_{3} + 2 \beta_{4} - 4 \beta_{5} - 2 \beta_{6} + 2 \beta_{7} ) q^{59} + ( -3 + 2 \beta_{1} + 4 \beta_{3} - \beta_{4} - \beta_{6} + 2 \beta_{7} ) q^{60} + ( -4 \beta_{1} - 2 \beta_{4} + 4 \beta_{5} - 2 \beta_{7} ) q^{61} + ( 4 + 4 \beta_{1} + 2 \beta_{3} + 4 \beta_{4} + 4 \beta_{6} + 4 \beta_{7} ) q^{62} + ( -\beta_{1} + \beta_{3} - \beta_{4} - \beta_{6} - \beta_{7} ) q^{63} + ( 3 - 2 \beta_{2} - 6 \beta_{3} - \beta_{4} + 2 \beta_{5} + \beta_{6} - 2 \beta_{7} ) q^{64} + ( -2 - 2 \beta_{1} + \beta_{2} - 6 \beta_{3} - 2 \beta_{4} + 4 \beta_{5} + \beta_{6} - 2 \beta_{7} ) q^{65} + ( -2 - \beta_{1} + 2 \beta_{3} + \beta_{4} + \beta_{5} + \beta_{6} - 2 \beta_{7} ) q^{66} + ( 4 + 2 \beta_{1} - 2 \beta_{2} - 6 \beta_{3} - 2 \beta_{4} + 4 \beta_{5} + 2 \beta_{6} - 2 \beta_{7} ) q^{67} + ( -4 \beta_{1} + 2 \beta_{2} - 6 \beta_{3} - 2 \beta_{4} + 2 \beta_{5} - 2 \beta_{7} ) q^{68} + ( 2 - 2 \beta_{1} - 2 \beta_{5} - 4 \beta_{6} - 2 \beta_{7} ) q^{69} + ( -\beta_{1} - \beta_{2} - 2 \beta_{3} - \beta_{4} + \beta_{5} - \beta_{6} - \beta_{7} ) q^{70} -8 q^{71} + ( -1 + 3 \beta_{1} + \beta_{2} + \beta_{3} + 2 \beta_{4} + \beta_{5} - 2 \beta_{6} + 3 \beta_{7} ) q^{72} + ( 4 \beta_{1} + 4 \beta_{3} + 4 \beta_{4} + 4 \beta_{7} ) q^{73} + ( -2 - 4 \beta_{2} - 2 \beta_{3} - 2 \beta_{4} - 2 \beta_{6} - 4 \beta_{7} ) q^{74} + ( -4 + 2 \beta_{1} - 3 \beta_{2} - 2 \beta_{3} + 2 \beta_{4} - 2 \beta_{7} ) q^{75} + ( -6 + 2 \beta_{4} - 4 \beta_{5} - 2 \beta_{6} ) q^{76} + ( \beta_{2} - \beta_{6} ) q^{77} + ( -4 - 3 \beta_{1} + 2 \beta_{2} - 6 \beta_{3} - 3 \beta_{4} + 3 \beta_{5} + \beta_{6} - 4 \beta_{7} ) q^{78} + ( 5 \beta_{2} + 4 \beta_{4} + 5 \beta_{6} + 4 \beta_{7} ) q^{79} + ( -1 - \beta_{1} + 3 \beta_{2} - \beta_{3} - 2 \beta_{4} + \beta_{5} + 2 \beta_{6} + \beta_{7} ) q^{80} + ( 3 \beta_{1} - \beta_{2} + 5 \beta_{3} + \beta_{4} - 4 \beta_{5} + 5 \beta_{7} ) q^{81} + ( 2 - 2 \beta_{1} + 2 \beta_{2} + 2 \beta_{5} + 2 \beta_{7} ) q^{82} + ( -2 + 4 \beta_{1} + 4 \beta_{2} + 4 \beta_{3} + 4 \beta_{4} + 4 \beta_{6} ) q^{83} + ( -1 - \beta_{1} - \beta_{2} - \beta_{3} - 2 \beta_{4} + \beta_{5} - \beta_{7} ) q^{84} + ( -2 + 5 \beta_{2} + 4 \beta_{3} + 4 \beta_{4} + 3 \beta_{6} ) q^{85} + ( -4 + 2 \beta_{1} + 2 \beta_{2} - 2 \beta_{3} + 2 \beta_{4} + 2 \beta_{5} + 2 \beta_{6} - 2 \beta_{7} ) q^{86} + ( 3 - 3 \beta_{1} + \beta_{3} - \beta_{4} - 2 \beta_{5} - 3 \beta_{6} + \beta_{7} ) q^{87} + ( -2 - 2 \beta_{1} + 2 \beta_{3} + 2 \beta_{5} ) q^{88} + ( 2 - 2 \beta_{2} - 6 \beta_{4} - 2 \beta_{6} - 2 \beta_{7} ) q^{89} + ( -2 + 2 \beta_{1} - 3 \beta_{2} + 2 \beta_{5} + 4 \beta_{6} - \beta_{7} ) q^{90} + ( -2 \beta_{1} + \beta_{2} - 2 \beta_{3} + \beta_{6} ) q^{91} + ( -6 - 4 \beta_{2} - 4 \beta_{3} - 2 \beta_{4} - 2 \beta_{6} - 4 \beta_{7} ) q^{92} + ( -2 - 2 \beta_{1} - 2 \beta_{5} + 6 \beta_{7} ) q^{93} + ( -1 - \beta_{1} + \beta_{2} - \beta_{5} - \beta_{7} ) q^{94} + ( 8 - 2 \beta_{1} - 2 \beta_{3} + 4 \beta_{5} ) q^{95} + ( -1 - 2 \beta_{1} + 4 \beta_{2} - 4 \beta_{3} + \beta_{4} - \beta_{6} ) q^{96} + ( 4 + 4 \beta_{1} - 3 \beta_{2} + 4 \beta_{3} - 6 \beta_{4} - 3 \beta_{6} + 2 \beta_{7} ) q^{97} -\beta_{3} q^{98} + ( -1 - \beta_{1} - 3 \beta_{2} - \beta_{3} + \beta_{4} - 2 \beta_{5} - \beta_{7} ) q^{99} +O(q^{100})$$ $$\operatorname{Tr}(f)(q)$$ $$=$$ $$8 q - 2 q^{3} + 2 q^{4} - 8 q^{5} + 4 q^{6} - 8 q^{7} + 6 q^{8} + 2 q^{9} + O(q^{10})$$ $$8 q - 2 q^{3} + 2 q^{4} - 8 q^{5} + 4 q^{6} - 8 q^{7} + 6 q^{8} + 2 q^{9} + 4 q^{10} + 4 q^{11} + 14 q^{12} + 10 q^{15} - 6 q^{16} + 4 q^{17} + 6 q^{18} + 6 q^{20} + 2 q^{21} - 6 q^{22} + 6 q^{24} - 24 q^{25} + 26 q^{26} - 8 q^{27} - 2 q^{28} - 24 q^{30} + 30 q^{32} - 26 q^{33} + 30 q^{34} + 8 q^{35} + 10 q^{36} + 20 q^{38} + 18 q^{39} + 2 q^{40} - 4 q^{42} + 8 q^{43} - 24 q^{44} - 18 q^{45} + 16 q^{46} + 38 q^{48} + 8 q^{49} - 8 q^{50} - 14 q^{51} - 16 q^{52} + 8 q^{54} - 4 q^{55} - 6 q^{56} - 20 q^{57} + 26 q^{58} + 8 q^{59} - 38 q^{60} - 16 q^{61} + 40 q^{62} - 2 q^{63} + 26 q^{64} - 32 q^{65} - 6 q^{66} + 24 q^{67} - 12 q^{68} + 24 q^{69} - 4 q^{70} - 64 q^{71} - 22 q^{72} - 4 q^{74} - 10 q^{75} - 28 q^{76} - 4 q^{77} - 42 q^{78} - 26 q^{80} + 2 q^{81} - 4 q^{82} - 14 q^{84} - 4 q^{85} - 24 q^{86} + 18 q^{87} - 24 q^{88} - 6 q^{90} - 36 q^{92} - 32 q^{93} - 2 q^{94} + 48 q^{95} - 14 q^{96} + 14 q^{99} + O(q^{100})$$

Basis of coefficient ring in terms of a root $$\nu$$ of $$x^{8} - x^{6} - 2 x^{5} + 2 x^{4} - 4 x^{3} - 4 x^{2} + 16$$:

 $$\beta_{0}$$ $$=$$ $$1$$ $$\beta_{1}$$ $$=$$ $$\nu$$ $$\beta_{2}$$ $$=$$ $$($$$$\nu^{7} - \nu^{5} + 2 \nu^{4} + 2 \nu^{3} - 4 \nu$$$$)/8$$ $$\beta_{3}$$ $$=$$ $$($$$$\nu^{7} - \nu^{5} - 2 \nu^{4} + 2 \nu^{3} - 4 \nu^{2} - 4 \nu$$$$)/8$$ $$\beta_{4}$$ $$=$$ $$($$$$-\nu^{7} + \nu^{5} - 2 \nu^{4} - 2 \nu^{3} + 8 \nu^{2} + 4 \nu$$$$)/8$$ $$\beta_{5}$$ $$=$$ $$($$$$\nu^{6} - \nu^{4} + 2 \nu^{3} + 2 \nu^{2} - 4 \nu - 8$$$$)/4$$ $$\beta_{6}$$ $$=$$ $$($$$$\nu^{7} + 2 \nu^{6} - \nu^{5} - 2 \nu^{3} - 4 \nu^{2} - 12 \nu$$$$)/8$$ $$\beta_{7}$$ $$=$$ $$($$$$\nu^{7} + 2 \nu^{6} + 3 \nu^{5} + 2 \nu^{3} - 4 \nu^{2} - 12 \nu - 24$$$$)/8$$
 $$1$$ $$=$$ $$\beta_0$$ $$\nu$$ $$=$$ $$\beta_{1}$$ $$\nu^{2}$$ $$=$$ $$\beta_{4} + \beta_{2}$$ $$\nu^{3}$$ $$=$$ $$-\beta_{6} + \beta_{5} - \beta_{4} + 2$$ $$\nu^{4}$$ $$=$$ $$-\beta_{4} - 2 \beta_{3} + \beta_{2}$$ $$\nu^{5}$$ $$=$$ $$2 \beta_{7} - \beta_{6} - \beta_{5} + \beta_{4} + 4$$ $$\nu^{6}$$ $$=$$ $$2 \beta_{6} + 2 \beta_{5} - \beta_{4} - 2 \beta_{3} - \beta_{2} + 4 \beta_{1} + 4$$ $$\nu^{7}$$ $$=$$ $$2 \beta_{7} + \beta_{6} - 3 \beta_{5} + 5 \beta_{4} + 4 \beta_{3} + 6 \beta_{2} + 4 \beta_{1}$$

## Character values

We give the values of $$\chi$$ on generators for $$\left(\mathbb{Z}/420\mathbb{Z}\right)^\times$$.

 $$n$$ $$211$$ $$241$$ $$281$$ $$337$$ $$\chi(n)$$ $$-1$$ $$1$$ $$-1$$ $$-1$$

## Embeddings

For each embedding $$\iota_m$$ of the coefficient field, the values $$\iota_m(a_n)$$ are shown below.

For more information on an embedded modular form you can click on its label.

Label $$\iota_m(\nu)$$ $$a_{2}$$ $$a_{3}$$ $$a_{4}$$ $$a_{5}$$ $$a_{6}$$ $$a_{7}$$ $$a_{8}$$ $$a_{9}$$ $$a_{10}$$
239.1
 −1.19503 + 0.756243i −1.19503 − 0.756243i −0.835949 + 1.14070i −0.835949 − 1.14070i 0.621372 + 1.27039i 0.621372 − 1.27039i 1.40961 + 0.114062i 1.40961 − 0.114062i
−1.19503 0.756243i 0.356193 1.69503i 0.856193 + 1.80747i −1.00000 + 2.00000i −1.70752 + 1.75624i −1.00000 0.343707 2.80747i −2.74625 1.20752i 2.70752 1.63382i
239.2 −1.19503 + 0.756243i 0.356193 + 1.69503i 0.856193 1.80747i −1.00000 2.00000i −1.70752 1.75624i −1.00000 0.343707 + 2.80747i −2.74625 + 1.20752i 2.70752 + 1.63382i
239.3 −0.835949 1.14070i −1.10238 + 1.33595i −0.602380 + 1.90713i −1.00000 2.00000i 2.44545 + 0.140697i −1.00000 2.67901 0.907128i −0.569517 2.94545i −1.44545 + 2.81259i
239.4 −0.835949 + 1.14070i −1.10238 1.33595i −0.602380 1.90713i −1.00000 + 2.00000i 2.44545 0.140697i −1.00000 2.67901 + 0.907128i −0.569517 + 2.94545i −1.44545 2.81259i
239.5 0.621372 1.27039i −1.72779 + 0.121372i −1.22779 1.57877i −1.00000 + 2.00000i −0.919412 + 2.27039i −1.00000 −2.76858 + 0.578773i 2.97054 0.419412i 1.91941 + 2.51314i
239.6 0.621372 + 1.27039i −1.72779 0.121372i −1.22779 + 1.57877i −1.00000 2.00000i −0.919412 2.27039i −1.00000 −2.76858 0.578773i 2.97054 + 0.419412i 1.91941 2.51314i
239.7 1.40961 0.114062i 1.47398 + 0.909606i 1.97398 0.321565i −1.00000 + 2.00000i 2.18148 + 1.11406i −1.00000 2.74586 0.678435i 1.34523 + 2.68148i −1.18148 + 2.93327i
239.8 1.40961 + 0.114062i 1.47398 0.909606i 1.97398 + 0.321565i −1.00000 2.00000i 2.18148 1.11406i −1.00000 2.74586 + 0.678435i 1.34523 2.68148i −1.18148 2.93327i
 $$n$$: e.g. 2-40 or 990-1000 Embeddings: e.g. 1-3 or 239.8 Significant digits: Format: Complex embeddings Normalized embeddings Satake parameters Satake angles

## Inner twists

Char Parity Ord Mult Type
1.a even 1 1 trivial
60.h even 2 1 inner

## Twists

By twisting character orbit
Char Parity Ord Mult Type Twist Min Dim
1.a even 1 1 trivial 420.2.l.c 8
3.b odd 2 1 420.2.l.d yes 8
4.b odd 2 1 420.2.l.e yes 8
5.b even 2 1 420.2.l.f yes 8
12.b even 2 1 420.2.l.f yes 8
15.d odd 2 1 420.2.l.e yes 8
20.d odd 2 1 420.2.l.d yes 8
60.h even 2 1 inner 420.2.l.c 8

By twisted newform orbit
Twist Min Dim Char Parity Ord Mult Type
420.2.l.c 8 1.a even 1 1 trivial
420.2.l.c 8 60.h even 2 1 inner
420.2.l.d yes 8 3.b odd 2 1
420.2.l.d yes 8 20.d odd 2 1
420.2.l.e yes 8 4.b odd 2 1
420.2.l.e yes 8 15.d odd 2 1
420.2.l.f yes 8 5.b even 2 1
420.2.l.f yes 8 12.b even 2 1

## Hecke kernels

This newform subspace can be constructed as the intersection of the kernels of the following linear operators acting on $$S_{2}^{\mathrm{new}}(420, [\chi])$$:

 $$T_{11}^{4} - 2 T_{11}^{3} - 11 T_{11}^{2} + 16 T_{11} + 16$$ $$T_{17}^{4} - 2 T_{17}^{3} - 35 T_{17}^{2} + 52 T_{17} + 100$$ $$T_{43}^{4} - 4 T_{43}^{3} - 56 T_{43}^{2} + 192 T_{43} - 128$$

## Hecke characteristic polynomials

$p$ $F_p(T)$
$2$ $$16 - 4 T^{2} - 4 T^{3} + 2 T^{4} - 2 T^{5} - T^{6} + T^{8}$$
$3$ $$81 + 54 T + 9 T^{2} + 6 T^{3} + 4 T^{4} + 2 T^{5} + T^{6} + 2 T^{7} + T^{8}$$
$5$ $$( 5 + 2 T + T^{2} )^{4}$$
$7$ $$( 1 + T )^{8}$$
$11$ $$( 16 + 16 T - 11 T^{2} - 2 T^{3} + T^{4} )^{2}$$
$13$ $$6400 + 5664 T^{2} + 1321 T^{4} + 70 T^{6} + T^{8}$$
$17$ $$( 100 + 52 T - 35 T^{2} - 2 T^{3} + T^{4} )^{2}$$
$19$ $$1024 + 2048 T^{2} + 1104 T^{4} + 88 T^{6} + T^{8}$$
$23$ $$6400 + 18944 T^{2} + 2656 T^{4} + 96 T^{6} + T^{8}$$
$29$ $$6400 + 5664 T^{2} + 1321 T^{4} + 70 T^{6} + T^{8}$$
$31$ $$12544 + 209920 T^{2} + 11488 T^{4} + 192 T^{6} + T^{8}$$
$37$ $$4096 + 25088 T^{2} + 3984 T^{4} + 136 T^{6} + T^{8}$$
$41$ $$65536 + 38912 T^{2} + 3472 T^{4} + 104 T^{6} + T^{8}$$
$43$ $$( -128 + 192 T - 56 T^{2} - 4 T^{3} + T^{4} )^{2}$$
$47$ $$16 + 280 T^{2} + 145 T^{4} + 22 T^{6} + T^{8}$$
$53$ $$( 5392 + 256 T - 200 T^{2} + T^{4} )^{2}$$
$59$ $$( -2240 + 1152 T - 140 T^{2} - 4 T^{3} + T^{4} )^{2}$$
$61$ $$( -1312 - 1232 T - 148 T^{2} + 8 T^{3} + T^{4} )^{2}$$
$67$ $$( -6848 + 2112 T - 124 T^{2} - 12 T^{3} + T^{4} )^{2}$$
$71$ $$( 8 + T )^{8}$$
$73$ $$( 64 + T^{2} )^{4}$$
$79$ $$753424 + 895192 T^{2} + 66289 T^{4} + 502 T^{6} + T^{8}$$
$83$ $$29073664 + 2034432 T^{2} + 48224 T^{4} + 432 T^{6} + T^{8}$$
$89$ $$6553600 + 712704 T^{2} + 26176 T^{4} + 352 T^{6} + T^{8}$$
$97$ $$16777216 + 2859008 T^{2} + 128601 T^{4} + 694 T^{6} + T^{8}$$


text:
# What are the Stack Exchange sites?

Is there any place where I can look at all the Stack Exchange sites? That is, I would like to have a list of all the sites available with Stack Exchange under the hood. If no such list exists right now, I think it would be a good idea to have one where users can configure what all they need to see in a dashboard view.

-
Well, the easiest place to start is to scroll down to the bottom of the page and check out the footer. – Benjol Mar 4 '11 at 14:10

There's the StackExchange 2.0 sites list on stackexchange.com - and also up there in the "StackExchange" dropdown at the top of the page.

There's a wiki of SE 1 sites on SE meta, although some are now running OSQA or an alternate engine I think.

-
As of a few days ago, the wiki link (meta.stackexchange.com/questions/4/list-of-stackexchange-sites) no longer exists. All meta.stackexchange.com URLs redirect to the MSO main page. – Pops Mar 3 '11 at 23:18

There's also a full list of SE 2.0 sites (including those in closed beta) maintained at http://metaoverflow.appspot.com/sites

MetaOverflow also provides RSS feeds which you can use to keep informed when new sites become available.

-
But that's just the 2.0 sites straight from the API. The StackExchange 1 sites e.g. mathoverflow.com are missing – Rup Mar 4 '11 at 10:20
I edited my answer to clarify that the list that is maintained is for SE 2.0 sites only. – Evan Mar 4 '11 at 13:59


text:
## 🔍 Overview

Okay, 90% of your engineers use my software (Homebrew), but I can't invert a binary tree, so fuck off. Don't worry, after this course, you can. Well, not exactly.

This course goes over the theory and analysis of algorithms. The topics and material heavily follow the textbook, Algorithms. There is not so much a focus on actual coding, but we do sometimes use pseudocode and implement with python. Rather, it trains you to use the fundamental algorithms we've used, and combine and alter their methods to apply them to different problems.

*I took this course Fall 2020, contents may have changed since then

## 🏢 Structure

• Eight Assignments - 15% (of the final grade)
• Three Coding Quizzes - 10%
• Three Exams - 75%

### Assignments

These involve written descriptions, and sometimes pseudocode, on how to solve a given problem. Analyzing its performance and verifying the correctness is also required.

1. Dynamic Programming - Notation and methods to solve dynamic programming problems
2. DP (Continued) - More problems in the domain
3. Divide & Conquer - D&C problem solving and time complexity analysis
4. D & C (Continued) - More problems in the domain
5. Graph Algorithms - Search algorithms, sorting, and strongly connected components
6. Graphs (Continued)- Max flow and more problems in the domain
7. NP-Completeness - Problem class distinctions, proofs, and reductions
8. Linear Programming - Applications, duality, and algorithms

### Coding Quizzes

These are pretty standard problems that require you to implement methods which are then tested against hidden test cases. I won't touch more on these, as they more more-so short exercises than in depth projects.

1. Knapsack - Use dynamic programming to solve the knapsack problem
2. Find X - Find target x in an infinite array using binary search
3. Kruskal's - Implement Kruskal's algorithm and Union Find to find the minimum spanning tree of a graph

### Exams

Exams were standard- closed note to be completed in a short time period. The content and problems were similar to that of homework assignments, covering 3-4 weeks of material. In addition, there were multiple choice and short answer problems that touched further topics than the assignments, including but not limited to: cryptography, Euler's method and modular arithmetic

## 📖 Assignments 1 + 2 - Dynamic Programming

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

The Fibonacci sequence is a problem that captures this well. For any input n, the solution is derived from solutions of subproblems.

$Fib(n) = Fib(n-1) + Fib(n-2)$

A vanilla recursive implementation would have every node in the above tree to be called, which is redundant. A common optimization is to use memoization with recursion (any DP problem can also be solved this way). Recursion is considered a top-down approach, as you start from the highest level and keep going down depths until you reach a base case. DP, on the other hand, is bottom-up, where we start from the base case.

def fib(n):
if n == 0: return 0
dp = [0] * n
# Base cases
dp[0] = 0
dp[1] = 1
for i in range(2, n):
dp[i] = dp[i-1] + dp[i-2]
return dp[i]

Dynamic programming solutions have three main components:

1. Define your subproblem. For Fib, this is equal to the solution at $n$
2. Define your recurrence. How can a solution at $n+1$ be expressed in terms of smaller subproblems? For Fib, this is as simple as its definition
3. What are your base cases? We need somewhere to start. For Fib, this is [0, 1].

### Results

I thought it would be fun to approach this section of my course reviews differently. Since the results of the homework assignments are typically dense written explanations, I'll instead work through a similar problem under the topic from Leetcode. The problems I pick are similar (some harder some easier) to what we'd see in a homework or exam, but keep in mind we wouldn't have to code them up.

The DP problem is Minimum Number of Removals To Make a Mountain Array. A mountain array has a strictly increasing sequence followed by a strictly decreasing sequence of numbers. For this problem, we need to remove the fewest numbers in an array to make it a valid mountain array.

Here is one of the sample test cases

[2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

This can be broken down into the common dynamic programming problem, longest increasing subsequence. We can remove elements in any order, so the problem is essentially finding an increasing subsequence followed by a decreasing subsequence. Removing the elements in between those yields a valid mountain array.

For a dynamic programming solution of LIS,

• Subproblem: $DP[i]$ = longest increasing subsequence that includes index $i$
• Recurrence: $DP[i] = 1+ max(DP[j])$ where $0 \leq j < i, arr[j] < arr[i]$
• Base case: initialize $DP$ with all ones

Example of the DP array, and the solution (highlighted). Source

To find the longest decreasing subsequence (LDS), we just need to sweep from right to left instead. Alternatively, we could change the comparator from less than to greater than in the recurrence relation. Running both on the example above gives arrays:

Input arr: [2, 1, 1, 5, 6, 2, 3, 1]

LIS:       [1, 1, 1, 2, 3, 2, 3, 1]
LDS:       [2, 1, 1, 3, 3, 2, 2, 1]

Now, to find the largest mountain, we just need to look for the shared point between the increasing subsequence and decreasing subsequence that yields the longest combination. This is the highest sum of the same index between both arrays- in this case, it is at index 5, where the sum is 3 and 3. Since they share the same center, we need to subtract 1, and the longest mountain is size 5! Subtracting this from the total length of the array gives the minimum number of removals.

def minimumMountainRemovals(self, nums: List[int]) -> int:
# t is the LIS, t_rev is the LDS
t = [1] * len(nums)
t_rev = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(0, i):
# Update our table based on the recurrence relation
if nums[i] > nums[j]:
t[i] = max(t[i], t[j] + 1)

for i in range(len(nums) - 2, -1, -1):
for j in range(len(nums) - 1, i, -1):
if nums[i] > nums[j]:
t_rev[i] = max(t_rev[i], t_rev[j] + 1)

best = 0
for i in range(0, len(t)):
# Now, find the best shared point.
# We need to check that both are > 1
# If not, then the sequence would only be 1 direction
if t[i] > 1 and t_rev[i] > 1:
best = max(best, t[i] + t_rev[i])

return len(nums) - best + 1

This solution runs in $O(n^2)$, since for the LIS, we pass through all previous elements for each index. There is an $O(nlog(n))$ solution that is possible.

## 📖 Assignments 3 + 4 - Divide and Conquer

The divide-and-conquer strategy solves a problem by:

1. Breaking it into subproblems that are themselves smaller instances of the same type of problem
2. Recursively solving these subproblems

The most common and probably well-known algorithm that uses this is probably merge sort. This sorting algorithm breaks down an unsorted array into two halves and then merges the two sorted halves.

The runtime complexity of this is O(nlog$_2$(n)). This is because for every level of merging, we pass through every element exactly 1 time, and there are log$_2$(n) levels, so the total number of operations is proportional to multiplying those two together.

The master-theorem expresses a runtime complexity for varying D&C problems.

Visualization of a general D&C problem which splits at rate 'b'

### Results

The D&C problem is Merge K-Sorted Lists. We are given a list of K sorted linked lists, and we want to merge all of them into one sorted linked list.

This can be solved by straightforward divide & conquer similar to merge sort. You break down all linked lists until they are of size 1. Combining two sorted linked lists is the same general technique as two sorted arrays. Each level forward, two combined linked lists will yield one sorted linked list, until it is all combined and returned!

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
# Keep splitting until there's at most 1 element
if len(lists) == 1:
return lists[0]
mid = len(lists) // 2
l, r = self.mergeKLists(lists[:mid]), \
self.mergeKLists(lists[mid:])
# This return will first be reached at the lowest level
return self.merge(l, r)

def merge(self, n1, n2):
'''
Alternatively, a recursive in-place solution could be used
'''
root = curr = ListNode()

# Combine the two sorted lists
while n1 and n2:
curr.next = ListNode()
curr = curr.next
if n1.val < n2.val:
curr.val = n1.val
n1 = n1.next
else:
curr.val = n2.val
n2 = n2.next
# At this point, we need at most 1 more pointer to handle
# the rest of the sorted values
curr.next = n1 or n2
return root.next

## 📖 Assignments 5 + 6 - Graph Algorithms

### Content

A wide range of problems in different domains can be represented concisely in graphs. A graph is defined by a set of vertices and edges which may or may not specify direction and weight.

The majority of operations within graphs that we encountered were:

• Search (DFS/BFS, Dijkstra's, MST, Strongly Connected Components)
• Flow-based (Edmund Karp, Max-flow mincut, ford fulkerson)
• Ordering (Topological sort)
• Manipulations (Removing, reversing, and adding edges)

We would typically use these algorithms as a black box with some modifications to solve for the problem at hand.

### Results

Here's a problem that does not seem immediately seem like a graph problem, Alien Dictionary.

There is an "alien" language that uses the english alphabet, but the ordering between letters is unknown (ex. instead of abcdef... it might be bpaoef...). Given a list of words which are sorted lexicographically, return the order of the letters in this language. An example:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
# 'w' must be first, followed by 'e' and 'r' since they are the 1st chars
# We know 't' is before 'f', since it is the only char that distiguishes
# words 'wrt' and 'wrf'

We know which character comes first one at a time, so we can map this relation for every single character to construct a directed graph. This can be constructed by comparing each word at $arr[i]$ with that at $arr[i+1]$, and finding the first changed character. For ['wrf', 'er'], this is 'w' and 'e'. For ['wrt', 'wrf'], this is 't' and 'f'. The direction of the edge is second → first, so 'e' → 'w', and 'f' → 't'

Topological sorting for directed acyclic graph is a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering. In this case, we want the direct opposite, so the furthest down is returned first. The direction is somewhat arbitrary, since you can return a reversed order, or point the edges in a reversed direction to achieve the same result.

There are a few methods to find the sorting, but to me the simplest is to use depth-first search, and I used that for my solution to alien dictionary. For each vertex, in any order, you run DFS on its outgoing edges, and after it returns for the current node, add the vertex to the solution.

If you first call the vertex at the highest level, then only after it traverses through the depths will it be added. Alternatively, if you first call a vertex with no outgoing edges, it is immediately added to the output. Both will yield the same solution, though vertices with the same degrees may not return in the same order. With this approach we get to ignore in-degree and out-degrees!

def alienOrder(self, words: List[str]) -> str:
graph = {c: set() for word in words for c in word}

# Construct the directed graph
for first, second in zip(words, words[1:]):
for c_first, c_second in zip(first, second):
if c_first != c_second:
break
else: # Didn't find anything in the above
if len(second) < len(first): return ""

order = []
visited = set()
for key in graph.keys():
no_cycle = self.dfs(graph, key, visited, order)
# We need to consider invalid inputs. If there is a cycle
# it is invalid. 'not no_cycle' means it has a cycle!
if not no_cycle:
return ''

return ''.join(order)

def dfs(self, graph, c, visited, order):
'''
Searches through and returns whether a cycle was found or not
'''
if c in visited:
if c not in order:
# If we're here, a node was visited a second time
# before it's added to the solution, so it's a cycle
return False
return True

for c_next in list(graph[c]):
no_cycle = self.dfs(graph, c_next, visited, order)
if not no_cycle:
return False

# Only after the DFS returns, we add to the result
order.append(c)
return True

## 📖 Assignment 7 - NP-Completeness

There are many great resources out there which define and provide examples for complexity classes P, NP, NP-Complete, and NP-Hard, so I'll instead touch on the main topic for the class, which is reductions.

We can prove that a problem is NP-Complete by demonstrating that it is in class NP (can it be verified in polynomial time?), and showing that it is at least as hard as a known NP-Complete problem, by reduction.

A reduction from problem A → problem B can be done by showing that A can be converted to B, converting the solution from B back to A, and showing that a solution to B exists iff a solution to A exists. The conversions must be done in polynomial time. In this case, problem A is the known NP-Complete problem, and B is what we are trying to prove for.

Let's say we want to prove that the problem, clique, is NP-Complete. Given an undirected graph find the a set of vertices of size k where an edge connects every pair together. Application: what is the largest set of friends on Facebook where everybody is friends with each other?

There is a valid clique as shown by the red edges

We first prove that this is in class NP by showing a given result is a valid clique. For every vertex, we check that there is an edge connecting to every other vertex, and if any are missing, it is not valid. This runs in $O(|V|^2)$ time, where $|V|$ is the number of vertices.

Let's consider the known NP-Complete problem, independent set. Given an undirected graph, find a set of vertices of size k where there are no edges which connect any pair. Application: alternatively, what is the largest set of users on Facebook where nobody is friends with each other?

To finish the proof that clique is NP-Complete, we can show a reduction from independent set to clique. I won't prove all steps here, but at the high level, an independent set of graph $G$ is the clique of complementary graph $G'$. This conversion can be done in $O(|V||E|)$ time.

The red nodes on the left graph are an independent set. The same nodes on the complementary graph are a clique. Source

The homework problems and exams required some pretty clever conversions that are not as clear as the case above. We were provided a list of NP-Complete problems we could reduce from. There was a large focus on proper proofs that cover all the steps.

### Results

We're not exactly going to demonstrate a reduction proof here, but there are some NP-Complete problems on Leetcode. Find the shortest superstring is a problem that can be converted to the Travelling Salesman Problem. Given a list of strings, find the smallest string (the superstring) which contains each string as a substring.

Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"
# gctaagttcatgcatc
# gcta
#  ctaagt
#       ttca
#         catg
#          atgcatc

I'll first mention that the reductions we had to do for the course were not nearly as abstract or complicated as this.

So how is this a search problem? In constructing a minimum superstring, we want to maximize the number of overlaps that occur. By brute force, we can solve this in $N!$ time, so for the example we have, this would be $5*4*3*2*1$, which is checking every combination of the 5 strings and calculating the overlap.

Instead, we can represent this as a graph. Each input string is a vertex, and the edges are the overlaps from each vertex to the others. Once we calculate the overlap between every single string, we find the path between every string that has the highest value. This is because the highest overall overlap results in the smallest string. Now, this is the TSP, except we want the longest path, and we don't need to return to the original location!

# For input ["catg","ctaagt","gcta","ttca","atgcatc"]
'''
For input ["catg","ctaagt","gcta","ttca","atgcatc"]
This will generate a matrix with the above edge weights
0s are omitted from my graph, but they are still a valid path to take.
'''
n = len(words)
shared = [[0] * n for _ in range(n)]
# Loop over every combination of two words. Order matters, ij != ji
for i in range(n):
for j in range(n):
if i != j: # Ignore when our word is the same
a, b = words[i], words[j]
# Find the longest substring from 'b' that overlaps the back of 'a'
for k in range(min(len(a), len(b)), -1, -1):
if a[-k:] == b[:k]:
shared[i][j] = k
break

This is as far as I'll go. A dynamic programming solution is the Held-Karp algorithm, which runs in $O(n^22^n)$ time. This is still not ideal, but it is better than factorial time. I believe most deployed applications of TSP utilize an approximate solution when the graph becomes too large.

## 📖 Assignment 8 - Linear Programming

Linear programming is an optimization task where you are given an objective function to maximize, as well as a set of constraints, all of which are linear functions. We didn't spend too much on this topic in this course, but the focus was on breaking down problems and converting them to be standard form for linear programming, as well as some theory. Not so much on algorithms to solve on them.

A common problem that can actually be expressed by linear programming is finding the max flow of a graph. We are given a graph where each edge represents a maximum capacity of flow, and the source + destination vertices. What is the maximum flow that can be achieved, given flow never surpasses the capacity of an edge, and the outgoing flow at a vertex is always equal to the incoming flow (except at the source and destination).

Max flow from s → t. Source

Ford-Fulkerson is a well known algorithm to solve this problem optimally. We can formulate it as a linear program.

maximize:

$\sum\limits_{(s,v)\in E} f(s, v)$

subject to:

$\sum\limits_{(u,v)\in E} f(u,v) = \sum\limits_{(v,w)\in E} f(v, w)$ for all edges except source & destination

$f(u, v) \leq c(u,v)$ for all edges

$f(u,v) \geq 0$ for all edges

Here, we want to maximize the sum of the flow. The first constraint means that, for every vertex, the incoming flow is equal to the outgoing flow. The second means that the flow at any edge is less than the or equal to its capacity. Finally, we want to ensure that the flow is non-negative.

We had a mix of higher-level problems to formulate into linear programs, as well as more algorithmic based, and taking existing linear programs and reworking them to fit under a modified problem.

## ⏩ Next Steps

Graduate Algorithms provides the theoretical and practical structure to begin to think about more complex problems. For further work, there are many directions one could go into. In addition to a breadth of topics, you can look into further mathematical analysis. Also, it would be interesting to find algorithmic optimizations not just for runtime complexity, but considering computer processor characteristics as well.


text:
## Zimin Words and Bifixes

One of the earliest contributions to the On-Line Encyclopedia of Integer Sequences (OEIS) was a family sequences counting the number of words that begin (or don’t begin) with a palindrome:

• Let $$f_k(n)$$ be the number of strings of length $$n$$ over a $$k$$-letter alphabet that begin with a nontrivial palindrome” for various values of $$k$$.
• Let $$g_k(n)$$ be the number of strings of length n over a $$k$$-letter alphabet that do not begin with a nontrivial palindrome.
• Number of binary strings of length $$n$$ that begin with an odd-length palindrome. (A254128)

(If I had known better, I would have published fewer sequences in favor of a table, and I would have requested contiguous blocks of A-numbers.)

I must have written some Python code to compute some small terms of this sequence, and I knew that $$g_k(n) = k^n – f_k(n)$$, but I remember being at in my friend Q’s bedroom when the recursion hit me for $$f_k(n)$$: $$f_k(n) = kf_k(n-1) + k^{\lceil n/2 \rceil} – f_k\big(\lceil \frac n 2 \rceil \big)$$

## “Bifix-free” words

One sequence that I didn’t add to the OEIS was the “Number of binary strings of length n that begin with an even-length palindrome”—that’s because this was already in the Encyclopedia under a different name:

A094536: Number of binary words of length n that are not “bifix-free”.

0, 0, 2, 4, 10, 20, 44, 88, 182, 364, 740, 1480, 2980, 5960, …

A “bifix” is a shared prefix and suffix, so a “bifix-free” word is one such that all prefixes are different from all suffixes. More concretely, if the word is $$\alpha_1\alpha_2 \dots \alpha_n$$, then $$(\alpha_1, \alpha_2, \dots, \alpha_k) \neq (\alpha_{n-k+1},\alpha_{n-k+2},\dots,\alpha_n)$$ for all $$k \geq 1$$.

The reason why the number of binary words of length $$n$$ that begin with an even length palindrome is equal to the number of binary words of length $$n$$ that have a bifix is because we have a bijection between the two sets. In particular, find the shortest palindromic prefix, cut it in half, and stick the first half at the end of the word, backward. I’ve asked for a better bijection on Math Stack Exchange, so if you have any ideas, please share them with me!

In 2019–2020, Daniel Gabric, Jeffrey Shallit wrote a paper closely related to this called Borders, Palindrome Prefixes, and Square Prefixes.

## Zimin words

A Zimin word can be defined recursively, but I think it’s most suggestive to see some examples:

• $$Z_1 = A$$
• $$Z_2 = ABA$$
• $$Z_3 = ABACABA$$
• $$Z_4 = ABACABADABACABA$$
• $$Z_n = Z_{n-1} X Z_{n-1}$$

All Zimin words $$Z_n$$ are examples of “unavoidable patterns”, because every sufficiently long string with letters in any finite alphabet contains a substring that matches the $$Z_n$$ pattern.

For example the word $$0100010010111000100111000111001$$ contains a substring that matches the Zimin word $$Z_3$$. Namely, let $$A = 100$$, $$B = 0$$, and $$C = 1011$$, visualized here with each $$A$$ emboldened: $$0(\mathbf{100}\,0\,\mathbf{100}\,1011\,\mathbf{100}\,0\,\mathbf{100})111000111001$$.

I’ve written a Ruby script that generates a random string of length 29 and uses a regular expression to find the first instance of a substring matching the pattern $$Z_3 = ABACABA$$. You can run it on TIO, the impressive (and free!) tool from Dennis Mitchell.

# Randomly generates a binary string of length 29.
random_string = 29.times.map { [0,1].sample }.join("")
p random_string
# Finds the first Zimin word ABACABA
p random_string.scan(/(.+)(.+)\1(.+)\1\2\1/)[0]
# Pattern:             A   B   A C   A B A

Why 29? Because all binary words of length 29 contain the pattern $$Z_3 = ABACABA$$. However, Joshua Cooper and Danny Rorabaugh’s paper provides 48 words of length 28 that avoid that pattern (these and their reversals):

1100000010010011011011111100
1100000010010011111101101100
1100000010101100110011111100
1100000010101111110011001100
1100000011001100101011111100
1100000011001100111111010100
1100000011011010010011111100
1100000011011011111100100100
1100000011111100100101101100
1100000011111100110011010100
1100000011111101010011001100
1100000011111101101100100100

1100100100000011011011111100
1100100100000011111101101100
1100100101101100000011111100
1100110011000000101011111100
1100110011000000111111010100
1100110011010100000011111100
1101010000001100110011111100
1101010000001111110011001100
1101010011001100000011111100
1101101100000010010011111100
1101101100000011111100100100
1101101100100100000011111100

## The Zimin Word $$Z_2 = ABA$$ and Bifixes

The number of Zimin words of length $$n$$ that match the pattern ABA is equal to the number of of words that begin with an odd-length palindrome. Analogously, the number of words with a bifix is equal to the number of words that begin with an even-length palindrome. The number of these agree when $$n$$ is odd.

I’ve added OEIS sequences A342510A342512 which relate to how numbers viewed as binary strings avoid—or fail to avoid—Zimin words. I asked users to implement this on Code Golf Stack Exchange.

## Richard Guy’s Partition Sequence

Neil Sloane is the founder of the On-Line Encyclopedia of Integer Sequences (OEIS). Every year or so, he gives a talk at Rutgers in which he discusses some of his favorite recent sequences. In 2017, he spent some time talking about a 1971 letter that he got from Richard Guy, and some questions that went along with it. In response to the talk, I investigated the letter and was able to sort out Richard’s 45-year-old idea, and correct and compute some more terms of his sequence.

## Richard Guy and his sequences

Richard Guy was a remarkable mathematician who lived to the remarkable age of 103 years, 5 months, and 9 days! His life was filled with friendships and collaborations with many of the giants of recreational math: folks like John Conway, Paul Erdős, Martin Gardner, Donald Knuth, and Neil Sloane. But what I love most about Richard is how much joy and wonder he found in math. (Well, that and his life-long infatuation with his wife Louise.)

[I’m] an amateur [mathematician], I mean I’m not a professional mathematician. I’m an amateur in the more genuine sense of the word in that I love mathematics and I would like everybody in the world to like mathematics.

Richard Guy in Fascinating Mathematical People: Interviews and Memoirs

### Richard’s letter to Neil

In January 2017, Neil Sloane gave a talk at Doron Zeilberger’s Experimental Mathematics Seminar, and about six minutes in, Neil discusses a letter that Richard sent to him at Cornell—which was the forwarded to Bell Labs—in June 1971.

When I was working on the book, the 1973 Handbook of Integer Sequences, I would get letters from Richard Guy from all over the world. As he traveled around, he would collect sequences and send them to me.

Neil Sloane, Rutgers Experimental Mathematics Seminar

At 11:30, Neil discusses “sequence I” from Richard’s letter, which he added to the OEIS as sequence A279197:

Number of self-conjugate inseparable solutions of $$X + Y = 2Z$$ (integer, disjoint triples from $$\{1,2,3,\dots,3n\}$$).

Neil mentioned in the seminar that he didn’t really know exactly what the definition meant. With some sleuthing and programming, I was able to make sense of the definition, write a Haskell program, correct the 7th term, and extend the sequence by a bit. The solutions for $$A279197(1)$$ through $$A279197(10)$$ are listed in a file I uploaded to the OEIS, and Fausto A. C. Cariboni was able to extend the sequence even further, submitting terms $$A279197(11)$$–$$A279197(17)$$.

## How the sequence works.

The idea here is to partition $$\{1,2,3,\dots,3n\}$$ into length-3 arithmetic progressions, $$\bigl\{\{X_i,Z_i,Y_i\}\bigr\}_{i=1}^{n}$$. And in particular, we want them to be inseparable and self-conjugate.

An inseparable partition is one whose “smallest” subsets are not a solution for a smaller case. For example, if $$n=3$$, then the partition $\bigl\{ \{1,3,5\}, \{2,4,6\}, \{7,8,9\} \bigr\}$ is separable, because if the subset $$\bigl\{ \{1,3,5\}, \{2,4,6\} \bigr\}$$ is a solution to the $$n=2$$ case.

A self-conjugate partition is one in which swapping each $$i$$ with each $$3n+1-i$$ gets back to what we started with. For example, $$\bigl\{\{1,3,5\}, \{2,4,6\}\bigr\}$$ is self-congugate, because if we replace the $$1$$ with a $$6$$ and the $$2$$ with a $$5$$, and the $$i$$ with a $$7-i$$, then we get the same set: $$\bigl\{\{6,4,2\}, \{5,3,1\} \bigr\}$$

### Generalizing Richard Guy’s idea

Of course, it’s natural to wonder about the separable solutions, or what happens if the self-conjugate restriction is dropped. In exploring these cases, I found four cases already in the OEIS, and I computed five more: A282615A282619.

## Generalizing further

There are lots of other generalizations that might be interesting to explore. Here’s a quick list:

• Look at partitions of $$\{1,2,\dots,kn\}$$ into $$n$$ parts, all of which are an arithmetic sequence of length $$k$$.
• Count partitions of $$\{1,2,\dots,n\}$$ into any number of parts of (un)equal size in a way that is (non-)self-conjugate and/or (in)separable.
• Consider at partitions of $$\{1,2,\dots,3n\}$$ into $$n$$ parts, all of which are an arithmetic sequence of length $$3$$, and whose diagram is “non-crossing”, that is, none of the line segments overlap anywhere. (See the 6th and 11th cases in the example for $$A279197(6) = 11$$.)

If explore any generalizations of this problem on your own, if you’d like to explore together, or if you have an anecdotes about Richard Guy that you’d like to share, let me know on Twitter!

## Polytopes with Lattice Coordinates

Problems 21, 66, and 116 in my Open Problem Collection concern polytopes with lattice coordinates—that is, polygons, polyhedra, or higher-dimensional analogs with vertices the square or triangular grids. (In higher dimensions, I’m most interested in the $$n$$-dimensional integer lattice and the $$n$$-simplex honeycomb).

This was largely inspired by one of my favorite mathematical facts: given a triangular grid with $$n$$ points per side, you can find exactly $$\binom{n+2}{4}$$ equilateral triangles with vertices on the grid. However, it turns out that there isn’t a similarly nice polynomial description of tetrahedra in a tetrahedron or of triangles in a tetrahedron. (Thanks to Anders Kaseorg for his Rust program that computed the number of triangles in all tetrahedra with 1000 or fewer points per side.)

The $$4$$-simplex (the $$4$$-dimensional analog of a triangle or tetrahedron) with $$n-1$$ points per side, has a total of $$\binom{n+2}{4}$$ points, so there is some correspondence between points in some $$4$$-dimensional polytope, and triangles in the triangular grid. This extends to other analogs of this problem: the number of squares in the square grid is the same as the number of points in a $$4$$-dimensional pyramid.

## The $$\binom{n+2}{4}$$ equilateral triangles

I put a Javascript applet on my webpage that illustrates a bijection between size-$$4$$ subsets of $$n+2$$ objects and triangles in the $$n$$-points-per-side grid. You can choose different subsets and see the resulting triangles. (The applet does not work on mobile.)

## Polygons with vertices in $$\mathbb{Z}^n$$

This was also inspired by Mathologer video “What does this prove? Some of the most gorgeous visual ‘shrink’ proofs ever invented”, where Burkard Polster visually illustrates that the only regular polygons with vertices in $$\mathbb{Z}^n$$ (and thus the $$n$$-simplex honeycomb) are equilateral triangles, squares, and regular hexagons.

## Polyhedra with vertices in $$\mathbb{Z}^3$$

There are some surprising examples of polyhedra in the grid, including cubes with no faces parallel to the $$xy$$-, $$xz$$-, or $$yz$$-planes.

While there are lots of polytopes that can be written with vertices in $$\mathbb{Z}^3$$, Alaska resident and friend RavenclawPrefect cleverly uses Legendre’s three-square theorem to prove that there’s no way to write the uniform triangular prism this way! However, he provides a cute embedding in $$\mathbb{Z}^5$$: the convex hull of $$\scriptsize{\{(0,0,1,0,0),(0,1,0,0,0),(1,0,0,0,0),(0,0,1,1,1),(0,1,0,1,1),(1,0,0,1,1)}\}.$$

## Polygons on a “centered $$n$$-gon”

I asked a question on Math Stack Exchange, “When is it possible to find a regular $$k$$-gon in a centered $$n$$-gon“—where “centered $$n$$-gon” refers to the diagram that you get when illustrating central polygonal numbers. These diagrams are one of many possible generalizations of the triangular, square, and centered hexagonal grids. (Although it’s worth noting that the centered triangular grid is different from the ordinary triangular grid.)

## A catalog of polytopes and grids

On my OEIS wiki page, I’ve created some tables that show different kinds of polytopes in different kinds of grids. There are quite a number of combinations of polygons/polyhedra and grids that either don’t have an OEIS sequence or that I have been unable to find.

If you’re interested in working on filling in some of the gaps in this table, I’d love it if you let me now! And if you’d like to collaborate or could use help getting started, send me a message on Twitter!

## Parity Bitmaps from the OEIS

My friend Alec Jones and I wrote a Python script that takes a two-dimensional sequence in the On-Line Encyclopedia of Integer Sequences and uses it to create a one-bit-per-pixel (1BPP) “parity bitmaps“. The program is simple: it colors a given pixel is black or white depending on whether the corresponding value is even or odd.

### An Unexpected Fractal

We’ve now run the script on over a thousand sequences, but we still both agree on our favorite: the fractal generated by OEIS sequence A279212.

Fill an array by antidiagonals upwards; in the top left cell enter $$a(0)=1$$; thereafter, in the $$n$$-th cell, enter the sum of the entries of those earlier cells that can be “seen” from that cell.

Notice that in the images below, increasing the rows and columns by a factor of $$2^n$$ seems to increase the “resolution”, because the parity bitmap is self similar at 2x the scale. We still don’t have a good explanation for why we’d expect these images are fractals. If you know, please answer our question about it on Math Stack Exchange. (Alec and I have generated these images up to 16384 × 32768 resolution, roughly 536 megapixels.)

#### The Construction of the Sequence

The sequence is built up by “antidiagonals”, as shown in the GIF below. In the definition, “seen” means every direction a chess queen can move that already has numbers written down (i.e. north, west, northwest, or southwest). That is, look at all of the positions you can move to, add them all up, write that number in your square, move to the next square, and repeat. (The number in cell $$C$$ also counts the number of paths a queen can make from $$C$$ to the northwest corner using only N, NW, W, SW moves.)

(Interestingly, but only tangentially related: Code Golf Stack Exchange User flawr noticed that the number of north/west rook walks is related to the number of ways of partitioning a $$1 \times n$$ grid into triangles.)

## Parity Bitmaps for Other Sequences

It’s worth noting that many sequences are all black, consist of simple repeating patterns, or look like static. However, chess-type constructions, as illustrated by the GIF above, the one above yield images that look like the Sierpiński triangle. (See A132439 and A334017 below, and look at A334016 and A334745 via their OEIS entries.) Look below for a couple other sequences with interesting images too.

I ordered a poster-sized print of the A279212 fractal for Alec, and he framed it in his office.

Some ideas for further exploration:

## Stacking LEGO Bricks

Back in May, I participated in The Big Lock-Down Math-Off from The Aperiodical. In the Math-Off, I went head-to-head against Colin Beveridge (who has, hands-down, my favorite Twitter handle: @icecolbeveridge). Colin wrote about using generating functions to do combinatorics about Peter Rowlett’s toy Robot Caterpillar. Coincidentally and delightfully, I wrote about using generating functions to do combinatorics about Peter Kagey’s toy LEGOs.

Counting LEGO configurations is a problem dating back to at least 1974, when Jørgen Kirk Kristiansen counted that there are 102,981,500 ways to stack six 2×4 LEGOs of the same color into a tower of height six. According to Søren Eilers, Jørgen undercounted by 4!

In my Math-Off piece, I wrote about a fact that I learned from Math Stack Exchange user N. Shales—a fact that may be my (and Doron Zeilberger’s) favorite in all of mathematics: there are exactly $$3^{n-1}$$ ways to make a tower out of $$1 \times 2$$ LEGO bricks following some simple and natural rules. Despite this simple formula, the simplest known proof is relatively complicated and uses some graduate-level combinatorial machinery.

## The Rules

1. The bricks must lie in a single plane.
2. No brick can be directly on top of any other.
3. The bottom layer must be a continuous strip.
4. Every brick that’s not on the bottom layer must have at least one brick below it.

Gouyou-Beauchamps and Viennot first proved this result in their 1988 statistical mechanics paper, but the nicest proof that I know of can be found in Miklós Bóna’s Handbook of Enumerative Combinatorics (page 26). Bóna’s proof decomposes the stacks of blocks in a clever way and then uses a bit of generating function magic.

## Other rules

In preparation for the Math-Off piece, I asked a question on Math Stack Exchange about counting the number of towers without Rule 2. The user joriki provided a small and delightful modification of Bóna’s proof that proves that there are $$4^{n-1}$$ towers if only rules 1, 3, and 4 are followed.

It might also be interesting to consider the 14 other subsets of the rules. I encourage you to compute the number of corresponding towers and add any new sequences to the On-Line Encyclopedia of Integer Sequences. If you do so, please let me know! And I’d be happy to work with you if you’d like to contribute to the OEIS but don’t know how to get started.

Another natural question to ask: How many different towers can you build out of $$n$$ bricks if you consider mirror images to be the same? In the example above with the red bricks, there are six different towers, because there are three pairs of mirror images. By Burnside’s Lemma (or a simpler combinatorial argument) this is equivalent to counting the number of symmetric brick stacks. If there are $$s(n)$$ symmetric towers with $$n$$ bricks, then there are $$\displaystyle \frac 12 (3^{n-1}+s(n))$$ towers. For $$n = 4$$, there are three such towers, shown below in blue.

I asked about this function on Math Stack Exchange and wrote a naive Haskell program to compute the number of symmetric towers consisting of $$n \leq 19$$ bricks, which I added to the OEIS as sequence A320314. OEIS contributor Andrew Howroyd impressively extended the sequence by 21 more terms. I also added sequence $$A264746 = \frac 12 (3^{n-1}+A320314(n))$$, which counts towers up to reflection, and A333650, which is a table that gives the number of towers with $$n$$ bricks and height $$k$$.

## Stacking Ordinary Bricks

It is also interesting to count the number of (stable) towers that can be made out of ordinary bricks without any sort of mortar. I asked on Math Stack Exchange for a combinatorial rule for determining when a stack of ordinary bricks is stable. MSE user Jens commented that this problem is hard, and pointed to the OEIS sequence A168368 and the paper “Maximum Overhang” by Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick, which provides a surprising example of a tower that one might expect to be stable, but in fact is not.

I’d still like to find a combinatorial rule, or implement a small physics engine, to determine when a stack of bricks is stable.

These problems and some generalizations can be found in Problem 33 of my Open Problem Collection. If you’d like to collaborate on any of these problems, let me know on Twitter. If you find yourself working on your own, I’d love for you to keep me updated with your progress!

(The graphics of LEGO bricks were rendered using the impressive and free LEGO Studio from BrickLink.)

## Regular Truchet Tilings

I recently made my first piece of math art for my apartment: a 30″×40″ canvas print based on putting Truchet tiles on the truncated trihexagonal tiling.

I first became interested in these sorts of patterns after my former colleague Shane sent me a YouTube video of the one-line Commodore 64 BASIC program:
 10 PRINT CHR$(205.5+RND(1)); : GOTO 10  I implemented a version of this program on my website, with the added feature that you could click on a section to recolor the entire component, and this idea was also the basis of Problem 2 and Problem 31 in my Open Problem Collection. I saw this idea generalized by Colin Beveridge in the article “Too good to be Truchet” in Chalkdust Magazine. In this article, Colin counts the ways of drawing hexagons, octagons, and decagons with curves connecting the midpoints of edges, and regions colored in an alternating fashion. In the case of the hexagon, there are three ways to do it, one of which looks like Palago tiles. It turns out that if you ignore the colors, the number of ways to pair up midpoints of the sides of a$latex 2n$-gon in such a way that the curves connecting the midpoints don’t overlap is given by the$latex n$-th Catalan number. For example, there are$latex C_4 = 14$ways of connecting midpoints of the sides of an octagon, where different rotations are considered distinct. There are three regular tilings of the plane by$latex 2n$-gons, the square tiling, the truncated square tiling, and the truncated trihexagonal tiling. Placing a Truchet tile uniformly at random over each of the$latex 2n\$-gons, results in a really lovely emergent structure.

If you find these designs as lovely as I do, I’d recommend taking a look at the Twitter bots @RandomTiling by Dave Richeson and @Truchet_Nested/@Trichet_Nested by @SerinDelaunay (based on a idea from Christopher Carlson) which feature a series of visually interesting generalizations of Truchet tilings and which are explained in Christopher’s blog post “Multi-scale Truchet Patterns“.

Edward Borlenghi has a blog post “The Curse of Truchet’s Tiles” about how he tried—mostly unsuccessfully—to sell products based on Truchet tiles, like carpet squares and refrigerator magnets (perhaps similar to “YoYo” magnets from Magnetic Poetry). The post is filled with lots of cool, alternative designs for square Truchet tiles and how they fit together. Edward got a patent for some of his ideas, and his attempt to sell these very cool products feels like it could have been my experience in another life.

If you want to see more pretty images and learn more about this, make sure to read Truchet Tilings Revisited by Robert J. Krawczyk! If you want to see what this looks like on a spherical geometry, check out Matt Zucker’s tweet. And if you want to try to draw some of these patterns for yourself, take a look at @Ayliean’s Truchet Tiles Zine.


text:
# How to: Create a Socket

Before you can use a socket to communicate with remote devices, the socket must be initialized with protocol and network address information. The constructor for the Socket class has parameters that specify the address family, socket type, and protocol type that the socket uses to make connections.

## Example

The following example creates a Socket that can be used to communicate on a TCP/IP-based network, such as the Internet.

Socket s = new Socket(AddressFamily.InterNetwork,
SocketType.Stream, ProtocolType.Tcp);

Dim s as New Socket(AddressFamily.InterNetwork, _
SocketType.Stream, ProtocolType.Tcp)

To use UDP instead of TCP, change the protocol type, as in the following example:

Socket s = new Socket(AddressFamily.InterNetwork,
SocketType.Dgram, ProtocolType.Udp);

Dim s as New Socket(AddressFamily.InterNetwork, _
SocketType.Dgram, ProtocolType.Udp)

The AddressFamily enumeration specifies the standard address families used by the Socket class to resolve network addresses (for example, the AddressFamily.InterNetwork member specifies the IP version 4 address family).

The SocketType enumeration specifies the type of socket (for example, the SocketType.Stream member indicates a standard socket for sending and receiving data with flow control).

The ProtocolType enumeration specifies the network protocol to use when communicating on the Socket (for example, ProtocolType.Tcp indicates that the socket uses TCP; ProtocolType.Udp indicates that the socket uses UDP).

After a Socket is created, it can either initiate a connection to a remote endpoint or receive connections from remote devices.