CIS 334 Assignment 3 – List, Stacks and Queues
Please make sure you follow the general instruction for all assignments:
Put a single line on TOP (as header) giving your name, section number, submission date, and assignment name (e.g. Yuanqiong Wang, COSC334-001/101, Oct. 6, 2013, Assignment 3: List, Stacks and Queues)
All answers MUST be typed. No scanned copy or handwritten copy will be accepted for this assignment.
Do check your spelling!
Submit your e-copy as an attachment to BlackBoard Assignment 3.
20% of grades will be deducted for each day late.
You won’t see the assignment six days after due date.
Assignment will NOT be accepted after the sixth working day period after the due date. In this case, a ZERO will be assigned.
Be sure to describe any assumptions you make.
If there is anything unclear, ASK!
Tasks:
1. Assuming time cost is the most important thing in our decision making process, present at least ONE example scenario that can best be solved by using a circular doubly linked list (2 point).
2. If there is no counter implemented for the linked list. Write an algorithm using pseudo code to calculate the size of the list. What will be the time complexity of the algorithm you designed? (2 points)
3. Hand trace a stack X through the following operations (2 point) (You don’t have to draw the stacks vertically. You can do it horizontally as long as you indicate which side is the “top” of the stack. For example, we can have: the stack, after the operation, with top of the stack on the left: 3, 5, 6)
X.push(4);
X.push(3);
Y = X.pop();
X.push(7);
X.push(2);
X.push(5);
X.push(9);
Y = X.pop();
X.push(3);
X.push(9);
Y = X.peek();
4. Hand trace a queue X through the following operations (2 point) (When you present the queue, make sure to indicate which side is the rear. For example, the queue is presented with rear of the queue at the left: 3, 5, 6):
X.enqueue(4);
X.enqueue(1);
Y = X.dequeue();
X.enqueue(8);
X.enqueue(2);
X.enqueue(5);
X.enqueue(3);
Y = X.dequeue();
X.enqueue(4);
X.enqueue(9);
5. Name five everyday examples of a queue (2 points).
6. Explain why the array implementation of a stack does not require elements to be shifted but the noncircular array implementation of a queue does (2 points).
7. Show how the undo operation in a word processor can be supported by the use of a stack. Give specific examples and draw the contents of the stack after various actions are taken (2 points).
8. Explain what would happen to the algorithms and the time complexity of an array implementation of the stack if the top of the stack were at position 0 (2 points).
9. Determine if parenthesis in a string are balanced and properly nested. Give an algorithm that returns the position in the string of the first offending parenthesis if the string is not properly nested and balanced. Assuming you only need to match “(“ and “)” in the string you received from the user input.
A. Design an algorithm using a stack and stack functions (e.g. PUSH, POP, etc.) to solve the above problem, present the algorithm in pseudo code (2 points).
B. Implement the algorithm using C++/Java (Upload both your source code file(s) and a screenshot of the program execution to the assignment) (2 points).
a. At the beginning of the program, the following heading must be included:
/********************************************************************************/
/* Author: Your name */
/* Program Function: Explain what your program can do */
/* Compilation and Execution Instructions: Explain how to compile and execute your program including the tools for editing and compiling (e.g. Dr. Java or VisualStudio version) */
/********************************************************************************/
b. Follow the coding style guide posted on the BlackBoard.
c. There should be plenty of comments in your program code to explain how you solved this problem.
d. A screenshot of running the program with at least the following input must be included with your submission:
i. Ab)cd //your program should display “incorrect expression with unwanted ‘)’ at position 3”
ii. a(b(c) // your program should display “incorrect expression with unmatched ‘(’ at position 2”
iii. (abcd // your program should display “incorrect expression with unmatched ‘(’ at position 1”
iv. (abc) // your program should display “correct expression”
C. Extra Credit: Modify your program to make it work with multiple types of parenthesis (2 points). Submit both source code as well as a screen shot containing the capture of the execution with the following input:
a. A[b)cd //your program should display “incorrect expression: ‘]’ is expected while ‘)’ is given at position 4”
b. A{b(c) // your program should display “incorrect expression: with unmatched ‘{’ at position 2”
c. Ab}cd // your program should display “incorrect expression: no ‘{‘ to match the ‘}’ at position 3”
d. {(abc)} // your program should display “correct expression”
Note:
When implementing your algorithm, you can use either the stack in the program library or implement a stack of your own for the program.
When writing pseudo code, please make sure to show the correct indentation to indicate the structure of the algorithm.