data

Question 1

important of Huffman coding

Answer 1

1) it is an algorithm to compress data
2) it applies compression algorithm to take a large file and store it as a smaller set of data
3) it applies decompression algorithm to take smaller compressed data and get the original back

Question 2

methods for data compression

Answer 2

1) Use ASCII Code - each character takes 8-bits
2) Use 3-bit to encode each character
3) Use Huffman Code
- use variable length code
- use fewer bits for more frequently occuring characters

Question 3

Calculate memory of Huffman Code

Answer 3

1) File Size: Frequency * number of bits
2) Table Size: (Frequency * 8) + (number of total bits)

Question 4

List 4 types of Shortest Path Problem

Answer 4

1) Single Source: Find a shortest path from a given source to each vertex
2) Single Destination: Find a shortest path to a give destination from each vertex
3) Single Pair: Find a shortest path from a to t, for given vertices a and t in a graph
4) All Pairs: Find a shortest path for every pair of vertice in graph

Question 5

Compare Dijkstra and Floyd Algorithm

Answer 5

similarity = can support both direct and non directed graoh

dijkstra = non negative weight

floyd = can support negative weight
= assume non-negative cycles

Question 6

the time complexity for Dijkstra Algorithm using Adjacency Matrix, Min Heap,

time complexity for Floyd Algorithm

Answer 6

1) Adjacecny Matrix = O(V2)
2) Min Heap Adjacency List = O(E(log V)

3) Floyd = O(V3)

Question 7

Types of Minimum Spanning Tree & their Time Complexity

Answer 7

1) Prim’s O(1)
2) Kruskal’s O(n2)
min heap > O(nlogn)

3) Topological Sort

Question 8

Important of knowing whether it is a spare/dense graph

Answer 8

1) it affects the choice of data structure to represent graph
2) it affects the choice of algorithm to process graph

Question 9

Advantages of Adjacency Matrix Representation

Answer 9

1) Simple and Clear
2) O(1) to check whether any 2 vertices have edges connecting to them
3) O(V) to find all adjacent vertices of V

Question 10

Disadvantages of Matrix Representation

Answer 10

1) Waste of time and space on Sparse Graph

Question 11

Advatages of Adjacency List

Answer 11

1) O(V) time to find all the adjacent vertices of V
2) Space efficient of Sparse Graph

Question 12

Disadvantages of Adjacency List

Answer 12

1) O(V) time to check whetehr any 2 vertices have edges connecting them

Question 13

Definition of Sparse & Dense Graph

Answer 13

Sparse
- number of edges is closer to the number of vertices

Dense
- number of edges is closer to the sequared of number of vertices

Question 14

Definition of Strongly connect Graph, Weakly Connected Graph and Complete Connected Graph

Answer 14

Strongly Connected Graph
- There is a path for every vertices to every other vertices in directed graph

Weakly Connected Graph
- There is a path for every vertices to every other vertice ignoring the direction of edge

Complete Connected Graph
- For every pair of vertices, u not equal to v, there exist an edge from u to v