My Blog Posts, in Reverse Chronological Order

subscribe via RSS or by signing up with your email here.

Project Euler 85

Jul 14, 2012

A few weeks ago, I remember solving a Project Euler question that particularly intrigued me. I saw problems similar to this when I was in middle school, but never recalled myself successfully solving something them. For reference, the problem was Project Euler 85, counting the number of rectangles in a rectangular grid.

But when I attempted this particular problem? It took me fewer than thirty minutes to think of a solution and code it. So what changed?

I believe it’s been my new algorithmic approach to solving problems.

I fully admit that I’m a brute-force, “try-them-all” kind of person. Whenever I see a problem of the form “How many X satisfy the property Y,” my first instinct is to go through all possible candidates of X and store a count of how many satisfy Y. I first approached this problem by remembering what I did years ago — count rectangles by hand. The questions I experienced back then were much easier in that it was feasible, though time consuming, to actually count all the possible rectangles. Of course, it’s so easy to miss or double-count a few rectangles here and there that I was bound to be off in my final answer.

So I realized I needed a formulaic, or algorithmic, approach to this problem. There had to be some formula out there that could take as input just the dimensions of the largest rectangle, and use that information to compute the total amount of rectangles contained within it.

There was. I started by counting rectangles by hand for rectangles of a small scope (e.g. a 2×3 one), and then testing my conclusions on other small rectangles. This was my algorithm:

total = 0
for i: 1 to n, inclusive
for j: 1 to m, inclusive
total += (n-i+1)*(m-j+1)
return total.

Basically, I consider all the possible dimensions of a smaller rectangle within a larger, n-by-m rectangle. (For instance, I could consider all 1×1 rectangles.) Then I use the (n-i+1)*(m-j+1) formula I derived which computed all the possible rectangles! It was very pleasing for me to solve this problem, and I know that I would be able to solve questions relating to counting rectangles within rectangles with an algorithms-based approach.

For reference, here was my actual code. It’s written in Python. (I used Java to solve the first 50 or so problems, but since then, it’s been Python all the way.) The code gave me the correct answer in fewer than five seconds.

import math

def computeRectangles(row, col):  
  total = 0  
  for r in range(1, row + 1):  
    for c in range(1, col + 1):  
      total += (row - r + 1) * (col - c + 1)  
  return total

smallestDiff = 2000000  
area = -1  
finalRow = -1  
finalCol = -1  
for row in range(1,101):  
  for col in range(1,101):  
    rectangles = computeRectangles(row, col)  
    diff = math.fabs(rectangles - 2000000)  
    if (diff < smallestDiff):  
      area = row * col  
      smallestDiff = diff  
      finalRow = row  
      finalCol = col  
print "Result: [%s]x[%s] with area of %s" %(finalRow, finalCol, area)  

I have to thank Project Euler for not just giving me a medium through which to practice programming, but also for lending me a new perspective on problem solving approaches. I’m just two solutions away from level 3 at this time….

This post is part of a series of posts related with my solutions to selected Project Euler questions.










On Fighting “That 2:30 Feeling”

Jul 6, 2012

redbull

After following a 9:30 AM to 6:00 PM schedule for most of the summer, I’ve occasionally experienced “That 2:30 Feeling,” courtesy of the 5-Hour Energy commercials. (Being a college student, in which I can nap as often as I wish, just doesn’t provide that experience.) For those who haven’t seen the commercial, “That 2:30 Feeling” refers to the almost complete exhaustion many people feel after lunch, which is then mysteriously followed by a period of renewed energy near the evening as the workday comes to a close. I clearly, though, don’t want the mid-afternoon lulls to attenuate my productivity. So what should I do?

Idea 1: Caffeine

Since I can’t stand coffee or tea, caffeine for me usually comes in the form of energy drinks. But is this really the right solution? A quick burst of caffeine might make the difference between making significant progress on a project or having another regrettable day of doldrums.

It comes at a cost, though. Caffeine’s side effects are well documented, and a particularly infamous one is that it can ruin a sleeping schedule. In fact, from my experience with consuming energy drinks, the immediate impact seems negligible. My focus during the hours after drinking Red Bull rarely seems to be on a higher level than my focus throughout days when I abstain from consuming energy drinks. The lasting impact is far more noticeable. On days when I would ordinarily sleep at around midnight, having a Red Bull before lunch makes it highly likely that I’ll stay up until 4:00 AM before managing to finally wrestle myself to sleep. Then the next day’s sleeping schedule is ruined … and it’s a constant struggle for me to return to my desired “midnight-to-8″ routine. So what is a better solution?

After a day at work when I was just about to feel “That 2:30 Feeling,” something happened that just screamed “crisis averted!” I found something to do that regained my focus and allowed me to stay alert for the entire day. It brings me to my next idea.

Idea 2: Code.

On that day I referred to earlier, I set a goal to write a Java program that could generate artificial sentences out of a bank of words. Suddenly, I felt eager. After a moment of deliberation, my fingers began tapping on my keyboard as fast as lightning. My brain was completely funneled in on the current task. My focus was optimal; my productivity was at its peak. And by the end of the day, I had a working program that generated humorous random sentences. (Those who have written random sentence generators will know what I am talking about.) In subsequent days, I tried to plan out my work by setting the period of time after lunch as a coding period.

So what is my point? Not everyone can or wants to code. And not all jobs are conducive to programming. I was lucky in that my interest in programming, combined with my work which requires me to write several scripts to support my overall goal of text simplification, made it easy for me to identify something that was necessary and could be solved with some programming.

In the grand scheme of things, having something to do that grabs your attention and mandates focus, but isn’t too dull, and is related to your job, is what you needs to fight “That 2:30 Feeling.” Everyone may have something different that works for him or her. For me, my solution is to code.










Blog Productivity

Jul 2, 2012

blog_productivity

I just made seven blog entries last June. That’s how many I had in the rest of 2012 combined, so it’s clear that I must be doing something different in the summer than during the spring semester.

The obvious answer is that I’m not faced with the overwhelming academic demands of Williams College. While I am working full time at Bard, I’m definitely laboring for fewer hours as compared to spring semester. And often, my work consists of twiddling my thumbs and rereading academic papers while I wait for a lengthy experiment to conclude. At the time of this writing, for instance, I have two processes running on my computer that I expect to take about ten hours to complete. Sadly, I haven’t shut down my lab computer in about a week.

But the deeper answer is that I have gotten more motivated about writing and have consequently been diligent in setting aside serious writing time. Even though I was inundated with coursework and applications last semester, there were still periods of time, like the entire Winter Study period, that were just ripe for writing. Yet I didn’t blog much, preferring to follow and play basketball, play Minecraft, and do other activities. But writing a blog, even if it doesn’t receive much attention, has a certain appeal that games lack. The lasting impression of written work I produce, by its very nature, affords me an opportunity to look back and see how my interests have developed and vacillated throughout my undergraduate years. And this is also practice for an activity that I will be performing often in life, whether it be for scholarship applications, formal emails, manuscripts, or other documents. By writing often, I feel like I experience hidden reservoirs of enjoyment. Those are especially prevalent during days when I don’t have much to do for the night, and want to make use of precious time.

I hope to maintain this rate of posting during my junior year of college. Since I won’t have a roommate, it’s easier for me to have my own sleeping schedule. My preliminary plan is to wake up much, much earlier than the 9:30 to 11:00 AM time that was the norm during my sophomore year, and use the early morning as study time. By doing more work before classes, I hope to easily set aside blogging time several nights a week.

On a general note, my recent surge in posting just shows that the more you like an activity or subject, the more productive you will be. That is why I need to make sure that I am deeply passionate about whatever computer science field I intend to study in the future.










Accommodations at Conferences and Talks

Jun 30, 2012

As a prospective computer science graduate student, I know I will likely be attending — and talking — at conferences. And my worry is that accommodations will be either lacking or unsuitable for the task. Just recently, I read a few startling messages on an email list aimed at people with disabilities interested in science, technology, engineering, and mathematics. A deaf student was in a tough situation regarding accommodations. Here was the message that started it all, with the author, location, and relevant names protected:

I’ve registered for two […] conferences this summer. […] I sent emails to the coordinators asking for interpreter support, but they have not responded. Since it’s illegal under the ADA for organizations to refuse to provide reasonable disability accommodations, what would the best approach be here? I don’t want to come off too strongly and alienate them.

Ouch. The student can’t gain the full experience of the conference without accommodations. But if he lets them know about the ADA’s (The Americans with Disabilities Act) requirements, will the coordinators view him as a nuisance and possibly block him from coming? The student’s position doesn’t improve with his update, in which he told us how the coordinator responded:

“We do not have the capability to provide an interpreter, but it will absolutely be no problem to accommodate if you obtain one yourself.

Let me know how else I can help.”

At least the coordinator responded, but not in a fair way! I don’t expect everyone to be experts on the ADA, but from what I can see, this message was, in my opinion, poorly constructed and displays a lack of research about accommodations on the coordinator’s part. I would hope that the writer would offer a better excuse1 rather than the current bland response. Fortunately, the deaf student received support from people on the email list. Here are some segments of the most scintillating response:

It is amazing, but not uncommon for anyone in any organization not to know the relevant rules or laws governing disabilities in general now. […] I do know for a fact, that there are several students in the country that have disabilities that earn their PHD’s with very little accommodations, because they don’t want to be seen as the troublemaker in their respective departments. They may win the grievance or lawsuit in the end, but don’t get the recommendations of their department heads when they start looking for faculty positions after that. This is an unwritten game that plays out each and every quarter and semester at a university in the country. I currently hear from people that want a solution that does not require them to file a grievance or lawsuit. Unfortunately, it is not limited to schools and businesses, it is also extremely prevalent in governmental agencies as well. I have seen it at the local and State levels, but it is still very common among the myriad of Federal agencies.

[…]

Fortunately, there were a lot of people in the disability rights movement that came along before me to help pave the way that has allowed me to be successful in life. I feel that it is my responsibility to continue to break down barriers that will allow even more people to benefit from the lives they want to lead. If that requires me to educate some people, then I gladly accept the role. If it requires me to kick the door down, then I can also achieve this as well.

This is well said. I admit that I feel like a burden when asking for accommodations, but I know that in the end I need them in order to perform well in my studies and work. My aim is to become the best computer scientist I can, and if others view me as a troublemaker, so be it. I will just have to take advantage of my accommodations and do the best work possible to show to others that I deserve to work wherever I please.

Another person wrote a short email that sums up all of our sentiments:

It shouldn’t be about how much the event costs. You have the right to get the same benefit from it as someone who is able to hear.

There has been no update from the original deaf student since his last message which thanked the respondents for their support. I hope it has worked out for him.

  1. My idea of an “excuse” would be just what the coordinator said — a lack of capability to provide interpreters — but there needs to be justification and evidence that the conference did as much as it could to provide accommodations. If the conference was in the middle of nowhere with no interpreters available within a 2-hour radius, then I can understand. But who would organize a conference in the middle of nowhere? 










Williams College Spoils Me

Jun 23, 2012

Midway through my Bard College summer REU, it is becoming clearer to me how I have been spoiled. At Williams College, all ASL interpreters who work for me are required to possess RID (Registry of Interpreters for the Deaf) certification. To obtain that title, interpreters have to possess a standard, national excellence of sign language fluency, knowledge, and skill. They have to pass tests and other requirements detailed on the linked website. The situation was the same at the University of Washington’s Summer Academy. During an “Academy Base,” which was the 9:00 to 10:30 AM time slot when all the students would gather around in a room and listen to several lecturers, the disability coordinator there once said verbatim: “Have you noticed that all the interpreters here are really good?

They were outstanding, and I’m wishing the same quality of services existed at the Bard College REU. I am grateful that Bard has generously provided me with interpreting services for all talks, even for those based on such abstruse topics that I would never be able to understand. The interpreters here, unfortunately, are not in the same class as those at Williams College or the University of Washington. They remind me of my interpreters during high school. That is the effect of being spoiled; you are gift-wrapped something outstanding, and do not want to release it and obtain a lesser version the next day. Even though the law requires that someone like me is entitled interpreting services, institutions can provide accommodations of varying quality.

So for all RID-certified interpreters out there, thank you for taking the extra step to ensure that you are delivering high quality interpreting services. I can only hope that my own signing will be up to your standards one day.










Category Swap: Academia ==> Computer Science

Jun 19, 2012

Update February 14, 2020: I made several changes to my earlier posts, so some (if not most) of the content in this blog post is not relevant anymore.

Tonight, I made the executive decision1 to rename one of the three categories of my blog, academia, as computer science.

Why did I do this? Lately, as a result of taking more high-level computer science courses and independent research, I have found more topics related to computer science that I feel comfortable enough writing about. I do not have a comparable level of knowledge of academia, as I obviously have never experienced what the life of a professor is like. (Heck, I don’t even have a Bachelor’s yet!) Furthermore, I feel like any future post I make filed under “academia” would be stale and likely a rewriting of another person’s opinion. Hence, I wish to avoid bifurcating “academia” into “computer science academia” and “generic academia” categories.

My category swap is also a reflection of my own plans for the future. I’d say there’s a 90% chance that I end up pursuing a Ph.D. in computer science, so that goal hasn’t changed. I do, though, want to keep my options open after graduate school. Computer science is a unique field in that there is significant industry demand for Ph.D.s, so many postdocs can find their way into prominent companies such as Google or Microsoft. There is an old letter (1999) here that always pops in my head when I think about graduate school. Obviously, I don’t worship that letter like it’s the Bible, and I’m aware that the writer, a professor of physics, makes a few spurious generalizations. But the general consensus I have heard and seen over the past few years, from my own experience, is that a computer science Ph.D. is more flexible than Ph.D.s in other fields. I have seen and met Ph.D.s at companies such as Google, and could easily see myself following that career path.

I am not going to neglect academia entirely, of course. I will keep it in mind, but I can’t see myself only considering a professorship as my future career. Incidentally, job flexibility might be a reason to side with systems over theory in computer science research. Hopefully I will have a greater understanding of the job market in computer science once I graduate from Williams College.

I have updated all older entries to be filed under the category that suits them best. I have only one category assigned to each blog entry. Including this one, I have made 27 posts on Seita’s Place. Six are categorized as “Deafness,” nine as the newly minted “Computer Science” category, and the remaining twelve encompass the “Everything Else” on my blog. I’d like to keep a balance among those three topics, so I think I know what I want to write about next.

  1. Yes, I know I’m the only person writing this blog, but it feels good to say something like “executive decision,” would you agree? 










ASL Guidelines, Revisited

Jun 16, 2012

Eight months ago (wow, has it really been that long?) I made the first of what I hoped would be a series of posts related with American Sign Language (ASL) guidelines. You can view that blog entry here. I hope to expand on Axiom IX:

Axiom IX: The simplest way to manage personal pronouns is to point.

With footnote:

Axiom IX Footnote: To sign the general word “he,” point your finger in the air.

For the purposes of brevity and clarity, I will focus on the personal pronouns listed in the corresponding Wikipedia entry. And by looking at that table, I realized that my axiom was slightly incorrect. Not all personal pronouns are indicated with the index finger. If one is signing a possessive pronoun, e.g. my, yours, his, and her, it’s best to use the entire hand with the palm facing towards the correct entity. More specifically, the hand should be flat and look as if it is the sign for the letter “b” but without the thumb curling towards the center of the palm.

Example: You are signing the equivalent English sentence of “That book is yours” to a friend. A correct ASL depiction would begin with pointing to the “book entity” — pointing to the actual book if it is visible to both of you, or pointing to any non-previously indexed location if it is a “virtual” book, followed by the sign for book. Then, the “your” sign would follow, with your flat palm facing towards your friend. Add emphasis by pushing your hand forward slightly.

The words his, her, and their have similar signs, except the hand will be pointing towards wherever he, she, or they are located (indexed), respectively. And clearly, “my” or “mine” will be the reverse of “your.” Your flat hand should be pointing towards your chest, possibly touching it.

So when is the finger (I mean … using a finger) appropriate? Right now, I think it’s the exclusive sign for he, she, and it. That’s fewer examples than I thought, so the axiom definitely needs to be reworded. And things get even more complex when including the reflexive personal pronouns: myself, yourself, herself, himself, itself. For those signs, you would use a “thumbs-up” on the dominant hand. Direction still needs to be respected; “myself,” for instance, is signed by tapping the “thumbs-up” hand slightly on your chest.

Given that there are multiple ways to express personal pronouns, and that all of them deal with respecting the orientation of the targeted entity, I think the axiom should be reworded as:

Axiom IX: To manage personal pronouns, indicate the targeted entity by pointing your hand in the appropriate location. In general, use one of the index finger, a flat palm, or a thumbs-up.

The related footnote would accentuate the distinctions between the dominant hand using its index finger, a flat palm, or a thumbs-up.










The Power of Intense Focus

Jun 9, 2012

Facebook Chief Operating Officer (COO) Sheryl Sandberg leaves work at 5:30 every day. That doesn’t surprise me at all. I’m also familiar with the stigma the article mentions towards people who leave work early, which the article’s author defines as before 8:00 PM. The latter view exists because it’s common sense to assume, if two people are working in the same job, and person A leaves at 6:00 PM while person B leaves at 10:00 PM, that person B is more hard working and the better employee. And Person B should be getting the promotions … the recommendations … the list goes on. But does it really have to be this way?

During the past few years, I keep reminding myself of “intense focus.” I consider my studying good when it is productive. That is, I have a high rate of material retention and understanding per hour of my studying. I hate, hate spending hours reading, thinking, or writing, and feeling like I haven’t made progress in whatever task I’m doing. And in almost all of those “wasteful” scenarios, a lack of focus is the issue. Which is, therefore, why I am unsurprised and pleased about Sandberg’s announcement. My hypothesis is that, when faced with a time constraint, people will be increasingly pressed to be productive and efficient during their work.

I certainly share this experience. I didn’t have to think hard for an easy example. In my Real Analysis class last semester, we had three exams. The first was a 4-hour take home exam, and the other two were 24-hour take home exams. Surprisingly, the exam length of the three was roughly similar. The first exam had seven questions, and the other two had eight. And the problems were relatively even in terms of time needed to solve them. Many students preferred the longer exam, since it gave them more time to think about and revise their answers with less fear of a time constraint.

But I argue that a shorter time constraint is beneficial because it forces me to stay alert. Knowing I had plenty of time on the later two exams, I felt myself uncontrollably browsing ESPN, my email, and other websites in between solved questions. But on the first exam, I “marathon-ed” the questions, refusing to spend my time on such trivial tasks. I only took deliberate breaks. Those are the ones that I put on my schedule before taking the exam, to make sure I do not suffer from burnout. Even though I got As on all three exams, the feeling of fruitfulness I had while taking the first exam was vastly different than what I experienced during the other two. This is why I generally advocate for time constraints on work. It’s okay if they are self-imposed. What matters is being efficient and not using the “I have all the time in the world” excuse when you’re taking unnecessary breaks.

I particularly wonder about work habits in academia. What happens to those professors who tend to leave work early1 as compared to those who stay up past their students pulling all-nighters? I’d be interesting in collecting data and seeing if those who spend more time in their offices may actually be doing themselves a disservice. But the problem is that times can be wildly unpredictable. A professor could leave work at 5:00 PM one day, leave at 3:30 AM the next, and not show up to his or her office at all on the third day. And of course, people vary. Some can sustain a level of incredible focus for long periods of time, while others may require more frequent breaks. Finally, there may be certain deadlines that cause people to work longer.

But what about me? What can I do to ensure that I take advantage of intense focus? As I mentioned before, I am working at Bard College this summer. This past week was my first on the job, and I was in the lab (during weekdays) from 9:00 AM to 6:00 PM. The 6:00 PM departure is an excellent time; it allows me to comfortably work out in the weight room before the 8:00 PM closing time, and I can also eat dinner in the 7:00 to 9:00 PM range, which is when I start getting hungry. And my weekends look like they will be free, allowing me to pursue other hobbies such as programming and running (and blogging, of course).

The lazy days between the end of my sophomore year and the start of my research internship are past me. It’s time to set laziness aside and … focus!

  1. By early, I arbitrarily mean before 6:00 PM. 










Summer at Bard

Jun 3, 2012

So it begins.

My research career will officially commence, on the day after the Williams College Class of 2012 commencement, on Monday, June 4. (That’s tomorrow.) I was accepted into the Bard College Mathematics & Computation Research Experience for Undergraduates, funded by the National Science Foundation. I am working with two Bard College professors on a project called “Using Machine Learning to Simplify Text.” My understanding of the project is that we are going to be exploring ways that computers can take a piece of text and simplify its wording and vocabulary to make it comprehensible to a wider audience of readers. Hopefully there will be some serious study of algorithms in this project — I learned so much from Algorithm Design & Data Analysis at Williams College. And all these Project Euler questions I’ve been doing have reinforced my interest in programming.

I’ll be working from June 4 to July 27. It’s a week short in total length from the summer program I was at last summer.

After the summer ends, I hope to recap on what I’ve done. Stay tuned!










Project Euler 179

Jun 1, 2012

UPDATE May 13, 2015: Migrated the code syntax to match Jekyll’s syntax.

Project Euler is an interesting website that offers about 400 different mathematics and computer programming questions. They range from easy (finding the sum of some set of big numbers) to impossible (navigating through Rudin-Shapiro sequences). Just recently, I solved the 179th question with the help of some Java code. While my program gave me the correct answer, the execution time on my Macbook Pro laptop was 80 seconds — and there is an informal “60 seconds” rule that implies that code should be able to solve a problem in fewer than 60 seconds. So I wanted to determine in what ways I could optimize my code.

Here was the question: Find the number of integers 1 < n < 10^7, for which n and n + 1 have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.

This wasn’t too bad for me. I already had a method that could compute the sum of the divisors of a number based on problem 23, so I revised it to add up the number of divisors, rather than the sum. Then I just iterated through each number from 1 to 10 million. Here was the first version of my code:

public class ProjectEuler179 {  
  public static void main(String[] args) {  
    long startTime = System.currentTimeMillis();  
    int result = 0;  
    int prevDivisors = 2;  
    for (int i = 3; i <= 10000000; i++) {  
      int currentDivisors = numberOfDivisors(i);  
      if (currentDivisors == prevDivisors) {  
        result++;  
      }  
      prevDivisors = currentDivisors;  
    }  
    System.out.println("The number of integers is: " + result + ".");  
    long endTime = System.currentTimeMillis();  
    System.out.println("Execution time: " + (endTime - startTime) + " ms.");  
  }

  public static int numberOfDivisors(int x) {  
    int numOfDivisors = 2;  
    for (int k = 2; k <= Math.sqrt(x); k++) {  
      if (x % k == 0) {  
        if (k != Math.sqrt(x)) {  
          numOfDivisors += 2;  
        } else {  
          numOfDivisors += 1;  
        }  
      }  
    }  
    return numOfDivisors;  
  }  
}  

I’m not going to say what the answer was, but as mentioned before, the execution time (endTime – startTime) was about 80 seconds. Looking at the code, the limiting factor is the 10 million calls I make to the method numOfDivisors(). So how can I improve this? In other words, how can I avoid making all those calls to my static method here?

To start, I initialized an array of 10,000,001 elements, called divs, where divs[x] refers to the number of divisors of x. Then, I used two nested for loops to make sure that each entry of divs[x] did hold the number of divisors of x. The outer for loop went from int i = 1 to 10,000,000, and the inner for loop went as far from int j = 1 to as large a number such that i*j <= x. This implies that all divisors for a number are counted! For instance, if we had the number 2, which has the divisors of 1 and 2, then the entry divs[2] should be incremented twice — which it is, because of i=1 and j=2 first, then i=2, j=1 second.

Here, I avoid all the testing of “is a number is a factor of another number?”, as I do in my old code, because if I consider i*j = n, then I know that n has at least those two factors!

The updated code is as follows:

public class ProjectEuler179 {  
  public static void main(String[] args) {  
    long startTime = System.currentTimeMillis();  
    int result = 0;  
    int[] divs = divisors(10000000);  
    for (int i = 2; i < 10000000; i++) {  
      if (divs[i] == divs[i+1]) {  
        result++;  
      }  
    }  
    System.out.println(result);  
    long endTime = System.currentTimeMillis();  
    System.out.println("Execution time: " + (endTime - startTime) + " ms.");  
  }

  public static int[] divisors(int x) {  
    int[] divs = new int[x + 1];  
    for (int i = 1; i <= x; i++) {  
      for (int j = 1; i * j <= x; j++) {  
        divs[i*j]++;  
      }  
    }  
    return divs;  
  }  
}  

It gave me the right answer. And the runtime was an amazingly quick 1.9 seconds — much, much better! I don’t claim full credit for this second code, as I read the discussion forum for that problem after I solved it the first time, but it’s still nice to know how to optimize a program.










Project Euler 1 in Several Languages

May 27, 2012

UPDATE May 13, 2015: Wow, look at the Jekyll code support!

Here’s some code to answer Project Euler 1 in a few languages.

By the way, you do not need code to solve this problem…

(1) Java:

public class pe1 {  
  public static void main(String[] args) {  
    int total = 0;  
    for (int i = 3; i < 1000; i++) {  
      if (i % 3 == 0 || i % 5 == 0) {  
        total += i;  
      }  
    }  
    System.out.println(total);  
  }  
}

(2) Python:

total = 0  
for i in range(1000):  
  if i % 3 == 0 or i % 5 == 0:  
  total += i  
print(total)  

(Alternatively, the one-liner below is probably “better”.)

print(sum(x for x in range(1000) if x % 3 == 0 or x % 5 == 0))  

(3) C++:

#include <iostream>

int main() {  
  int total = 0;  
  for (int i = 3; i < 1000; i++) {  
    if (i % 3 == 0 || i % 5 == 0) {  
      total += i;  
    }  
  }  
  std::cout << total << std::endl;  
  return 0;  
}

(4) Scala:

object HelloWorld {  
  def main(args: Array[String]): Unit = {  
    var result : Int = 0  
    for (a <- 1 until 1000) {  
      if (a % 3 == 0 || a % 5 == 0) {  
        result += a;  
      }  
    }  
    println(a)  
  }  
}  

Note to self for Scala: to means it includes the last value, until means it does not.










ASL Country Signs and Variation

Apr 14, 2012

Ever since I failed to recognize the sign for “Hungary” in a conversation several weeks ago, I have made it a personal goal to learn more ASL signs for countries. Related to that, I have investigated about certain countries having “old” ASL versus “new” ASL signs.

China

The current and traditional sign for China is here. As the website explains, the new version was actually borrowed from China. (The sign language that ASL primarily borrowed from was French Sign Language.) The traditional version is similar to Korea’s traditional version, but does not seem to possess as much of the negative connotations as the latter did (see below). Interestingly enough, the first sign for China that I learned was actually the third sign seen in the link. I’ll sometimes slip up and use it in conversations when I really should not.

Korea

There are several variations of the current sign for Korea. The one I most frequently use starts with my right hand slightly above my head, with my fingertips touching my temple – think of doing a salute. Then I (quickly) bring my hand “out” to the right, then back “in” where my fingertips end up touching my lower cheek and my palm is facing down. This is generally the sign for South Korea; North Korea’s sign is the reverse of the South Korean sign, though I don’t quite see the need, as it is easy to first sign “north” or “south” before the “Korea” part. The old ASL sign is the second sign demonstrated here, with the middle finger “pulling” near the right eye. This sign started to disappear from common use due to the perception of it being a pejorative sign, aimed at deriding the many Asians who have long, narrow eyes. Even if that weren’t the case, I would still prefer the current sign as the second one causes my glasses to shift uncomfortably.

Russia

Russia’s current ASL sign is displayed here. As the caption insinuates, this sign came to fruition out of the public perception that Russians drink heavily. The hand motion is there to wipe off the ale from your (er … I mean the Russian’s) mouth. The old sign is when you put your hands on your hips twice, palms facing downwards – click here to see. I am unsure why this change occurred, although I can tell you that I have never heard a Russian protest about the new sign. Perhaps they are proud of the hefty amount they can drink?

That’s all for now, but I’ll continue to comment about country signs in the future.










On the Hardness of Nintendo Games

Mar 30, 2012

This was a nice article that explains how some of the games I played as a youth were NP-hard. I suppose that makes me feel better that I was such a great player. I’ve read part of this and will read it completely after my finals.

Click here!

EDIT (July 2013): So it took a little longer than I thought for me to finish reading. I was fairly impressed with these results, though I can understand if some “serious” scientists might not think highly of these. Professor Erik Demaine lists this article as a manuscript**, so it looks like it hasn’t been accepted into a prestigious conference.

The paper itself is easy reading, and you don’t have to be an expert in theory to understand the big idea. The techniques mostly rely on reducing the game to a set of really simple rules.










Technical Term Dilemma

Feb 4, 2012

The number one problem with American Sign Language for deaf students taking courses in technical fields is the lack of sign standardization. Want to know what the sign for surjective is? You might run into a problem in that no sign exists or there will be some unusual sign that hasn’t been adopted in standard practice. (By the way, simply spelling out the letters of a technical term is a big no-no in ASL unless it’s the first time an interpreter is expressing that word.) And I can’t blame ASL for that; most people won’t use technical terms like homomorphism or even the word cache on a regular basis. So there’s little motivation for ASL to include esoteric words in its common vocabulary.

So how can we fix this problem? Or, perhaps, is it even necessary to fix this problem? As someone taking a myriad of undergraduate math and science classes, I am fairly used to having my two ASL interpreters collaborate with me to decide on signs for a variety of technical terms. Typically, if we can’t agree on a sign for a term, we settle for a one-letter representation of that word. The word chromosome, for instance, would be signed by just slightly shaking the letter “C” in the dominant hand along with a lip motion of the word. But even if we were able to come up with a sign, it’s highly likely that it will differ from what another student composed at a different university, so there’s a clear lack of standardization.

How has this issue been addressed? Possibly the best single resource on the web is the ASL-STEM Forum, which has done a tremendous job recruiting sign language users to share and distribute signs for terms commonly used in math and science. But there are some glaring pitfalls.

That website allows multiple users to upload different signs, so you might see three or four different signs for the same term, which defeats the purpose of having one sign for one word. Another downside is that this website does not provide an index for subjects that are beyond the level of college underclassmen. Math, for instance, has nothing beyond calculus, which is often the first course required for math majors. This is not as big of a problem as it seems, though, since there probably is not a large enough segment of deaf students taking advanced math and science courses at the upper-undergraduate or graduate level – which is definitely a prominent factor in the lack of signs for technical terms.

But even worse is that we are still nowhere close to providing signs for all the technical terms. One look at the listing of terms in the “Algebra” subsection of the Mathematics section reveals that just five of the twenty-one words have signs! And this is a subject that I hope all deaf students should take before graduating from high school.

The possible benefits of this website, though, leave me optimistic. It’s a user-contributed website, so its data could theoretically grow exponentially. I have contributed one sign to that website, and I hope to contribute more depending on my access to a PC. (For some reason, Macs cause issues with creating videos.) I’ll also try to spread the word to other people I know who may find the website a long-overdue resource.

What can I conclude? It would be nice to have the ASL-STEM Forum more widely known across the ASL community, and it would definitely be great if interpreters were required to know about that website as part of their job. They wouldn’t have to learn all the signs there – they would just need to keep the site in mind to act as a possible reference. Alternatively, perhaps only interpreters with the special R.I.D. (Registry of Interpreters for the Deaf) certification should be required to contribute or incorporate signs from that website since they are typically the ones interpreting undergraduates, who take more advanced courses than secondary school children.

Ultimately, though, this is not going to make or break a deaf student’s undergraduate career. College students should generally be prepared to understand terms on their own and actively collaborate among others to make sure that no comprehension is lost when an ASL sign is missing.










Rubik's Cube Orientations

Jan 27, 2012

A completely solved cube is one orientation of a Rubik’s Cube. Turning a face results in another … so how many total orientations of the Rubik’s Cube are there? To answer that, we need to look at how many possible combinations of corner and edge pieces are valid, in the sense that the cube is solvable. Later, I’ll discuss how many possible ways there are of combining the pieces randomly after disassembling the cube, which usually results in an unsolvable cube.

rubiks

There are six center “pieces” that do not move; they are fixed in place. Then we have the corners and edges that compose the rest of each of the six faces of the cube. There are eight corner pieces, which have three colors, and twelve edge pieces, which have two colors. Take a look at a Rubik’s cube and make sure you understand the distinction.

We think of having eight corner pieces to “fit” into eight corner “slots” in the Rubik’s cube, so there are 8! ways to position the corners. Each individual corner, though, has three faces, and they can be oriented in different ways while maintaining the same actual position on the cube. Therefore, there are 3^7 ways of orienting the faces of the corners. Notice that it’s not 3^8 because if we orient the faces of the first seven corners, then the eighth corner is fixed in place – it cannot be modified without changing the position of the faces on the other corners.

So far, that gives us 8!*3^7 possible orientations. But we now have to consider our 12 edges. We have 12 edges so there are 12! ways of positioning them, along with 2^11 orientations for their two faces. Again, we use n-1 edges where n=12 since the twelfth edge is forced in place if we don’t want to alter the first 11 edges. This implies that if we have a completely “solved” Rubik’s cube with the exception of one edge that is in the wrong orientation, we won’t ever be able to solve that cube since there’s no algorithm that can adjust the faces of one edge without messing up another part of the cube. (Well, you could take the cube apart if you want, but that is cheating.)

All together, we have 8!*3^7*12!*2^11 orientations of the cube. But this is actually double the amount we have, because we have to consider even vs. odd permutations. By this, we are talking about the amount of transpositions we have to perform. A transposition here refers to swapping two corners without altering the rest of the cube, or swapping two edges without altering the rest of the cube. A key concept is that the overall “sign” for the group of edges and the group of corners must be the same; both can be even, both can be odd, but they cannot differ. A group, by the way, is a set with an operation that satisfies properties of associativity, identity and invertibility, but that is beyond the scope of this article because no abstract algebra knowledge is assumed.

What does this mean? Suppose we have a cube that is almost solved. Also suppose that if we can perform 3 transpositions (or swaps) of the corner pieces, we will have correctly oriented all the remaining corners. This means that, if the cube is solvable, the number of swaps needed for the edge pieces must be odd, so the overall parity is even. We might also need 3 swaps of the edges to solve the cube, or we could use just 1 swap if necessary. It is impossible to solve a cube that has an overall parity that is odd.

Therefore, we have to divide what we computed before by half. So the number of possible orientations of a Rubik’s cube, under the assumption that the cube is solvable, is (8!*3^7*12!*2^11)/2 = 43,252,003,274,489,856,000. If we wanted to see the total number of orientations, regardless of whether the cube is solvable, we multiply this by 12. Only a third of the corner orientations are solvable, and only half of the edge orientations are solvable. And, of course, we have the even vs. odd permutations as I explained above. All together, 2*2*3 = 12.

The astute observer will realize that this means that if he has all the pieces of the Rubik’s cube scattered in front of him and assembles them randomly, he will have a 1 in 12 chance of creating a solvable Rubik’s Cube.