Here we are. This is the end of the term. Here, I want to share with all my experience during taking this course. To begin with this course is called an Introduction to Computer Science(CSC148). As it's named, it is purely the course of Computer Science, that let the student to see and experience some real introductive stuff of this "field" and get some basic knowledge for the other or higher CS courses. When you take CSC108- Programming language(Python), you learn first steps of coding and have some understanding about your code and the language. However, on CSC148 you develop that learning and more sense about real programming. I would agree for some students and also for me, it'd been hard to solve the problem right away and had found themselves more frustrated and nervous. Despite the problems I faced, I always tried to find the way to solve them whether is piazza, office hours, or googling :) But what I understood for myself, this course was not really about just coding, it's more about complexity, coherence and efficiency. Let me explain what I really mean by complexity, coherence and efficiency. Before this course, I would take my computer and then start to code right away like "no needs to think on paper". But when I came to CSC148, it just didn't work for me in that way. Everything was attached complexly and cohesively. You would first think about more efficient way of writing any work on paper. If it there would be many classes, you might need to use Inheritance wisely in order to not have repeated codes or chunks in your work. So thinking about efficiency, brings you to make a cohesive design of your codes, choosing proper names for your methods or functions, giving a good description to them, as if somebody will be reading your code. And I must admit that everything comes with practice as like "no pain, no gain". At last, I really liked this journey to paramount of Computer Science, and I hope everyone feels the same way.
Monday, April 7, 2014
Monday, March 31, 2014
SLOG - week11: Sorting and Efficiency
Sorting. It's the thing which you sometimes wish to use. There are moments when you extremely want to use sorting techniques to solve or sort things out. For example, every time when professor spreads all the midterm papers or any handed-work at class and says, come and get it. Huh. Imagine that episode for a moment, the whole class is just like bees running downward towards a front giant-lenghty desk. At that time, I wish we had sorting machine for that....
So there are so many sorting algorithms that each can be effective in a different way. As we covered at class some of them: merge sort, quick sort, bubble sort, tim sort, selection, insertion and etc. Let's shortly give a brief explanation to each of these algorithms.
Buble sort has a sorted and an unsorted part. At every pass, it traverses unsorted part from right to the left thereby swaps unordered elements. Hence, bubble at one pass puts one element at a proper place, so it relatively takes n passes, and performs n -1 comparisons and swaps at each pass. Bubble sort can be efficient to use on a nearly sorted list because it will not swap entire list.
Selection sort also has a sorted and unsorted part. But the difference is initially its sorted part will be empty, and entire list will be unsorted part. At every pass, it finds the smallest element in the unsorted part and swaps with the first element of the unsorted part. So the process takes n times to sort entire list.
Insertion is a bit similar to selection. It also has sorted and unsorted parts. Initally, sorted part is empty and presumes an entire list as unsorted. At every pass, it takes first element in the unsorted and puts it at the right place, and is repeated till the list gets sorted from right to left. It will also keep each element at each pass not to have space problem. Insertion is slower compare to selection sort on average cases and performs more swaps, but it's good on nearly sorted list. The time complexity of bubble, selection and insertion sorts are O(n^2). And all these three sorts are not efficient to use on a large size of data.
Quicksort recursively sorts list. We pick a pivot, so at every run each element gets compared with the pivot. It has sublists which in one sublist gets items smaller than pivot and in the next sublist bigger than pivot, and then recombines sublists and pivot. The problem of this is to choose right pivot, and mostly for pivot is picked first or last item in the list. The time complexity of quick sort is different from previous three sorts. For partitioning list by pivot, and halving problem size by 2 it overall takes O(nlgn). Quicksort is generally faster than other O(nlgn) algorithms. However, the worst case of using quick sort is using it on already sorted list because if it picks first element as pivot, it goes through the entire list. It's disaster. Hence, the time complexity will be O(n^2).
Mergesort, instead of choosing pivot, equally (mostly) halves the list. At every run, it halves into 2 sublists, recursively sorts, and recombines by repeatedly taking the smallest element in he sublists. Mergesort has O(nlgn) time complexity, and it's efficient on sorting a reversed sorted list compare to quick sort.
Timsort - the last but one of the most efficient sorting algorithm, and it's Python's built-in sort. The process of sorting of timsort is mix of existing sorting algorithms such as insertion and merge sort. The sorting performance of timsort on reversed, sorted, unsorted lists is quite impressive because it's faster than other sorting algorithms. Timsort can take O(n) time in the worst and best cases.
Sorting. It's the thing which you sometimes wish to use. There are moments when you extremely want to use sorting techniques to solve or sort things out. For example, every time when professor spreads all the midterm papers or any handed-work at class and says, come and get it. Huh. Imagine that episode for a moment, the whole class is just like bees running downward towards a front giant-lenghty desk. At that time, I wish we had sorting machine for that....
So there are so many sorting algorithms that each can be effective in a different way. As we covered at class some of them: merge sort, quick sort, bubble sort, tim sort, selection, insertion and etc. Let's shortly give a brief explanation to each of these algorithms.
Buble sort has a sorted and an unsorted part. At every pass, it traverses unsorted part from right to the left thereby swaps unordered elements. Hence, bubble at one pass puts one element at a proper place, so it relatively takes n passes, and performs n -1 comparisons and swaps at each pass. Bubble sort can be efficient to use on a nearly sorted list because it will not swap entire list.
Selection sort also has a sorted and unsorted part. But the difference is initially its sorted part will be empty, and entire list will be unsorted part. At every pass, it finds the smallest element in the unsorted part and swaps with the first element of the unsorted part. So the process takes n times to sort entire list.
Insertion is a bit similar to selection. It also has sorted and unsorted parts. Initally, sorted part is empty and presumes an entire list as unsorted. At every pass, it takes first element in the unsorted and puts it at the right place, and is repeated till the list gets sorted from right to left. It will also keep each element at each pass not to have space problem. Insertion is slower compare to selection sort on average cases and performs more swaps, but it's good on nearly sorted list. The time complexity of bubble, selection and insertion sorts are O(n^2). And all these three sorts are not efficient to use on a large size of data.
Quicksort recursively sorts list. We pick a pivot, so at every run each element gets compared with the pivot. It has sublists which in one sublist gets items smaller than pivot and in the next sublist bigger than pivot, and then recombines sublists and pivot. The problem of this is to choose right pivot, and mostly for pivot is picked first or last item in the list. The time complexity of quick sort is different from previous three sorts. For partitioning list by pivot, and halving problem size by 2 it overall takes O(nlgn). Quicksort is generally faster than other O(nlgn) algorithms. However, the worst case of using quick sort is using it on already sorted list because if it picks first element as pivot, it goes through the entire list. It's disaster. Hence, the time complexity will be O(n^2).
Mergesort, instead of choosing pivot, equally (mostly) halves the list. At every run, it halves into 2 sublists, recursively sorts, and recombines by repeatedly taking the smallest element in he sublists. Mergesort has O(nlgn) time complexity, and it's efficient on sorting a reversed sorted list compare to quick sort.
Timsort - the last but one of the most efficient sorting algorithm, and it's Python's built-in sort. The process of sorting of timsort is mix of existing sorting algorithms such as insertion and merge sort. The sorting performance of timsort on reversed, sorted, unsorted lists is quite impressive because it's faster than other sorting algorithms. Timsort can take O(n) time in the worst and best cases.
Wednesday, March 5, 2014
Week 6: Intro to Trees and Assignment 1
Week 6 was the most busiest and exhausting week for me so far. There were so many assignments need to be done in the same week and same day from the other classes also. It just made me nervous. I was having problem with my tour function for assignment 1. I'd been thinking about coming up more efficient way of moving of four cheeses for a week. Professor Danny Heap, showed his way of moving three cheeses with three stools. He explained it so accessibly to understand choosing origin, intermediate stool, and destination to move each cheese around. But when I tried myself to apply that for four cheeses, it got more harder than I thought. Eventually, I ended up using four stools. So I finally managed to finish on time.
Trees. I heard about it before from my friends, but never had an idea what really that is. Even it was the introduction, I felt confused because it was completely new thing. We did not cover trees on CSC108. However, I am going to take time and try to understand it during reading week.
Week 6 was the most busiest and exhausting week for me so far. There were so many assignments need to be done in the same week and same day from the other classes also. It just made me nervous. I was having problem with my tour function for assignment 1. I'd been thinking about coming up more efficient way of moving of four cheeses for a week. Professor Danny Heap, showed his way of moving three cheeses with three stools. He explained it so accessibly to understand choosing origin, intermediate stool, and destination to move each cheese around. But when I tried myself to apply that for four cheeses, it got more harder than I thought. Eventually, I ended up using four stools. So I finally managed to finish on time.
Trees. I heard about it before from my friends, but never had an idea what really that is. Even it was the introduction, I felt confused because it was completely new thing. We did not cover trees on CSC108. However, I am going to take time and try to understand it during reading week.
Week 4: Testing and choosing test cases
I remember some basic things about testing from CSC108, but I never thought that it would be so troublesome here. The reason why I am telling about this is because when we started to deeply cover Object Oriented Programming it just got so confusing. Especially, I felt that during the lab. We had to write collection of classes and use inheritance, then test each class for correctness. The main trouble started when we had to think about the cases for each class because me and my partner did not know how to even write them. So we furiously started thinking about on what we're going to test and what tests are the best to test. It really gets you frustrated indeed. However, our TA showed some good ways to test the codes and pointed to the mistakes we were doing.
But there is also a good side of it when your code passes all the tests and prints "OK" at the end. You feel just happy. To be honest, I never liked testing and more choosing test cases. But now, I somehow managed to test the code more properly and avoid useless test cases after all, which really helps me not to think about my fails at the beginning.
I remember some basic things about testing from CSC108, but I never thought that it would be so troublesome here. The reason why I am telling about this is because when we started to deeply cover Object Oriented Programming it just got so confusing. Especially, I felt that during the lab. We had to write collection of classes and use inheritance, then test each class for correctness. The main trouble started when we had to think about the cases for each class because me and my partner did not know how to even write them. So we furiously started thinking about on what we're going to test and what tests are the best to test. It really gets you frustrated indeed. However, our TA showed some good ways to test the codes and pointed to the mistakes we were doing.
But there is also a good side of it when your code passes all the tests and prints "OK" at the end. You feel just happy. To be honest, I never liked testing and more choosing test cases. But now, I somehow managed to test the code more properly and avoid useless test cases after all, which really helps me not to think about my fails at the beginning.
Monday, March 3, 2014
Week 7: Recursion
Recently, I have found out for myself new thing - recursion. Now, I don't even know how I would imagine programming language without recursion. Recursion is really makes everything easy compare to "you-do-all".
To begin with, to implement a recursive function, you need to remember three simple steps that are base case, recursive step and work.
The base case step is very less or more crucial compare to two other steps because you need to define, when your program should stop going further and extract the answer right away. For that, you first all of all, you really need to understand what program should do. Then, the rest will be easy.
Recursive step as it's written means you write a real recursive line that will call the program itself and recursively solve it. For this step, you need decide which part of your problem you want to apply recursion, so it will make easy your job.
The last step is work. In this step, you simply get results from recursive step and combine them to return or do something else.
So to clarify my understanding about recursion, I want to explain benefits of using it. I found recursion very efficient way of solving for any kind of programming problems, especially, for running time efficiencies. We know that any kind of loops may take exponential time or more when recursive function could perform the same job in a linear time or less. So from programming perspectives, it is very handy to use recursion. The second advantage of recursion, it does the job for you, so you do not have to iterate through all of your loops, just simply extract the answer you need. It may look like, if we imagine recursion as tons of minions who do each little work and give you one-done job at the end, when iterative function as Spiderman fighting with all monsters alone.
Recently, I have found out for myself new thing - recursion. Now, I don't even know how I would imagine programming language without recursion. Recursion is really makes everything easy compare to "you-do-all".
To begin with, to implement a recursive function, you need to remember three simple steps that are base case, recursive step and work.
The base case step is very less or more crucial compare to two other steps because you need to define, when your program should stop going further and extract the answer right away. For that, you first all of all, you really need to understand what program should do. Then, the rest will be easy.
Recursive step as it's written means you write a real recursive line that will call the program itself and recursively solve it. For this step, you need decide which part of your problem you want to apply recursion, so it will make easy your job.
The last step is work. In this step, you simply get results from recursive step and combine them to return or do something else.
So to clarify my understanding about recursion, I want to explain benefits of using it. I found recursion very efficient way of solving for any kind of programming problems, especially, for running time efficiencies. We know that any kind of loops may take exponential time or more when recursive function could perform the same job in a linear time or less. So from programming perspectives, it is very handy to use recursion. The second advantage of recursion, it does the job for you, so you do not have to iterate through all of your loops, just simply extract the answer you need. It may look like, if we imagine recursion as tons of minions who do each little work and give you one-done job at the end, when iterative function as Spiderman fighting with all monsters alone.
Thursday, January 23, 2014
SLOG-week3: Object-Oriented Programming
Hello everyone,
To begin with, it is the week 3 since the classes started. Although I can surely say that I have found CSC148 very helpful. If you ask exactly in what way? Well, I have been asking myself " what is really exciting about being a programmer "! I think, everyone agrees for that moment. And that moment is when your code is not working, which you are on to solve for so long hours, is finally get worked. And sometimes you do not know how, but it works. At that times, I feel so happy and feel the pleasure of fulfilment about what you are doing.
On the other hand, the good thing is you can always get a help when you are stuck, For that I like Piazza. For example, for my exercise 1, I found Piazza very helpful, especially, when I misunderstood an auto marking report. Moreover, for exercise 1, I found labs very very helpful when I did not know how to even start it. The thing is during lectures I may not pay attention or understand a topic right away, but with labs it comes more clear. For instance, when we started covering "Classes", I was not that comfortable with classes and constructing it for exercise 1. After the lab, I felt myself less nervous about class.
Subscribe to:
Posts (Atom)