Tuesday, November 23, 2010

[DSA] General Maths Algo

Long long long time ago.....
Programs are written in C++ to solve mathematical problem, not much of user click here and there on the GUI. Mathematical problem can range from calculating relative distance, trajectory etc.

To make life simple, there was "math.h" in C(include math in c++) to help make the calculation. "math.h" alone might not be sufficient to cover each and every possible scenario, hence some programmer do have their custom class to do the math related to their program.

We have studied general maths routine such as converting from decimal to binary (d2b) and at least 2 method to calculate Greatest Common Divisor(GCD). Through the d2b function, we learned how to decompose the "steps" to get the binary from the decimal and translate the "steps" it into code.

The direct application of the GCD I could thought of is the computation of the public key and private key pairs in the RSA algorithm (http://en.wikipedia.org/wiki/RSA). Encryption is as simple as calling a function (java and C++ have the library), but behind the function call, these are the necessary code to calculate the key pairs.

Notice there are 2 possible way of programming the GCD, through the recursive method or the iterative method which we have discussed previously. Is it easier to understand the recursive code then the iterative code???

Below are the questions for the week.
IP address in the form of A.B.C.D, where each octet A,B,C,D range from 0 to 255 in decimal.
1. How many bits each octet hold?
2. What are the "steps" required to convert one octet to binary?
3. Write the function that would convert the IP and gives it equivalence in binary.

note: you could modify from the d2b function, or propose a simpler algorithm based on the characteristic of the IP address's octet

Monday, November 22, 2010

[DSA] Iteration and recursion

Look into the mirror and observe your self. Look into your eyes, you will notice that in your pupil (the dark/blue/green color portion of the eye if you are asian/Caucasian) you can see yourself in it. Now, look into that pupil on the mirror. You will observe yourself again, albeit a scaled version. That is what i call recursion, you will see yourself again and again in your pupil.

Assume that you can see even the smallest detail of yourself through the mirror, notice that there is no end to the vision?

This is not good for recursion in computer science/programming. The program keeps executing recursively, until the system resources run out. So, at least a condition for the recursion to stop must be defined, which what we called the base case.

Anything that is solved iteratively, can be solved recursively.

Fibonacci The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself. Once the formula is established, it is easy to figure out the code.
Fibonacci is a natural candidate for recursion, because it need to use data that are computed before in that particular series. Hence, we need to store this temporary data somewhere. In recursion, temporary data is stored on the stack. 

Drill Questions
1. Write a iteration fuction that calculates 2^n. 2 to the power of n. n being the input from cin.
2. Write a recursive function that calculates 2^n. n being the input from cin.
3. when n is very large, what are the parameters need to take into considerations?
4. What do you observed for the 1. and 2. when n is very large?
5. Is 2^n a natural candidate for recursion??

Sunday, November 21, 2010

[FYP] mini obstacle course

video src from my student's facebook-> sara

if you wonder how to embed facebook video into blogspot. take a look at the code below. simply replace the video id "167054809983605" with your own video from "facebook.com/video/video.php?v=copy_the_id_here"

Monday, November 15, 2010


My favorite quote from Issac Newton "I am Standing on the shoulders of giants" greatly illustrate the idea of STL. Code have been written by other programmers, using the template feature to greatly help other programmers to overcome programming difficulties. I.e, reduce the time from concept to code.

Being a lazy programmer I am (yes I do admit I like to find the easiest and shortest possible way of writing a piece of code), I do not like to reinvent the wheel.

As in write my own custom code that serves the same purpose as those already written/tested/proven best code by the c++ community.

Why make your life suffer when there are already ready code for you to use?

Programming, in general, is the ability to synthesize code to solve real-world problem by making use of available code. Only in the very dire situation (think high security, high accuracy and the need for real time operation), custom code is needed. *read=> proprietary software*
By learning all the basic building blocks of programming such as template, variable passing etc. When one day this dire state occur, YOU have the ability to create the code library to save the day~!

The STL contains three main components:


Containers, as the name suggested is some form of storage for our data.

Iterators, instead of the programmer manually keeping track on 
ALL pointers declared and used (not an easy feat when the code is in the range of >10k lines ), this STL-Iterator helps the programmer to achieve the same objective.

Algorithms, fancy writing some code to solve the question in the math tutorial? Here is the partial solution. You need to piece this building blocks together.

Drill question

1. We have written some code to check whether a given word is a palindrome in the previous week, by using some member functions of the string class. Good work guys. 
Now, use STL containers, iterators to achieve the same objective.

2. Write a phonebook directory that let the user to store
1. first name
2. phone number

(Store some dummy data into the phone book for testing,)
and the ability to "scroll" the phone book

and the ability to "search" for a particular entry in the phone book.

hint: use ready code from

*non-OOP implementation is acceptable for now.*


Thursday, November 11, 2010

Tuesday, November 9, 2010

[DSA] string class

I hope you have enjoyed and learned some "know how" of writing a program from scratch, with our lil' palindrome example.

To make our lives easier, C++ have lots of library for us to choose from
#include < string > is one of them. Take note string and cstring. both are different!

If you check out the book pg260. There is a piece of code that is very similar of what we have done today. It is using CString instead of String.

Drill Question

Write a name generator (star wars name anybody? hehe) software.
1. The software takes in a name for input and
2. think of the "magic" algorithm to generate a "NINJA" name. Or any name modifiers you can think of. Similar to those name generators you have played on facebook. I guess pretty much of everybody have generated at least once.  Code it FREE STYLE ~maybe you want to start by storing 10 sample first name and 10 sample last name. Which gives a 10 to 10 mapping. Easily 100 names~

Append part of your original name to the sample name "randomly".
3. Check out the string member functions attached~

below are the member functions of String. http://www.cplusplus.com/reference/string/string/

Member functions

(constructor) Construct string object (constructor member)
operator= String assignment (public member function)

begin Return iterator to beginning (public member function)
end Return iterator to end (public member function)
rbegin Return reverse iterator to reverse beginning (public member function)
rend Return reverse iterator to reverse end (public member function)

size Return length of string (public member function)
length Return length of string (public member function)
max_size Return maximum size of string (public member function)
resize Resize string (public member function)
capacity Return size of allocated storage (public member function)
reserve Request a change in capacity (public member function)
clear Clear string (public member function)
empty Test if string is empty (public member function)

Element access:
operator[] Get character in string (public member function)
at Get character in string (public member function)

operator+= Append to string (public member function)
append Append to string (public member function)
push_back Append character to string (public member function)
assign Assign content to string (public member function)
insert Insert into string (public member function)
erase Erase characters from string (public member function)
replace Replace part of string (public member function)
copy Copy sequence of characters from string (public member function)
swap Swap contents with another string (public member function)

String operations:
c_str Get C string equivalent (public member function)
data Get string data (public member function)
get_allocator Get allocator (public member function)
find Find content in string (public member function)
rfind Find last occurrence of content in string (public member function)
find_first_of Find character in string (public member function)
find_last_of Find character in string from the end (public member function)
find_first_not_of Find absence of character in string
find_last_not_of Find absence of character in string from the end (public member function)
substr Generate substring (public member function)
compare Compare strings (public member function)

Monday, November 8, 2010

[DSA] template class

Template, as the name suggested is a standard or generic way/form we could use for creating different output. For an example, you would ask for a report template from your senior so that you more or less know how what is expected from you.

One of the benefits of programming through a template, it reduces the effort to recode the same function/class but pass in a different variable type. Our good friend the STL Algorithms is the best example of programming template. Imagine the sort() function need to be rewrite again and again and again for each type of variable...............

I strongly do not advocate of getting report from other people and change it to your name. That is not template nor referencing. It is called plagiarism.

A function template or class template, beside used with primary variable, eg int, char, double. It can be used with data structures too. As usual, it is possible to pass in more then 1 parameter of the same or different variable type to the function template or class template.

reference the code below. NOTE: The Code is NOT COMPLETE you need to fix it before you could use it.

Q1. What does both of the function trying to do??? Is there a way to generalize it without repeating the "same" code?
Q2. Populate the given code with a template function that will double each number stored as elements in the data structure. Is it possible to double a char or a string stored in the data structure??

Q3. Write a template function reverselist() that could take in a list display the content of the list and store the contents of the list on to a stack and later display the content of the stack.
Q4. Is there a more efficient way to create a test for a palindrome????

Tuesday, November 2, 2010

[DSA] File Op

Data need to be saved somewhere. The reason being, if all data are stored in memory and the computer get accidentally turned off. The effect would be epidemic!
Data output using fstream are clear text by default! ENCRYPT any sensitive info before output to file!!!!!

Some text file are delimited in a certain way, for example below.
sample of comma delimited file=> aa,bb,cc
sample of semicol delimited file=>aa;bb;cc

File operations of the program, should be able to read in the lines, and "parse" the input accordingly and stored into the required variable.

This usually happens when legacy software needed an upgrade to the most-IN technology (Programmer Guru Mantra= If it ain't spoil, don't fix it). However, the data are not compatible. One common feature of software, it has the ability to "dump" data out of the system.

As as programmer, we need to write code to extract those that required to the new system. Therefore, we still get to keep our jobs, make ourself valuable.

Regarding on the issue of Out Sourcing to other country. Fret Not. Why would the company would entrust their data to a 3rd party other then their employer? The audit trail of hands dipped into the data would be clearer and easier to trace. Hence the accountability.

With Great monies, comes great responsibilities.

Talking about file IO and security, take a look at the game below.

I played the game when i was still a teenager like most of you. My friend challenged me to complete the game (eg Lvl 99) in the shortest possible time. Few of us, being kiasu (hokkien colloquial for afraid to loose), keep comparing each other's progress. Me, for being me went to my usual corner and gave my friend Lvl99 at the end of the day. Guess how I manage to get it done????

The sample of file operations are in the writescore.cpp and readscore.cpp. Compile and run it to get a feel of how File I/O is done.

Drill Questions
1. Write a program that READS IN records (eg A.txt) that are semicol delimited eg
tom 19 dcpe/2B/01 DSA B+;kelly 18 dcpe/2B/01 DSA A; .....

2. Write a program that WRITE OUT records (eg B.txt) that are semicol delimited eg
tom 19 dcpe/2B/01 DSA B+; kelly 18 dcpe/2B/01 DSA A; ....

3. write a program that reads in Q1 but modifies to comma delimited and output to a new file.

HINT: It is good to have a menu driven system to choose between the options instead of running 2 cpp projects concurrently.

Monday, November 1, 2010

[DSA] Class & Objects

In programming, class is a common topic. No matter is C++ or Java, the same concept on class still applies. Killing N birds with 1 stone.

In programming, objects are end product of a class. Objects represent data that are generalized by the class.

Think of the Class as a cookie cutter, Objects are the cookies, the dough is generic material that all cookie need to use. Each object may have some unique attribute(s), such you would sprinkle some chocolate on the dough to make a chocolate chip cookie or add some almond to it almond cookie. In the generalization point of view (the class pov), it is still cookie. All cookie uses the same dough.

Think about it, I went to eat dim sum http://en.wikipedia.org/wiki/Dim_sum last weekend and realize some of the items taste the same. I wonder they use the class method to make it. I.e generic minced meat to make dim sum of different shapes.

How would data be generalized and yet representable?
For an example, Cats and dogs. Both are mammals. Both have four legs. Does it means that the cat is a dog and vice versa???!!! Sure we can think of some other attribute that differentiates a dog and a cat. dog barks and cat meows.

So we can have a class named pets, we can have data attribute of pet type, pet breed etc. Below is the sample code for inventory I have for the dog class for my imaginary dog kennel.

drill question 1, create a class for a cat shelter? Think of the attribute you can put into the class to represent the data of a cat. Some attributes like owner telephone and address should be set as private, and accompany by the neccesary get and set function.

drill question 2, create bank account objects with classes as specified in DS03 Objects Q3.

Notice from the code I posted, I have to manually track the objects, manually remember what objects I have created and use it.
In programming, the ability to link one topic learned previously to another topic, "mesh" the knowledge together is very important. So to speak.
From data structures , we know that it is convenient to manipulate data in a data structure, and depends on the condition we can choose the best data structure to represent the data. Can we "link" class&objects with data structures?

Refer to the code below,

Drill question 3. Based on the class you have created, can you store the objects in a data structure of your choice???? Think of what are the possible applications for data structures "meshing" with class&objects?
HINT: try to use constructors

below is the code for the SpStudent class in the slides, with my comments