Lab-Work

To compile a c program with debugging information, use -g option:  gcc -g <programName.c>

To run the program under GNU Debugger (GDB), use the following command:  gdb a.out

A few commands/options available with GDB can be found here

Lab 0 Arrays

1) A jupyter notebook of Vector class implementation can be found HERE

2) Basic information about the numpy package can be found HERE. Use this link to understand how 2-D and higher dimension array are created using numpy in python

3) Design a Matrix class that supports addition, subtraction, multiplication of two matrices

Lab 1 Stack 

0) Jupyter notebook of basic implementation of Stack can be found HERE

1) Implement the following stack operations using a char array:push , pop, read, and change. 

2) Implement a Infix to Postfix converter that takes an infix-expression string and generates the postfix string as an output

3) Using the shared code HERE, implement the infix to postfix converter that supports operands consisting of multi-letter numbers and variables e.g. (var1 + var2 * 100 - 12 /var3).  ALSO SUPPORT EXPONENT OPERATOR " ^ " WITH RIGHT ASSOCIATIVITY

4) Implement an program to evaluate a Postfix expression involving numbers and operators (e.g. 10 15 + 20 * should result in 500)

5) Write recursive programs for

• Factorial calculation

• Fibonacci element calculation

• GCD of two numbers

• Tower  of Hanoi for N plates

Submit a single zip file containing all the programs. The filename should be <rollnumber>_lab1.zip

Note: The output of the run of a program should be pasted at the end of the program in comments.

Deadline for uploading on Moodle is 27 August

Lab2 Queues (Basic Operations in Jupyter Nodebook can be found  HERE)

1) Implement the insert and delete operations for a First-in-First-out queue

2) Implement the insert and delete operations for a First-in-First-out queue Circular Queue

3) Implement a queuing program that supports three levels of priority (0- Highest, 1, and 2). An element with higher priority should be processed (removed) before the lower priority ones.  Comment about the fairness in this basic implementation.

Submit a single zip file containing all the programs. The filename should be <rollnumber>_lab2.zip

Note: The output of the run of a program should be pasted at the end of the program in comments.

Deadline for uploading on Moodle is 1st September

Lab3 Linked List (Basic Operations in Jupyter Nodebook can be found HERE)

1) Implement the Singly linked list with following operations:

• insert at the head (front), insert at the tail (end), insert in an ordered list, insert before/after a node with value v

• Delete from head (front) , delete from the tail (end), delete a node with value v,

• traverse and display the linked list

2) Implement the doubly linked list with all of the above operations

3) Implement a circular linked list with all of the above operations

4) Represent a polynomial with one variables (e.g. x) using a linked list. Write functions perform the following arithmetic operations on two polynomials: add, subtract, and multiply. YOU MAY IMPLEMENT A DIVIDE OPERATION TO EARN EXTRA POINTS.

Submit a single zip file containing all the programs. The filename should be <rollnumber>_lab3.zip

Note: The output of the run of a program should be pasted at the end of the program in comments.

Deadline for uploading on Moodle is 8th September.

Lab 4 Tree Implementation

1) Implement a Binary Search Tree (BST) with the following operations:

• implement an INSERT() function to insert a node with value v in the BST. Implement both, the iterative and recursive version of the function.

• implement a DELETE () function to delete a node with value v in the BST. Implement both, the iterative and recursive version of the function.

• Implement a  PREORDER() function to carry out pre-order traversal of the tree

• Implement a  POSTORDER() function to carry out Post-order traversal of the tree

• Implement a  INORDER() function to carry out In-order traversal of the tree

• Implement a  LEVELORDER() function to carry out pre-order traversal of the tree. (Hint: you will need a Queue that can store TreeNode  type elements)

• Implement a function to generate a clone (copy) of the tree

2) Implement the HEAP-SORT algorithm to sort a list of integer numbers.

Output of the code should be appended at the end of source code in the Comment section.

Submit a single zip file containing all the programs. The filename should be <rollnumber>_lab4.zip

Deadline of the submission is 9th April 2021. You are advised to start working on the assignment. The submission link has been placed on LMS MOODLE 

Lab 5 AVL Tree and Graph Implementation. Basic AVL tree operations in Jupyter notebook can be found HERE

1) Implement an AVL Tree with the following operations:

• implement an INSERT(struct  TreeNode *root, int value) function to insert a node with value v in the BST.

• implement a DELETE (struct  TreeNode *root, int value) function to delete a node with value v in the BST.

2) Implement a Graph using Adjacency list representation. Further, implement the Depth First Search and Bredth First Search Traversal

Submit a single zip file containing all the programs. The filename should be <rollnumber>_lab6.zip

Note: The output of the run of a program should be pasted at the end of the program in comments.

Deadline for uploading on Moodle is 30 November

Lab 6 Red-Black Tree  Implementation (Optional) The code of red-black tree insert operation with all the supporting functions can be found here

1) Implement a Red-Black Tree with the following operations:

• implement an INSERT(struct  TreeNode *root, int value) function to insert a node with value v

• implement a DELETE (struct  TreeNode *root, int value) function to delete a node with value v

• Traverse the tree

Submit a single zip file containing all the programs. The filename should be <rollnumber>_lab7.zip

Note: The output of the run of a program should be pasted at the end of the program in comments.

Lab 7 Searching Sorting and Time Complexity Analysis

1) Implement a linear search program to search an element in a list of n elements. Take a list of n=1000000 elements populated with random elements. Also record the worst case running time (using time command on terminal)

2)   Implement a Binary search program to search an element in an ordered list of n elements. Take a list of n=1000000 elements. Also record the worst case running time (using time command on terminal) and compare it with the liner search performance

3) Implement insertion sort algorithm to sort a list of n elements in ascending order.

Take a list of n=1000000 elements populated with random elements. Also record the worst case running time (using time command on terminal)

4) Implement Merge sort algorithm to sort a list of n elements in ascending order.

Take a list of n=1000000 elements populated with random elements. Also record the worst case running time (using time command on terminal)  and compare it with the liner search performance