Updates from Kyle Rosales Toggle Comment Threads | Keyboard Shortcuts

  • Kyle Rosales 1:12 pm on May 23, 2017 Permalink | Reply
    Tags:   

    WALANG FOREVER (Week 5: Synthesis) 

    Which topic/s in class made an impact to you? Why?

    Siguro yung Fourier Transform kasi natutunan kong pwede parin kayong magkaintindihan kahit na puro mixed signals natatanggap mo, hahaha jk.

    It’s not really on the topic but I guess it’s on the teaching style as a whole. In the first post I mentioned that I like math but I don’t like it in a classroom setting. Well in this class it didn’t feel like a typical classroom setting. I liked how there was an “appreciation” for every lesson and we don’t just learn them because we have to but because the topics have an importance in real life.

    If you can summarize this course in one word or sentence, what would it be?

    Appreciating math in computer  science.

    What would be your parting message to the class?

    I think everyone had fun, it was a great ride. Good luck to everyone and I hope we have a great future ahead of us. I’ll leave with a favorite quote from an anime I’ve started watching recently.

    Go beyond! PLUS ULTRA!

    (All Might, Boku No Hero Academia)

    Advertisements
     
  • Kyle Rosales 7:40 am on May 8, 2017 Permalink | Reply
    Tags:   

    Bioinformatics: Multiple Sequence Alignment and the MAFFT software (Week 4: Laplace and Fourier Transform) 

    According to bioinfo.org.cn

    A sequence alignment is a scheme of writing one sequence on top of another where the residues in one position are deemed to have a common evolutionary origin.

    In oversimplified terms, if you have two strings like ASPOTATOLOL and ASDTOMATOLL, you want to align them in such a way that they are most “similar”. In sequence alignment the strings aren’t just random strings, they are representations of biological sequences like DNA.

    Analyzing the “similarities” in the DNA could give insights regarding the sequences: perhaps two similar protein sequences share similar functions? I’m not a biologist, so I’m not really sure about the applications of this in that field, however it seems to be a big thing.

    What I’m more interested on is the perspective from a Computer Science background. From what I remember in high school biology, there are different ways for genes to mutate. For example, a sequence may be inserted, deleted, repeated, or even changed completely. This adds a lot of complexity to the problem, you don’t just “move” one string against another and compare, you have to consider other mutations.

    For example, a “most similar” way of sequencing the two strings above might be:

    A S __ P O T A T O L O L

    A S D T O M A T O L _ L

    The “_” above represents an insertion. In terms of complexity the search space is really large (I don’t know how much exactly), it scales with the length of the strings. If you add even more sequences as in Multiple Sequence Alignment, it would scale even more.

    There are different ways of computing how “similar” sequences are, there may be different results depending on how you “score” similarities between them.

    Because of the huge time complexity of this problem it isn’t feasible to compute for the most optimal solution (and it’s even hard to define “optimal” in the first place), so an approximation or heuristic may be used.

    One software for Multiple Sequence Alignment is MAFFT (Multiple Alignment using Fast Fourier Transform ). The have a paper about their software and it’s performance measures (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC135756/) and their software can be downloaded for free (http://mafft.cbrc.jp/alignment/software/).

    As the meaning of the acronym implies, this software uses FFT. I don’t know the exact details, but from what I understand the process is somewhat similar to using FFT for audio compression. In audio compression, FFT can be used to identify “important” parts of a sound file, the “unimportant” parts are usually scraped with minimal loss to quality. Similarly, MAFFT uses FFT to find the “important” parts of the sequence and instead of analyzing the whole sequence the more “important” parts are analyzed since they’re much shorter than the whole string.

    References:
    https://www.ncbi.nlm.nih.gov/pmc/articles/PMC135756/

    http://www.bioinfo.org.cn/lectures/index-13.html

    https://en.wikipedia.org/wiki/Multiple_sequence_alignment

     
  • Kyle Rosales 8:28 am on February 14, 2017 Permalink | Reply
    Tags:   

    Using symmetry in optimizing algorithms 

    In some problems, symmetry can be used to optimize algorithms that solve it. Symmetry implies that there is a similarity to make our solutions more efficient. 

    To make things more clear,  let’s use a simple game as an example, tic-tac-toe. In this game there are 9 squares and two players take turns picking a square  and making it. If we ignore the winning condition, there are 9! =362,880 configurations. 

    If we want to make a program that plays tic-tac-toe against a human that never loses, we can do this by searching the whole 9! search space for a non-losing end state (either win or draw) 
    However, we can optimize the 9! search space  by utilizing symmetry. Consider the two possible first moves.


    Even though they are different positions, they are functionally the same because they are symmetric. The first option is neither better nor worse than the second option. 

    Initially there are 9 possible moves the first player can do, but if we apply properties of symmetry (rotations and reflection) we can reduce the first move to just 3 distinct options (edge, corner, center). 

    If we apply properties of symmetries to every move and factor in the winning condition, we can reduce the state space from 9! to just 138 (according to Wikipedia). 

    As we can see, by taking advantage of symmetric properties we can make our algorithms more efficient, and sometimes it makes a lot of difference. 

     
  • Kyle Rosales 12:31 pm on January 29, 2017 Permalink | Reply
    Tags:   

    2d line-to-line collision detection using vectors (Week 2: Vectors) 

    • As we’ve seen in class, vectors can be used to represent several objects such as physical quantities like velocity or force; 2-dimensional images; and even the bag-of-words model.
    • In what other ways can we use vectors?
    • Give one sample application and describe/illustrate how the vector can be used.

    While computers are good at calculating lots and lots of numbers that would be impossible for a human to do, amusingly some trivial things for humans are much more complex when it is done by a computer. One of these things is checking whether two lines intersect or not.

    lines

    At one glance it is easy for a human to check if two lines intersect or not, but how would you make a computer do it? This problem seems simple and doesn’t seem to be useful for anything, however it has its use in some areas like collision detection in video game development.

    One way to do line-to-line collision is through the use of vectors. We can represent each line as a vector with one end as the the tail and the other head as a tail.

    vectors

    From here we can get the “projection” of each vector on a certain axis, like the x-axis. This can be easily done by getting the dot product of the vector and a unit vector in the same direction as the axis you want to project on. In this case since we will be projecting each vector to the x-axis, we will get the dot product of each vector with the (1,0) unit vector.

    projection

    Once the vectors are projected into an axis, it’s easier to compare whether the projection lines intersect or not (the details on how exactly would depend on what you are using). If the projections do not intersect, then we are sure that the original lines do not intersect.

    This method does not handle all cases of collisions though, for example in case A below if we use the x-axis as a projection it would say that they intersect even though they aren’t. If we projected case A along the y-axis we would detect that indeed they aren’t intersecting. Case B passes both x and y axis tests even though they do not intersect. It seems testing for x and y axis isn’t sufficient.

    other_cases

    The correct axis to use is the two normal axis perpendicular to any of the two vectors. This check works for any case and is sufficient on its own (no need to check other axis). The image below shows a projection onto the axis perpendicular to the blue line. Note that if we project using the axis perpendicular to the red line it would seem that they are intersecting, that’s why it’s important to use the two normal axis for checking.

    normal_axis

    The use of vectors for collision detection can even be used on other things that aren’t two lines. For example, a 2d rectangle can be represented by a vector from the lower left corner to the upper right corner of the box. A 3d cube can also be represented by a vector in a similar manner. Vectors are useful in collision detection and game development in general.

     

     
  • Kyle Rosales 8:40 am on January 19, 2017 Permalink | Reply
    Tags:   

    The Evil Ruler of All Potatoes (Week 1: Introduce Yourself) 

    • What’s your name?

    Hi I’m Kyle irl, but online I usually go by the name DarkPotatoKing (or DPK for short). I’m fine with being called any of those names. 🙂

    This is what I look like both online and irl.

    15319242_333520503700492_6091328632144042957_n

    • What were your thoughts when you enrolled in this course?

    I heard that CS 130 was gonna be a difficult course, but now I guess it’s all okay since Sir Paul will be the one teaching. I think that this will be an exciting course and I hope I will be able to appreciate and apply the concepts even after I pass this course (Yes let’s be positive 🙂 #ClaimingIt).

    • How comfortable are you with math?

    Much more comfortable than blogging in wordpress, seriously I’ve never done this before or anything similar so I’m still figuring out the functionalities. :)))

    Anyway back to the topic, outside of classroom settings I actually like math. I hate having to solve problems and solving them really fast during an exam, but when I apply it in other things irl I find it fun to do.

    One of my favorite games is Fire Emblem. It’s a turn based strategy game where you control your units (people), fight enemy units, and do certain objectives like killing the boss of that chapter or seizing a castle or throne room. It has an RNG, but a lot of things can be calculated using math. For example: damage is UNIT_TOTAL_ATTACK – ENEMY_TOTAL_DEFENCE, hit rate is UNIT_HIT – ENEMY_AVOID, etc.

    In this game you can predict the future (outcomes of battles, enemy movement, etc.) by calculating A LOT. Sometimes I even have to use a calculator when I’m planning my strategy for the current map. I find it fun calculating a lot of little things just to make sure that my unit can kill all enemies within range while at the same time remaining alive. Since this game has an RNG I also have to calculate probabilities, for example what is the probability that my player will miss an attack. Even “good” strategies can be turned around if you’re unlucky to have your opponent land a 1% crit on one of your low hp units. I think that these probability calculations in Fire Emblem somewhat helped me develop the idea for IskoDuler.

    So yeah, I’d say I’m comfortable with math, but only outside the classroom.

    • What’s your dominant feeling right now?

    Cold. Anlamig dito sa TLC. So sad na tapos na yung pasko pero SMP parin ako :((( hahaha jk :)))

     
    • Paul Rossener 4:02 pm on February 22, 2017 Permalink | Reply

      I like turn-based games too! And what you said sounds like a good AI project for me 🙂

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: