Description
CS3353 Programming assignment 1
- Implement insertion, deletion and search for a doubly-linked list as defined in class. The input has a list of pairs of an integer key followed with an operation delimited by spaces. An example of input file contents would look like 1.in 3.in 5.in 3.del 2.in 1.sch. There are a total of 3 operations in the input file given:
- in operation: Insertions to the doubly-linked list are to be performed at the head unless otherwise specified. Duplicate insertions are to be rejected and DUPLICATE KEY should be output to the console.
3.in – Insert node with value 3 at the head of the list
5.in_8 – Insert node with value 5 between the node with value 8 and the next node. If the node with value 8 is a tail node, insert at the end.
- del operation: Delete the node with the value of the integer key as specified.
6.del – Delete the node that has value 6 in the doubly linked list. If no such node exists, ignore the command.
- sch operation: Search for the node with the value of the integer key as specified. If such a node exists, output FOUND to the console, else NOT FOUND.
2.sch – Search for a node with value 2 in the doubly linked list. If present output FOUND to the console. If not, output NOT FOUND to the console.
Output:
The list before operation and the list after operation displayed on the screen standard outout (not into a file).
Example:
Input file contents:
1.in 3.in 5.in 3.del 2.in 1.sch 4.in_5
Output of the program should look like:
Operation: 1.in
List before: NULL
List after: 1
Operation: 3.in
List before: 1
List after: 3 -> 1
Operation: 5.in
List before: 3 -> 1
List after: 5 -> 3 -> 1
Operation: 3.del
List before: 5 -> 3 -> 1
List after: 5 -> 1
Operation: 2.in
List before: 5 -> 1
List after: 2 -> 5 -> 1
Operation: 1.sch
FOUND
Operation: 4.in_5
List before: 2 -> 5 -> 1
List after: 2 -> 5 -> 4 -> 1
- Implement insertion (or push) and deletion (or pop) for a stack and a circular queue with length of n keys as defined in class. An example of input file contents for stack would look like 10 1.push 3.push 5.push pop 2.push and for queue it would look like 13 1.in 3.in 5.in 3.del 2.in. There are two operations for stack and two operations for queue. The first number in both the files indicates the size of the stack and queue respectively.
- Stack operations: push and pop are the two operations for stack.
3.push – Push value 3 onto the stack, in case of overflow, print OVERFLOW and halt the program.
pop – Pops out the first value on the stack and outputs to the console.
- Circular Queue operations: in and del are the two operations for the circular queue.
3.in – Insert value 3 into the circular queue, in case of overflow, print OVERFLOW and halt the program.
del – Deletes the first value at the front of the circular queue.
Output:
The list before operation and the list after operation displayed on the screen standard outout (not into a file).
Example:
Input file contents for STACK:
10 1.push 3.push 5.push pop
Output of the program should look like:
Operation: 1.push
List before: EMPTY
List after: 1
Operation: 3.push
List before: 1
List after: 3 -> 1
Operation: 5.push
List before: 3 -> 1
List after: 5 -> 3 -> 1
Operation: pop
List before: 5 -> 3 -> 1
List after: 3 -> 1
Input file contents for CIRCULAR QUEUE:
7 1.in 3.in 5.in del
Output of the program should look like:
Operation: 1.in
List before: EMPTY
List after: 1
Operation: 3.in
List before: 1
List after: 1 -> 3
Operation: 5.in
List before: 1 -> 3
List after: 1 -> 3 -> 5
Operation: del
List before: 1 -> 3 -> 5
List after: 3 -> 5
- Write a program to evaluate the correctness of parenthesis matching problem using stacks. Given a string of parenthesis, program should output “True” or “False” depending on whether the parenthesis are matched or not.
Example:
Input file contents:
({}[]{}()[]))]
Output of the program should look like:
Incorrect
Write a separate program for each question., total 4 programs (one program for linked list, one for stack, one for queue and one for evaluator) are to be submitted to the same directory under “handin”. The output should be displayed for each operation except for problem #3.
*Provide a README file with specific instructions for compilation and execution for the grader to follow, and any notes you want to add such as how you handle “overflow”, etc.
CS3353 Programming assignment 2
- Implement insertion and deletion for a max-heap as defined in class.
Input: list of pairs of an integer and an operation, e.g., pre (or post or in) 1.in 3.in 5.in del 2.in ….. Note that the “pre”, “post” or “in” is the method you use to traverse the heap for output display. Also, note that “del” will delete the max key by default.
/* Notice that pairs are delimited by a single space in between. Note that input is to be read in from a file in a batch. */
Output: the list before operation and the list after operation displayed on the screen standard output (not into a file) by using the traversal method as specified in your input file.
Input examples:
pre 1.in 34.in del 24.in
post 1.in 3.in 5.in del 2.in
in 1.in del 12.in 5.in
pre 1.in 3.in 25.in del 4.in 231.in
Example input file:
pre 1.in 3.in 5.in del 2.in
Example output: For the same input example file as above, the output should will be as follows:
Operation: 1.in
Heap before: NULL
Heap after: 1
Operation: 3.in
Heap before: 1
Heap after: 3 1
Operation: 5.in
Heap before: 3 1
Heap after: 5 1 3
Operation: del
Heap before: 5 1 3
Heap after: 3 1
Operation: 2.in
Heap before: 3 1
Heap after: 3 1 2
Note: The output will be different if the traversal mentioned is different in the input file i.e. for input “ post 1.in 3.in 5.in del 2.in” .The “post” traversal would produce a different output even though the max heap is the same tree. The output should be printed as per the traversal mentioned in the input.
- This problem is to simulate scheduling CPU jobs by using a PRIORITY QUEUE to be built. Your program to be written for the simulation should run in a loop, each iteration of which corresponds to a time slice for the CPU. Each job is assigned a priority, which is an integer between -10 (highest priority) and +10 (lowest priority), inclusive. Each job is also assigned an arrival time – the time at which the job shows up at the CPU. From among all jobs waiting to be processed in a time slice, the CPU, the CPU must work on a job with highest priority.
In this simulation, each job will come with arrival time, which is the time at which the job has arrived (integer >= 0). Each job will also include a length value, which is an integer between 1 and 100, inclusive, indicating the number of time slices that are needed to process this job. Jobs CAN be interrupted in the middle if another job with higher priority arrives. Your simulator must output the name of the job running on the CPU in each time slice as shown below.
Note: If there are two or more jobs with same priority, the jobs that arrived earlier are executed first (LIFO – last come first out) basis.
Input File format: Each line in the input file contains the details one single job delimited by “space”. Read the entire file first and then process the priority queue algorithm on all the jobs based on the arrival time. As some jobs will have a different arrival time, the priority queue will have to be re-done after every time slice. The order of the jobs in the input file are random and not sorted in any way.
JobName priority arrivalTime lengthOfJob
Example input file:
Job114 -9 0 25
Job345 2 0 66
Job234 -10 10 5
Job999 10 27 56
Output format: Output on the command line should display the job arrivals on that time slice (if any) and job that is being executed for that timeslice along with the priority and the remaining time of that job.
Time Slice #n – Job arrivals at this time slice (if any)
Executing JobName priority remainingLengthOfJob
Example output File: For the same input example file as above, the output should will be as follows:
Time Slice #1 – Job114 arrived
Job345 arrived
Executing Job114 -9 25
Time Slice #2 – Executing Job114 -9 24
Time Slice #3 – Executing Job114 -9 23
Time Slice #4 – Executing Job114 -9 22
Time Slice #5 – Executing Job114 -9 21
.
.
Time Slice #10 – Job234 arrived
Executing Job234 -10 5
Time Slice #11 – Executing Job234 -10 4
Time Slice #12 – Executing Job234 -10 3
Time Slice #13 – Executing Job234 -10 2
Time Slice #14 – Executing Job234 -10 1
Time Slice #15 – Executing Job114 -9 16
Time Slice #16 – Executing Job114 -9 15
.
.
Time Slice #27 – Job999 arrived
Executing Job114 -9 4
Time Slice #28 – Executing Job114 -9 3
Time Slice #29 – Executing Job114 -9 2
Time Slice #30 – Executing Job114 -9 1
Time Slice #31 – Executing Job345 2 66
Time Slice #32 – Executing Job345 2 65
Time Slice #33 – Executing Job345 2 64
Time Slice #34 – Executing Job345 2 63
Time Slice #35 – Executing Job345 2 62
.
.
Time Slice #96 – Executing Job345 2 1
Time Slice #97 – Executing Job999 10 56
Time Slice #98 – Executing Job999 10 55
Time Slice #99 – Executing Job999 10 54
.
.
Example input file 2:
Job114 -9 0 25
Job345 8 0 66
Job234 -10 2 5
Job999 6 99 7
Job456 9 6 10
Job121 5 8 10
Example output File: For the same input example file as above, the output should will be as follows:
Time Slice #1 – Job114 arrived
Job345 arrived
Executing Job114 -9 25
Time Slice #2 – Job234 arrived
Executing Job234 -10 5 24
Time Slice #3 – Executing Job234 -10 4
Time Slice #4 – Executing Job234 -10 3
Time Slice #5 – Executing Job234 -10 2
Time Slice #6 – Job456 arrived
Executing Job234 -10 1
Time Slice #7 – Executing Job114 -9 24
Time Slice #8 – Job121 arrived
Executing Job114 -9 24
.
.
Time Slice #25 – Executing Job114 -9 1
Time Slice #26 – Executing Job114 -9 5
Time Slice #27 – Executing Job114 -9 4
Time Slice #28 – Executing Job114 -9 3
Time Slice #29 – Executing Job114 -9 2
Time Slice #30 – Executing Job114 -9 1
Time Slice #31 – Executing Job121 5 10
Time Slice #32 – Executing Job121 5 9
.
.
Time Slice #40 – Executing Job121 5 1
Time Slice #41 – Executing Job345 8 66
.
.
Time Slice#99 – Job999 arrived
Executing Job999 6 7
Time Slice#100 – Executing Job999 6 6
Time Slice#102 – Executing Job999 6 5
Time Slice#103 – Executing Job999 6 4
Time Slice#104 – Executing Job999 6 3
Time Slice#105 – Executing Job999 6 2
Time Slice#106 – Executing Job999 6 1
Time Slice#107 – Executing Job345 8 8
Time Slice#108 – Executing Job345 8 7
.
.
Time Slice#114 – Executing Job345 8 1
The output of all the time slices MUST be printed to the console.
A command line user interface to read the input must be provided as follows:
Enter your input file name:
The program is to be submitted to the directory in “handin”.
*Provide a README file with specific instructions for compilation and execution for the grader to follow, and any notes you want to add.
CS3353 Programming assignment 3
This assignment is to study and implement hash table.
Alice has a fixed number of closed empty boxes (lined up and indexed from ‘0’ like an array) and some numbered cubes. Each empty box can fit only one cube. Alice opens a box and puts the numbered cube in and closes the box. Alice could put the numbered cubes into random boxes, but if done so Alice was not able to tell which numbered cube was in which box without looking into the box. If Alice has used any hashing algorithm to place the numbered cubes in the empty boxes, after putting all the cubes Alice will be able to tell which cube is in which box without looking into the box by using the same hashing algorithm that was used earlier. Alice has implemented three different hashing algorithms to places the numbered cubes in the empty boxes. Implement as detailed below.
- Implement insertion, deletion and search for a hash table by using the chaining method as defined in class.
Input format: <#EmptyBoxes> <NumberedCube>.command <NumberedCube>.command
Sample input: 13 1.in 2.in 15.in 5.in 7.in 2.del 11.in 12.in
Sample output:
0:
1: 1
2: 15
3:
4:
5: 5
6:
7: 7
8:
9:
10:
11: 11
12: 12
- Implement insertion, deletion and search for a hash table by using the single linear probing method as defined in class.
Input format: <#EmptyBoxes> <NumberedCube>.command <NumberedCube>.command
Sample input: 13 1.in 2.in 15.in 5.in 7.in 2.del 11.in 12.in
Sample output:
0:
1: 1
2:
3: 15
4:
5: 5
6:
7: 7
8:
9:
10:
11: 11
12: 12
- Implement insertion, deletion and search for a hash table by using the double hashing method as defined in class. Suppose your double hashing is h(k) = i + jd(k) mod N and d(k) = q – k mod q, then pick q the largest prime less than N.
Input format: <#EmptyBoxes> <primeNumber> <NumberedCube>.command …
Sample Input: 13 7 18.in 41.in 18.sch 22.in 44.in 45.sch 59.in 32.in 41.del 31.in 73.in
The first and second integers are, N and q values, respectively.
Note to that stop your input once the hash table is full.
Output:
Two sets of outputs to be displayed, one for before the operation, another for after the operation.
In each set of output, each entry to be displayed on a new line possibly with more than one key.
Note that output of a “sch” is to be “found” or “not found”.
If a duplicate is inserted display “duplicate key”.
Sample output format:
0:31
1:
2:
3:
4:
5:18
6:32
7:59
8:73
9:22
10:44
11:
12:
Write a separate program for each question. Total 3 programs are to be submitted to the same directory un “handin”.
CS3353 Programming assignment 4
In Linux, red black tree is used for a couple of applications in the Completely Fair Scheduler and for keeping track of the virtual memory segments for a process.
In the completely fair scheduler, the process’ virtual runtimes are used as the key and the start address of the range is used as the key for keeping track of the virtual memory segments for a process.
A main benefit of employing red black tree in above applications is to retrieve a node by its key faster than linear time likely otherwise.
- Implement insertion and deletion for a red-black tree as defined in class.
Note that insertion should check for duplicate keys, and when there is no such key after exhausting the input in case of deletion, display “the key does not exist.”
Example input file:
in 56.in 23.in 45.in 7.in 5.in 23.del 45.del
Example output: For the same input example file as above, the output should will be as follows:
Operation: 56.in
Before: NULL / EMPTY
After: 56B
Operation: 23.in
Before: 56B
After: 23R 56B
Operation: 45.in
Before: 23R 56B
After: 23R 45B 56R
Operation: 7.in
Before: 23R 45B 56R
After: 7R 23B 45B 56B
Operation: 5.in
Before: 7R 23B 45B 56B
After: 5R 7B 23R 45B 56B
Operation: 23.del
Before: 5R 7B 23R 45B 56B
After: 5R 7B 45B 56B
Operation: 45.del
Before: 5R 7B 45B 56B
After: 5B 7B 56B
Note: The output will be different if the traversal mentioned is different in the input file i.e. for input “ post 1.in 3.in 5.in 5.del 2.in” the output would be different as the “post” traversal would produce a different output even though the tree looks similar. The output should be printed as per the traversal mentioned in the input.
CS3353 Sorting Programming Assignment 5
Implement a MERGE sort and BUCKET sort as defined in class. Input file consists of integers, one integer per line. Input file name is to be read from command line. For bucket sort, the range of the input numbers, can be obtained after reading the contents of the file. The minimum and maximum number can be determined after reading the contents of the file.
Output should be printed upon request in the command line, based on user entered range of sorted numbers. The range of numbers to be output on the command line is requested to the user as shown below. Only the sorted numbers in that range (inclusive) are to be output on the console. Two different programs, one for merge sort and one for bucket sort should be submitted along with Readme.txt if necessary.
Input example:
34
567
12344
122
3
45
Sample Program Execution:
Enter file name: input.txt
Enter left range: 2
Enter right range: 4
Sorted numbers in the selected range are:
34
45
122
Plots:
Modify the above bucket and merge sort programs to calculate the elapsed time (in nanoseconds) for different input sizes. The input size should start from 1000 numbers and ends at 100,000 incrementing the input size by 1000 every time. The inputs given here are random numbers.
Plot all the execution times of both Merge sort and bucket sort for all the input sizes from 1000 to 100000 in an excel spreadsheet. In the same plot, also add the asymptotic time for merge sort and bucket sort.
Plot in excel:
X axis: input size: 1000, 2000, 3000,……………….100000;
Y axis: execution time in nano seconds
What to submit:
A source code for each algorithm (merge sort and bucket sort) and Readme (if necessary) using “handin”. Upload plot file into “Assignments” on Canvas.
