Definition of FunctionDefinition of Domain, Codomain, and ImageDefinition of SurjectionDefinition of InjectionDefinition of BijectionIllustration of Different TypesThe Main Goals in Proving a Function's TypeDefinition of Inversefrom Rosen "Discrete Mathematics"
Sum Rule : when the events cannot happen at the same timeProduct Rule : when the events happen in conjunction AND the number of leaves for each branch of the problem space tree is the sameHow to classify the problem space into events/sets : Rule 1) Do it exhaustivelyRule 2) Avoid over-counting!ex) There are N kids running around the field. How will you count them?Let's say we use the groups "Boy..
1 ~ n : n itemsThis is easy. You only need to read the last item's number to get the number of items.8 ~ 11 : 4 numbers11 - 8 = 3 numbers? WRONG!!! Why? Subtraction = the number of spans between numbers, NOT a count of how many thingsA span = distance or some quantity measure.8am ~ 11am has 3 units (hours) of time8cm ~ 11cm has 3 units (cm) of distance 8 ~ 11 floors means we are counting the num..
귀납법으로 그래프 문제를 증명할 때 항상 노드를 하나 지우는 방식으로 접근하라고 배웠는데사실 왜 그렇게 해야 맞는지는 확실히 배우지 않았다.물론 그냥 딱 듣고 왜 그런지 알아채는 친구들도 있겠지만.. 내 경우에는 ㄴㄴWith the help of Professor John F. Hughes, Brown University Department of Computer Science, here is a proof showing why you should always remove a vertex, not add a vertex, in the induction step of your proofs on graphs.
When designing an algorithm, ask yourself : For which cases does the obvious method work?Then find a new way to tackle the remaining cases!예제)Find a hamiltonian path through a tournament graph.Using a more-of-input approach, we claim to have a solution while pretending that the nodes we have processed so far is the entire input instance.We want to maintain the Loop Invariant by adding a new node..