Блог пользователя Lance_HAOH

Автор Lance_HAOH, история, 7 лет назад, По-английски

Hi. I have always been curious about learning styles. Since this is a competitive programming site, I'll discuss purely about my learning in algorithms/programming. No, this is not another post about how to become red in 1 year or how to become as good as _________ (fill in the blank). I just wish to understand how people comprehend(difficult) stuff.

I have been dabbling with algorithms/competitive programming for almost a year. Some algorithms like binary search, sliding window, trivial DP are so easy to understand that simply anyone could learn it. However, there are also topics like complexity theory, max flow, DP optimizations, etc. that are really complicated. Any attempts to understand the copious mathematical proofs in topcoder articles, university lecture slides, etc. would make my head hurt. After many hours of trying to internalize those difficult concepts, I feel that I don't understand anything. When I run into this deadlock, I will just forgo the proof and learn about how the algorithm works. This makes me feel really uncertain as I didn't understand why it works (Maybe I am just stupid).

I was wondering, how do people even understand these complicated algorithms and proofs? Surely memorizing the algorithm isn't the right way to go? Would anyone care to share about how they learn algorithms? What would you do if you ran into the same situation as me?

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the first step is to get a general idea of what the algorithm is trying to do then go into the details. Let's take max flow for example since you mentioned it. First you need to figure out what a flow network is. You read the definition and discover it is basically directed graph with two special points one called the source and one called the sink. Next there is something flowing from the source to the sink. Then you come across edge capacity and all that is saying is edges have a maximum amount of flow that can go through them. Also you come across flow conservation, which has a complex formula but is basically saying apart from the source and sink whenever you have a bunch of stuff flowing into one vertex the same amount of stuff must flow out of it. At this point you could imagine water flowing through some pipes and conclude the assumptions seem reasonable. Then you see the max flow problem and that is asking given a network what is the most stuff that can flow through it. You read this can be solved with the Edmonds-Karp algorithm. You skim through the equations and theorems and get the general idea. Let's start having nothing flowing through the network. Then use a breadth first search to find a shortest path from the source to the sink and push as much flow as we can through it. When you do this you need to do some sort of update since you can't keep pushing crap through the same path indefinitely. You read the algorithm deals with this by keeping track of flow through edges and maintaining a second network that also gets updated. So now all your flow pushing activities are in order you just repeatedly breadth first search and push flow until it is not possible to do it anymore. Now you have a general idea on how this works you can look at the proof of why this works, try to figure how you would implement it, read about some simple applications e.g bipartite matching or look into more efficient algorithms like Dinic and push-relabel.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

You can read Antti Laaksonen (pllk)'s book. You can get from here. This is written most of algorithm that uses in competitive programming.