Coursera 1 (https://class.coursera.org/algs4partI-007/lecture)

Question 0

why algorithms? why is n square so bad?

Answer 0

rough standard is 10 to power 9 ops per second. that means touch all such words (billion) in memory in 1 sec.
But 10 to power 18 will take 30 years.

Question 1

dynamic connectivity (is there a path between 2 pts) is referred to as?

Answer 1

Union - Find. Pixels is photo. computers in network.

1. create groups of connected elements
2. better is to create a tree as unions happen and 2 elems connected if root same
3. further improve to keep tree balanced by moving a smaller size tree within larger one
4. further improve by balancing lazily when find operation is triggered

Question 2

What is Monte Carlo method?

Answer 2

Computational (not mathematical) algos that rely on repeated random sampling. eg sprinkle random points in square and a circle inside to guess PI.
Percolation probability in a square of connected points used this plus Union-find algo to find that cutoff probability when percolation will happen.

Question 3

what is 3-sum problem and how to do better than n cube?

Answer 3

In an array of numbers, find cases where sum of 3 = zero.
instead of 3 loops, sort the array and then for every 2 numbers binary search for -(n+m)

even if sort is n square, binary search is log n
so total is n square log n still better

Question 4

What are commonly used notations for complexity measure?

Answer 4

Tilde, Big Theta, Big Oh, Big Omega

Big Oh develops upper bounds while Big Omega develops lower bounds. Tilde is approximate model

Question 5

Memory sizes for Java arrays?

Answer 5

In bytes:
char[] = 2N + 24
int[] = 4N + 24

Question 6

Memory sizes for some objects in Java, like Date and String?

Answer 6

Object overhead = 16 bytes
and optional padding to round to multiple of 8 = ~4 bytes

Date object = 16 + (3 ints for year, month, day) + 4 padding = 32 bytes
String object = 16 + (char[] = 2N + 24) + char[] reference (8 bytes) + (3 ints for offset, count, hash) + 4 padding = 2N + 64 bytes

(Note: Some JVMs support compressed pointers of 4 bytes)

Question 7

What two data structures can be used to create a Stack or Queue impl?

Answer 7

LinkedList and array[]

LinkedList uses more memory due to object overhead, however all operations are O(1)
With array impl, you have to resize array (both up and down) by factor of 2. When resizing down though, better to wait till 25% of array is full before reducing array by half.

Question 8

What is Djiktra’s 2 stack algo?

Answer 8

For arithmetic operations, solve them via 2 stacks. One stack for values, other for operators. Whenever closing bracket encountered, pick top values from both stack and operate and but value on value stack.
(1 + (2 + 4) * (5-1))

It adds to basis of computation, as well as compilers!

Question 9

Selection sort?

Answer 9

Most basic. Move one index at a time, and swap with min beyond that index. Brings forward the min item one by one by comparisons.
Num compares = N square / 2
Max Num swaps = N

Question 10

Insertion sort?

Answer 10

Very basic. Grabs an extra element (like insert a new element in array) and brings it into position with existing sorted elements.
Num compares = ~ N square / 4

Best case compares = N if already sorted. Worst case is N square / 2

However for partially sorted arrays this still is linear!

Question 11

Shell sort?

Answer 11

Shell == inventor’s name.
Instead of moving in increments of 1, increments of say 3x+1 … better performance but hard to put in O(n) terms.

3,6,2,5,1
First iteration use increment = 4, compare (and swap if needed) 3 and 5 and then 6 and 1 etc
Second iteration use increment = 1 and start again

Question 12

How to implement shuffling?

Answer 12

One way is to assign random float (0-1) to each entry and sort. Performance is as good as sort is.

Better is knuth shuffle: In linear traversal, for every ith card, generate random between first card and ith card and swap the cards. Works like a charm!

Question 13

Convex hull?

Answer 13

It is perimeter on points in 2D where we can make polygon with least vertices. Helps in finding smallest distance around a cluster of points.
first sort points by y coord, then by polar angle. Start traversing and ignore points that involve counter-clockwise turn.

Question 14

Merge sort?

Answer 14

Divide and conquer from middle point. Merge function merges two sorted arrays.

Disadv: Pure version needs an auxillary array of N size. In-place merge becomes tough.
NlogN perf though.

Question 16

Quicksort?

Answer 16

Fastest sort!!!
Still NlogN but faster than mergesort. Plus is in-place.

Here find a pivot (First element of array). Move two pointers to create 2 badges, one small and one larger than pivot. Swap the pivot to position it in between the badges. Recurse on both sides.

Important to shuffle to have good distribution.

Question 17

Good impl of priority queues?

Answer 17

Binary Heap. Heap can simply be an array where:
parent index = child index / 2
children index = parent index * 2 and parent index * 2 + 1

log N time to take node max out as well as insert.
Take max out: Replace smallest on the root and call ‘sink’ on it.
Insert: Call ‘swim’ on it to get to the upper position.

Heap sort comes into picture: First starting from N/2 array, call sink to heapify sections of heap in children. Once heap properties done, one by one move max out of the heap and replace with smallest and call sink on it.

Question 18

How to implement event driven simulation? (X balls in 2D space colliding with walls and each other)

Answer 18

Keep a priority queue of next event.

First initialize queue (in quadratic time) based on velocity and coords etc with respect to time till next collision, then dequeue and act on it (Skip act if invalid interaction i.e. using counts on collisions, if already collision has happened). If perform collision, recompute events for the collided ones with respect to all other.

Without the event queue, cost will be quadratic after every x time of checking the state.

Question 19

What are impls of symbol tables?

Answer 19

Unordered (Linked List with composite key-value) or ordered array (pair of arrays with keys and values on separate arrays).

Ordered is much better since binary search can be performed to search for key (logarithmic) as well as several other APIs (Ordered operations like count, min, max, floor, ceil, rank) can be supported.

Better is BST: Binary search tree offers better support. But for other APIs like Ordered operations, the tree node will have to keep a count of children and then recursions can be run on queries.
Delete in BST is difficult and leads to more unbalanced tree. From log N perf gets to square-root N (which isnt good).

Question 20

What are 2-3 trees?

Answer 20

Balanced tree impl. Each node is not one entry but can be 2 entries as well. In case of 2 entries there will be 3 children node between those 2 nodes. In insert case, if 2 entries becomes 3 entries, we move the middle entry UP a level and split tree accordingly. We swim up the tree if further 3 entries exist.
Note that whenever tree increases in levels, its because the root splits because of 3 entries.

Question 21

What are Red-Black trees?

Answer 21

Pretty much same concept as 2-3 trees just that makes it a true binary tree (1 entry per node) and easier to implement. Conceptually same balanced tree. Understand red edge between nodes is same as ‘internal connection’ to entries in single node.

LLRB tree == Left leaning red black tree

On balancing, left reference is only red. No 2 reds together.

On insert, always make red edge.
Right child red, left black == rotate left.
Left child red, left left grandchild left == rotate right. (Top node comes to right)
Both children red, flip colors.

Question 22

What are B-trees?

Answer 22

In practicality, page fetch from hard disk is costlier for every tree node traversal. Hence just like 2-3 trees, we go for N-tree model. Each node contains ‘starting points’ do facilitate left or right traversal. Only leaf nodes contain data. Splitting happens if nodes get full just like 2-3 trees.

Question 23

What are two collision handling methods for hashing based symbol tables?

Answer 23

Separate chaining: Create a linked list on each node and add elements if collision happens.

Linear probing: If collision, move to i+1, i+2 the next empty space. When searching too if not found, keep moving ahead and looking. The size of array needs to be larger than N

Both give constant time perf.

Question 24

Hash tables vs. BST?

Answer 24

HT are simple to code but BST have stronger perf guarantees, support for ordered ops.

Java has TreeMap as BST.

Question 25

How to do 1-d search (range search / between query) using BST?

Answer 25

Keep ranks as well on BST nodes. When querying how many nodes in range, simple difference in ranks work. When fetching all nodes in range, traverse both sides of root node recursively and keep picking if in range.

Question 26

How to efficiently find line intersections (only 0 degree or 90 degree slopes) in a rectangle?

Answer 26

Do sweep-line analysis on x axis i.e. Sweep from left to right and keep adding every y-start to BST. Remove entry if y-end on a line is encountered.
When a vertical line encountered, do a range search of y in between to find intersection.

Using ‘interval trees’ same logic can be used to find intersecting rectangles!

Question 27

What are 2d trees? (And Kd trees?)

Answer 27

2d trees are designed for 2 dimensional space problems. If there are points scattered on a plane, problems like all points in a rectangle range can be answered.

Also nearest neighbor algo can be addressed.

2d tree is a BST where you divide the plane into 2 halves on each point. You start vertically and then next level is horizontal and then again vertical.

Kd is for K dimensions in similar fashion.