Description

Submission Link: https://forms.gle/wjnELjkCCi4gZCxcA
Submission Guidelines:
1. You can code all of them either in Python or Java. But you should choose 1 language for all tasks.
2. For each task write separate python files like task1.py, task2.py and so on.
3. For each problem, take input from files called “inputX.txt”, and output at
“outputX.txt”, where X is the task number. So, for problem 2, input file is basically this, “input2.txt”. Same for output.
4. For each task include the input files(if any) in the submission folder.
5. All files MUST be put in a folder. The folder MUST be named following the format sec_ID_labNo. Zip this folder. This will result in a zip format of sec_ID_labNo.zip. (Example: 2_20101234_1.zip). Submit this zip in the above mentioned submission link.
6. Don’t copy from you
7. You MUST follow all the guidelines, naming/file/zipping convention stated above.
Failure to follow instructions will result in straight 50% mark deduction.
Problem Descriptions:
The following tasks need to be solved using Sorting Algorithms. Sorting algorithm is an algorithm that is used to arrange data in certain order, i,e- either ascending or descending order. We use sorting algorithms on numerical and lexicographical data to optimize the efficiency of other algorithms. You have learned several sorting algorithms such as bubble sort, insertion sort, selection sort, quick sort,merge sort etc. The problems below are related or similar to some of the sorting algorithms you learned in class. Read the task descriptions carefully and implement the algorithm using either Java or Python. The output format MUST match exactly as shown in each task.
Task 1:
Here is code of bubble sort. It’s run time complexity is θ(n2). Change the code in a way so that its time complexity is θ(n) for the best case scenario. Find the best case and change the code a little bit. And explain how you did it in a comment block of your code.
def bubbleSort(arr):
for i in range(len(arr)-1):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
swap( arr[j+1], arr[j] )
Input 1:
5
3 2 1 4 5 Input 2:
6
10 20 5 15 25 30
Output 1: 1 2 3 4 5 Output 2:
5 10 15 20 25 30
Task 2:
You have a list of elements and their prices. Select your preferred lists from the item based on lowest price. So to complete the task you have a tool called selection sort.
In selection sort:
● Select the minimum element from the unsorted part of the given array.
● Move the selected element to a sorted part of the array. ● Repeat this process to make the unsorted array sorted.
Here is pseudo code:
𝑓𝑜𝑟 𝑖 ← 0 𝑡𝑜 𝑛 − 1
𝑚 = 𝑎𝑟𝑔𝑚𝑖𝑛𝑗 (𝐴[𝑖], 𝐴[𝑖 + 1], . 𝐴[𝑛 − 1])
𝑠𝑤𝑎𝑝 (𝐴[𝑖], 𝐴[𝑚])
𝑒𝑛𝑑 𝑓𝑜𝑟
Use the above pseudo code to complete the selection sort.
First line of the input will contain N items and M preferred choices (where M ≤ N). The next line will contain the price of each element. Output will contain the price of M number of preferred elements.
Input 1: 5 3 Input 2: 7 4
5 10 2 1 4 10 2 3 4 1 100 1
Output 1: 1 2 4 Output 2: 1 1 2 3
Task 3:
Suppose you are given a task to rank the students. You have gotten the marks and id of the students. Now your task is to rank the students based on their marks using only insertion sort.
Here is the pseudocode for insertion sort.
𝑓𝑜𝑟 𝑖 ← 0 𝑡𝑜 𝑛 − 1
𝑡𝑒𝑚𝑝 ← 𝐴[𝑖 + 1]
𝑓𝑜𝑟 𝑗 ← 𝑖 𝑡𝑜 0
𝑖𝑓(𝐴[𝑗] > 𝑡𝑒𝑚𝑝)
𝐴[𝑗 + 1] ←𝐴[𝑗]
𝑒𝑙𝑠𝑒
𝑏𝑟𝑒𝑎𝑘
𝑒𝑛𝑑 𝑓𝑜𝑟
𝐴[𝑗 + 1] ← 𝑡𝑒𝑚𝑝
𝑒𝑛𝑑Implement this pseudocode to complete your task. 𝑓𝑜𝑟
First line will contain an integer N. The next line will contain N number of id of the students.The next line will contain the N number of the marks of corresponding students. Output will be ranking the id based on their marks (descending order).
Input 1:
5
11 45 34 22 12
40 50 20 10 10 Input 2:
6
1 2 3 4 5 6
50 60 80 20 10 30
Output 1:
45 11 34 22 12 Output 2:
3 2 1 6 4 5
Task 4:
Here is the problem, just simply sorting an array. Now, to sort the array you should use efficient sorting techniques. It will have worst-case time complexity better than the above sorting algorithms. The sorting algorithm pseudocode is given below:
𝑀𝐸𝑅𝐺𝐸 (𝐴, 𝑝, 𝑞, 𝑟 )
𝑛1 ← 𝑞 − 𝑝 + 1
𝑛2 ← 𝑟 − 𝑞
𝐶𝑟𝑒𝑎𝑡𝑒 𝑎𝑟𝑟𝑎𝑦𝑠 𝐿[1 . . 𝑛1 + 1] 𝑎𝑛𝑑 𝑅[1 . . 𝑛2 + 1]
𝐹𝑂𝑅 𝑖 ← 1 𝑡𝑜 𝑛1
𝐷𝑂 𝐿[𝑖] ← 𝐴[𝑝 + 𝑖 − 1]
𝐹𝑂𝑅 𝑗 ← 1 𝑡𝑜 𝑛2
𝐷𝑂 𝑅[𝑗] ← 𝐴[𝑞 + 𝑗 ]
𝐿[𝑛1 + 1] ← ∞
𝑅[𝑛2 + 1] ← ∞
𝑖 ← 1
𝑗 ← 1
𝐹𝑂𝑅 𝑘 ← 𝑝 𝑇𝑂 𝑟
𝐷𝑂 𝐼𝐹 𝐿[𝑖 ] ≤ 𝑅[ 𝑗]
𝑇𝐻𝐸𝑁 𝐴[𝑘] ← 𝐿[𝑖] 𝑖 ← 𝑖 + 1
𝐸𝐿𝑆𝐸 𝐴[𝑘] ← 𝑅[𝑗]
𝑗 ← 𝑗 + 1
𝑀𝐸𝑅𝐺𝐸 − 𝑆𝑂𝑅𝑇 (𝐴, 𝑝, 𝑟)
𝑖𝑓 𝑝 < 𝑟 // 𝐶ℎ𝑒𝑐𝑘 𝑓𝑜𝑟 𝑏𝑎𝑠𝑒 𝑐𝑎𝑠𝑒
𝑞 = (𝑝 + 𝑟)/2
𝑀𝐸𝑅𝐺𝐸 − 𝑆𝑂𝑅𝑇 (𝐴, 𝑝, 𝑞)
𝑀𝐸𝑅𝐺𝐸 − 𝑆𝑂𝑅𝑇 (𝐴, 𝑞 + 1, 𝑟)
𝑀𝐸𝑅𝐺𝐸 (𝐴, 𝑝, 𝑞, 𝑟)
Take help from pseudocode or use your way to complete the task.
First line will contain N . The next line will contain N number of elements. The output will contain a sorted N number of elements (ascending order).
Input 1:
5
5 -1 10 2 8 Input 2:
6
10 20 3 40 5 6
Output 1:
-1 2 5 8 10 Output 2:
3 5 6 10 20 40