To start off, we learned about some more proof strategies. In particular, we learned how to proove by looking at different cases that a proof could present to see whether all cases work, if the proof is supposed to be universal, or none or only some work. Conceptually this was fairly straight forward, but it is something that will need more practice because sometimes the cases that need to be looked at aren't too obvious (or there are just too many cases, but we probably wont be dealing with problems too big).
Proof patterns were another thing we went over. Again, this was mostly straight forward, but it's definitely something important to go over and write down to keep it in mind when looking at how to go through a proof because they can save a lot of struggle. In lecture I was actually confused by it at first, though I'm not sure if it just didn't get to me conceptually or the format of how it was presented was confusing, but when we got to elimination examples it made more sense. I'm still going over the introduction examples to understand them better.
The final part was about algorithms, or more precisely, algorithms in relation to how they grow over time. Some of the concepts that were explained here were things I've been taught about in different classes, but in different contexts from programming algorithms (for example, population growth). From our understanding, algorithms are designed to deal with growth and large inputs, and we generally should care about how they work and grow when given large inputs. Hence, while with very small inputs, a constant could be very important, in a growing algorithm constants become practically negligible. Also, they become increasingly negligible as an input grows and the algorithm consists of a fairly high order term. That is, with something like 1209x^2, as x grows, 1209 becomes less and less important, so we don't compare two algorithms in terms of their constants. So 5x^2 has the same order as 12091x^2 as it grows. We also looked at the linear search program in python and how input influences running time. Iterating through a list grows in linear time if you're searching from the first index at 0 and moving to the next item to search each time. Based on how you build the algorithm, different inputs could be the best or worst cases. This connected a lot to some of the things we learned about in CSC148 in terms of lists and other data structures and efficiency of traversing them, and how implementation can greatly change efficiency.
Proof patterns were another thing we went over. Again, this was mostly straight forward, but it's definitely something important to go over and write down to keep it in mind when looking at how to go through a proof because they can save a lot of struggle. In lecture I was actually confused by it at first, though I'm not sure if it just didn't get to me conceptually or the format of how it was presented was confusing, but when we got to elimination examples it made more sense. I'm still going over the introduction examples to understand them better.
The final part was about algorithms, or more precisely, algorithms in relation to how they grow over time. Some of the concepts that were explained here were things I've been taught about in different classes, but in different contexts from programming algorithms (for example, population growth). From our understanding, algorithms are designed to deal with growth and large inputs, and we generally should care about how they work and grow when given large inputs. Hence, while with very small inputs, a constant could be very important, in a growing algorithm constants become practically negligible. Also, they become increasingly negligible as an input grows and the algorithm consists of a fairly high order term. That is, with something like 1209x^2, as x grows, 1209 becomes less and less important, so we don't compare two algorithms in terms of their constants. So 5x^2 has the same order as 12091x^2 as it grows. We also looked at the linear search program in python and how input influences running time. Iterating through a list grows in linear time if you're searching from the first index at 0 and moving to the next item to search each time. Based on how you build the algorithm, different inputs could be the best or worst cases. This connected a lot to some of the things we learned about in CSC148 in terms of lists and other data structures and efficiency of traversing them, and how implementation can greatly change efficiency.
No comments:
Post a Comment