An Algorithms Course with Minimal Prerequisites

There are amazing materials for teaching theoretical algorithms courses: excellent books, lecture notes, and online courses. But none of the resources I am familiar with fits the algorithms course I was supposed to prepare. I wanted to teach a course for students who hardly have any prerequisites.

My students are non-CS majors (mostly math majors), so they did not take a data structures course. I also cannot assume that they have experience with probability, graph theory, linear algebra, writing proofs, and so on. So I made a class that only has two basic requirements:

• Basic programming background: being comfortable with loops, if-else statements, and recursion.
• No mathematical knowledge beyond calculus is required. However, the course is aimed at people who are comfortable with mathematical/abstract thinking.

Even though the course assumes minimum prerequisites, it gets into the technical details and some of the problems require a lot of thinking (although not at the beginning of course).

I made an effort to include many real-world applications, historical anecdotes, horrible jokes, and more. You can find the lecture notes and assignments by clicking on this sentence.

Any comments, questions, and complaints are welcome!

Teenagers doing Mathematical Research

I’d like to ramble about another program that our group is running. We are searching for unusually promising high-school-age students and mentor each in a serious research project. We started doing this already before our REU program. However, I never advertised this program before, because I felt that we were still learning how to do such mentoring. We are still learning, but I now feel more comfortable talking about this.

A couple of recent students. Let’s start with a couple of examples. These are the two most recent young students we worked with.

Kiki Pichini is currently 16 years old. She lives in a small town in the middle of Washington State, far from any big city. A few years ago, she wanted to learn more advanced mathematics but did not wish to leave home at her age. So she enrolled to an online undergraduate program of Indiana University. She will complete her undergraduate degree this upcoming spring.

While working on her degree at 15, Kiki wanted to continue to even more advanced projects, so I started working with her on a research project. This was done purely by email and video chats. Kiki just submitted her paper to a combinatorics journal. It can also be found on arXiv here. Kiki improved the current best upper bound on the number of rectangulations a planar point set can have – a bound that remained unchanged since 2006. She was recently accepted to a graduate program at Oxford.

Our second most recent student is Michael Manta. Michael is a high-school student in Xavier High School in New York City. He was studying more advanced mathematics through an NYC-based program called Math-M-Addicts. We met Michael in the summer after his sophomore high-school year. He worked under the mentorship of Frank de Zeeuw and proved a new result about triangle colorings of the plane. He submitted his paper to a combinatorics journal a few months ago and it is currently being refereed. The paper can also be found on arXiv.

Michael was accepted to many top colleges. Eventually he chose to attend Caltech. After finishing his research project, he wanted to do more math. So he is currently taking a couple of the more advanced courses our department has to offer.

We’re Hiring!

Come join us! This year our math department has two types of positions available. We have a standard tenure track position, which would hopefully continue our awesome sequence of recent hires. But this post is not about the standard position. Instead, I’d like to talk a bit about our other type of position – a Lecturer position.

The lecturer position is basically a teaching-based “tenure-track” position. This brief description gives the wrong impression about the position. So here is a bit more information:

• Lecturers must have a Ph.D. in math. They choose whether they wish to continue doing research – some do and others don’t. (This summer one of our lecturers had a paper accepted to the Annals of Mathematics!)
• Our lecturers are some of the most highly respected people in the department. All of our current lecturers are amazingly professional and productive. They run a large part of the department, work closely with the chair, and so on.
• After 5 years, a lecturer applies to receive a CCE status (Certificate of Continuous Employment), somewhat similar to tenure.

If you are a strong and enthusiastic teacher, and may be interested to join our team, apply on mathjobs.org. (Here is our standard tenure track position). I very much hope that we will hire someone who could be part of our REU program. But I’m only one person, and others have other priorities.

Since Baruch College is not the most well-known place in the mathematical world, I would like to also tell you a bit about us.

• Baruch College is highly focused affordability, diversity, and social mobility. It is consistently ranked #1 in Social Mobility Index, towards the top of Money magazine’s Best Colleges For Your Money, WSJ Biggest Bargains Among U.S. Colleges, Affordable elite ranking, and so on.
• We have a strong group of “junior” mathematicians. For example, Louis-Pierre Arguin‘s work was recently featured in the Bourbaki seminar (Louis-Pierre also holds an NSF career award). Other recent hires include strong people such as Yumeng Ou and Andrew Obus.
• Our department’s financial math team has several impressive achievements. The master’s program in Financial Engineering is consistently ranked as one of the top in the world (see here and here) and the financial math students keep winning trading competitions (see here).
• I believe that another advantage of our department is its unusually friendly and positive atmosphere. Somehow one does not see very bad politics here. For example, our last vote for the executive committee (handling hiring, tenure, etc.) was over extremely quickly and was almost unanimous.

Abstraction is Hard

A few weeks ago I read Malcolm Gladwell’s book The Tipping Point. The book doesn’t really deal with mathematics, but it does contain one math-related anecdote. This anecdote demonstrates an interesting principle of learning mathematics, so I wanted to share it.

Problem 1. We have a deck of cards, such that each card contains a digit on one side and an English letter on the other. We are dealing four cards, with the following result:

We are told that behind every vowel there is an even digit. Which of the four cards should we flip to check whether this claim is true?

I suspect that most mathematicians would only need a few seconds to answer this. On the other hand, people who are not used to mathematical logic would probably need a minute to get to the correct answer.

Problem 2. A cop walks into a bar to check for underage drinking and sees four people drinking. From a first glance, the cop notices that the first is a teenager, the second drinks water, the third is middle aged, and the fourth is drinking beer. Which of the four people should the cop check more carefully?

Most people would probably answer this problem immediately. This is interesting, since the two problems are completely identical! The only difference is that the second problem has a social context while the first is abstract. Even experienced mathematicians probably need to think for a couple of seconds to solve the first problem, but not the second.

This is a nice demonstration of why it is difficult to start studying advanced math. I will definitely use it when teaching proofs classes.

Here is another example of abstract things being hard to get:

Linear Algebra Riddle

I’d like to tell you about a nice riddle, which I heard from Bob Krueger (one of our current REU participants, who already has four papers on arXiv!!). The riddle requires very basic linear algebra and is in the spirit of the previous post.

Riddle. A library has books and subscribers. Each subscriber read at least one book from the library. Prove that there must exist two disjoint sets of subscribers who read exactly the same books (that is, the union of the books read by the subscribers in each set is the same).

Hint: Very basic linear algebra. Try the first thing that comes to mind.

The Math Art of Gábor Damásdi

You may have noticed that the credit for the drawing in my previous post went to Gábor Damásdi. Gábor is a PhD student at the Hebrew University of Jerusalem. He is also one of the top math art creators I have met.

Gábor Damásdi.

I think it took Gábor less than two minutes to prepare the drawing for the previous post, and this is one of his least interesting creations. Check out his site, which contains many more interesting things. You can find there drawings and animation of many mathematical results. Here is an animation of Pascal’s theorem:

Here is a Voronoi diagram of moving points:

I hope that in the future we’d have more of Gábor’s creations in this blog!

Child Care at STOC 2018 + Riddle

I’ve been asked to post the following message by the STOC 2018 local arrangements chairs – Ilias Diakonikolas and David Kempe.

We are pleased to announce that we will provide pooled, subsidized
child care at STOC 2018. The cost will be $40 per day per child for
regular conference attendees, and $20 per day per child for students.
For more detailed information, including how to register for STOC 2018
childcare, see http://acm-stoc.org/stoc2018/childcare.html

To have something slightly mathematical in this post, here’s a cute riddle: 100 passengers enter an airplane one at a time. The plane contains 100 seats and every passanger has a ticket with a seat number. The first passanger lost his ticket, so he randomly chooses a seat (uniformly). When any other passanger enters, if their seat is available they use it, and otherwise they randomly choose one of the available seats (uniformly). What is the probability that the last passanger got their correct seat.

Finally the name of this blog makes sense!

A New Discrete Geometry Group!

This year I moved to Baruch College (which is part of CUNY – the City University of New York), and I’m constantly surprised about wonderful things that keep happening here. In this post I’d like to write about just a couple of these. First, we just hired two additional Discrete Geometers! Together with myself and Rados Radoicic who are already here, we will have quite a large Discrete Geometry group. We have plenty of plans for what to do with this group, and hope that we’ll manage to establish a strong and well-known Discrete Geometry center.

The Discrete Geometers who will be joining us are

• Frank de Zeeuw – working mainly on polynomial methods in Discrete Geometry. Frank has very impressive results concerning expanding polynoamials, and the current best bound for the Szemerédi–Trotter theorem over finite fields.
• Pablo Soberon – working mainly on central ideas in convex geometry, such as Tverberg’s theorem and Helly’s theorem. Pablo also has an impressive background in the world of math competitions.

Frank de Zeeuw, Pablo Soberon, Yumeng Ou, and Andrew Obus.

If the above is not enough for you, we just hired two additional amazing mathematicians! With these four new hires, the pure part of our math department is receiving a huge boost.

The two additional new hires are:

• Yumeng Ou – working in Harmonic Analysis and more specifically on restriction problems and related topics. Personally, I’m very interested in her works involving polynomial methods and Falconer’s distance problem.
• Andrew Obus – working in Algebraic Geometery and Number Theory. I can write more but I’m afraid of getting the details wrong. So just look at Andrew’s webpage to see his impressive works.

By some weird coincidence I am interested in the works of all four people, and I cannot wait to interact with all of them! The future here looks exciting!

Research and Willpower

For years I have been mentoring undergraduate students (and others) in math research projects. For example, see the new REU program I recently posted about. I therefore spend time thinking about the issues that beginning researchers have to overcome. One issue stands out as the most common and most problematic problem that beginning researchers need to overcome: learning to think hard about the research for long stretches of time without being distracted. For lack of a better name, I will refer to this as the problem of willpower.

In this post I will write some of my own thoughts about the willpower problem. I am still struggling with it myself (who doesn’t?) and will be happy to hear your own opinion about handling it.

Even without getting into academic research, everyone is familiar with the issue of procrastination from school and work. While studying for an exam, the idea of peeling 200 grapes might become unusually tempting. One suddenly has to check online what happened with that friend of a friend they briefly met ten years ago (or is that just me?). Or perhaps there is a blog post about procrastination that must be written right now…

When one gets to working on academic research, they most likely already figured out how to overcome the above issues when doing homework or studying for an exam. But then they find out that the same problem pops up several orders of magnitude larger. There are several obvious reasons for that:

• Unlike learning material or doing an assignment, it is not clear whether what you are trying to do is possible. It might be that the math problem you are trying to solve is unsolvable. Or perhaps the problem is solvable but the tools for handling it would only be discovered in 200 years. Or perhaps it is solvable now but after several months of making slow progress, some renowned mathematician will publish a stronger result that makes your work obsolete. These scenarios are not that rare in mathematics and related theoretical fields. Are you still going to spend months of hard work on a problem with these possibilities in mind?
• Unlike exams and most jobs, there are no clear deadlines. It is likely that nothing horrible will happen if you will not work on research today, or this week, or this month. There might not be any short term consequences when spending a whole month watching the 769 episodes of “Antique Roadshow”.
• It’s hard! Working on an unsolved problem tends to require more focus and deeper thinking than learning a new topic. Also, part of the work involves trying to prove some claim for weeks/months/years and not giving up. It is surprising to discover that reading a textbook or doing homework becomes a way of procrastinating – it is easier than thinking hard on your research.

(This might give the impression that theoretical research is a horrible career choice. It is much more stressful than one might expect, and requires a lot of mental energy. However, most people who have been doing this for a while seem to agree that it is one of the more satisfying, challenging, and fulfilling jobs that they can think of. I think that I am more excited about and happy with my job than most of my non-academic friends. But I digress…)

So how can one overcome the issue of willpower? While there are many good resources for similar academic issues (writing guides, career advice, etc.), I am not familiar with any good sources on this topic. I am also not an expert on this issue. All I will do here is write some of my current observations and personal opinions. I assume that some of these are naïve and will change over the years.

• Brainstorming is not a solution. For most people it is much easier to discuss a problem with others than to focus on it on their own. Sessions of working with someone obviously have many advantages, but they are not a solution for the willpower problem. One needs to spend time and frustration thinking hard on the problem on their own. Otherwise, they are unlikely to get a good understanding of the topic and get to the deeper issues. Brainstorming sessions become much more effective after first spending time alone and obtaining some deeper understanding and intuition.
• Collaborations do help. Unlike a brainstorming session, long-term collaborations do seem to help with the willpower problem. Not wanting to disappoint a collaborator that I respect, I will have extra motivation to work hard. Having someone else that is interested in the problems also helps keep the motivation high.
• Reserve long stretches of time for research work. Like most people, I constantly have a large amount of non-research tasks, from preparing lectures to babyproofing the house. It is tempting to focus on the non-research tasks since these require less focus and are easier to scratch of the to-do list. When this happens I try to place in my schedule long stretches of time dedicated to research. I try to find times when I am unlikely to be tired or distracted. Sometimes I turn off the wireless and phone during these times. To quote Terence Tao:
  

  “Working with high-intensity requires a rather different “mode” of thought than with low-intensity tasks. (For instance, I find it can take a good half-hour or so of uninterrupted thinking before I am fully focused on a maths problem, with all the relevant background at my fingertips.) To reduce the mental fatigue of transitioning from one “mode” to another, I find it useful to batch similar low-intensity tasks together, and to separate them in time (or space) from the high-intensity ones.”

• Procrastination with writing tasks is a separate issue. While beginners often have a hard time sitting to write and revise their work, this seems to be a simpler problem. The magic solution seems to be writing a lot (not necessarily research work). After a lot of practice, writing becomes a task that does not require a lot of mental energy or deep concentration, is easy to do, and is mostly fun.
• Find the research environment that works best for you. This is an obvious observation, but I would still like to state it. Different people have different environments that work better for them: Some need a quiet environment while others focus better in a crowded coffee shop, some focus better in the morning while others prefer the middle of the night, and so on.
• Find ways to keep yourself highly motivated. Everyone seems to be at least somewhat motivated by being successful and by their ego. Everyone seem to be at least somewhat motivated by an urge to discover the mathematical truth. However, most people seem to need additional motivation when things are not going well. Some people get extra motivation by being surrounded with hard working people. Others become more motivated by reading biographies of successful mathematician and scientists. And so on.

So what are your thoughts? Do you have any tips? Any sources worth reading?

A New Combinatorics REU

I am excited to announce the beginning of the CUNY Combinatorics REU, which I am organizing together with Radoš Radoičić. For the past three years I have been mentoring Caltech undergraduates in research projects, and before that students in Tel-Aviv University. These often led to papers and almost all of the students continued to grad school or are applying now. This REU is our way of continuing this work in CUNY. Many more details can be found here.

Radoš Radoičić. My partner in this project.

Please send us strong students! Also, if you are a mathematician with some interest in combinatorics, might be around NYC at some point during the summer, and might be willing to give a talk or just come to chat with the participants, let me know!

I’m happy to hear any comments and questions. Now let’s work hard and get some impressive research done in this program!