# DSA Exercises

## Ex1
a. Insert the following sequence of elements into an AVL tree, starting with an empty tree: 10, 20, 15, 25, 30, 16, 18, 19.

b. Delete 30 in the AVL tree that you got.

## Ex2

a. What is the sequence of level-order, inorder, preorder, postorder traversal in the tree that you got at Ex1.

b. Given an AVL tree T, is it always possible to build the same tree by a sequence of BSTinsert and delete operations (with no rotations)?

## Ex3

Implement Counting Sort using C++. Then show the contents of the data arrays (input, count, output) used in the Counting Sort for the following input data: 4, 2, 2, 8, 3, 3, 1

## Ex4

Suppose you have the following has table, implemented using *linear probing*. For the hash function we are using the identity function modulo the length of the list, **h(x) = x mod 9**:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 27 | 9 | | 12 | 3 | 14 | 4 | 21 | |

In which order could the elements have been added to the hash table?

## Ex5

Given a hash table with m = 11 entries and the following hash function h1 and step function h2:
- h1(key) = key mod m
- h2(key) = {key mod (m-1)} + 1

Insert the keys {22, 1, 13, 11, 24, 33, 18, 42, 31} in the given order (from left to right) to the hash table using each of the following hash methods:

a. Chaining with h1 $\to$ h(k) = h1(k)
b. Linear-Probing with h1 $\to$ h(k,i) = (h1(k)+i) mod m
c. Double-Hashing with h1 as the hash function and h2 as the step function $\to$ h(k,i) = (h1(k) + ih2(k)) mod m

## Ex6

What is the time complexity of the following pseudo-code:

factorial(n):
    if n is 0
         return 1
    return n * factorial(n-1)

## Ex7
For $f(N)$ find a simple $g(N)$ such that $f(N) = O(g(N))$.

- $f(N) = N + 1$
- $f(N) = 1 + \frac{1}{N}$
- $f(N) = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{N}$
- $f(N) = (1 + \frac{1}{N})(1 + \frac{2}{N})$
- $f(N) = 2N^3 – 15N^2 + N$
- $f(N) = \frac{lg(2N)}{lg N}$
- $f(N) = \frac{lg(N^2 + 1)}{lg N}$
- $f(N) = \frac{N^{100}}{2^N}$

## New (in Vietnamese)

1. Cho một đồ thị vô hướng biểu diễn bằng ma trận kề;
- đếm số thành phần liên thông
- cho biết đồ thị có là cây?

2. Cho một cây nhị phân tìm kiếm chứa các số nguyên. Hãy tìm số lớn chẵn lớn nhất nhỏ hơn k.

3. Cho 1 tự điển 1 triệu từ, hãy thiết kế cách lưu trữ bằng hash và xử lý đụng độ bằng chaining. Viết code minh họa.

4. Điểm tốt nghiệp của SV từ 5.0 đến 10, làm tròn đến 0.1. Điểm này được lưu trong mảng S có N phần tử và chưa được sắp xếp.
- Hãy cho biết điểm nhỏ nhất của top 30% là bao nhiêu. Yêu cầu không được sắp xếp và chỉ được duyệt qua mảng đã cho đúng 1 lần.
- Hãy phân tích độ phức tạp của thuật toán.
- Ví dụ:
- input N = 10, S= {5.1, 7.4, 8.4, 6.7, 9.3, 5.6, 8.5, 6.5, 8.4, 7.1}
- output: 8.5