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 http://www.cprogramming.com/tutorial.html
  • The reference to STL container is at http://www.cplusplus.com/reference/stl/
  • Slides of all lectures by Aj. Somchai is at http://dl.dropboxusercontent.com/u/36007508/2110211/index.htm

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 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 [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

Resource

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