Written By Yuki Shimizu

Senior Fall

Published: December 25, 2016

Long time no blogging! Hope you all are having a good holiday. Having finished four exam, one presentation and one essay last Saturday, I’m now back in Tokyo. Let’s quickly wrap up one of my classes this semester: Combinatorics. This is one of my math minor electives, which I enjoyed most.

 

We learned basic methods to tackle problems of combinatorics. Combinatorial problems are involved in the situations where each actor has so many possible actions that the number of conceivable strategies or patterns increases very rapidly. Say, you choose your passcode for your iPhone from 10^4=1000 patterns because the default lock system allows you to pick a 4-digit number. However, if you change your passcode option to “6-Digit Numeric Code” or “Custom Alphanumeric Code,” you have to choose your passcode from way more possible combinations.

Final exam was a presentation about one of the combinatorial theories of our choice, so my friend and I did the “Travelling Salesman Problem.” Basically, it poses the question; Given a list of cities and distances between each pair of cities, what is the shortest possible tour to visit each city exactly once and come back to the origin city? Do you think it sounds easy? Wanna try to find the shortest route that covers 10 cities…?? You might have to check the lengths of 180,000 tours, so there are many algorithms that construct tours more optimally and efficiently. For example, you can first take a random tour and try to reach an optimal tour by interchanging several routes to shorten the entire cycle.

2-opt1 2-opt2 2-opt3

 

 

 

 

 

 

 

 

Say, you start with a tour of the top figure. Intuitively it seems inefficient to have the two crossings, so you can “uncross” these two crossings (AC x BD and AJ x DE) to make a shorter tour.

 

You might ask, what is this combinatorial theory used for? Some intuitive examples are airline crew scheduling, arranging school bus routes and transportation/logistics/delivery services. Am I taking this class to make me a strong candidate to UPS in the future? Hmm not really.

In fact, one of the memorable moments in this class was when my classmate asked the professor, “what are the practical applications of combinatorics?” And he said, we do not have to think about it at this stage. There are a lot of really complicated and difficult fields such as biological engineering that combinatorics plays a role (DNA sequence is a good combinatorial example). However, as an undergrad genuinely enjoy learning theories to feel comfortable with solving the combinatorial problems. Once you start working, you have to face a lot of practical problems. There is no life period like undergraduate study when you can invest your time just learning, so have fun studying combinatorics! It is not always necessary to have direct and immidiate use of what I learned in the classroom. This is my key takeout from this class.

 

Have a great rest of the year and if you are applying for US colleges, good luck with your applications! Hope these tons of blog posts on StudyAdvantage help!

Leave a Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

Other posts by Yuki Shimizu

View all posts by Yuki Shimizu