DSA Lab Assignment 1 - Time and space complexity of different data structures & algorithms

Q 1:

Write the time and space complexity of the following data structures:

• Array
• Stack
• Queue
• LinkedList
• HashTable
• BinarySearchTree
• AVL

Also write the time complexity of Insertions, Deletion and Access operations of above mentioned data structures.

Q 2:

Write the time and space complexity of the following algorithms:

• Quick Sort
• Selection Sort
• Bubble Sort
• Merge Sort
• Insertion Sot
• Linear Search
• Binary Search

DSA Lab 4 - Recursion & Sorting Algorithems

Task 1:

Implement the following algorithms recursively:

• sumOfArray()      // This function will take an integer array as input and output its sum.
• computeFactorial()    //This function will take an integer as input and output its factorial
• displayFibonacciSeries()    //This function will take an integer as input and output that many terms of fibonacci series. e.g input = 6 then output = 1 1 2 3 5 8

Task 2:

Implement the following sorting algorithms recursively:

• mergeSort()
• quickSort()

Note: we have implemented these sorting algorithms before in lab 2. This time we have to implement them recursively. 

DSA Lab 3 - Queue & Post-fix In-fix expressions

Task 1:

Write the complete implementation of double ended queue (as discussed in class) containing the following functions:

• enqueueAtTail()
• dequeueAtTail()
• enqueueAtHead()
• dequeueAtHead()
• isEmpty()
• isFull()
• resizeQueue()    //This function will double the size of the queue when it is 75% full and half the size of it when it is 25% full.

Note: you have to implement queue with integer array (not with pointers).

Task 2:

Use the queue you have implemented in Task 1 and write a code to convert an in-fix expression into post-fix expression. You have to implement the following 2 functions:

• convertInfixToPostfix()
• evaluatePostfix()     //This function will take a post-fix expression as input and output its result.

DSA Lab 2 - Implementation of Sorting and searching algorithms

Task # 1:
Implement the following sorting algorithms:

• Selection sort
• Insertion sort
• Quick sort
• Merge sort
• bubble sort

Note: Your Implementation should contain a class named "mySort". You have to write a separate function of all above mentioned sorting algorithms in your class "mySort". Then you can call and test your algorithms in Main as "mySort.selectionSort()". In your main function you have to take input from a file "input.txt" and show the results on console.

Task # 2:

Implement the following sorting algorithms:

• Binary Search

Your have to perform binary search on strings this time. (Hint: convert word into number by adding up the ASCII code of each letter in the word.)

Note: Your Implementation should contain a class named "mySearch". You have to write a separate function of binary search algorithm in your class "mySearch". Then you can call and test your algorithms in Main as "mySearch.binarySearch()". In your main function you have to take input from a file "input.txt" and show the results on console.