Category: Programming

AI

QUANTUM COMPUTING BOOSTS DEEP LEARNING TO TOP LEVEL

 

“This is the beginning of the quantum age of computing and the latest advancement is towards building a universal quantum computer.

“A universal quantum computer, once built, will represent one of the greatest milestones in the history of information technology and has the potential to solve certain problems we couldn’t solve, and will never be able to solve, with today’s classical computers.”

quantum computing is likely to have the biggest impact on industries that are data-rich and time-sensitive. Machine Learning is the main application for quantum computing.

a quantum computer has quantum bits or qubits, which work in a particularly intriguing way. Where a bit can store either a zero or a 1, a qubit can store a zero, a one, both zero and one, or an infinite number of values in between—and be in multiple states (store multiple values) at the same time! If that sounds confusing, think back to light being a particle and a wave at the same time, Schrödinger’s cat being alive and dead, or a car being a bicycle and a bus.

A quantum computer exponentially expands the vocabulary of binary code words by using two spooky principles of quantum physics, namely ‘entanglement’ and ‘superposition’. Qubits can store a 0, a 1, or an arbitrary combination of 0 and 1 at the same time. Multiple qubits can be made in superposition states that have strictly no classical analogue, but constitute legitimate digital code in a quantum computer.

In a quantum computer, each quantum bit of information–or qubit–can therefore be unfixed, a mere probability; this in turn means that in some mysterious way, a qubit can have the value of one or zero simultaneously, a phenomenon called superposition.

And just as a quantum computer can store multiple values at once, so it can process them simultaneously. Instead of working in series, it can work in parallel, doing multiple operations at once.

In theory, a quantum computer could solve in less than a minute problems that it would take a classical computer millennia to solve.

To date, most quantum computers have been more or less successful science experiments. None have harnessed more than 12 qubits, and the problems the machines have solved have been trivial. Quantum computers have been complicated, finicky machines, employing delicate lasers, vacuum pumps, and other exotic machinery to shepherd their qubits.

The world’s fastest supercomputer, China’s Sunway TaihuLight, runs at 93 petaflops (93 quadrillion flops, or around 1017) – but it relies on 10 million processing cores and uses massive amounts of energy.

In comparison, even a small 30-qubit universal quantum computer could, theoretically, run at the equivalent of a classical computer operating at 10 teraflops (10 trillion flops, or 1012

A QUANTUM COMPUTER IS “NOT JUST A ‘FASTER’ COMPUTER, BUT THEY ARE THE EQUIVALENT OF A JET PLANE TO A BICYCLE.”

IBM says “With a quantum computer built of just 50 qubits, none of today’s TOP500 supercomputers could successfully emulate it, reflecting the tremendous potential of this technology,” .

A screenshot of IBM’s the author attempting to quantum compute. (courtesy : Silicon)

 

 

 

 

QUANTUM COMPUTING TIMELINE

The significant advance, by a team at the University of New South Wales (UNSW) in Sydney appears today in the international journal Nature.

“What we have is a game changer,” said team leader Andrew Dzurak, Scientia Professor and Director of the Australian National Fabrication Facility at UNSW.

“We’ve demonstrated a two-qubit logic gate – the central building block of a quantum computer – and, significantly, done it in silicon. Because we use essentially the same device technology as existing computer chips, we believe it will be much easier to manufacture a full-scale processor chip than for any of the leading designs, which rely on more exotic technologies.

“This makes the building of a quantum computer much more feasible, since it is based on the same manufacturing technology as today’s computer industry,” he added.

 

The benefits of quantum computing

quantum computers could be used for discovering new drugs, securing the internet, modeling the economy, or potentially even building far more powerful artificial intelligence systems—all sorts of exceedingly complicated tasks.

A functional quantum computer will provide much faster computation in a number of key areas, including: searching large databases, solving complicated sets of equations, and modelling atomic systems such as biological molecules and drugs. This means they’ll be enormously useful for finance and healthcare industries, and for government, security and defence organisations.

For example, they could be used to identify and develop new medicines by greatly accelerating the computer-aided design of pharmaceutical compounds (and minimizing lengthy trial and error testing); develop new, lighter and stronger materials spanning consumer electronics to aircraft; and achieve much faster information searching through large databases.

Functional quantum computers will also open the door for new types of computational applications and solutions that are probably too premature to even conceive.

The fusion of quantum computing and machine learning has become a booming research area. Can it possibly live up to its high expectations?

“These advantages that you end up seeing, they’re modest; they’re not exponential, but they are quadratic,” said Nathan Wiebe, a quantum-computing researcher at Microsoft Research. “Given a big enough and fast enough quantum computer, we could revolutionize many areas of machine learning.” And in the course of using the systems, computer scientists might solve the theoretical puzzle of whether they are inherently faster, and for what.

A recent Fortune essay states, “Companies like Microsoft, Google and IBM are making rapid breakthroughs that could make quantum computing viable in less than 10 years.”

Very soon you will find hardware and software with fundamentally new integrated circuits that store and process quantum information. Many important computational problems will only be solved by building quantum computers. Quantum computing has been picking up the momentum, and there are many startups and scholars discussing quantum machine learning. A basic knowledge of quantum two-level computation ought to be acquired.

I am sure that Quantum Information and Quantum Computation will play a crucial role in defining where the course of our technology is headed.

“For quantum computing to take traction and blossom, we must enable the world to use and to learn it,” said Gambetta. “This period is for the world of scientists and industry to focus on getting quantum-ready.”

The Era of Quantum Computing Is Here.

Generics

Algorithms FAQs Part 1.

The following are the list of most important FAQs of Algorithms and Data Structures used in most of the programming languages. To improve your




coding skills every programmer has to know the how to implement Algorithms and Data structures in his application.

1. What is an algorithm?
The process of providing solution to a problem is a sequence of steps is called an algorithm.

 

2. What are the properties of an algorithm?  

An algorithm must possess the following properties:
a. It should get input data.
b. It should produce output.
c. The algorithm should terminate.
d. Algorithm should be clear to understand.
e. It should be easy to perform.

3. What are the types of algorithms?
Algorithms are of two types: iterative and recursive algorithms.

4. Define iterative algorithms.
Algorithms which use loops and conditions to solve the problem are called iterative algorithms.

5. Define recursive algorithms.
Algorithms which perform the recursive steps in a divide and conquer method are called recursive algorithms.

6. What is an array?
An array is a sequential collection of same kind of data elements.

7. What is a data structure?

A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.

8. Name the areas of application of data structures.

The following are the areas of application of data structures:

a. Compiler design
b. Operating system
c. Statistical analysis package
d. DBMS
e. Numerical analysis
f. Simulation
g. Artificial Intelligence
h. Graphics

9. What are the major data structures used in the following areas: Network data model, Hierarchical data model, and RDBMS?

The major data structures used in the above areas are:
Network data model – Graph
Hierarchical data model – Trees
RDBMS – Array

10. What are the types of data structures?
Data structures are of two types: Linear and non linear data structures.

11. What is a linear data structure?
If the elements of a data structure are stored sequentially, then it is a linear data structure.

12. What is non linear data structure?
If the elements of a data structure are not stored in sequential order, then it is a non linear data structure.

13. What are the types of array operations?

The following are the operations which can be performed on an array:
Insertion, Deletion, Search, Sorting, Merging, Reversing and Traversal.

14. What is a matrix?
An array of two dimensions is called a matrix.

15. What are the types of matrix operations?

The following are the types of matrix operations:
Addition, multiplication, transposition, finding determinant of square matrix, subtraction, checking whether it is singular matrix or not etc.

16.  What is the condition to be checked for the multiplication of two matrices?
If matrices are to be multiplied, the number of columns of first matrix should be equal to the number of rows of second matrix.

 

17.  Write the syntax for multiplication of matrices?Syntax:
for (=0; < value;++)
{
for (=0; < value;++)
{
for (=0; < value;++)
{
arr[var1][var2] += arr[var1][var3] * arr[var3][arr2];
}
}
}

 

18.  What is a string?
A sequential array of characters is called a string.

19.  What is use terminating null character?
Null character is used to check the end of string.

20.  What is an empty string?
A string with zero character is called an empty string.

21.  What are the operations that can be performed on a string?
The following are the operations that can be performed on a string:
finding the length of string, copying string, string comparison, string concatenation, finding substrings etc.

22.  What is Brute Force algorithm?
Algorithm used to search the contents by comparing each element of array is called Brute Force algorithm.

23.  What are the limitations of arrays?
The following are the limitations of arrays:
Arrays are of fixed size.
Data elements are stored in continuous memory locations which may not be available always.
Adding and removing of elements is problematic because of shifting the locations.

24.  How can you overcome the limitations of arrays?
Limitations of arrays can be solved by using the linked list.

25.  What is a linked list?
Linked list is a data structure which store same kind of data elements but not in continuous memory locations and size is not fixed. The linked lists are related logically.

26.  What is the difference between an array and a linked list?
The size of an array is fixed whereas size of linked list is variable. In array the data elements are stored in continuous memory locations but in linked list it is non continuous memory locations. Addition, removal of data is easy in linked list whereas in arrays it is complicated.

27.  What is a node?
The data element of a linked list is called a node.

28.  What does node consist of?
Node consists of two fields:
data field to store the element and link field to store the address of the next node.

29.  Write the syntax of node creation?

Syntax:
struct node
{
data type ;
node *ptr; //pointer for link node
}temp;

 

30.  Write the syntax for pointing to next node?Syntax:
node->link=node1;

32.  What is a data structure? What are the types of data structures? Briefly explain them

The scheme of organizing related information is known as ‘data structure’. The types of data structure are:

Lists: A group of similar items with connectivity to the previous or/and next data items.
Arrays: A set of homogeneous values
Records: A set of fields, where each field consists of data belongs to one data type.
Trees: A data structure where the data is organized in a hierarchical structure. This type of data structure follows the sorted order of insertion, deletion and modification of data items.
Tables: Data is persisted in the form of rows and columns. These are similar to records, where the result or manipulation of data is reflected for the whole table.

33.  Define a linear and non linear data structure.

Linear data structure: A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. Ex: Arrays, Linked Lists

Non-Linear data structure: Every data item is attached to several other data items in a way that is specific for reflecting relationships. The data items are not arranged in a sequential structure. Ex: Trees, Graphs

34.  Define in brief an array. What are the types of array operations?

An array is a set of homogeneous elements. Every element is referred by an index.

Arrays are used for storing the data until the application expires in the main memory of the computer system. So that, the elements can be accessed at any time. The operations are:

– Adding elements
– Sorting elements
– Searching elements
– Re-arranging the elements
– Performing matrix operations
– Pre-fix and post-fix operations

35.  What is a matrix? Explain its uses with an example

A matrix is a representation of certain rows and columns, to persist homogeneous data. It can also be called as double-dimensioned array.

Uses:
– To represent class hierarchy using Boolean square matrix
– For data encryption and decryption
– To represent  traffic flow and plumbing in a network
– To implement graph theory of node representation

36.  Define an algorithm. What are the properties of an algorithm? What are the types of algorithms?

 

Algorithm: A step by step process to get the solution for a well defined problem.
Properties of an algorithm:

– Should be unambiguous, precise and lucid
– Should provide the correct solutions
– Should have an end point
– The output statements should follow input, process instructions
– The initial statements should be of input statements
– Should have finite number of steps
– Every statement should be definitive

37.  Types of algorithms:

– Simple recursive algorithms. Ex: Searching an element in a list
– Backtracking algorithms Ex: Depth-first recursive search in a tree
– Divide and conquer algorithms. Ex: Quick sort and merge sort
– Dynamic programming algorithms. Ex: Generation of Fibonacci series
– Greedy algorithms Ex: Counting currency
– Branch and bound algorithms. Ex: Travelling salesman (visiting each city once and minimize the total distance travelled)
– Brute force algorithms. Ex: Finding the best path for a travelling salesman
– Randomized algorithms. Ex. Using a random number to choose a pivot in quick sort).

38.  What is an iterative algorithm?

The process of attempting for solving a problem which finds successive approximations for solution, starting from an initial guess. The result of repeated calculations is a sequence of approximate values for the quantities of interest.

39.  What is an recursive algorithm?

Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repetition is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.

40.  Explain quick sort and merge sort algorithms.

Quick sort employs the ‘divide and conquer’ concept by dividing the list of elements into two sub elements.

The process is as follows:

1. Select an element, pivot, from the list.
2. Rearrange the elements in the list, so that all elements those are less than the pivot are arranged before the pivot and all elements those are greater than the pivot are arranged after the pivot. Now the pivot is in its position.
3. Sort the both sub lists – sub list of the elements which are less than the pivot and the list of elements which are more than the pivot recursively.

41.  Merge Sort: A comparison based sorting algorithm. The input order is preserved in the sorted output.

Merge Sort algorithm is as follows:

1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Otherwise divide the unsorted list into two lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, merge  both the lists back into one sorted list.

42.  What is Bubble Sort and Quick sort?

Bubble Sort: The simplest sorting algorithm. It involves the sorting the list in a repetitive fashion. It compares two adjacent elements in the list, and swaps them if they are not in the designated order. It continues until there are no swaps needed. This is the signal for the list that is sorted. It is also called as comparison sort as it uses comparisons.

Quick Sort: The best sorting algorithm which implements the ‘divide and conquer’ concept. It first divides the list into two parts by picking an element a ‘pivot’. It then arranges the elements those are smaller than pivot into one sub list and the elements those are greater than pivot into one sub list by keeping the pivot in its original place.

43.  What are the difference between a stack and a Queue?

Stack – Represents the collection of elements in Last In First Out order.
Operations includes testing null stack, finding the top element in the stack, removal of top most element and adding elements on the top of the stack.

Queue – Represents the collection of elements in First In First Out order.

Operations include testing null queue, finding the next element, removal of elements and inserting the elements from the queue.

Insertion of elements is at the end of the queue

Deletion of elements is from the beginning of the queue.

44.  Can a stack be described as a pointer? Explain.

A stack is represented as a pointer. The reason is that, it has a head pointer which points to the top of the stack. The stack operations are performed using the head pointer. Hence, the stack can be described as a pointer.

45.  Explain the terms Base case, Recursive case, Binding Time, Run-Time Stack and Tail Recursion.

Base case: A case in recursion, in which the answer is known when the termination for a recursive condition is to unwind back.

Recursive Case: A case which returns to the answer which is closer.

Run-time Stack: A run time stack used for saving the frame stack of a function when every recursion or every call occurs.

Tail Recursion: It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.

46.  Is it possible to insert different type of elements in a stack? How?

Different elements can be inserted into a stack. This is possible by implementing union / structure data type. It is efficient to use union rather than structure, as only one item’s memory is used at a time.

47.  Explain in brief a linked list.

A linked list is a dynamic data structure. It consists of a sequence of data elements and a reference to the next element in the sequence. Stacks, queues, hash tables, linear equations, prefix and post fix operations. The order of linked items is different that of arrays. The insertion or deletion operations are constant in number.

48.  Explain the types of linked lists.

The types of linked lists are:

Singly linked list: It has only head part and corresponding references to the next nodes.

Doubly linked list: A linked list which both has head and tail parts, thus allowing the traversal in bi-directional fashion. Except the first node, the head node refers to the previous node.

Circular linked list: A linked list whose last node has reference to the first node.

49.  How would you sort a linked list?

Step 1: Compare the current node in the unsorted list with every element in the rest of the list. If the current element is more than any other element go to step 2 otherwise go to step 3.

Step 2: Position the element with higher value after the position of the current element. Compare the next element. Go to step1 if an element exists, else stop the process.

Step 3: If the list is already in sorted order, insert the current node at the end of the list. Compare the next element, if any and go to step 1 or quit.

 

50.  What is sequential search? What is the average number of comparisons in a sequential search?

 

Sequential search: Searching an element in an array, the search starts from the first element till the last element.

The average number of comparisons in a sequential search is (N+1)/2 where N is the size of the array. If the element is in the 1st position, the number of comparisons will be 1 and if the element is in the last position, the number of comparisons will be N.

51.  What are binary search and Fibonacci search?

Binary Search: Binary search is the process of locating an element in a sorted list. The search starts by dividing the list into two parts. The algorithm compares the median value. If the search element is less than the median value, the top list only will be searched, after finding the middle element of that list. The process continues until the element is found or the search in the top list is completed. The same process is continued for the bottom list, until the element is found or the search in the bottom list is completed. If an element is found that must be the median value.

52.  Define Fibonacci Search: Fibonacci search is a process of searching a sorted array by utilising divide and conquer algorithm. Fibonacci search examines locations whose addresses have lower dispersion. When the search element has non-uniform access memory storage, the Fibonacci search algorithm reduces the average time needed for accessing a storage location.

Generics

Algorithms FAQs Part 2.

What is linear search?

Answer: Linear search is the simplest form of search. It searches for the element sequentially starting from the first element. This search has a disadvantage if the element is located at the end. Advantage lies in the simplicity of the search. Also it is most useful when the elements are arranged in a random order.

What is binary search?  

Answer: Binary search is most useful when the list is sorted. In binary search, element present in the middle of the list is determined. If the key (number to search) is smaller than the middle element, the binary search is done on the first half. If the key (number to search) is greater than the middle element, the binary search is done on the second half (right). The first and the last half are again divided into two by determining the middle element.

Explain the bubble sort algorithm.

Answer: Bubble sort algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at a time and swaps them if they are in wrong order. This process is repeated until no swapping is needed. The algorithm is very inefficient if the list is long.

E.g. List: – 7 4 5 3
1. 7 and 4 are compared

2. Since 4 < 7, 4 is stored in a temporary variable.

3. the content of 7 is now stored in the variable which was holding 4

4. Now, the content of temporary variable and the variable previously holding 7 are swapped.

What is quick sort?  

Answer: Quick sort is one the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are portioned or divided such that elements less than the pivot point are in left and those greater than the pivot are on the right. Now, the elements on the left and right can be recursively sorted by repeating the algorithm.

Describe Trees using C++ with an example.

Tree is a structure that is similar to linked list. A tree will have two nodes that point to the left part of the tree and the right part of the tree. These two nodes must be of the similar type.

The following code snippet describes the declaration of trees. The advantage of trees is that the data is placed in nodes in sorted order.

struct TreeNode
{
int item; // The data in this node.
TreeNode *left; // Pointer to the left subtree.
TreeNode *right; // Pointer to the right subtree.
}

The following code snippet illustrates the display of tree data.

void showTree( TreeNode *root )
{
if ( root != NULL ) { // (Otherwise, there’s nothing to print.)
showTree(root->left); // Print items in left sub tree.
cout << root->item << ” “; // Print the root item.
showTree(root->right ); // Print items in right sub tree.
}
} // end inorderPrint()

Data Structure trees – posted on August 03, 2008 at 22:30 PM by Amit Satpute

Question – What is a B tree?

Answer: A B-tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties :

1. Every node has <= m children.
2. Every node (except root and leaves) has >= m/2 children.
3. The root has at least 2 children.
4. All leaves appear in the same level, and carry no information.
5. A non-leaf node with k children contains k – 1 keys

Question – What are splay trees?

Answer: A splay tree is a self-balancing binary search tree. In this, recently accessed elements are quick to access again

It is useful for implementing caches and garbage collection algorithms.

When we move left going down this path, its called a zig and when we move right, its a zag.

Following are the splaying steps. There are six different splaying steps.
1. Zig Rotation (Right Rotation)
2. Zag Rotation (Left Rotation)
3. Zig-Zag (Zig followed by Zag)
4. Zag-Zig (Zag followed by Zig)
5. Zig-Zig
6. Zag-Zag

Question – What are red-black trees?

Answer :A red-black tree is a type of self-balancing binary search tree.
In red-black trees, the leaf nodes are not relevant and do not contain data.
Red-black trees, like all binary search trees, allow efficient in-order traversal of elements.
Each node has a color attribute, the value of which is either red or black.

Characteristics:
The root and leaves are black
Both children of every red node are black.
Every simple path from a node to a descendant leaf contains the same number of black nodes, either counting or not counting the null black nodes

Question – What are threaded binary trees?

Answer: In a threaded binary tree, if a node ‘A’ has a right child ‘B’ then B’s left pointer must be either a child, or a thread back to A.

In the case of a left child, that left child must also have a left child or a thread back to A, and so we can follow B’s left children until we find a thread, pointing back to A.

This data structure is useful when stack memory is less and using this tree the treversal around the tree becomes faster.

Question – What is a B+ tree?

Answer: It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment. all records are stored at the lowest level of the tree; only keys are stored in interior blocks.

Describe Tree database. Explain its common uses.

A tree is a data structure which resembles a hierarchical tree structure. Every element in the structure is a node. Every node is linked with the next node, either to its left or to its right. Each node has zero or more child nodes. The length of the longest downward path to a leaf from that node is known as the height of the node and the length of the path to its root is known as the depth of a node.

Common Uses:

– To manipulate hierarchical data
– Makes the information search, called tree traversal, easier.
– To manipulate data that is in the form of sorted list.

What is binary tree? Explain its uses.

A binary tree is a tree structure, in which each node has only two child nodes. The first node is known as root node. The parent has two nodes namely left child and right child.

Uses of binary tree:

– To create sorting routine.
– Persisting data items for the purpose of fast lookup later.
– For inserting a new item faster

How do you find the depth of a binary tree?

The depth of a binary tree is found using the following process:

1. Send the root node of a binary tree to a function
2. If the tree node is null, then return false value.
3. Calculate the depth of the left tree; call it ‘d1’ by traversing every node. Increment the counter by 1, as the traversing progresses until it reaches the leaf node. These operations are done recursively.
4. Repeat the 3rd step for the left node. Name the counter variable ‘d2’.
5. Find the maximum value between d1 and d2. Add 1 to the max value. Let us call it ‘depth’.
6. The variable ‘depth’ is the depth of the binary tree.

Explain pre-order and in-order tree traversal.

A non-empty binary tree is traversed in 3 types, namely pre-order, in-order and post-order in a recursive fashion.

Pre-order:
Pre-order process is as follows:

– Visit the root node
– Traverse the left sub tree
– Traverse the right sub tree

In-Order:
In order process is as follows:
– Traverse the left sub tree
– Visit the root node
– Traverse the right sub tree

What is a B+ tree? Explain its uses.

B+ tree represents the way of insertion, retrieval and removal of the nodes in a sorted fashion. Every operation is identified by a ‘key’. B+ tree has maximum and minimum bounds on the number of keys in each index segment, dynamically. All the records in a B+ tree are persisted at the last level, i.e., leaf level in the order of keys.

B+ tree is used to visit the nodes starting from the root to the left or / and right sub tree. Or starting from the first node of the leaf level. A bi directional tree traversal is possible in the B+ tree.

Define threaded binary tree. Explain its common uses

A threaded binary tree is structured in an order that, all right child pointers would normally be null and points to the ‘in-order successor’ of the node. Similarly, all the left child pointers would normally be null and points to the ‘in-order predecessor’ of the node.

Uses of Threaded binary tree:

– Traversal is faster than unthreaded binary trees
– More subtle, by enabling the determination of predecessor and successor nodes that starts from any node, in an efficient manner.
– No stack overload can be carried out with the threads.
– Accessibility of any node from any other node
– It is easy to implement to insertion and deletion from a threaded tree.

Explain implementation of traversal of a binary tree.

Binary tree traversal is a process of visiting each and every node of the tree. The two fundamental binary tree traversals are ‘depth-first’ and ‘breadth-first’.

The depth-first traversal are classified into 3 types, namely, pre-order, in-order and post-order.

Pre-order: Pre-order traversal involves visiting the root node first, then traversing the left sub tree and finally the right sub tree.

In-order: In-order traversal involves visiting the left sub tree first, then visiting the root node and finally the right sub tree.

Post-order: Post-order traversal involves visiting the left sub tree first, then visiting the right sub tree and finally visiting the root node.

The breadth-first traversal is the ‘level-order traversal’. The level-order traversal does not follow the branches of the tree. The first-in first-out queue is needed to traversal in level-order traversal.

Explain implementation of deletion from a binary tree.

To implement the deletion from a binary tree, there is a need to consider the possibilities of deleting the nodes. They are:

– Node is a terminal node: In case the node is the left child node of its parent, then the left pointer of its parent is set to NULL. In all other cases, if the node is right child node of its parent, then the right pointer of its parent is set to NULL.

– Node has only one child: In this scenario, the appropriate pointer of its parent is set to child node.

– Node has two children: The predecessor is replaced by the node value, and then the predecessor of the node is deleted.

 

Describe stack operation. 

Stack is a data structure that follows Last in First out strategy.

Stack Operations:-

�  Push – Pushes (inserts) the element in the stack. The location is specified by the pointer.

�  Pop – Pulls (removes) the element out of the stack. The location is specified by the pointer

�  Swap: – the two top most elements of the stack can be swapped

�  Peek: – Returns the top element on the stack but does not remove it from the stack

�  Rotate:- the topmost (n) items can be moved on the stack in a rotating fashion

A stack has a fixed location in the memory. When a data element is pushed in the stack, the pointer points to the current element.

Describe queue operation.

Queue is a data structure that follows First in First out strategy.

Queue Operations:

�  Enqueue- Inserts the element in the queue at the end.

�  Dequeue – removes the element out of the queue from the front

�  Size – Returns the size of the queue

�  Front – Returns the first element of the queue.

�  Empty – to find if the queue is empty.

Discuss how to implement queue using stack.
A queue can be implemented by using 2 stacks:-

�  1. An element is inserted in the queue by pushing it into stack 1

�  2. An element is extracted from the queue by popping it from the stack 2

�  3. If the stack 2 is empty then all elements currently in stack 1 are transferred to stack 2 but in the reverse order

�  4. If the stack 2 is not empty just pop the value from stack 2.

Explain stacks and queues in detail.

A stack is a data structure based on the principle Last In First Out. Stack is container to hold nodes and has two operations – push and pop. Push operation is to add nodes into the stack and pop operation is to delete nodes from the stack and returns the top most node.

A queue is a data structure based on the principle First in First Out. The nodes are kept in an order. A node is inserted from the rear of the queue and a node is deleted from the front. The first element inserted in the first element first to delete.

Question – What are priority queues?
A priority queue is essentially a list of items in which each item is associated with a priority
Items are inserted into a priority queue in any, arbitrary order. However, items are withdrawn from a priority queue in order of their priorities starting with the highest priority item first.

Priority queues are often used in the implementation of algorithms

Question – What is a circular singly linked list?
In a circular singly linked list, the last node of the list is made to point to the first node. This eases the traveling through the list..

Describe the steps to insert data into a singly linked list.
Steps to insert data into a singly linked list:-

Insert in middle
Data: 1, 2, 3, 5
1. Locate the node after which a new node (say 4) needs to be inserted.(say after 3)

2. create the new node i.e. 4

3. Point the new node 4 to 5 (new_node->next = node->next(5))

4. Point the node 3 to node 4 (node->next =newnode)

Insert in the beginning

Data: 2, 3, 5

1. Locate the first node in the list (2)

2. Point the new node (say 1) to the first node. (new_node->next=first)

Insert in the end

Data: 2, 3, 5

1. Locate the last node in the list (5)

2. Point the last node (5) to the new node (say 6). (node->next=new_node)

Explain how to reverse singly link list.

Answer: Reverse a singly link list using iteration:-

1. First, set a pointer ( *current) to point to the first node i.e. current=base

2. Move ahead until current!=null (till the end)

3. set another pointer (* next) to point to the next node i.e. next=current->next

4. store reference of *next in a temporary variable ( *result) i.e current->next=result

5. swap the result value with current i.e. result=current

6. and now swap the current value with next. i.e. current=next

7. return result and repeat from step 2

A linked list can also be reversed using recursion which eliminates the use of a temporary variable.

Define circular linked list.

Answer: In a circular linked list the first and the last node are linked. This means that the last node points to the first node in the list. Circular linked list allow quick access to first and last record using a single pointer.

Describe linked list using C++ with an example.

A linked list is a chain of nodes. Each and every node has at least two nodes, one is the data and other is the link to the next node. These linked lists are known as single linked lists as they have only one pointer to point to the next node. If a linked list has two nodes, one is to point to the previous node and the other is to point to the next node, then the linked list is known as doubly linked list.

To use a linked list in C++ the following structure is to be declared:

 

typedef struct List
{

long Data;
List* Next;
List ()
{

Next=NULL;
Data=0;
}

};
typedef List* ListPtr.

The following code snippet is used to add a node.

void List::AddANode()
{

ListPtr->Next = new List;
ListPtr=ListPtr->Next;

}

The following code snippet is used to traverse the list

void showList(ListPtr listPtr)
{
� while(listPtr!=NULL) {
cout<<listPtr->Data;
}
return temp;
}

 

 

/ / LListItr class; maintains “current position”.

/ I

/ / CONSTRUCTION: With no parameters. The LList class may

/ / construct a LListItr with a pointer to a LListNode.

/ /

/ / ******************PUBLOIPCE RATIONS*********************

/ / boo1 isValid( j –> True if not NULL

/ / void advance ( j –> Advance (if not already NULL)

/ / Object retrieve( ) –> Return item in current position

/ / ******************ERRORS********************************

/ / Throws BadIterator for illegal retrieve.

 

template <class Object>

class LListItr

{

public:

LListItr( ) : current( NULL ) { 1

 

boo1 isValid( j const

{ return current ! = NULL; )

 

void advance ( j

{ if( isValid( j j current = current->next; 1

 

const Object & retrieve( ) const

{ if( !isValid( j j throw BadIterator( ) ;

return current->element; }

 

private:

LListNode<Object> *current; / / Current position

 

LListItr( LListNode<Object> *theNode )

: current ( theNode ) {

 

friend class LList<Object>; / / Grant access to constructor

};

 

 

 

/ / LList class.

/ /

/ / CONSTRUCTION: with no initializer.

/ / Access is via LListItr class.

/ /

/ / ******************PUBLIoC~ ERATIoNs******************X**

/ / boo1 isEmpty( ) –> Return true if empty; else false

/ / void makeEmpty( ) –> Remove all items

/ / LListItr zeroth( ) –> Return position to prior to first

10 / / LListItr first( ) –> Return first position

11 / / void insert( x, p ) –> Insert x after position p

12 / / void remove( x ) –> Remove x

13 / / LListItr find( x ) –> Return position that views x

14 / / LListItr findprevious( x )

15 / / –> Return position prior to x

16 / / ******************ERR~R~*****~****************************

17 / / No special errors.

18

19 template <class Object>

20 class LList

21 I

22 public:

23 LList( ) ;

24 LList( const LList & rhs ) ;

25 -LList( ) ;

26

27 boo1 isEmpty( const;

28 void makeEmpty( ) ;

29 LListItr<Object> zeroth( ) const;

30 LListItr<Object> first ( ) const;

31 void insert( const Object & x, const ~~istItr<Object&> p ) ;

32 LListItr<Object> find( const Object & x ) const;

33 LListItr<Object> findprevious( const Object & x ) const;

34 void remove( const Object & x ) ;

35

36 const LList & operator=( const LList & rhs ) ;

37

38 private:

39 LListNode<Object> *header;

};

 

/ / Construct the list.

template <class Object>

LList<Object>: :LList ( )

{

header = new LListNode<Object>;

1

7

/ / Test if the list is logically empty.

/ / Return true if empty, false, otherwise.

10 template <class Object>

11 boo1 LList<Object>: :isEmpty( ) const

12 {

13 return header->next == NULL;

14 1

15

16 / / Return an iterator representing the header node.

17 template <class Object>

18 LListItr<Object> LList<Object>::zeroth( ) const

19 I

20 return LListItr<Object>( header ) ;

21 1

22

23 / / Return an iterator representing the first node in the list.

24 / / This operation is valid for empty lists.

25 template <class Object>

26 LListItr<Object> LList<Object>::first( ) const

27 {

28 return LListItr<Object>( header->next ) ;

29 };

 

/ / Simple print function.

template <class Object>

void printlist( const LList<Object> & theList )

(

if( theList.isEmptyi ) )

6 cout << “Empty list” << endl;

else

8 }

LListItr<Object> itr = theList.first( ) ;

10 for( ; itr.isValid( ) ; itreadvance( ) )

11 cout << itr.retrieve( ) << ” “;

12 {

13 cout << endl;

14 }

 

/ / Return iterator corresponding to the first node matching x.

/ / Iterator is not valid if item is not found.

template <class Object>

LListItr<Object> LList<Object>::find( const Object & x ) const

{

6 LListNode<Object> *p = header->next;

7

8 while( p ! = NULL && p->element ! = x )

9 p = p->next;

10

11 return LListItr<Object>( p ) ;

12 }

/ / Remove the first occurrence of an item X .

template <class Object>

void LList<Object>::remove( const Object & x

{

LListNode<Object> *p = findprevious( x ) .current;

6

if( p->next ! = NULL )

8 I

LListNode<Object> *oldNode = p->next;

10 p->next = p->next->next; / / Bypass

11 delete oldNode;

12 }

13 1

Figure 17.13 The remove routine for the LList class.

/ / Return iterator prior to the first node containing item x.

template <class Object>

LListItr<Object>

LList<Object>: : f indprevious ( const Object & x ) const

{

LListNode<Object> *p = header;

7

8 while( p-znext ! = NULL && p->next->element ! = x )

p = p->next;

10

11 return LListItr<Object>( p ) ;

12 }

Figure 17.14 The f indprevious routine-similar to the find routine-for use

with remove.

/ / Insert item x after p.

template <class Object>

void LList<Object>::

insert( const Object & x, const LListItr<Object> & p )

{

if ( p.current ! = NULL )

p.current->next = new LListNodecObject>( x,

8 p.current->next ) ;

}

Figure 17.15 The insertion routine for the LList class.

 

/ / Make the list logically empty.

template <class Object>

void LList<Object>: :makeEmpty( )

I

while( !isEmptyi ) )

6 remove ( first ( ) .retrieve ( ) ) ;

1

8

/ / Destructor.

10 template <class Object>

11 LList<Object>::-LList( )

12 (

13 makeErnpty ( ) ;

14 delete header;

15 1

Figure 17.16 The makeEmpty method and the LLis t destructor.

/ / Copy constructor.

template <class Object>

LList<Object>::LList( const LList<Object> & rhs )

{

header = new LListNodeiObject>;

*this = rhs;

}

8

/ / Deep copy of linked lists.

10 template <class Object>

11 const LList<Object> &

12 LList<Object>::operator=( const ~~ist<Object&> rhs i

13 {

14 if ( this ! = &rhs )

15 (

16 makeEmpty ( ) ;

17

18 LListItr<Object> ritr = rhs.first( ) ;

19 LListItr<Object> itr = zeroth( ) ;

20 for( ; ritr.isValid( ) ; ritr.advance( ) , itr.advance( )

21 insert( ritr.retrieve( ) , itr ) ;

22 {

23 return *this;

24 }

Figure 17.17 Two LLis copy routines: operator= and copy constructor.

 

Q: Implement a Algorithm to check if the link list is in Ascending order?

A: template

bool linklist::isAscending() const{

nodeptr ptr = head;

while(ptr->_next)

{

if(ptr->_data > ptr->_next->_data)

return false;

ptr= ptr->_next;

}

return true;

}

 

Q: Write an algorithm to reverse a link list?

A: template

void linklist::reverselist()

{

nodeptr ptr= head;

nodeptr nextptr= ptr->_next;

while(nextptr)

{

nodeptr temp = nextptr->_next;

nextptr->_next = ptr;

ptr = nextptr;

nextptr = temp;

}

head->_next = 0;

head = ptr;

}

Generics

Algorithms FAQs Part 3.

Q: Implement Binary Heap in C++?

A: BinaryHeap.h

————

#ifndef BINARY_HEAP_H_

#define BINARY_HEAP_H_

#include “dsexceptions.h”

#include “vector.h”

// BinaryHeap class

//

// CONSTRUCTION: with an optional capacity (that defaults to 100)

//

// ******************PUBLIC OPERATIONS*********************

// void insert( x ) –> Insert x

// deleteMin( minItem ) –> Remove (and optionally return) smallest item

// Comparable findMin( ) –> Return smallest item

// bool isEmpty( ) –> Return true if empty; else false

// bool isFull( ) –> Return true if full; else false

// void makeEmpty( ) –> Remove all items

// ******************ERRORS********************************

// Throws Underflow and Overflow as warranted

template

class BinaryHeap

{

public:

explicit BinaryHeap( int capacity = 100 );

bool isEmpty( ) const;

bool isFull( ) const;

const Comparable & findMin( ) const;

void insert( const Comparable & x );

void deleteMin( );

void deleteMin( Comparable & minItem );

void makeEmpty( );

private:

int currentSize; // Number of elements in heap

vector array; // The heap array

void buildHeap( );

void percolateDown( int hole );

};

#endif

BinaryHeap.cpp

————–

#include “BinaryHeap.h”

/**

* Construct the binary heap.

* capacity is the capacity of the binary heap.

*/

template

BinaryHeap::BinaryHeap( int capacity )

: array( capacity + 1 ), currentSize( 0 )

{

}

/**

* Insert item x into the priority queue, maintaining heap order.

* Duplicates are allowed.

* Throw Overflow if container is full.

*/

template

void BinaryHeap::insert( const Comparable & x )

{

if( isFull( ) )

throw Overflow( );

// Percolate up

int hole = ++currentSize;

for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )

array[ hole ] = array[ hole / 2 ];

array[ hole ] = x;

}

/**

* Find the smallest item in the priority queue.

* Return the smallest item, or throw Underflow if empty.

*/

template

const Comparable & BinaryHeap::findMin( ) const

{

if( isEmpty( ) )

throw Underflow( );

return array[ 1 ];

}

/**

* Remove the smallest item from the priority queue.

* Throw Underflow if empty.

*/

template

void BinaryHeap::deleteMin( )

{

if( isEmpty( ) )

throw Underflow( );

array[ 1 ] = array[ currentSize– ];

percolateDown( 1 );

}

/**

* Remove the smallest item from the priority queue

* and place it in minItem. Throw Underflow if empty.

*/

template

void BinaryHeap::deleteMin( Comparable & minItem )

{

if( isEmpty( ) )

throw Underflow( );

minItem = array[ 1 ];

array[ 1 ] = array[ currentSize– ];

percolateDown( 1 );

}

/**

* Establish heap order property from an arbitrary

* arrangement of items. Runs in linear time.

*/

template

void BinaryHeap::buildHeap( )

{

for( int i = currentSize / 2; i > 0; i– )

percolateDown( i );

}

/**

* Test if the priority queue is logically empty.

* Return true if empty, false otherwise.

*/

template

bool BinaryHeap::isEmpty( ) const

{

return currentSize == 0;

}

/**

* Test if the priority queue is logically full.

* Return true if full, false otherwise.

*/

template

bool BinaryHeap::isFull( ) const

{

return currentSize == array.size( ) – 1;

}

/**

* Make the priority queue logically empty.

*/

template

void BinaryHeap::makeEmpty( )

{

currentSize = 0;

}

/**

* Internal method to percolate down in the heap.

* hole is the index at which the percolate begins.

*/

template

void BinaryHeap::percolateDown( int hole )

{

/* 1*/ int child;

/* 2*/ Comparable tmp = array[ hole ];

/* 3*/ for( ; hole * 2 <= currentSize; hole = child )

{

/* 4*/ child = hole * 2;

/* 5*/ if( child != currentSize && array[ child + 1 ] < array[ child ] )

/* 6*/ child++;

/* 7*/ if( array[ child ] < tmp )

/* 8*/ array[ hole ] = array[ child ];

else

/* 9*/ break;

}

/*10*/ array[ hole ] = tmp;

}

TestBinaryHeap.cpp

——————

#include

#include “BinaryHeap.h”

#include “dsexceptions.h”

// Test program

int main( )

{

int numItems = 10000;

BinaryHeap h( numItems );

int i = 37;

int x;

try

{

for( i = 37; i != 0; i = ( i + 37 ) % numItems )

h.insert( i );

for( i = 1; i < numItems; i++ )

{

h.deleteMin( x );

if( x != i )

cout << “Oops! ” << i << endl;

}

for( i = 37; i != 0; i = ( i + 37 ) % numItems )

h.insert( i );

h.insert( 0 );

h.insert( i = 999999 ); // Should overflow

}

catch( Overflow )

{ cout << “Overflow (expected)! ” << i << endl; }

return 0;

}

Q: Implement Binary Search Tree in C++?

A: BinarySearchTree.h

———————-

#ifndef BINARY_SEARCH_TREE_H_

#define BINARY_SEARCH_TREE_H_

#include “dsexceptions.h”

#include // For NULL

// Binary node and forward declaration because g++ does

// not understand nested classes.

template

class BinarySearchTree;

template

class BinaryNode

{

Comparable element;

BinaryNode *left;

BinaryNode *right;

BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )

: element( theElement ), left( lt ), right( rt ) { }

friend class BinarySearchTree;

};

// BinarySearchTree class

//

// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds

//

// ******************PUBLIC OPERATIONS*********************

// void insert( x ) –> Insert x

// void remove( x ) –> Remove x

// Comparable find( x ) –> Return item that matches x

// Comparable findMin( ) –> Return smallest item

// Comparable findMax( ) –> Return largest item

// boolean isEmpty( ) –> Return true if empty; else false

// void makeEmpty( ) –> Remove all items

// void printTree( ) –> Print tree in sorted order

template

class BinarySearchTree

{

public:

explicit BinarySearchTree( const Comparable & notFound );

BinarySearchTree( const BinarySearchTree & rhs );

~BinarySearchTree( );

const Comparable & findMin( ) const;

const Comparable & findMax( ) const;

const Comparable & find( const Comparable & x ) const;

bool isEmpty( ) const;

void printTree( ) const;

void makeEmpty( );

void insert( const Comparable & x );

void remove( const Comparable & x );

const BinarySearchTree & operator=( const BinarySearchTree & rhs );

private:

BinaryNode *root;

const Comparable ITEM_NOT_FOUND;

const Comparable & elementAt( BinaryNode *t ) const;

void insert( const Comparable & x, BinaryNode * & t ) const;

void remove( const Comparable & x, BinaryNode * & t ) const;

BinaryNode * findMin( BinaryNode *t ) const;

BinaryNode * findMax( BinaryNode *t ) const;

BinaryNode * find( const Comparable & x, BinaryNode *t ) const;

void makeEmpty( BinaryNode * & t ) const;

void printTree( BinaryNode *t ) const;

BinaryNode * clone( BinaryNode *t ) const;

};

#endif

BinarySearchTree.cpp

——————–

#include “BinarySearchTree.h”

#include

/**

* Implements an unbalanced binary search tree.

* Note that all “matching” is based on the < method.

*/

/**

* Construct the tree.

*/

template

BinarySearchTree::BinarySearchTree( const Comparable & notFound ) :

root( NULL ), ITEM_NOT_FOUND( notFound )

{

}

/**

* Copy constructor.

*/

template

BinarySearchTree::

BinarySearchTree( const BinarySearchTree & rhs ) :

root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )

{

*this = rhs;

}

/**

* Destructor for the tree.

*/

template

BinarySearchTree::~BinarySearchTree( )

{

makeEmpty( );

}

/**

* Insert x into the tree; duplicates are ignored.

*/

template

void BinarySearchTree::insert( const Comparable & x )

{

insert( x, root );

}

/**

* Remove x from the tree. Nothing is done if x is not found.

*/

template

void BinarySearchTree::remove( const Comparable & x )

{

remove( x, root );

}

/**

* Find the smallest item in the tree.

* Return smallest item or ITEM_NOT_FOUND if empty.

*/

template

const Comparable & BinarySearchTree::findMin( ) const

{

return elementAt( findMin( root ) );

}

/**

* Find the largest item in the tree.

* Return the largest item of ITEM_NOT_FOUND if empty.

*/

template

const Comparable & BinarySearchTree::findMax( ) const

{

return elementAt( findMax( root ) );

}

/**

* Find item x in the tree.

* Return the matching item or ITEM_NOT_FOUND if not found.

*/

template

const Comparable & BinarySearchTree::

find( const Comparable & x ) const

{

return elementAt( find( x, root ) );

}

/**

* Make the tree logically empty.

*/

template

void BinarySearchTree::makeEmpty( )

{

makeEmpty( root );

}

/**

* Test if the tree is logically empty.

* Return true if empty, false otherwise.

*/

template

bool BinarySearchTree::isEmpty( ) const

{

return root == NULL;

}

/**

* Print the tree contents in sorted order.

*/

template

void BinarySearchTree::printTree( ) const

{

if( isEmpty( ) )

cout << “Empty tree” << endl;

else

printTree( root );

}

/**

* Deep copy.

*/

template

const BinarySearchTree &

BinarySearchTree::

operator=( const BinarySearchTree & rhs )

{

if( this != &rhs )

{

makeEmpty( );

root = clone( rhs.root );

}

return *this;

}

/**

* Internal method to get element field in node t.

* Return the element field or ITEM_NOT_FOUND if t is NULL.

*/

template

const Comparable & BinarySearchTree::

elementAt( BinaryNode *t ) const

{

if( t == NULL )

return ITEM_NOT_FOUND;

else

return t->element;

}

/**

* Internal method to insert into a subtree.

* x is the item to insert.

* t is the node that roots the tree.

* Set the new root.

*/

template

void BinarySearchTree::

insert( const Comparable & x, BinaryNode * & t ) const

{

if( t == NULL )

t = new BinaryNode( x, NULL, NULL );

else if( x < t->element )

insert( x, t->left );

else if( t->element < x )

insert( x, t->right );

else

; // Duplicate; do nothing

}

/**

* Internal method to remove from a subtree.

* x is the item to remove.

* t is the node that roots the tree.

* Set the new root.

*/

template

void BinarySearchTree::

remove( const Comparable & x, BinaryNode * & t ) const

{

if( t == NULL )

return; // Item not found; do nothing

if( x < t->element )

remove( x, t->left );

else if( t->element < x )

remove( x, t->right );

else if( t->left != NULL && t->right != NULL ) // Two children

{

t->element = findMin( t->right )->element;

remove( t->element, t->right );

}

else

{

BinaryNode *oldNode = t;

t = ( t->left != NULL ) ? t->left : t->right;

delete oldNode;

}

}

/**

* Internal method to find the smallest item in a subtree t.

* Return node containing the smallest item.

*/

template

BinaryNode *

BinarySearchTree::findMin( BinaryNode *t ) const

{

if( t == NULL )

return NULL;

if( t->left == NULL )

return t;

return findMin( t->left );

}

/**

* Internal method to find the largest item in a subtree t.

* Return node containing the largest item.

*/

template

BinaryNode *

BinarySearchTree::findMax( BinaryNode *t ) const

{

if( t != NULL )

while( t->right != NULL )

t = t->right;

return t;

}

/**

* Internal method to find an item in a subtree.

* x is item to search for.

* t is the node that roots the tree.

* Return node containing the matched item.

*/

template

BinaryNode *

BinarySearchTree::

find( const Comparable & x, BinaryNode *t ) const

{

if( t == NULL )

return NULL;

else if( x < t->element )

return find( x, t->left );

else if( t->element < x )

return find( x, t->right );

else

return t; // Match

}

/****** NONRECURSIVE VERSION*************************

template

BinaryNode *

BinarySearchTree::

find( const Comparable & x, BinaryNode *t ) const

{

while( t != NULL )

if( x < t->element )

t = t->left;

else if( t->element < x )

t = t->right;

else

return t; // Match

return NULL; // No match

}

*****************************************************/

/**

* Internal method to make subtree empty.

*/

template

void BinarySearchTree::

makeEmpty( BinaryNode * & t ) const

{

if( t != NULL )

{

makeEmpty( t->left );

makeEmpty( t->right );

delete t;

}

t = NULL;

}

/**

* Internal method to print a subtree rooted at t in sorted order.

*/

template

void BinarySearchTree::printTree( BinaryNode *t ) const

{

if( t != NULL )

{

printTree( t->left );

cout << t->element << endl;

printTree( t->right );

}

}

/**

* Internal method to clone subtree.

*/

template

BinaryNode *

BinarySearchTree::clone( BinaryNode * t ) const

{

if( t == NULL )

return NULL;

else

return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );

}

TestBinarySearchTree.cpp

————————

#include

#include “BinarySearchTree.h”

// Test program

int main( )

{

const int ITEM_NOT_FOUND = -9999;

BinarySearchTree t( ITEM_NOT_FOUND );

int NUMS = 4000;

const int GAP = 37;

int i;

cout << “Checking… (no more output means success)” << endl;

for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )

t.insert( i );

for( i = 1; i < NUMS; i+= 2 )

t.remove( i );

if( NUMS < 40 )

t.printTree( );

if( t.findMin( ) != 2 || t.findMax( ) != NUMS – 2 )

cout << “FindMin or FindMax error!” << endl;

for( i = 2; i < NUMS; i+=2 )

if( t.find( i ) != i )

cout << “Find error1!” << endl;

for( i = 1; i < NUMS; i+=2 )

{

if( t.find( i ) != ITEM_NOT_FOUND )

cout << “Find error2!” << endl;

}

BinarySearchTree t2( ITEM_NOT_FOUND );

t2 = t;

for( i = 2; i < NUMS; i+=2 )

if( t2.find( i ) != i )

cout << “Find error1!” << endl;

for( i = 1; i < NUMS; i+=2 )

{

if( t2.find( i ) != ITEM_NOT_FOUND )

cout << “Find error2!” << endl;

}

return 0;

}

 

 

Vector : The Vector ADT extends the notion of� array by storing a sequence of arbitrary objects An element can be accessed, inserted or removed by specifying its rank (number of elements preceding it) An exception is thrown if an incorrect rank is specified (e.g., a negative rank)

 

The Stack ADT stores arbitrary objects Insertions and deletions follow the last-in first-out scheme.

The Queue ADT stores arbitrary objects Insertions and deletions follow the first-in first-out scheme Insertions are at the rear of the queue and removals are at the front of the queue Main queue operations:

enqueue(object): inserts an element at the end of the queue object

dequeue(): removes and returns the element at the front of the queue

 

A singly linked list is a concrete data structure consisting of a sequence of nodes

Each node stores

􀂄 element

􀂄 link to the next node

 

A doubly linked list provides a natural implementation of the List ADT Nodes implement Position and store:

􀂄 element

􀂄 link to the previous node

􀂄 link to the next node

 

A tree is an abstract model of a hierarchical structure A tree consists of nodes with a parent-child relation

 

Root: node without parent (A)

Internal node: node with at least one child (A, B, C, F)

External node (a.k.a. leaf): node without children (E, I, J, K, G, H, D)

Ancestors of a node: parent, grandparent, grand-grandparent, etc.

Depth of a node: number of ancestors

Height of a tree: maximum depth of any node (3)

Descendant of a node: child, grandchild, grand-grandchild, etc.

Subtree: tree consisting of a node and its descendants

 

 

A binary tree is a tree with the following properties:

􀂄 Each internal node has two children

􀂄 The children of a node are an ordered pair

We call the children of an internal node left child and right child

Alternative recursive definition: a binary tree is either

􀂄 a tree consisting of a single node,

or

􀂄 a tree whose root has an ordered pair of children, each of which is a

binary tree

 

Notation

n number of nodes

e number of

external nodes

i number of internal

nodes

h height

 

Properties:

􀂄 i + 1

􀂄 = 2− 1

􀂄 h ≤ i

􀂄 h ≤ (− 1)/2

􀂄 e ≤ 2h

􀂄 h ≥ log2 e

􀂄 h ≥ log2 (+ 1) – 1

 

A priority queue stores a collection of items

An item is a pair (key, element)

Main methods of the Priority Queue ADT

􀂄 insertItem(k, o) inserts an item with key k and element o

􀂄 removeMin() removes the item with smallest key and returns its element.

 

A heap is a binary tree storing keys at its internal nodes and satisfying the

following properties:

􀂄 Heap-Order: for every internal node v other than the root,

key(v) ≥ key(parent(v))

􀂄 Complete Binary Tree: let be the height of the heap

􀂊 for i = 0, . , − 1, there are 2nodes of depth i

􀂊 at depth − 1, the internal nodes are to the left of the external nodes

The last node of a heap is the rightmost internal node of depth – 1

 

A hash function maps keys of a given type to integers in a fixed interval [0, − 1]

Example:

h(x) = mod is a hash function for integer keys

The integer h(x) is called the hash value of key x

A hash table for a given key type consists of

􀂄 Hash function h

􀂄 Array (called table) of size N

When implementing a dictionary with a hash table, the goal is to store item (ko) at index i h(k)

 

A hash function is usually specified as the composition of two

functions:

Hash code map:

h1: keys → integers

Compression map:

h2: integers → [0, − 1]

The hash code map is applied first, and the compression map is applied next on the result, i.e.,

h(x) = h2(h1(x))

The goal of the hash function is to �disperse� the keys in an apparently random way.

 

The dictionary ADT models a searchable collection of key element items

The main operations of a dictionary are searching, inserting, and deleting items

Multiple items with the same key are allowed

 

 

Merge-sort on an input

sequence with n

elements consists of

three steps:

􀂄 Divide: partition into

two sequences S1 and S2

of about n/2 elements

each

􀂄 Recur: recursively sort S1

and S2

􀂄 Conquer: merge S1 and

S2 into a unique sorted

Sequence

 

 

Algorithm mergeSort(S, C)

Input sequence with n

elements, comparator C

Output sequence sorted

according to C

if S.size() 1

(S1, S2) ← partition(Sn/2)

mergeSort(S1, C)

mergeSort(S2, C)

← merge(S1, S2)

 

 

Quick-sort is a randomized

sorting algorithm based

on the divide-and-conquer

paradigm:

􀂄 Divide: pick a random

element (called pivot) and

partition into

􀂊 elements less than x

􀂊 elements equal x

􀂊 elements greater than x

􀂄 Recur: sort and G

􀂄 Conquer: join Land G

 

We represent a set by the sorted sequence of its elements

􀂊 By specializing the auxliliary methods the generic merge algorithm can be used to perform basic set operations:

􀂄 union

􀂄 intersection

􀂄 subtraction

􀂊 The running time of an operation on sets and should be at most O(nA nB)

 

Quick-select is a randomized selection algorithm based on the prune-and-search paradigm:

􀂄 Prune: pick a random element x(called pivot) and partition into

􀂊 elements less than x

􀂊 elements equal x

􀂊 elements greater than x

􀂄 Search: depending on k, either answer is in E, or we need to recurse in either or G

 

Big O:

F(n) (- O(g(n)) if there exists c > 0 and an integer n0 > 0 such that f(n) <= c*g(n) for all n >= n0.

 

Big Omega

F(n) (- O(g(n)) if there exists c > 0 and an integer n0 > 0 such that f(n) >= c*g(n) for all n >= n0.

 

Big theta

F(n) (- O(g(n)) if there exists c > 0 and an integer n0 > 0 such that f(n) = c*g(n) for all n >= n0.

.NET

Typescript – A new web technology for WEB Creators.

Introduction to TypeScript

TypeScript is a superset of Javascript that compiles to idiomatic JavaScript code, TypeScript is used for developing industrial-strength scalable application. All Javascript code is TypeScript code; i.e. you can simply and paste JS code into TS file and execute with out any errors.
TypeScript works on any browser, any host, any OS. Typescript is aligned with emerging standards, class, modules, arrow functions, ‘this’ keyword implementation all align with ECMAScript 6 proposals.

TypeScript support most of the module systems implemented in popular JS libraries. CommonJS and AMD is used in TypeScript, these module systems
are compatible in any ECMA environment and developer can specify how the TypeScript should be compiled to specified ECMAScript i.e. ECMAScript 3 or
ECMAScript 5 or ECMAScript 6. All major Javascript library work with TypeScript (Node, underscore, jquery etc) using declaration of the required types definition
TypeScript support oops concepts like private, public, static, inheritance, TypeScript enables scalable appilcation development and excellent tooling using all popular
IDEs like Visual Studio, WebStorm, Atom, Sublime Text etc.
TypeScript adds zero overhead in performance and execution, since static types completely disappear at runtime.
TypeScripts has awesome language features like Interfaces, Classes and Modules enable clear contract between components.

Now I briefly try to highlight and explain the special features of TypeScript:

TypeScript, we support much the same types as you would expected in JavaScript, with a convenient enumeration types implemented to help things along. The Basic types of TypeScript are

Boolean
var isDone: boolean = false;

Number
var height: number = 6;

String
var name: string = “bob”;
name = ‘smith’;

Array
var list:number[] = [1, 2, 3];
The second way uses a generic array type, Array<elemType>:
var list:Array<number> = [1, 2, 3];

Enum
Enum is the new addition to TypeScript not available in JS
an enum is a way of implementing friendly names to sets of numeric values.

enum Color {Red, Green, Blue};
var c: Color = Color.Green;

Any
The ‘any’ type is a powerful way to work with existing JavaScript, allowing you
to gradually opt-in and opt-out of type-checking during compilation.
var notSure: any = 4;
notSure = “maybe a string instead”;
notSure = false; // okay, definitely a boolean

Also you can use ‘any’ during mixed types, For example, you may have an array but the array has a mix of different types:

var list:any[] = [1, true, “free”];

list[1] = 100;

Void
‘void’ is the opposite of ‘any’ ie., the absence of having any type at all. You may commonly see this as the return type of functions that do not return a value:

function warnUser(): void {
alert(“This is my warning message”);
}

TypeScript provides static typing through type annotations to enable type checking at compile-time. This is optional and
can be ignored to use the regular dynamic typing of JavaScript.

Example of static Type checking and emitting errors
Optionally static typed variables

class Greeter {
greeting: string;
constructor (message: string) {
this.greeting = message;
}
greet() : string {
return “Hello, ” + this.greeting;
}
}

var greeter = new Greeter(“Hi”);
var result = greeter.greet();

If you modify the above code snippet where string is replaced by number in greet() method.
you’ll see red squiggles in the playground editor if you try this:

greet() : number {
return “Hello, ” + this.greeting;
}

Type Inference in TypeScript:

Type inference flows implicitly in TypeScript code
In TypeScript, there are several places where type inference is used to provide type information when there is no explicit type annotation. For example, in this code
var x = 3;

If you want TypeScript to determine the type of your variables correctly, do not do:
1st Code snippet:
var localVar;
// Initialization code
localVar = new MyClass();
The type of localVar will be interpretted to be ‘any’ instead of MyClass. TypeScript will not complain about it but you’ll not get ‘any’ static type checking.

Instead, do:
2nd Code snippet:

var localVal : MyClass;
localVal = new MyClass();

TypeScript introduces the –noImplicitAny flag to disallow such programs. Then the 1st code snippet will not compile:
Type inference also work in opposite direction known as ‘Contextual Type’
Contextual typing applies in many cases. Common cases include arguments to function calls, right hand sides of assignments, type assertions, members of object and array literals, and return statements. The contextual type also acts as a candidate
type in best common type. For example:

function createZoo(): Animal[] {
return [new Rhino(), new Elephant(), new Snake()];
}

In this example, best common type has a set of four candidates: Animal, Rhino, Elephant, and Snake. Of these, Animal can be chosen by the best common type algorithm.

TypeScript File Definitions

The file extension for such a file is .d.ts, where d stands for definition. Type definition files make it possible to enjoy
the benefits of type checking, autocompletion, and member documentation. Any file that ends in .d.ts instead of .ts will never
generate a corresponding compiled module, so this file extension can also be useful for normal TypeScript modules that contain
only interface definitions.

Type Systems in TypeScript is automatically inferred since the lib.d.ts, the main TypeScript definition file
is loaded implicitly. For detail information on TypeScript defintion file visit here(http://definitelytyped.org/guides.html)

TypeScript code Works with existing JS libraries, TypeScript declaration files (*.d.ts) for most of the common JS libraries are
maintained seperately in DefinitelyTyped.org. TypeScript declaration files make it easy to work with exisiting libraries using
repoistory available in DefinitelyTyped.org
TypeScript decl files (*.d.ts) can used for debuging and source mapping of TypeScript and JS file, also for type referencing.
If you want to document your function, provide documentation in TypeScript declaration files. if you want to reference d.ts files use
reference comment syntax

Functions
You can create a function on an instance member of the class, on the prototype, or as a static function

Creating a function on the prototype is easy in TypeScript, which is great since you don;t even have to know you are using the prototype.
// TypeScript
class Bike {
engine: string;
constructor (engine: string) {
this.engine = engine;
}

kickstart() {
return “Running ” + this.engine;
}
}
Notice the start function in the TypeScript code. Now look at the emitted JavaScript below, which defines that start function on the prototype.
// JavaScript
var Bike = (function () {
function Bike(engine) {
this.engine = engine;
}
Bike.prototype.kickstart = function () {
return “Running ” + this.engine;
};
return Bike;
})();

 Interface

One of the coolest parts of TypeScript is how it allows you to define complex type definitions in the form of interfaces.
Interfaces are used to implement duck Typing. duck typing is a style of typing in which an object’s methods and properties determine
the valid semantics, rather than its inheritance from a particular class or implementation of a specific interface.

I have 2 interfaces with the same interface but completely unrelated sematics:

interface Chicken {
id: number;
name: string;
}

interface JetPlane {
id: number;
name: string;
}
then doing the following is completely fine in TypeScript:

var chicken : Chicken = { id: 1, name: ‘Thomas’ };
var plane: JetPlane = { id: 2, name: ‘F 35’ };
chicken = plane;

TypeScript Interface uses ‘Duck typing’ or ‘Structural subtyping’

Functions

You can create a function on an instance member of the class, on the prototype, or as a static function

Creating a function on the prototype is easy in TypeScript, which is great since you don;t even have to know you are using the prototype.
// TypeScript
class Car {
engine: string;
constructor (engine: string) {
this.engine = engine;
}

start() {
return “Started ” + this.engine;
}
}
Notice the start function in the TypeScript code. Now look at the emitted JavaScript below, which defines that start function on the prototype.
// JavaScript
var Car = (function () {
function Car(engine) {
this.engine = engine;
}
Car.prototype.start = function () {
return “Started ” + this.engine;
};
return Car;
})();

Class

TypeScript classes are basic unit of abstraction very similar to C#/Java classes. In TypeScript a class can be defined with
keyword “class” followed by class name. TypeScript classes can contain constructor, fields, properties and functions.
TypeScript allows developers to define the scope of variable inside classes as “public” or “private”.
It’s important to note that the “public/private” keyword are only available in TypeScript,

When using the class keyword in TypeScript, you are actually creating two things with the same identifier:

A TypeScript interface containing all the instance methods and properties of the class; and
A JavaScript variable with a different (anonymous) constructor function type

Creating a Class

You can create a class and even add fields, properties, constructors, and functions (static, prototype, instance based). The basic syntax for a class is as follows:
// TypeScript
class Car {
// Property (public by default)
engine: string;

// Constructor
// (accepts a value so you can initialize engine)
constructor(engine: string) {
this.engine = engine;
}
}

The property could be made private by prefixing the definition with the keyword private. Inside the constructor the engine property is referred to using the this keyword.

Inheritance in TypeScript
TypeScript extends keyword provides a simple and convenient way to inherit functionality from a base class (or extend an interface)
CLASS INHERITANCE:

// TypeScript
class Vehicle {
engine: string;
constructor(engine: string) {
this.engine = engine;
}
}

class Truck extends Vehicle {
bigTires: bool;
constructor(engine: string, bigTires: bool) {
super(engine);
this.bigTires = bigTires;
}
}

When inheritance is implemented, compiler injects (extra extends) code which is other than the developer written code to show inheritance

TypeScript emits JavaScript that helps extend the class definitions, using the __extends variable. This helps take care of some of the heavy lifting on the JavaScript side.
var __extends = this.__extends || function (d, b) {
function __() { this.constructor = d; }
__.prototype = b.prototype;
d.prototype = new __();
};
var Vehicle = (function () {
function Vehicle(engine) {
this.engine = engine;
}
return Vehicle;
})();
var Truck = (function (_super) {
__extends(Truck, _super);
function Truck(engine, bigTires) {
_super.call(this, engine);
this.bigTires = bigTires;
}
return Truck;
})(Vehicle);

Modules

One easy way to help maintain code re-use and organize your code is with modules. There are patterns such as the Revealing Module Pattern (RMP) in JavaScript that make
this quite simple, but the good news is that in TypeScript modules become even easier with the module keyword (from the proposed ECMAScript 6 spec).

However, it is important to know how your code will be treated if you ignore modules: you end up back with spaghetti.

Modules can provide functionality that is only visible inside the module, and they can provide functionality that is visible from the outside using the export keyword.

TypeScript categorizes modules into internal and external modules.

TypeScript has the ability to take advantage of a pair of JavaScript modularization standards – CommonJS and Asynchronous Module Definition (AMD).
These capabilities allow for projects to be organized in a manner similar to what a “mature,” traditional server-side OO language provides.
This is particularly useful for Huge Scalable Web Applications.

TypeScript Internal modules are TypeScript’s own approach to modularize your code.
TypeScript Internal modules can span across multiple files, effectively creating a namespace.

There is no runtime module loading mechanism, you have to load the modules using <script/> tags in your code.
Alternatively, you can compile all TypeScript files into one big JavaScript file that you include using a single <script/> tag.

External modules leverage a runtime module loading mechanism. You have the choice between CommonJS and AMD.
CommonJS is used by node.js, whereas RequireJS is a prominent implementation of AMD often used in browser environments.
When using external modules, files become modules. The modules can be structured using folders and sub folders.

Benefits of Modules:
Scoping of variables (out of global scope)
Code re-use
AMD or CommonJS support
Encapsulation
Don’t Repeat Yourself (DRY)
Easier for testing

exports keyword in TypeScript
you can make internal aspects of the module accessible outside of the module using the export keyword.

You an also extend internal modules, share them across files, and reference them using the triple slash syntax.
///<reference path=”shapes.ts”/>

Lambda or Arrow function expression :
TypeScript introduces Lambda expressions which in itself is so cool but to make this work it also automates the that-equals-this pattern.

The TypeScript code:
var myFunction = f => { this.x = “x”; }

Is compiled into this piece of JavaScript, automatically creating the that-equals-this pattern:

var _this = this;
var myFunction = function (f) {
_this.x = “x”;
};

Arrow function expressions are a compact form of function expressions that have a scope of ‘this’.
You can define an arrow function expression by omitting the function keyword and using the lambda syntax =>.

a simple TypeScript function that calculates sum earned by deposited funds.

var calculateInterest = function (amount, interestRate, duration) {
return amount * interestRate * duration / 12;
}
Using arrow function expression we can define this function alternatively as follows:

var calculateInterest2 = (amount, interestRat, duration) => {
return amount * interestRate * duration / 12;
}

Standard Javascript functions will dynamically bind this depending on execution context,
arrow functions on the other hand will preserve this of enclosing context.
This is a conscious design decision as arrow functions in ECMAScript 6 are meant to address
some problems associated with dynamically bound ‘this’ (eg. using function invocation pattern).

Being primarily a OOPS developer, lambda expressions in TypeScript is an extremely useful and
compact way to express anonymous methods.
Bringing this syntax to JavaScript though TypeScript is definitely a win for me.

There are lots of awesome features to list in TypeScript, all those new features of TypeScript in next post.

Hope this post brings a lot interest in developing apps using TypeScript.

.NET

SQL Server Database Programming Part 2

Managing Transactions

  1. A transaction is a set of actions that make up an atomic unit of work and must succeed or fail as a whole
  2. By default, implicit transactions are not enabled. When implicit transactions are enabled, a number of statements automatically begin a transaction. The developer must execute a COMMIT or ROLLBACK statement to complete the transaction.
  3. Explicit transactions start with a BEGIN TRANSACTION statement and are completed by either a ROLLBACK TRANSACTION or COMMIT TRANSACTION statement.
  4. Issuing a ROLLBACK command when transactions are nested rolls back all transactions to the outermost BEGIN TRANSACTION statement, regardless of previously issued COMMIT statements for nested transactions.
  5. SQL Server uses a variety of lock modes, including shared (S), exclusive (X), and intent (IS, IX, SIX) to manage data consistency while multiple transactions are being processed concurrently.
  6. SQL Server 2008 supports the READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SNAPSHOT, and SERIALIZABLE isolation levels.

Working with Tables and Data Types

  1. Creating tables is about more than just defining columns. It is very important to choose the right data type and to implement data integrity.
  2. You need to know the details of how the different data types behave before you can use them correctly.
  3. Data integrity needs be a part of your table definition from the beginning to make sure that you protect your data from faults.

Common Table Expressions (CTE)

  1. A recursive CTE contains two SELECT statements within the WITH clause, separated by the UNION ALL keyword. The first query defines the anchor for the recursion, and the second query defines the data set that is to be iterated across.
  2. If a CTE is contained within a batch, all statements preceding the WITH clause must be terminated with a semicolon.
  3. The outer query references the CTE and specifies the maximum recursion.

Subqueries

  1. Noncorrelated subqueries are independent queries that are embedded within an outer query and are used to retrieve a scalar value or list of values that can be consumed by the outer query to make code more dynamic.
  2. Correlated subqueries are queries that are embedded within an outer query but reference values within the outer query.

Ranking Functions

  1. ROW_NUMBER is used to number rows sequentially in a result set but might not produce identical results if there are ties in the column(s) used for sorting.
  2. RANK numbers a tie with identical values but can produce gaps in a sequence.
  3. DENSE_RANK numbers ties with identical values but does not produce gaps in the sequence.
  4. NTILE allows you to divide a result set into approximately equal-sized groups.

Stored Procedures

  1. A stored procedure is a batch of T-SQL code that is given a name and is stored within a database.
  2. You can pass parameters to a stored procedure either by name or by position. You can also return data from a stored procedure using output parameters.
  3. You can use the EXECUTE AS clause to cause a stored procedure to execute under a specific security context.
  4. Cursors allow you to process data on a row by row basis; however, if you are making the same modification to every row within a cursor, a set-oriented approach is more efficient.
  5. A TRY. . .CATCH block delivers structured error handling to your procedures.

User Defined Functions

  1. You can create scalar functions, inline table-valued functions, and multi-statement table-valued functions.
  2. With the exception of inline table-valued functions, the function body must be enclosed within a BEGIN. . .END block.
  3. All functions must terminate with a RETURN statement.
  4. Functions are not allowed to change the state of a database or of a SQL Server instance.

Triggers

  1. Triggers are specialized stored procedures that automatically execute in response to a DDL or DML event.
  2. You can create three types of triggers: DML, DDL, and logon triggers.
  3. A DML trigger executes when an INSERT, UPDATE, or DELETE statement for which the trigger is coded occurs.
  4. A DDL trigger executes when a DDL statement for which the trigger is coded occurs.
  5. A logon trigger executes when there is a logon attempt.
  6. You can access the inserted and deleted tables within a DML trigger.
  7. You can access the XML document provided by the EVENTDATA function within a DDL or logon trigger.

Views

  1. A view is a name for a SELECT statement stored within a database.
  2. A view has to return a single result set and cannot reference variables or temporary tables.
  3. You can update data through a view so long as the data modification can be resolved to a specific set of rows in an underlying table.
  4. If a view does not meet the requirements for allowing data modifications, you can create an INSTEAD OF trigger to process the data modification instead.
  5. You can combine multiple tables that have been physically partitioned using a UNION ALL statement to create a partitioned view.
  6. A distributed partitioned view uses linked servers to combine multiple member tables across SQL Server instances.
  7. You can create a unique, clustered index on a view to materialize the result set for improved query performance.

Queries Tuning

  1. Understanding how queries are logically constructed is important to knowing that they correctly return the intended result.
  2. Understanding how queries are logically constructed helps you understand what physical constructs (like indexes) help the query execute faster.
  3. Make sure you understand your metrics when you measure performance.

Indexes

  1. Indexes typically help read performance but can hurt write performance.
  2. Indexed views can increase performance even more than indexes, but they are restrictive and typically cannot be created for the entire query.
  3. Deciding which columns to put in the index key and which should be implemented as included columns is important.
  4. Analyze which indexes are actually being used and drop the ones that aren’t. This saves storage space and minimizes the resources used to maintain indexes for write operations.

Working with XML

  1. XML can be generated using a SELECT statement in four different modes: FOR XML RAW, FOR XML AUTO, FOR XML PATH, and FOR XML EXPLICIT.
  2. FOR XML PATH is typically the preferred mode used to generate XML.
  3. The XML data type can be either typed (validated by an XML schema collection) or untyped.
  4. In an untyped XML data type, all values are always interpreted as strings.
  5. You can use the value, query, exist, nodes, and modify methods to query and alter instances of the XML data type.

SQLCLR and FileStream

  1. To use user-defined objects based on SQLCLR, SQLCLR must be enabled on the SQL Server instance.
  2. The objects most suitable for development using SQLCLR are UDFs and user-defined aggregates.
  3. If you create UDTs based on SQLCLR, make sure that you test them thoroughly.
  4. Consider using Filestream if the relevant data mostly involves storing streams larger than 1 MB.

Spatial Data Types

  1. The geography and geometry data types provide you with the ability to work with spatial data with system-defined data types rather than having to define your own CLR data types.
  2. You can instantiate spatial data by using any of the spatial methods included with SQL Server 2008.

Full-Text Search

  1. SQL Server 2008 provides fully integrated full-text search capabilities.
  2. Full-text indexes are created and maintained inside the database and are organized into virtual full-text catalogs.
  3. The CONTAINS and FREETEXT predicates, as well as the CONTAINSTABLE and FREETEXTTABLE functions, allow you to fully query text, XML, and certain forms of binary data.

Service Broker Solutions

  1. Service Broker provides reliable asynchronous messaging capabilities for your SQL Server instance.
  2. You need to configure the Service Broker components for your solution. These components might include message types, contracts, services, queues, dialogs, and conversation priorities.
  3. You use the BEGIN DIALOG, SEND, and RECEIVE commands to control individual conversations between two services.

Database Mail

  1. Database Mail was introduced in SQL Server 2005 and should be used in place of SQL Mail.
  2. Database Mail is disabled by default to minimize the surface area of the server.
  3. You should use the sp_send_dbmail system stored procedure to integrate Database Mail with your applications.
  4. A wide variety of arguments allows you to customize the e-mail messages and attachments sent from the database server.

Windows PowerShell

  1. SQL Server PowerShell is a command-line shell and scripting environment, based on Windows PowerShell.
  2. SQL Server PowerShell uses a hierarchy to represent how objects are related to each other.
  3. The three folders that exist in the SQL Server PowerShell provider are SQLSERVER:SQL,SQLSERVER:SQLPolicy, and SQLSERVERSQLRegistration.
  4. You can browse the hierarchy by using either the cmdlet names or their aliases.

Change Data Capture (CDC)

  1. Change tracking is enabled first at the database and then at the table level.
  2. Change tracking can tell you what rows have been modified and provide you with the end result of the data.
  3. Change tracking requires fewer system resources than CDC.
  4. CDC can tell you what rows have been modified and provide you with the final data as well as the intermediate states of the data.
  5. SQL Server Audit allows you to log access to tables, views, and other objects.
Digg This
.NET

Design Patterns

pattern is a commonly occurring reusable piece in software system that provides a certain set of functionality.A pattern is a commonly occurring reusable piece in software system that provides a certain set of functionality. The identification of a pattern is also based on the context in which it is used. Design patterns are solutions to general problems that software developers faced during software development. So, using patterns in modelling of systems helps in keeping design standardised and more importantly, minimizes the reinventing of the wheel in the system design. This article is all about patterns; especially design patterns.The class diagram in UML can be used to capture the patterns identified in a system.

Factory Method

  • How does this promote loosely coupled code?

A Factory pattern returns an instance of one of several possible classes, depending on the data provided to it.  Usually, all the classes it returns have a common parent class and common methods, but each of them performs a different task, and is optimized for different kinds of data.  Thus, the Factory pattern eliminates the need to bind application specific classes into the code.  The code only deals with the Product interface , and can therefore work with any user-defined Concrete Product classes. Thus the code is not tightly bound to a particular application. for eg. in the example discussed in class(and the book), the abstract classes Application and Document have generic methods to manipulate documents. However, to realize the application specific implementation, one has to subclass them- say a DrawingApplication and DrawingDocument for drawings, TextApplication and TextDocument.Instead of putting code inside Document and Application classes for each document type (binding application specific code), the factory method lets them defer the instantiation for a specific application to a subclass.

Proxy

  • If a Proxy is used to instantiate an object only when it is absolutely needed, does the Proxy simplify code?


This is not necessarily true.  A proxy pattern is used when we need to represent a complex object by a simpler one.  It provides a certain level of indirection when accessing an object.  A proxy usually has the same methods as the object it represents, and hence provides an identical interface to that object.  This definitely improves performance, but may or may not simplify the code.  In some cases, the overall code may become simpler.  e.g. protection proxies and smart references allow housekeeping tasks when an object is accessed (access permissions, ref counts, object locking etc.) This makes the Subject code simpler as it does not have to bother with the bookkeeping code. Thus a Proxy would simplify Subject code, by moving it to the RealSubject code, at the expense of implementing the Proxy code.

Strategy

  • What happens when a system has an explosion of strategy objects? Is there some better way to manage these strategies?


There are several ways to manage these strategies if a system has an explosion of strategy objects.  One way is to use the Template pattern which would in turn use several simpler strategy classes.  Such an explosion could occur if there are a lot of strategies for one context, or several context objects and corresponding strategy objects.  This leads to increased load on memory and system resources.  Other ways to manage this would be to implementing strategies as stateless objects that contexts can share, or making strategy objects optional. 

  • (ii) In the implementation section of this pattern, the authors describe two ways in which a strategy can get the information it needs to do its job. One way describes how a strategy object could get passed a reference to the context object, thereby giving it access to context data. But is it possible that the data required by the strategy will not be available from the context’s interface? How could you remedy this potential problem?


Yes, it is possible that the data required by the strategy will not be available from the context’s interface.  If the data were private to the context (not accessible from the interface), then the strategy would not be able to access it.  We could pass all the data required by the strategy explicitly, although this increases communication overhead.  We could also use strategies as template parameters – in this case, since the strategy would be a context method, the data would be accessible.

 

Decorator

  • In the Implementation section of the Decorator Pattern, the authors write: A decorator object’s interface must conform to the interface of the component it decorates. Now consider an object A, that is decorated with an object B. Since object B “decorates” object A, object B shares an interface with object A. If some client is then passed an instance of this decorated object, and that method attempts to call a method in B that is not part of A’s interface, does this mean that the object is no longer a Decorator, in the strict sense of the pattern? Furthermore, why is it important that a decorator object’s interface conforms to the interface of the component it decorates?


If some client is then passed an instance of this decorated object, and that method attempts to call a method in B that is not part of A’s interface, this does NOT necessarily mean that the object is no longer a Decorator, in the strict sense of the pattern. Object B’s interface is still the same as object A’s interface although some more methods are added.  The book says that a decorator and its component are not identical. Component can add functionality to the base class. Decorator object’s interface should conform to the interface of the component it decorates because of the inheritance issues, since the Decorator acts as a transparent enclosure.  The client would be unaware of the decorators presence, and would access the contents of the object through a common interface.

 

Adapter

  • Would you ever create an Adapter that has the same interface as the object which it adapts? Would your Adapter then be a Proxy?


An Adapter could indeed have the same interface as the object which it adapts.  In that case, the adapter would add some extra functionality before making the call to the adaptee object.  So, we would not want the exact same interface.  But in the case of a proxy, we do want the same interface since it is a virtual placeholder for an object.  Also, the adapter’s implementation would be different from that of the proxy.

Bridge

  • How does a Bridge differ from a Strategy and a Strategy’s Context?


A strategy is a behavioral pattern that allows a client (Strategy context) to interchangably use multiple algorithms (Strategy).  A bridge is a structural pattern that influences the creation of a class hierarchy by decoupling an abstraction from the implementation.   In a strategy, usually the Strategy is allowed to vary to change the behavior of the algorithm, while the Context may not vary as much. In a bridge however, the abstraction and its implementation can vary independently, and it hides the implementation details from the client.

 

Facade

  • (i) How complex must a sub-system be in order to justify using a facade?


A facade is justified whenever the dependencies between the clients and the implementation classes of an abstration become complex enough to decouple the subsystem.  Sometimes, it is justified to use even for single class subsystem, if we expect that to grow in the future (although this would be against the principles of extreme programming 🙂 

  • (ii) What are the additional uses of a facade with respect to an organization of designers and developers with varying abilities? What are the political ramifications?


The facade in indeed a great tool for an organization of designers and developers with varying abilities.  It provides a simple access to complex subsystems for less experienced participants, but as they grow and learn, they could access the subsystems directly.  Also, the developers may present a facade of the system to the designers, thus the designers do have to concern themselves about the details of the subsystems.  Thus the developers could extend on the subsystem code independently, without affecting the design.

 

Composite

  • (i) How does the Composite pattern help to consolidate system-wide conditional logic?


It does this by providing a general design which makes client code simple and makes it easier to add new kinds of components. Thus the clients can treat composite structures and individual objects uniformly,  without worrying about whether they’re a leaf or composite node.  This helps avoid a lot of case style statements. 

  • (ii) Would you use the composite pattern if you did not have a part-whole hierarchy? In other words, if only a few objects have children and almost everything else in your collection is a leaf (a leaf that has no children), would you still use the composite pattern to model these objects?


We could still use a composite pattern here to provide a common interface to all the objects.  Thus we may define a composite pattern and call an operation on the component, when we wish to issue an operation on a few composite objects, and all the leaf objects.

Iterator

  • Consider a composite that contains loan objects. The loan object interface contains a method called “AmountOfLoan()”, which returns the current market value of a loan. Given a requirement to extract all loans above, below or in between a certain amount, would you write or use an Iterator to do this?


An iterator goes through all the objects, and hence that would be a very inefficient search, given our problem.  However, if we built the hierarchy like a binary search tree and stored some min/max key value at each composite node, then we could implement an iterator to go through the children of a composite which satisfies the current search criterion.

 

Template Method

  • The Template Method relies on inheritance. Would it be possible to get the same functionality of a Template Method, using object composition? What would some of the tradeoffs be?


Yes, but we would then have to store the state of our class in such a way that all the different objects can access it.  But we couldn’t run these at the same time, unless they are very independent of each other.

 

Abstract Factory

  • In the Implementation section of this pattern, the authors discuss the idea of defining extensible factories. Since an Abstract Factory is composed of Factory Methods, and each Factory Method has only one signature, does this mean that the Factory Method can only create an object in one way?


We would have to specify different concrete factory subclasses in order to create an object in multiple ways.  We could avoid this by using a prototype pattern for implementing the concrete factory. 

  • Consider the MazeFactory example. The MazeFactory contains a method called MakeRoom, which takes as a parameter one integer, representing a room number. What happens if you would also like to specify the room’s color & size? Would this mean that you would need to create a new Factory Method for your MazeFactory, allowing you to pass in room number, color and size to a second MakeRoom method?


In the current MazeFactory implementation we would have to add another Factory Method with a MakeRoom method to create a room with a number, color and size. We could also use overloaded constructors which take multiple arguments (and initialize some, e.g. color and size to a default if we want to pass only the room number). The other alternative would be to use a prototype based approach, in which the concrete MakeRoom factory would have methods to add color, size parts to the catalog.

Builder

  • Like the Abstract Factory pattern, the Builder pattern requires that you define an interface, which will be used by clients to create complex objects in pieces. In the MazeBuilder example, there are BuildMaze(), BuildRoom() and BuildDoor() methods, along with a GetMaze() method. How does the Builder pattern allow one to add new methods to the Builder’s interface, without having to change each and every sub-class of the Builder?


The builder method returns child nodes back to the director, which passes them back to the builder to build additional/parent nodes. MazeBuilder does not create the maze itself, but just defines the interface for creating mazes – letting the subclasses do the actual work. Since the subclasses use the methods defined in the Builder interface, adding  a new method to the interface would not require changing each subclass as the original methods would still work and create a valid maze. Once might want to create a new subclass of the builder to make use of the additional methods in the Builder’s interface.

 

Singleton

  • The Singleton pattern is often paired with the Abstract Factory pattern. What other creational or non-creational patterns would you use with the Singleton pattern?


We could also use the Facade pattern since we would need a single instance of a point of entry/layer to the subsystem.  We could also use a mediator with a singleton, providing one controller for the system of classes, and a proxy with a singleton, providing a single placeholder to the real object.

 

Mediator

  • Since a Mediator becomes a repository for logic, can the code that implements this logic begin to get overly complex, possible resembling spaggheti code? How could this potential problem be solved?


Yes, this is likely to happen in certain situations.  We could then use a behavioral pattern such as strategy to couple together a family of policies to be used depending on the classes.  We may also group the classes into a hierarchy and use the Composite pattern to talk to them, simplifying code in the client (the mediator).

 

Observer

  • (i) The classic Model-View-Controller design is explained in Implementation note #8: Encapsulating complex update semantics. Would it ever make sense for an Observer (or View) to talk directly to the Subject (or Model)?


The Observer may request an immediate update from the Subject without going through the Controller, when we need a “real-time” update of the Subject.  This would, however, create redundant update and synchronization issues, and would be in conflict with the Mediator based design of the Controller. 

  • (ii) What are the properties of a system that uses the Observer pattern extensively? How would you approach the task of debugging code in such a system?


The system can be divide into two distinct part – the observers and the subjects.   If we were to model the relationships between objects as graph links, the graph would resemble a digraph.   We could then debug the two components of the digraph independantly.  We could first check if the subjects are updating states correctly, observers are recording the updates correctly, and then check if the communication(update) protocol between the two is working correctly. 

  • (iii) Is it clear to you how you would handle concurrency problems with is pattern? Consider an Unregister() message being sent to a subject, just before the subject sends a Notify() message to the ChangeManager (or Controller).


We would have to add a communication protocol at the Controller for handling the updates. e.g. the Controller could buffer the updates from the subjects, check if the system is in a consistent state, send the updates to the observers, check for consistency and then send the messages to the subjects.  It would be trade-off between efficiency and consistency.

 

Chain of Responsibility

  • (i) How does the Chain of Responsibility pattern differ from the Decorator pattern or from a linked list?.


In a chain, an object in the chain may or may not act on a request and just pass it on to the next object(handler). A decorator, however, adds responsibilites to an object dynamically, and each object in the list adds responsibilities.  Also in a chain, a receipt is not guaranteed (the request can drop off the end of the chain without ever being handled) 

  • (ii) Is it helpful to look at patterns from a structural perspective? In other words, if you see how a set of patterns are the same in terms of how they are programmed, does that help you to understand when to apply them to a design?


Yes, sometimes it helps.  And of course, experience with programming, and using the right patterns helps tp figure out more easily what patterns to use in a given situation.

 

Memento

  • The authors write that the “Caretaker” participant never operates on or examines the contents of a memento. Can you consider a case where a Caretaker would infact need to know the identity of a memento and thus need the ability to examine or query the contents of that memento? Would this break something in the pattern?


The idea of the memento is based on that the “Caretaker” participant never operates on or examines the contents of a memento.  So, yes, the pattern is broken if it is allowed to examine or query the contents of the memento.  But, say we wish to ensure that something cannot be “undone” after a certain action, then we would need such an ability for the Caretaker.

 

Command

  • In the Motivation section of the Command pattern, an application’s menu system is described. An application has a Menu, which in turn has MenuItems, which in turn execute commands when they are clicked. What happens if the command needs some information about the application in order to do its job? How would the command have access to such information such that new comamnds could easily be written that would also have access to the information they need?


In such a case, the application and the command could both access a made-up in-between object, so that the command could get the information that way.  We can create more commands, but we need to make them all aware of this in-between object.

 

Prototype

  • (i) When should this creational pattern be used over the other creational patterns?


Prototype hides the concrete product classes from the user, reducing the number of names the user needs to know.  This is of course common to several creational patterns.  But the Prototype allows a client to be installed and removed at run time, which adds flexibility that other creational patterns don’t have. 

  • (ii) Explain the difference between deep vs. shallow copy.


With a shallow copy, pointers will be continue to be shared between the original and the copy.  i.e. the copy will not be completely independent because it will still refer to the same variable as the original.  With a deep copy, however, we copy the original itself, but we also make copies of all the variables’ original uses. So the new object is independent , because when it refers to a variable , it actually refers to its own variable, which is a copy of the original variable.

 

State

  • If something has only two to three states, is it overkill to use the State pattern?


Not really.  One uses the State pattern when the transitions between the states are complex.  Also, albeit in contrast with extreme programming principles, if future growth will demand more states, then the State pattern should be used.

 

Visitor

  • One issue with the Visitor pattern involces cyclicality. When you add a new Visitor, you must make changes to existing code. How would you work around this possible problem?


We could make a default Visitor that could be implemented by most of the other Visitors.

 

Flyweight

  • (i) What is a non-GUI example of a flyweight?


An example is the checkout system at a video store.  There are a large number of different objects here, but we make one single instance of an object and pass as an intrinsic state the data about who is checking out what video. 

  • (ii) What is the minimum configuration for using flyweight? Do you need to be working with thousands of objects, hundreds, tens?


There is better savings if more flyweights are shared, i.e. more objects are added.  However, it depends on the size of the objects.  If we use large and different objects and only few of them, we would still save space, although there is additional overhead for using the flyweight itself.

 

What are design patterns?

Design patterns are documented tried and tested solutions for recurring problems in a given context. So basically you have a problem context and the proposed solution for the same. Design patterns existed in some or other form right from the inception stage of software development. Let’s say if you want to implement a sorting algorithm the first thing comes to mind is bubble sort. So the problem is sorting and solution is bubble sort. Same holds true for design patterns.

 

Which are the three main categories of design patterns?

There are three basic classifications of patterns Creational, Structural, and Behavioral patterns.

Creational Patterns

 Abstract Factory:- Creates an instance of several families of classes 
 Builder: – Separates object construction from its representation 
 Factory Method:- Creates an instance of several derived classes 
 Prototype:- A fully initialized instance to be copied or cloned 
 Singleton:- A class in which only a single instance can exist

Note: – The best way to remember Creational pattern is by ABFPS (Abraham Became First President of States).
Structural Patterns

 Adapter:-Match interfaces of different classes. 
 Bridge:-Separates an object’s abstraction from its implementation. 
 Composite:-A tree structure of simple and composite objects. 
 Decorator:-Add responsibilities to objects dynamically. 
 Façade:-A single class that represents an entire subsystem.
 Flyweight:-A fine-grained instance used for efficient sharing. 
 Proxy:-An object representing another object.

Note : To remember structural pattern best is (ABCDFFP)
Behavioral Patterns

 Mediator:-Defines simplified communication between classes.
 Memento:-Capture and restore an object’s internal state. 
 Interpreter:- A way to include language elements in a program.
 Iterator:-Sequentially access the elements of a collection. 
 Chain of Resp: – A way of passing a request between a chain of objects.
 Command:-Encapsulate a command request as an object. 
 State:-Alter an object’s behavior when its state changes. 
 Strategy:-Encapsulates an algorithm inside a class. 
 Observer: – A way of notifying change to a number of classes. 
 Template Method:-Defer the exact steps of an algorithm to a subclass. 
 Visitor:-Defines a new operation to a class without change.

Note: – Just remember Music……. 2 MICS On TV (MMIICCSSOTV).

Note :- In the further section we will be covering all the above design patterns in a more detail manner.

Can you explain factory pattern?

·         Factory pattern is one of the types of creational patterns. You can make out from the name factory itself it’s meant to construct and create something. In software architecture world factory pattern is meant to centralize creation of objects. Below is a code snippet of a client which has different types of invoices. These invoices are created depending on the invoice type specified by the client. There are two issues with the code below:-

·         First we have lots of ‘new’ keyword scattered in the client. In other ways the client is loaded with lot of object creational activities which can make the client logic very complicated.

Second issue is that the client needs to be aware of all types of invoices. So if we are adding one more invoice class type called as ‘InvoiceWithFooter’ we need to reference the new class in the client and recompile the client also.

clip_image003

Figure: – Different types of invoice

Taking these issues as our base we will now look in to how factory pattern can help us solve the same. Below figure ‘Factory Pattern’ shows two concrete classes ‘ClsInvoiceWithHeader’ and ‘ClsInvoiceWithOutHeader’.

The first issue was that these classes are in direct contact with client which leads to lot of ‘new’ keyword scattered in the client code. This is removed by introducing a new class ‘ClsFactoryInvoice’ which does all the creation of objects.

The second issue was that the client code is aware of both the concrete classes i.e. ‘ClsInvoiceWithHeader’ and ‘ClsInvoiceWithOutHeader’. This leads to recompiling of the client code when we add new invoice types. For instance if we add ‘ClsInvoiceWithFooter’ client code needs to be changed and recompiled accordingly. To remove this issue we have introduced a common interface ‘IInvoice’. Both the concrete classes ‘ClsInvoiceWithHeader’ and ‘ClsInvoiceWithOutHeader’ inherit and implement the ‘IInvoice’ interface.

The client references only the ‘IInvoice’ interface which results in zero connection between client and the concrete classes ( ‘ClsInvoiceWithHeader’ and ‘ClsInvoiceWithOutHeader’). So now if we add new concrete invoice class we do not need to change any thing at the client side. 

In one line the creation of objects is taken care by ‘ClsFactoryInvoice’ and the client disconnection from the concrete classes is taken care by ‘IInvoice’ interface.


clip_image004

Figure: – Factory pattern

Below are the code snippets of how actually factory pattern can be implemented in C#. In order to avoid recompiling the client we have introduced the invoice interface ‘IInvoice’. Both the concrete classes ‘ClsInvoiceWithOutHeaders’ and ‘ClsInvoiceWithHeader’ inherit and implement the ‘IInvoice’ interface.

 

Figure :- Interface and concrete classes

We have also introduced an extra class ‘ClsFactoryInvoice’ with a function ‘getInvoice()’ which will generate objects of both the invoices depending on ‘intInvoiceType’ value. In short we have centralized the logic of object creation in the ‘ClsFactoryInvoice’. The client calls the ‘getInvoice’ function to generate the invoice classes. One of the most important points to be noted is that client only refers to ‘IInvoice’ type and the factory class ‘ClsFactoryInvoice’ also gives the same type of reference. This helps the client to be complete detached from the concrete classes, so now when we add new classes and invoice types we do not need to recompile the client.

clip_image005

Figure: – Factory class which generates objects

Note :- The above example is given in C# . Even if you are from some other technology you can still map the concept accordingly. You can get source code from the CD in ‘FactoryPattern’ folder.

Can you explain abstract factory pattern?

 

Abstract factory expands on the basic factory pattern. Abstract factory helps us to unite similar factory pattern classes in to one unified interface. So basically all the common factory patterns now inherit from a common abstract factory class which unifies them in a common class. All other things related to factory pattern remain same as discussed in the previous question.

A factory class helps us to centralize the creation of classes and types. Abstract factory helps us to bring uniformity between related factory patterns which leads more simplified interface for the client.

clip_image006

Figure: – Abstract factory unifies related factory patterns

 

Now that we know the basic lets try to understand the details of how abstract factory patterns are actually implemented. As said previously we have the factory pattern classes (factory1 and factory2) tied up to a common abstract factory (AbstractFactory Interface) via inheritance. Factory classes stand on the top of concrete classes which are again derived from common interface. For instance in figure ‘Implementation of abstract factory’ both the concrete classes ‘product1’ and ‘product2’ inherits from one interface i.e. ‘common’. The client who wants to use the concrete class will only interact with the abstract factory and the common interface from which the concrete classes inherit. 

clip_image008

Figure: – Implementation of abstract factory


Now let’s have a look at how we can practically implement abstract factory in actual code. We have scenario where we have UI creational activities for textboxes and buttons through their own centralized factory classes ‘ClsFactoryButton’ and ‘ClsFactoryText’. Both these classes inherit from common interface ‘InterfaceRender’. Both the factories ‘ClsFactoryButton’ and ‘ClsFactoryText’ inherits from the common factory ‘ClsAbstractFactory’. Figure ‘Example for AbstractFactory’ shows how these classes are arranged and the client code for the same. One of the important points to be noted about the client code is that it does not interact with the concrete classes. For object creation it uses the abstract factory ( ClsAbstractFactory ) and for calling the concrete class implementation it calls the methods via the interface ‘InterfaceRender’. So the ‘ClsAbstractFactory’ class provides a common interface for both factories ‘ClsFactoryButton’ and ‘ClsFactoryText’. 

clip_image009

Figure: – Example for abstract factory

Note: – We have provided a code sample in C# in the ‘AbstractFactory’ folder. People who are from different technology can compare easily the implementation in their own language.

We will just run through the sample code for abstract factory. Below code snippet ‘Abstract factory and factory code snippet’ shows how the factory pattern classes inherit from abstract factory.

clip_image011

Figure: – Abstract factory and factory code snippet

Figure ‘Common Interface for concrete classes’  how the concrete classes inherits from a common interface ‘InterFaceRender’ which enforces the method ‘render’ in all the concrete classes.

clip_image013

Figure: – Common interface for concrete classes


The final thing is the client code which uses the interface ‘InterfaceRender’ and abstract factory ‘ClsAbstractFactory’ to call and create the objects. One of the important points about the code is that it is completely isolated from the concrete classes. Due to this any changes in concrete classes like adding and removing concrete classes does not need client level changes.

clip_image014

Figure: – Client, interface and abstract factory

 

Can you explain builder pattern?

Builder falls under the type of creational pattern category. Builder pattern helps us to separate the construction of a complex object from its representation so that the same construction process can create different representations. Builder pattern is useful when the construction of the object is very complex. The main objective is to separate the construction of objects and their representations. If we are able to separate the construction and representation, we can then get many representations from the same construction. 

clip_image015

Figure: – Builder concept


To understand what we mean by construction and representation lets take the example of the below ‘Tea preparation’ sequence.

You can see from the figure ‘Tea preparation’ from the same preparation steps we can get three representation of tea’s (i.e. Tea with out sugar, tea with sugar / milk and tea with out milk). 

clip_image016

Figure: – Tea preparation


Now let’s take a real time example in software world to see how builder can separate the complex creation and its representation. Consider we have application where we need the same report to be displayed in either ‘PDF’ or ‘EXCEL’ format. Figure ‘Request a report’ shows the series of steps to achieve the same. Depending on report type a new report is created, report type is set, headers and footers of the report are set and finally we get the report for display.

clip_image017

Figure: – Request a report

Now let’s take a different view of the problem as shown in figure ‘Different View’. The same flow defined in ‘Request a report’ is now analyzed in representations and common construction. The construction process is same for both the types of reports but they result in different representations.

clip_image018

Figure: – Different View


We will take the same report problem and try to solve the same using builder patterns. There are three main parts when you want to implement builder patterns.

 Builder: – Builder is responsible for defining the construction process for individual parts. Builder has those individual processes to initialize and configure the product.
 Director: – Director takes those individual processes from the builder and defines the sequence to build the product.
 Product: – Product is the final object which is produced from the builder and director coordination.

First let’s have a look at the builder class hierarchy. We have a abstract class called as ‘ReportBuilder’ from which custom builders like ‘ReportPDF’ builder and ‘ReportEXCEL’ builder will be built.

clip_image019

Figure: – Builder class hierarchy

 

Figure ‘Builder classes in actual code’ shows the methods of the classes. To generate report we need to first Create a new report, set the report type (to EXCEL or PDF) , set report headers , set the report footers and finally get the report. We have defined two custom builders one for ‘PDF’ (ReportPDF) and other for ‘EXCEL’ (ReportExcel). These two custom builders define there own process according to the report type.


 

clip_image021

Figure: – Builder classes in actual code

Now let’s understand how director will work. Class ‘clsDirector’ takes the builder and calls the individual method process in a sequential manner. So director is like a driver who takes all the individual processes and calls them in sequential manner to generate the final product, which is the report in this case. Figure ‘Director in action’ shows how the method ‘MakeReport’ calls the individual process to generate the report product by PDF or EXCEL.

 

 


clip_image023

Figure: – Director in action

 

 

The third component in the builder is the product which is nothing but the report class in this case.

 

 

clip_image024

Figure: – The report class

 

Now let’s take a top view of the builder project. Figure ‘Client,builder,director and product’ shows how they work to achieve the builder pattern. Client creates the object of the director class and passes the appropriate builder to initialize the product. Depending on the builder the product is initialized/created and finally sent to the client.

 

 

 

clip_image026

Figure: – Client, builder, director and product 

 

 

The output is something like this. We can see two report types displayed with their headers according to the builder.

 

 

clip_image027

Figure: – Final output of builder

 


Note :- In CD we have provided the above code in C# in ‘BuilderPattern’ folder.

 

 

Can you explain prototype pattern?

 

 

Prototype pattern falls in the section of creational pattern. It gives us a way to create new objects from the existing instance of the object. In one sentence we clone the existing object with its data. By cloning any changes to the cloned object does not affect the original object value. If you are thinking by just setting objects we can get a clone then you have mistaken it. By setting one object to other object we set the reference of object BYREF. So changing the new object also changed the original object. To understand the BYREF fundamental more clearly consider the figure ‘BYREF’ below. Following is the sequence of the below code:-
• In the first step we have created the first object i.e. obj1 from class1.
• In the second step we have created the second object i.e. obj2 from class1.
• In the third step we set the values of the old object i.e. obj1 to ‘old value’.
• In the fourth step we set the obj1 to obj2.
• In the fifth step we change the obj2 value.
• Now we display both the values and we have found that both the objects have the new value.

 

 

clip_image028

Figure :- BYREf

 

 

The conclusion of the above example is that objects when set to other objects are set BYREF. So changing new object values also changes the old object value.

There are many instances when we want the new copy object changes should not affect the old object. The answer to this is prototype patterns.

Lets look how we can achieve the same using C#. In the below figure ‘Prototype in action’ we have the customer class ‘ClsCustomer’ which needs to be cloned. This can be achieved in C# my using the ‘MemberWiseClone’ method. In JAVA we have the ‘Clone’ method to achieve the same. In the same code we have also shown the client code. We have created two objects of the customer class ‘obj1’ and ‘obj2’. Any changes to ‘obj2’ will not affect ‘obj1’ as it’s a complete cloned copy.

 

clip_image029

Figure: – Prototype in action 

 

 


Note :- You can get the above sample in the CD in ‘Prototype’ folder. In C# we use the ‘MemberWiseClone’ function while in JAVA we have the ‘Clone’ function to achieve the same.

Can you explain shallow copy and deep copy in prototype patterns?

There are two types of cloning for prototype patterns. One is the shallow cloning which you have just read in the first question. In shallow copy only that object is cloned, any objects containing in that object is not cloned. For instance consider the figure ‘Deep cloning in action’ we have a customer class and we have an address class aggregated inside the customer class. ‘MemberWiseClone’ will only clone the customer class ‘ClsCustomer’ but not the ‘ClsAddress’ class. So we added the ‘MemberWiseClone’ function in the address class also. Now when we call the ‘getClone’ function we call the parent cloning function and also the child cloning function, which leads to cloning of the complete object. When the parent objects are cloned with their containing objects it’s called as deep cloning and when only the parent is clones its termed as shallow cloning.

 

 

clip_image030

Figure: – Deep cloning in action

 

 

Can you explain singleton pattern?

 

 

There are situations in a project where we want only one instance of the object to be created and shared between the clients. No client can create an instance of the object from outside. There is only one instance of the class which is shared across the clients. Below are the steps to make a singleton pattern:-

1) Define the constructor as private.
2) Define the instances and methods as static.

Below is a code snippet of a singleton in C#. We have defined the constructor as private, defined all the instance and methods using the static keyword as shown in the below code snippet figure ‘Singleton in action’. The static keyword ensures that you only one instance of the object is created and you can all the methods of the class with out creating the object. As we have made the constructor private, we need to call the class directly.

 

clip_image032

Figure: – Singleton in action


 

Note :- In JAVA to create singleton classes we use the STATIC keyword , so its same as in C#. You can get a sample C# code for singleton in the ‘singleton’ folder.

Can you explain command patterns?

 

Command pattern allows a request to exist as an object. Ok let’s understand what it means. Consider the figure ‘Menu and Commands’ we have different actions depending on which menu is clicked. So depending on which menu is clicked we have passed a string which will have the action text in the action string. Depending on the action string we will execute the action. The bad thing about the code is it has lot of ‘IF’ condition which makes the coding more cryptic.

 

clip_image033

Figure: – Menu and Commands

 

Command pattern moves the above action in to objects. These objects when executed actually execute the command. 
As said previously every command is an object. We first prepare individual classes for every action i.e. exit, open, file and print. Al l the above actions are wrapped in to classes like Exit action is wrapped in ‘clsExecuteExit’ , open action is wrapped in ‘clsExecuteOpen’, print action is wrapped in ‘clsExecutePrint’ and so on. All these classes are inherited from a common interface ‘IExecute’.


 

clip_image034

Figure: – Objects and Command

 

Using all the action classes we can now make the invoker. The main work of invoker is to map the action with the classes which have the action. 
So we have added all the actions in one collection i.e. the arraylist. We have exposed a method ‘getCommand’ which takes a string and gives back the abstract object ‘IExecute’. The client code is now neat and clean. All the ‘IF’ conditions are now moved to the ‘clsInvoker’ class.


 

clip_image036

Figure: – Invoker and the clean client

 

Note: – You can find a sample code for C# code in command pattern in ‘Command’ folder. 

 

Define UML?

Unified Modeling Language, a standard language for designing and documenting a system in an object-oriented manner. It has nine diagrams which can be used in design document to express design of software architecture.

Can you explain use case diagrams?

Use case diagram answers what system does from the user point of view. Use case answer ‘What will the system do?’. Use cases are mainly used in requirement document to depict clarity regarding a system. There are three important parts in a use case scenario, actor and use case. 

Scenario: – A scenario is a sequence of events which happen when a user interacts with the system.

Actor: – Actor is the who of the system, in other words the end user. 

Use Case: – Use case is task or the goal performed by the end user. Below figure ‘Use Case’ shows a simple scenario with ‘Actor’ and a ‘Use Case’. Scenario represents an accountant entering accounts data in the system. As use case’s represent action performed they are normally represented by strong verbs.

Actor’s are represented by simple stick man and use case by oval shape as shown in figure ‘Use Case’ below.

clip_image037

Figure: – Use Case

Can you explain primary and secondary actors?


Actors are further classified in to two types primary and secondary actors. Primary actors are the users who are the active participants and they initiate the user case, while secondary actors are those who only passively participate in the use case.


How does a simple use case look like?


Use case’s have two views of representation in any requirement document. One is the use case diagrams and the other is a detail step table about how the use case works. So it’s like a pair first an over view is shown using a use case diagram and then a table explaining the same in detail. Below is a simple ‘login’ use case shown diagrammatically and then a detail table with steps about how the use case is executed.

clip_image038

Figure: – Login Use Case

Use Case

Rel001

Use Case Name

Login

Description

This uses depicts the flow of how user will log-in into the chat application.

Primary Actor

Simple chat user.

Trigger

User types chat application on URL of the browser.

Pre-condition

NA

Assumption

No password is currently present for the system
Rooms will remain constant as explained in the assumption section of this document

Failed End conditions

Duplicate user name is not allowed in the chat application.

Action

User clicks on the log-in button.

Main Scenario

• User types chat application on URL of the browser which in turn opens the main page.
• In the main page of application user is popped up with ‘Enter user name’ option and various ‘rooms’ option drop down menu.
• User then types the name and selects one of the room from drop down menu and then clicks on the ‘Log-in’ button.
• Application then checks whether the user name is unique in the system if not then user is popped up with error message that “user already exist”.
• After entering the unique name the user is finally logged in the application.

Action

NA

Alternate Scenario

NA

Success Scenarios

1. Opens page of a selected room in that other user names and their messages can be seen.

Note and Open Issues

NA

 

Table: – Login use case table

Note: – You must be wondering why we have this pair why not just a use case table only. Use case diagrams are good to show relationship between use case and they also provide high over view. The table explanation of a use case talks details about the use case. So when a developer or a user is reading a requirement document, he can get an overview by looking at the diagram if he is interested he can read the use case tables for more details.

Can you explain ‘Extend’ and ‘Include’ in use cases?


‘Extend’ and ‘Include’ define relationships between use cases. Below figure ‘Extend and Include’ shows how these two fundamentals are implemented in a project. The below use case represents a system which is used to maintain customer. When a customer is added successfully it should send an email to the admin saying that a new customer is added. Only admin have rights to modify the customer. First lets define extend and include and then see how the same fits in this use case scenario.

Include: – Include relationship represents an invocation of one use case by the other. If you think from the coding perspective its like one function been called by the other function.

Extend: – This relationship signifies that the extending use case will work exactly like the base use case only that some new steps will inserted in the extended use case.

Below figure ‘Extend and Include’ shows that ‘add customer’ is same as the ‘add discounted customer’. The ‘Add discounted customer’ has an extra process, to define discount for the discounted customer which is not available for the simple customer. One of the requirements of the project was that when we add a customer, the system should send an email. So after the customer is added either through ‘Add simple customer’ use case or ‘Add discounted customer’ use case it should invoke ‘send a email’ use case. So we have defined the same with a simple dotted line with <<include>> as the relationship.

clip_image038[1]

Figure: – Extend and Include

Note: – One of the points to be noted in the diagram ‘Extend and Include’ is we have defined inheritance relationship between simple and admin user. This also helps us defining a technical road map regarding relationships between simple and admin user.

Can you explain class diagrams?


Class diagram

Class is basically a prototype which helps us create objects. Class defines the static structure of the project. A class represents family of an object. By using Class we can create uniform objects.

In the below figure you can see how the class diagram looks. Basically there are three important sections which are numbered as shown in the below. Let’s try to understand according to the numbering:-
• Class name:-This is the first section or top most section of the Class which represents the name of the Class (clsCustomer).
• Attributes:-This is the second section or the middle section of the class which represents the properties of the system.
• Methods: – This section carries operation or method to act on the attributes.

clip_image039

Figure: – Three sections of the class

Now in the next section we will have a look on Association relationship between these classes.


How do we represent private, public and protected in class diagrams?


In order to represent visibility for properties and methods in class diagram we need to place symbols next to each property and method as shown in figure ‘Private, Public and Protected’. ‘+’ indicates that it’s public properties/methods. ‘-‘indicates private properties which means it can not be accessed outside the class. ‘#’ indicate protected/friend properties. Protected properties can only be seen within the component and not outside the component.


clip_image040

Figure: – Private, public and protected

what does associations in a class diagram mean?

Associations in Class diagrams


A single Class cannot represent the whole module in a project so we need one or more classes to represent a module. For instance, a module named ‘customer detail’ cannot be completed by the customer class alone , to complete the whole module we need customer class, address class, phone class in short there is relationship between the classes. So by grouping and relating between the classes we create module and these are termed as Association. In order to associate them we need to draw the arrowed lines between the classes as shown in the below figure. 

In the figure ‘Order is paid by payments class’, we can see Order class and the Payment class and arrowed line showing relationship that the order class is paid using payment class in other words order class is going to be used by payment class to pay the order. The left to right marked arrow basically shows the flow that order class uses the payment class.
In case payment class using the order class then the marked arrow should be right to left showing the direction of the flow.

clip_image041

Figure:- Order is paid by Payments class

There are four signs showing the flow:-

clip_image042

Figure: – Direction signs in UML

Multiplicity

Multiplicity can be termed as classes having multiple associations or one class can be linked to instances of many other classes. If you look at the below figure the customer class is basically associated with the address class and also observes the notations (*, 0 and 1).If you look at the right hand side the (1….*) notation indicates that at least one or many instance of the address class can be present in the customer class. Now towards left hand side we have (0….*) notation indicating that address class can exist without or many customer class can link him.
In order to represent multiplicity of classes we have to show notations like (1….*), (0….*) as shown in below figure.

Note: ‘*’ means “many” where as ‘(0, 1)’ means “(zero or at least one)” respectively.

clip_image043

Figure: – Multiplicity in Classes


Can you explain aggregation and composition in class diagrams?


In this Association there are two types mainly Aggregation Association and Composition Association.

Aggregation Association signifies that the whole object can exist without the Aggregated 
Object. For example in the below figure we have three classes university class, department class and the Professor Class. The university cannot exist without department which means that university will be closed as the department is closed. In other words lifetime of the university depend on the lifetime of department.

In the same figure we have defined second Association between the department and the Professor. In this case, if the professor leaves the department still the department continues in other words department is not dependent on the professor this is called as Composition Association.

Note: – The filled diamond represents the aggregation and the empty diamond represents the composition. You can see the figure below for more details.

clip_image044


Figure: – Aggregation and composition in action


What are composite structure diagram and reflexive association in class diagrams?

Composite structure diagramWhen we try to show Aggregation and Composition in a complete project the diagram becomes very complicated so in order to keep it simple we can use Composite structure diagram. In the below figure we have shown two diagrams one is normal diagram other is Composite structure diagram and the simplicity can easily be identified. In the composite diagram the aggregated classes are self contained in the main class which makes it simpler to read.


clip_image045

Figure: – Composite Structure diagram

Reflexive associations
In many scenarios you need to show that two instances of the same class are associated with each other and this scenario is termed as Reflexive Association. For instance in the below figure shows Reflexive Association in the real project. Here you can see customer class has multiple address class and addresses can be a Head office, corporate office or Regional office. One of the address objects is Head office and we have linked the address object to show Reflexive Association relationship. This is the way we can read the diagram Regional address object is blocked by zero or one instance of Head office object.

clip_image046

Figure: – Reflexive association


Can you explain business entity and service class?


Business entity objects represent persistent information like tables of a database. Just making my point clearer they just represent data and do not have business validations as such. For instance below figure ‘Business entity and service’ shows a simple customer table which with three fields ‘Customer Code’,’ Customer Address’ and ‘Phone Number’. All these fields are properties in ‘ClsCustomer’ class. So ‘ClsCustomer’ class becomes the business entity class. The business entity class by itself can not do anything it’s just a place holder for data. In the same figure we have one more class ‘ClsServiceCustomer’. This class aggregates the business entity class and performs operations like ‘Add’,’ Next’ (Move to next record), ‘Prev’ (Move to previous record) and ‘GetItem’ (get a customer entity depending on condition).

With this approach we have separated the data from the behavior. The service represents the behavior while the business entity represents the persistent data.

clip_image047

Figure:-Business entity and service


Can you explain System entity and service class?


System entity class represents persistent information which is related to the system. For instance in the below figure ‘System entity and service class’ we have a system entity class which represents information about ‘loggedindate’ and ‘loggedintime’ of the system registry. System service class come in two flavors one is it acts like a wrapper in the system entity class to represent behavior for the persistent system entity data. In the figure you can see how the ‘ClsAudit’ system entity is wrapped by the ‘ClsAuditSytem’ class which is the system service class. ‘ClsAuditSystem’ adds ‘Audit’ and ‘GetAudit’ behavior to the ‘ClsAudit’ system entity class.

clip_image048

Figure: – System entity and service class


The other flavor of the system service class is to operate on non-persistent information. The first flavor operated on persistent information. For instance the below figure ‘Non-persistent information’ shows how the class ‘ClsPaymentService’ class operates on the payment gateway to Check is the card exists , Is the card valid and how much is the amount in the card ?. All these information are non-persistent. By separating the logic of non-persistent data in to a system service class we bring high reusability in the project.

clip_image049

Figure: – Non-persistent information


Note: – The above question can be asked in interview from the perspective of how you have separated the behavior from the data. The question will normally come twisted like ‘How did you separate the behavior from the data?’.


Can you explain generalization and specialization?


Generalization and specializationIn Generalization and Specialization we define the parent-child relationship between the classes. In many instance you will see some of the classes have same properties and operation these classes are called super class and later you can inherit from super class and make sub classes which have their own custom properties. In the below figure there are three classes to show Generalization and Specialization relationship. All phone types have phone number as a generalized property but depending upon landline or mobile you can have wired or simcard connectivity as specialized property. In this diagram the clsphone represent Generalization whereas clslandline and clsmobile represents specialization.

clip_image050

Figure: – Generalization and Specialization


How do we represent an abstract class and interface UML?


Interface is represented by <<type>> in the class diagram. Below figure ‘Interface in action’ shows we have defined an interface ‘IContext’. Note the ‘<<type>>’ represents an interface. If we want to show that the interface is used in a class we show the same with a line and a simple circle as shown in figure ‘Interface in Action’ below.

clip_image051

Figure: – Interface in action

Abstract classes are represented by ‘{abstract}’ as shown in figure ‘Abstract classes in action’.

clip_image052

Figure: – Abstract classes in action.

How do we achieve generalization and specialization?

By using inheritance.

Can you explain object diagrams in UML?


Class represents shows the static nature of the system. From the previous question you can easily judge that class diagrams shows the types and how they are linked. Classes come to live only when objects are created from them. Object diagram gives a pictorial representation of class diagram at any point of time. Below figure ‘Object diagram’ shows how a class looks in when actual objects are created. We have shown a simple student and course relationship in the object diagram. So a student can take multiple courses. The class diagram shows the same with the multiplicity relationship. We have also shown how the class diagram then looks when the objects are created using the object diagram. We represent object with Object Name: Class Name. For instance in the below figure we have shown ‘Shiv : ClsStudent’ i.e ‘Shiv’ is the object and ‘ClsStudent’ the class. As the objects are created we also need to show data of the properties, the same is represented by ‘PropertyName=Value’ i.e. ‘StudentName=Shiv’.

clip_image053

Figure: – Object diagrams


The diagram also states that ‘ClsStudent’ can apply for many courses. The same is represented in object diagram by showing two objects one of the ‘Computer’ and the other of ‘English’.

Note: – Object diagrams should only be drawn to represent complicated relationship between objects. It’s possible that it can also complicate your technical document as lot. So use it sparingly.

Can you explain sequence diagrams?


Sequence diagrams
Sequence diagram shows interaction between objects over a specific period time. Below figure ‘Sequence diagram’ shows how a sequence diagram looks like. In this sequence diagram we have four objects ‘Customer’,’Product’,’Stock’ and ‘Payment’. The message flow is shown vertically in waterfall manner i.e. it starts from the top and flows to the bottom. Dashed lines represent the duration for which the object will be live. Horizontal rectangles on the dashed lines represent activation of the object. Messages sent from a object is represented by dark arrow and dark arrow head. Return message are represented by dotted arrow. So the figure shows the following sequence of interaction between the four objects:-

• Customer object sends message to the product object to request if the product is available or not.
• Product object sends message to the stock object to see if the product exists in the stock.
• Stock object answers saying yes or No.
• Product object sends the message to the customer object.
• Customer object then sends a message to the payment object to pay money.
• Payment object then answers with a receipt to the customer object.

One of the points to be noted is product and stock object is not active when the payment activity occurs.


clip_image054

Figure: – Sequence diagram


Messages in sequence diagrams
There are five different kinds of messages which can be represented by sequence 
Synchronous and asynchronous messages:-
Synchronous messages are represented by a dark arrow head while asynchronous messages are shown by a thin arrow head as shown in figure ‘Synchronous and Asynchronous’.

clip_image055

Figure: – Synchronous and Asynchronous

Recursive message:-
We have scenarios where we need to represent function and subroutines which are called recursively. Recursive means the method calling himself. Recursive messages are represented by small rectangle inside a big rectangle with an arrow going from the big rectangle to the small rectangle as shown in figure ‘Recursive message’.

clip_image056

Figure: – Recursive message


Message iteration:-

Message iteration represents loops during sequences of activity. Below figure ‘message iteration’ shows how ‘order’ calls the ‘orderitem’ objects in a loop to get cost. To represent loop we need to write ‘For each <<object name>>’. In the below figure the object is the ‘orderitem’. Also note the for each is put in a box to emphasize that it’s a loop.

clip_image056[1]

Figure: – Message iteration

Message constraint:-
If we want to represent constraints it is put in a rectangle bracket as shown in figure ‘message constraint’. In the below figure ‘message constraint’ the ‘customer’ object can call ‘book tickets’ only if the age of the customer is greater than 10.

clip_image057

Figure: – Message constraint

Message branching:-
Below figure ‘message branching’ shows how ‘customer’ object have two branches one is when the customer calls save data and one when he cancels the data.

clip_image058

Figure: – Message branching


Doing Sequence diagram practically
Let’s take a small example to understand sequence diagram practically. Below is a simple voucher entry screen for accounts data entry. Following are the steps how the accountant will do data entry for the voucher:-

  • Accountant loads the voucher data entry screen. Voucher screen loads with debit account codes and credit account codes in the respective combo boxes.
  • Accountant will then fill in all details of the voucher like voucher description, date, debit account code, credit account code, description, and amount and then click ‘add voucher’ button.
  • Once ‘add voucher’ is clicked it will appear in the voucher screen below in a grid and the voucher entry screen will be cleared and waiting for new voucher to be added. During this step voucher is not added to database it’s only in the collection.
  • If there are more vouchers to be added the user again fills voucher and clicks ‘add voucher’.
  • Once all the vouchers are added he clicks ‘submit voucher’ which finally adds the group of vouchers to the database.

Below figure ‘Voucher data entry screen’ shows pictorially how the screen looks like.

clip_image059

Figure: – Voucher data entry screen


Figure ‘Voucher data entry sequence diagram’ shows how the sequence diagram looks like. Below diagram shows a full sequence diagram view of how the flow of the above screen will flow from the user interface to the data access layer. There are three main steps in the sequence diagram, let’s understand the same step by step.

Step 1:- The accountant loads the voucher data entry screen. You can see from the voucher data entry screen image we have two combo boxes debit and credit account codes which are loaded by the UI. So the UI calls the ‘Account Master’ to load the account code which in turn calls the data access layer to load the accounting codes.

Step 2:- In this step the accountant starts filling the voucher information. The important point to be noted in this step is that after a voucher is added there is a conditional statement which says do we want to add a new voucher. If the accountant wants to add new voucher he again repeats step 2 sequence in the sequence diagram. One point to be noted is the vouchers are not added to database they are added in to the voucher collection.

Step 3:- If there are no more vouchers the accountant clicks submit and finally adds the entire voucher in the database. We have used the loop of the sequence diagram to show how the whole voucher collection is added to the database.

clip_image060

Figure: – Voucher data entry sequence diagram

 

Digg This