Data Structure, second semester 2013

News & Announcement

  • 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.
  • C++ Tutorial is at
  • The reference to STL container is at
  • Slides of all lectures by Aj. Somchai is at

The Source code

Here are the source code of the data structure used in this class, along with its testing code.

Lecture Log

  • (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.
  • Hello, World
  • BMI
  • Time
  • (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-04) no class
  • (2013-11-06) also no class
  • (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-20) Queue. The Application of Queue in Radix Sort. The M3D2 problem. The code is here
  • (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.
  • Example 4 The last method of sorting, Using a comparator class in std::map
  • 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 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 [email protected] .
  • (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-16) Implementation of the vector class. The source code is here
  • (2013-12-18) Implementation of the stack class and the queue class. The source code is here and here
  • (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.
  • (2013-01-08) Asymptotic Notation (Big-Oh, Big-Omega, etc...)
  • (2014-01-13) and (2014-01-15) No class again... Political turmoil around the Campus. We will have video lecture instead. Check these videos for Binary Heap. video1, video2, video3. The source code for the priority_queue is here
  • (2014-01-20) and (2014-01-22) No class yet again... National University Sport Game.
  • (2014-01-27) Hash Table, CP::unordered_map.
  • (2014-01-29) Hash Table (cont.) The source code for the unordered_map is here
  • (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 reverse(); Check this detail
  • void remove (const value_type& val); check this detail
  • void unique(); Check this detail
  • 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-17) Summary of all data structure in the class, Binary Search Tree. The code is here
  • (2014-02-19) More on Binary Search Tree.
  • (2014-02-24) AVL Tree, the concept.
  • (2014-02-26) AVL Tree, imeplementation. The code is here


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.

Designing a class

Template related