exercise code

refer to your year1 structure programming book

1. pg 121 . create a new function that calculates the difference of 2 numbers

2a. pg 146. modify the code to use a vector instead of an array.
2.b. pass by reference the vector to a new function to add 5 into each elements of the vector. Cout the vector in the main() to verify the value.

[DSA] binary tree

terminology
the root: the beginning of a tree.

every node is possibly the root node for the nodes below it. eg. the parent node.

parent node, the n-1 lvl of the n's lvl node.
child node, the n+1 lvl of the n's lvl node.

(n-1)
|
___n____
| |
(n+1) (n+1)

edge, the path for traversal to happend.
leaves, the lowest lvl in the tree.

a binary tree, a tree where each parent node only have 2 children.

binary search tree (BST)

a binary tree, where the root node is always the middle value of the list of values.

remember binary search from previous week?
what are the 2 possible condition to be satisfied before one can qualify for binary search?

BST it self is not efficient. there is a possibility that the insertion of the node will cause it to behave like a worst case binary tree.

we need a sorted BST, where each time a node is inserted the tree is "sorted" to find out which is the new node. What are the implications if the tree are always sorted when insertion or deletion is done??? Is there any other possible way to enhance it?

3 ways for tree traversal
-Inorder
Traverse the left subtree
Visit the current parent
Traverse the right subtree

-Preorder
Visit the current parent
Traverse the left subtree
Traverse the right subtree

-Postorder
Traverse the left subtree
Traverse the right subtree
Visit the current parent


uses of binary tree data structure
- compression
- encoding
- conversion of mathematical formula to prefix or post fix form
- data structure of choice for "fast" retrieval of search items

there are many other type of binary tree
full binary tree
perfect binary tree
balanced binary tree
self balancing binary tree

[DSA] map and set container

map<string,int> mapp;
map<string,int>::iterator mit;
string name_search;

    mapp.insert(map<string,int>::value_type("Amy",81377442));
    mapp.insert(map<string,int>::value_type("Bob",32731631));
    mapp.insert(map<string,int>::value_type("Catherine",32387163));
    mapp.insert(map<string,int>::value_type("Danny",21321312));
    mapp.insert(map<string,int>::value_type("Ecuador",54543947));
    mapp.insert(map<string,int>::value_type("Felicia",32535612));
    mapp.insert(map<string,int>::value_type("Genie",24172312));



refer to above on how the map data structure is used.


use the map data structure to satisfy the following requirements.
1. create a phone book application that can store name and phone number.
1a. perform a display all entry in the phone book.
2. phone number need to that ensure it is 8 numerical digits only.
3. initialize the phone book application with some data.
4. perform a lookup for a random entry in the phone book and display it.

challenge
5. Suggest a method to store address, email and msn address to the phone book that you have already created.
6. what are the advantages and disadvantages of your method??? explain why you choose the design.

[DSA] searching

Have you ever tried to find something in your house/room. Yet can't seems to ever find it. Now, lets not talk about misplacing items out of carelessness. Let's discuss how to "find" items in your wardrobe.

Assume you have your apparels hanging in the wardrobe, how would you "find" your favorite shirt/dress? would you start looking from the left hand side? the right hand side or simply in the middle???

If you find 1 apparel at a time from either direction, that is linear search. The worst case scenario is, you would traverse all your apparels before finding your favourite.

If you have sorted your apparels according to a certain sequence, eg, warm colours to the right and cold colours to the left, you can simply start finding from the middle, then to the left if your favourite falls in the cold colour. This is binary search. searching time can be reduced significantly.

Again, if you do like what i did, simply pile up all my apparels in the wardrobe without sorting/folding/ironing it. "Finding" for a particular item in the wardrobe can be disastrous.

Linear Search => O(N)

Go through the entire array of items to lookup on the searched key. The sequence of items are not sorted.

Best case , the 1st item in the array.

Worst case, the last item in the array.

Average case, traverse for half of the array

Binary Search => O(logN)

Uses a divide and conquer method.

array of items must be sorted first, involves a cost.

L <> root

|---|---|

L---M---R

For any array of 1000000 items, Linear search need 500000 comparison (assume an average case), Binary Search 20 comparison.

Pop Quiz

1. Create a generic code of linear search to take in different data type.

2. Create a Binary Search tht uses recursive method.

3. Use find() or search() from the STL to do a lookup of a string, among many strings stored in the memory

[DSA] Sorting

Here comes the interesting part in algorithms.

Sorting and searching are the crowns in the algorithm topic. So to speak, these are hottt topics for research in computer science world.

Efficiency, cost. Remember???

We will be examining bubble sort, insertion sort, selection sort and merge sort in details. Studying the complexity of the above algorithms, and not forgetting the implementation of the algorithm. Both DIY code and STL.

But Why Bother to Sort?

Here comes the question>>>>>>>>>

1. Implement sort descending for Bubble Sort, Selection Sort, Insertion Sort, STL sort. Use int arrays or vectors to try it out.

2. In our session, we use integer to demonstrate sorting. Is it possible to sort characters, strings, double, objects etc? Use vector or arrays to try it out.

3. Use the sorting algorithm of your choice, sort 10 tropical fruits of your choice.

4. On top of the previous implementation, create a class for fruits with 2 parameter namely int price and string fruitName. Sort the 10 tropical fruits according to fruit name or price. Your implementation should be able to sort both price and fruitName ASC or DESC. A menu might help in here.

5. Lastly, what considerations when we need to ponder when comparing 2 arbitrary Sort Algo A and Sort Algo B. How would we really know that A is better then B ?

There might be more then one implementation of the above sorting algorithm. Below are my flavor for the 3 algorithm. Codes are commented for easy following.

//bubble sort

//insertion sort

//selection sort

//merge sort