DS Lab 5 Review Solved

 

Lab 5
Review

In this tutorial, we will review Linked List, Stack, Queue, Recursion and Sorting to prepare for the midterm examination.

1. Linked List
Implementing the integer Linked List following the class diagram:

 

(a)            Method public void addFirst(int data): add the new node contains data to the head of the linked list.

(b)           Method public boolean addLast(int data): this method first checks if the entered data already existed in the the linked list then return false. Otherwise, this method will add the new node as the last element of the linked list and return true if the node is added successfully.

(c)            Method public boolean removeAt(int position): if the position value is larger than the number of nodes in the linked list, this method will return false, if not, this method will remove the element at the position given by the paramater and return true if the node is removed. (position 1 is the head of linked list)

(d)           Method public int countOdd(): return how many odd numbers there are in the linked list.



dcquang@it.tdt.edu.vn   1 (e) Method public int searchKey(int key): return the position of the node which contains the key value. If there are no elements with the key value, the method will return -1. (position 1 is the head of linked list)

(f) Method public boolean checkSorted(): return true if the linked list is sorted in ascending or descending order, if not, return false.

2. Stack and Queue

Exercise 1
Reimplemeting the Stack in Lab 2. We will use Stack<String or Stack<Character to solve this exercise. Giving an infix:

((9 - 2) * 6 + 7) / 7

We can transform to postfix:

9 2 - 6 * 7 + 7 /

Implement a function using Stack to calculate the result from postfix. This is the pseudocode:



CalculatePostfix(String 𝑠) Split s into the array 𝑠𝑝𝑙𝑖𝑡_𝑐ℎ for 𝑐ℎ : 𝑠𝑝𝑙𝑖𝑡_𝑐ℎ do

if 𝑐ℎ is an operator then

𝑎 ←pop first element from stack 𝑏 ←pop second element from the stack

res ←𝑏 ”operator” 𝑎 push res into the stack

end

𝑐ℎ is an operand add ch into the stack end return element of stack top



Exercise 2
Using a Stack and a Queue to check a positive integer number 𝑛 is palindrome or not. (Examples of the palindrome number: 101, 256652, 1221, 121)

3. Recursion

Exercise 1
(a)            Implement function public double prod_recur(int a, int b) to calculate product of 2 numbers using recursion.

(b)           Implement function public int bin2dec(int n, int exp) to convert a binary number (in decimal number form) to decimal number using recursion. Ex: Given n = 1000, bin2dec(n, 0) = 8

(c)            Implement function public int maxDigit(int n) to find the largest digit in a positive integer n using recursion.

(d)           Implement function public int maxElement(int a[], int n) to find the largest element in an array a using recursion.

(e)            Implement function public int search(int a[], int n, int key) to find the position of the key in an array a, if key is not in the array, return -1, using recursion.

Exercise 2
Solve this exercise in 2 ways, using recursion and using iteration

(a)        ∑𝑛𝑖=1(2𝑖)

(b)        ∑𝑛𝑥=0(𝑥+12  )

(c)        ∑𝑛𝑖=1((𝑖−1)!𝑖!        )

(d)        ∑𝑛𝑥=1(𝑥∗(𝑥 −1))

(e)        ∏𝑛𝑥=1(𝑥)

Exercise 3
For each sub-exercise below, define 2 functions, one uses recursion to solve and the other uses iteration to solve:

(a)

2, 𝑛 = 0 𝐴(𝑛) = {   1

                                                             2−    𝐴(𝑛−1),      𝑛 0

2

(b)

                                                                               1,    𝑛 < 10

𝐴(𝑛) = {

                                                              1 + 𝐴(𝑛/10),      𝑛 ≥ 10

(c)

n, 𝐴(𝑛,𝑘) = {

𝑛+𝐴(𝑛,𝑘 −1),

(d)
𝑘 = 1

𝑘 1
                                               ⎧{                                0,

𝐹(𝑛) = ⎨{ 𝐹(𝑛 −1) +𝐹(𝑛 −2)1,,
n = 0 n = 1 otherwise
⎩

4. Sorting
Implement Selection Sort, Bubble Sort and Insertion Sort again, but you need to print to the screen the state of the array before each outer loop for statement completed.

Example: We sort an array a in ascending order and follow this rules:

1.   Selection Sort: choose minimum element

2.   Bubble Sort: ”bubbling up” the largest element to the right partition of the array

3.   Insertion Sort: insert the number to the left partition of the array

We will have result print on screen:

•     Selection Sort - With array 𝑎 = {3,1,4,6,2,5}

 

•     Bubble Sort - With array 𝑎 = {5,3,4,2,6,1}

 

•     Insertion Sort - With array 𝑎 = {5,1,2,6,4,3}