We will use C++ as our language. The IDE is Code::Blocks and can be downloaded here. You have to grab the "codeblocks-12.11mingw-setup_user.exe" Version. A local copy is shared here for faster access from CU.
Here are the source code of the data structure used in this class, along with its testing code.
(2013-10-28) We have simple C++ example problems. The file is here. In short, we should be able to write a simple C++ program, using input/output. Basic Loop structure and if-clause.
(2013-10-30) Example of stl, wordcount. Discussion on the impact of data structure. Different data structure gives different speed and implementation detail.
(2013-11-11) Introduction to std::pair. We did array of pair and write a program that rearrange item in an array of pair. Homework! modify this file from array to vector.
(2013-11-13) std::map, iterator, the function find in . Another homework, modify the wordcount program to identify and display the most frequent words. Due date: Monday, Nov 18th.
(2013-11-18) More on pointer and "pass by reference". The effect of "pass by reference" to the speed and parameter value. Discussion on "wordfreq" homework. std::pair with std::vector and another example using std::map. In class ex was to use std::vector::erase to make the content of the vector unique.
(2013-11-25) Custom Sorting example. Operator overloading of > and ().
Example 1 This code shows that we cannot simply use a custom class in sorting without doing anything.
Example 2 This code shows the "Comparator function" and "operator overloading of <"
Example 3 More example of overloading.
In-class exercise: McFinder. An exercise to program to find the nearest McDonalds from the given Latitude and Longitude. The solutions are here.
(2013-11-27) std::priority_queue and the problem of finding the best k value out of n value. The example code is here.
Homework (due 2013-12-04), download the best-bitcoin.zip. In there, you will find mtgoxGBP.csv which is a three-column value of bitcoin exchange rate from Mt. Gox. The columns are the unix timestame, the exchange rate from bitcoin to GBP and the amount of the exchange. Write a program to find the unique date of k best bitcoin exchange transaction. Send the solution to ds.cp.cu@gmail.com .
(2013-12-02) No class, political turmoil in BKK.
(2013-12-04) No class, political turmoil in BKK.
(2013-12-09) Problem session, containAny and removeOdd problem.
Homework (due 2013-12-16) Implementing "reorder" (the detail is here and the starting file is here).
(2013-12-11) Stack, [arenthesis checking, postfix evaluation, infix2posfix, Class in C++, implementation of CP::pair.
(2013-12-23) and (2013-12-25) We have mid-term exam this week. Good luck guys.
(2013-12-30) and (2014-01-01) New year holidays. Happy new year.
(2013-01-06) Measurement of efficiency. Growth rate of functions. Comparison of efficiency between functions.
(2014-01-20) and (2014-01-22) No class yet again... National University Sport Game.
(2014-02-03) Hash Table (cont.) In class exercise: write simple unordered_map. The starting code is here and here. Homework: Due Date Monday 10 Feb, complete the simple hash class as a separate chaining hashtable. The starting code is here. Use this as a testing code.
(2014-02-05) Today we had a quiz #2, Analysis and Priority Queue. After the quiz, we talked about Linked List.
(2014-02-10) More on linked list. The code is here. In class exercise, we did push_front for a doubly linked list.
(2014-02-12) More on linked list. Homework #6, start from the code of list, add the following functions.
void merge (list& x); Check this detail. For merge, it should take times as O(N) where N is the summation of the size of both lists. Remember that both list are already sorted.
(2014-02-19) More on Binary Search Tree.
(2014-02-24) AVL Tree, the concept.
This year, we thread into the world of C++. An elegance world, I must say. All classes we provided have many non-obvious implementations which require clarification. I provide here links to many articles that discusses several question in writing class in C++. Of course, the issues themselves have their own right to be lengthy explained and I will do so when I have more free time. For now, please make do with the following articles.
Defining nested template class, check here for a syntax.