Essential

• We will use C++. The IDE is Code::Blocks, it can be downloaded from the official site. You have to grab the "codeblocks-13.12mingw-setup.exe" Version. A local copy is hosted at our Department for faster access.
• C++ Tutorial is at http://www.cplusplus.com/doc/tutorial/. Please read this before the start of the class.
• Slides of all lectures by Aj. Somchai is at http://dl.dropboxusercontent.com/u/36007508/2110211/index.htm
• The updated syllabus is here.

Lecture Log

• (2015-01-05) Introduction to the class and distribution of the syllabus. Introduction to the IDE. We create a simple C++ program. The following problems are given as a homework: BMI, Time After, Find Max, Check Mapping
• (2015-01-07) Intro to C++, basic syntax. C++ uses the same control structure as JAVA. The overall syntax is somewhat different from JAVA. We have learned about function, the parameter passing using by-value and by-reference. Array. We saw the "index out of bound" effect in C++ which is unlike java.
• (2015-01-12) More on C++, we talked about character sequence in C, std::string in C++. We also talked about the usage of STL in the problem of "wordcount". It is shown that, by using STL called std::map, we are able to count the number of unique word much faster than using array.
• (2015-01-14) More on word count. This is our first time in using vector. A usage example of vector is shown. In word count problem, we've shown that vector can handle arbitrarily large array. The library is discussed with the example of using find() to solve word count. We talked more on how C/C++ handles things like index-out-of-about in vector. In-class exercise is to receive input (integers) from keyboard and count how many of them is more/less than the average.
• (2015-01-19 and 2015-01-21) No class, University Sort Game.
• (2015-01-26) 3 more topics of stl are covered. First, we talk about the iterator, using vector::iterator as an example and more discussion on what is vector.begin() and vector.end(). Second, we talked about sort() which is similar in calling to find. It requires a range from first to last and a value to be searched. Finally, we talked about stl::map which is a mapping between a key_type and a mapped_type. A very simple example are given. This includes the usage of iterator of map. It is discussed why + n is allow in vector::iterator but not in map::iterator. In map::iterator, we have to use only the ++.
• (2015-01-28) An exercise of map. We talked about the problem of checking if a given mapping is 1-1 and onto. However, the mapping is given as two vector of domain and codomain which contain possibly repetitive elements. The second part of the lecture is dedicated to the problem of *3/2 and an introduction to queue. We've covered push(), pop() and top().
• (2015-02-02) We've done more programming on std::map<string,int> using map::erase, map::find. An invalidation of iterator is discussed and shown in the example. In class exercise are 1) to write a program that delete a specific member from a map and 2) to write a program that identified the k-th smallest member from the given vector. The intended solution for the student is to use sort(). The problem is shown to be solvable using priority_queue.
• (2015-02-04) Quiz #1
• (2015-02-09) We started to talk about writing our own data structure. The CP::pair data structure is the first one we wrote. There are several concepts about writing a class that are discussed: 1) The #ifndef directive, 2) namespace CP, 3) what is template?, 4) writing a constructor, 5) initialization list. In-class exercise, start from the code of pair.h. and its tester test_pair.cpp. Write another constructor and show that that constructor is called. Also, try to write a constructor that assign value directly to first and second that fails to compile.
• (2015-02-11) The rest of CP::pair. We have more discussion on the constructor, describing the function overloading. Then, we talked about operator overloading with the example of operator=, operator== and operator<. We try using sort with different implementation of operator<. In the second half, we talk about CP::vector where the data is stored in an array defined as a pointer with operator new. The pointer in C, C++ are explained in detail in this lecture. Basically, a pointer store an address of a variable.
• (2015-02-16) The rest of CP::vector, namely, destructor, iterator, etc. We also touch the concept of reference. (in operator[] and .at()
• (2015-02-18) All of CP::stack. We first talked about the application of stack, namely, parenthesis checking, JVM stack for returning address and postfix evaluation. We then proceeded to the implementation of CP::stack which is quite similar to vector. Finally, we showed that it is possible to write a stack that uses vector as internal storage, i.e., delegation class. In class exercise is to start writing a stack class.
• (2015-02-23) CP::queue. In-class exercise is to write a delegation class of queue using vector. Please d/l these files: queue.h test.cpp and make them work.
• (2015-03-11) Introduction to Complexity Analysis using Asymptotic Notation (Big-Oh). We introduce "barometric instruction" and how to measure the growth rate of the time with respect to the size of input. We briefly discussed various asymptotic notation.
• (2015-03-16) Start with in-class exercise to identify barometric instruction of some sample code. We focus more on the calculation of Big-O and Big-Theta.
• (2015-03-18) Start again with another in-class exercise to write a priority queue using simple array. There are various solution resulting in different big-o but most of the solution requires O(n log n) or O(n) in at lease on of the operation. We proceed to the introduction of Binary Heap. Showing that it is conceptually possible to have a priority queue that has O(log N) for push() and pop().
• (2015-03-23) More on Binary Heap. We detailed the actual implementation of the class.
• (2015-03-25) We start with an in-class exercise for a problem similar to "word count" but this time we don't use words, we just want to know if a set of integer of value between [1,1000] as K as its member. Of course we can use vector, set or map but the best solution is to use a bucket. This is the introduction to Hashing. We talk about collision resolution using "separate chaining" and "open addressing".
• (2015-04-08) More on Hash. Download hash.h here.
• (2015-04-18) Revisit the pointer again. This time more in the detail, In class exercise is about pointer.
• (2015-04-20) Finally, we can finished linked list here. We discussed variation of linked list, including singly, double and header/no header and circular/non-circular variants of linked lists.
• (2015-04-22) Make up class. Review on pointer again and then we talked about Binary Tree, Binary Search Tree and AVL tree. In class exercise is more on algorithmic nature of the problem. How to create worst binary search tree, how many permutation of data that creates worst binary search tree.
• (2015-04-25) We look into the code of AVL tree, discussing what is rotation and how it was done.
• (2015-04-27) FINAL QUIZ