Showing 3-4 out of 4
pset10.pdf-CS 114: Introduction to Computer Scienc...
pset10.pdf-CS 114: Introduction to Computer Science
pset10.pdf-CS 114: Introduction to ...
pset10.pdf-CS 114: Introduction to Computer Science
Page 3
Suppose
G
is a complete graph of
n
vertices. Show that the number
of possible Pr¨
ufer sequences corresponding to spanning trees of
G
is
n
n
-
2
.
(d) (1 point) Using part (c), explain why the number of spanning trees
in a complete graph of
n
vertices is
n
n
-
2
.
Part 2: Coding (50 points)
Please complete the following problems.
You may use whatever IDEs / text
editors you like, but you must submit your responses on Vocareum. Responses
will be graded on correctness, code design, and code style.
In the following questions, each program will read several lines of input and
print one line of output; the contents of these lines are explicitly defined in each
problem. The code for reading inputs and writing outputs is provided for you;
you need only implement the logic that computes the output. The “run” button
on Vocareum runs your code using the input from
input.txt
; to test different
test cases, you can modify the contents of
input.txt
in a way that matches the
problem description and example. (If you are using the command line or another
IDE to do your work, you can use the command
java ClassNameGoesHere <
input.txt
.)
(6) (20 points) (This is related to a common interview question.) Suppose you
are given a string containing only the characters ( , ), [, ],
{
, and
}
. In this
problem, you will write a function to determine whether the string has
balanced parentheses. Your algorithm should have a worst-case runtime
in
O
(
n
). Additionally, your algorithm should use no more than
O
(
n
) space
beyond the input; any algorithms that use time or space not in
O
(
n
) will
receive half credit at most. Any solutions that hardcode
true
or
false
or
otherwise try to game the distribution of test cases will receive zero credit.
Balanced parentheses
means that every open parenthesis has exactly
one close parenthesis
of the same type
corresponding to it and vice versa,
and that for each such pair the opening parenthesis precedes the closed
parenthesis. The following strings have balanced parentheses:
()
(()())
((())())
()[]
{}
([
{}
])
The following strings do not have balanced parentheses:
)(
3
Page 4
(()
())(()))())
(
}
([
{
)]
}
[(
{
We consider the empty string to have balanced parentheses, as there
is no imbalance.
Your program should accept as input a single string
containing only the characters ) and (, and output a single line stating
true
or
false
.
The functionality for reading and printing answers is
written in the class
ParenthesesChecker
; your task is to complete the
hasBalancedParentheses()
method.
(7) (30 points) (This is a common interview question.) In this problem, we
will be evaluating simple math expressions that contain numbers, +, *, (,
and ). Specifically, you will write a function that takes in a string repre-
senting an expression and returns an integer representing its result. The
following are examples of input and corresponding output:
Input:
3+5
Output:
8
Input:
3+5*7
Output:
38
Input:
3*(5*(7+2))
Output:
135
The functionality for reading and printing answers is written in the class
Calculator
; your task is to complete the
eval()
method which takes
in a string representing an arithmetic expression as described above and
outputs a single integer representing the result of this expression. (Hint:
Parentheses are only used in the second half of the test cases.)
4
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
New Jersey Institute of T...
New_Jersey_Institute_of_Technology
School:
Introduction_to_Computer_Science_2
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
