Data structures and algorithms 2
Why do we need a high level language? - Answer- High-level languages encourage
you to think more about the problem domain and less about the execution platform.
There is less ceremony, so you can spend more time on stuff that actually brings you
value. Money. Cheaper developers, faster development speeds, and less bugs equal
more money.
A high level language is easier to code in and therefore less error prone.
Program - Answer- A set of instructions for the computer to perform a task.
It can be stored in memory or downloaded from the internet.
when do you use float instead of double? - Answer- Though both Java float and
Double can represent floating-point numbers, we can consider a couple of things to
choose between Java float and double.
Though both Java float vs Double is approximate types, use double if you need more
precise and accurate results. Use float if you have memory constraint because it
takes almost half as much space as double. If your numbers cannot fit in the range
offered by float, then use double. Though be careful with floating-point calculation
and representation, don't use double or float for monetary calculation, instead use
Big Decimal.
What is selection? - Answer- Making the program behave differently each time it
runs.
the switch statement - Answer- In computer programming languages, a switch
statement is a type of selection control mechanism used to allow the value of a
variable or expression to change the control flow of program execution via search
and map.
Designing algorithms - Answer- A strategy to solve a problem in terms of
1. the actions to be executed
2. the order in which the actions are to be executed
when do we use a for loop? - Answer- generally used when the number of repetitions
or iterations is known in advance.
For example, you know there are 10 students in a class and you want to calculate
the average mark for them all.
What to do when the number of loops is not fixed? - Answer- Use a while loop
What is the difference between a while loop and a for loop? - Answer- A while loop
causes the code inside it to be repeated until some condition is satisfied.
A for loop is repeated for a fixed number of iterations.
,Asymptotic Notation - Answer- Asymptotic notations are the mathematical notations
used to describe the running time of an algorithm when the input tends towards a
particular value or a limiting value.
For example: In bubble sort, when the input array is already sorted, the time taken by
the algorithm is linear i.e. the best case.
But, when the input array is in reverse condition, the algorithm takes the maximum
time (quadratic) to sort the elements i.e. the worst case.
When the input array is neither sorted nor in reverse order, then it takes average
time. These durations are denoted using asymptotic notations.
There are mainly three asymptotic notations:
Big-O notation
Omega notation
Theta notation
What types of trees do you know? - Answer- Free trees
Binary
Positional trees
Rooted trees
Ordered trees
Define a free tree - Answer- In a free tree there's no designated root vertex.
You can make a free tree into a rooted one by choosing any of its vertices to be the
root.
Define rooted tree - Answer- In graph theory, the basic definition of a tree is that it is
a connected graph without cycles. This definition does not use any specific node as
a root for the tree. A rooted tree introduces a parent — child relationship between the
nodes and the notion of depth in the tree.
Roughly and visually, adding a root to a tree just corresponds to grabbing one of the
nodes of the tree and hanging the tree with this node. Once the tree is hanged, each
node has a depth related to its height, a parent to which it is suspended and several
children which hang from this node.
what is a binary and positional tree - Answer- a binary tree is a tree data structure in
which each node has at most two children, which are referred to as the left child and
the right child.
A tree is either empty or consists of a node containing a label value and an indexed
sequence of zero or more children, each a positional tree. If every node has two
positions, we have a binary tree and the children are its left and right subtrees.
Again, nodes are the parents of their non-empty children.
How can you distinguish between binary trees and ordered trees - Answer- An
ordered tree is an oriented tree in which the children of a node are somehow
"ordered."
What sorting algorithms do you know? - Answer- Quicksort
, Heapsort
merge sort
insertion sort
Insertion Sort - Answer- Each item is take in turn, compared to the items in a sorted
list and placed in the correct position.
A simple sorting algorithm that builds the final sorted array (or list) one item at time. It
is much less efficient on large lists than more advanced algorithms such as
quicksort, heapsort, or merge sort.
Insertion sort sorts in place and therefore uses less memory space. Though its
asymptotic running time is O(n^2), its code is very tight so the constant factor in the
running time is very small. Insertion sort is, therefore, an efficient algorithm for a
small input size.
Merge Sort Algorithm - Answer- Sorts an array by cutting the array in half,
recursively sorting each half, and then merging the sorted halves
Insertion Sort Algorithm - Answer-
Insertion Sort Worst Case - Answer- O(n^2)
Heapsort algorithm - Answer- a sorting algorithm that inserts the values to be sorted
into a heap
Heapsort Worst Case - Answer- n log n
Quick Sort Worst Case - Answer- O(n^2)
Quick Sort - Answer- Unstable, O(n log n) for a good pivot,O(n^2) for a bad pivot Ω(n
log n) : Uses partitioning O(n), Pick a median of 1st, middle, and last element for
pivot. Random selection is also good, but expensive. Algorithm can be slow because
of many function calls.
Sorts in place - Answer- in-place sort
(algorithm)
Definition: A sort algorithm in which the sorted items occupy the same storage as the
original ones. These algorithms may use o(n) additional memory for bookkeeping,
but at most a constant number of items are kept in auxiliary memory at any time.
Also known as sort in place.
Generalization (I am a kind of ...)sort.
Specialization (... is a kind of me.)American flag sort, quicksort, insertion sort,
selection sort, Shell sort, diminishing increment sort, J sort, gnome sort.
Heap Data Structure - Answer- The (binary) heap data structure is an array object
that we can view as a nearly complete binary tree
Nearly complete binary tree - Answer- An almost complete binary tree is a special
kind of binary tree where insertion takes place level by level and from left to right
