Assignment 1 PDF

Preview

Summary

Assignment given for submission...

Description

Assignment 1 – Introduction to Computing and Programming

For this assignment, you will solve problems based on what you have learned in Data Structures. Instructions  Review notes of the Chapter.  There are 6 questions in this assignment.  Assignment submitted after due date will not be evaluated and a score of zero will be awarded for this assignment.  Upload a pdf version of the document. Due Date: 5 pm, March 04, 2018. Submitting this Assignment    

You will submit (upload) this assignment in Blackboard. Email/paper submissions will not be accepted. Write your answer after each question in this document. Questions must be answered in the given order. Name this document as A1_2018_John_Doe.pdf in case your name is John Doe.

Grading Criteria Correct and to-the-point answers will be awarded full points. This assignment has 05points (with weightage of 05% in your overall 100 points). Questions: 1. Write a Modified Insertion Sort Algorithm for integer key values. However, the moderation is: The input is a stack (not an array), and the only variables that your algorithm may use are a fixed number of integers and a fixed number of stacks. The algorithm should return a stack containing the records in sorted order (with the least value being at the top of the stack). Your algorithm should be Ɵ(n2) in the worst case. 2. What is the worst-case time complexity of Bubble Sort algorithm? Show how you derive the complexity. 3. A recursive version (or linked list version) of Insertionsort works as follows. We have a list to sort. If the list is empty then there is nothing to do. Otherwise, sort all but the first element of the list recursively, then insert the first element of the list into its proper place in the list by comparing it to members of the returned list, whichis already sorted. a. Assume a node in the list has two fields: value which holds an integer, and next which is a pointer to a node. Design the recursive linked list version of Insertionsort. Your function should be destructive. (A destructive function

on a linked list is a function that changes the list, either by changing the items in the list cells or by changing the next pointers (or both)) b. Analyze the worst-case time of your algorithm. 4. Design an array based data structure for two stacks called a DualStack The two stacks should share the same array in an efficient manner. If there are MaxSize entries in the array then the IsFull function should only return true if all the entries in the array are occupied. Your operations should all be constant time. a. Implement Push( ), Pop( ), IsEmpty( ) and IsFull( ) functions. b. Explain why such a nice data structure would not be possible for 3 stacks. 5. Implement the following pseudocode for directly evaluating an arithmetic expression without intermediate step of converting it into postfix notation: 1. Initialize one stack of characters to hold operation symbols and one stack of numbers to hold intermediate results. 2. Do the following until the line is completely read: o if the next input is a left parenthesis, then read it and push it onto the character stack; o

else if the next input is a number, then read it and push it onto the number stack;

o

else if the next input is one of the operation symbols, then pop symbols from the character stack until one of three things happens: (a) the stack becomes empty, or (b) the next symbol on the stack is a left parenthesis, or (c) the next symbol on the stack is an opeation with lower precedence than the next input symbol. When you are done popping, then push the new input symbol onto the character stack. else if the next symbol is a right parenthesis, then pop operations off the character stack until you reach a left parenthesis. Also pop and discard this left parenthesis.

o

o else the next input symbol should be a space that you can discard. Within this loop, each time you pop a symbol from the character stack, you should apply that operation to the top two numbers on the numbers stack and push the answer back onto the numbers stack.

When the loop finishes, pop and process any remaining symbols on the character stack. There should then be one number on the numbers stack, and this number is the value of the expression.

6. A bag (also called multiset) is a generalization of a set, where elements are allowed to appear more than once. For example, the bag {a, a, b} consists of two copies of a and one copy of b. However, a bag is still unordered, so the bags {a, b, a} and {a, a, b} are equivalent. In this task you have to implement some features for a linked representation of bags. This

representation is very similar to a regular singly-linked list, except for the following: In addition to the value and the reference to the next cell, each bag cell stores the number of copies of its value (see Figure 1), which is always positive. For a given value, at most one cell storing that value should appear in the data structure.

Implement the following functions: add (v: G; n: INTEGER), which adds n copies of v to the bag. remove (v: G; n: INTEGER), which removes as many copies of v as possible, up ton. For example, removing one copy of ‘a’ from the bag {a, a, b} will result in a bag {a, b}, while removing two copies of ‘c’ from the same bag will not change it. subtract (other: LINKED BAG [G]), which removes all elements of other from the current bag. For example, taking the bag { a, a, b} and subtracting { a, b, c} from it will yield the bag { a }. Display( ), which displays all the values along with their frequencies at any given point of time.

Your implementation should satisfy the provided constraints....