Showing 1-2 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 1
CS 114: Introduction to Computer Science II
Problem Set 10
John Tsai
Due April 18, 2019
Part 1 of this assignment is due Thursday, April 18, in class. Part 2 is
due Saturday, April 20, at noon.
Anyone who wants to take an extension
until the beginning of class on Monday, April 22nd (for section 006) or Tuesday,
April 23 (for section 002, 004) may do so; however, as this is the day of the
midterm, I highly recommend getting this homework done earlier!
Part 1: Written (50 points)
(1) (10 points) For each of the situations below, state whether a
stack
or a
queue
would be better suited in a solution. Explain your answers.
(a) (3 points) Maintaining a stack of T-shirts in a way that one wears
each one equally
(b) (3 points) Managing customer complaints at a helpdesk
(c) (4 points) Determining whether a word is a palindrome
(2) (10 points) Describe, in your own words, the similarities and differences
between
Stack
,
Queue
, and
Deque
in Java. Your answer should make sense
to a student currently enrolled in CS 113.
(3) (10 points) Suppose you are given a balanced binary search tree with 15
nodes in it, containing the even numbers from 2 to 30 inclusive.
(a) (5 points) Draw this tree.
(b) (3 points) Explain how you would check if the number 18 is in this
tree, and state the number of operations this would take.
(c) (2 points) Explain how you would insert the number 27 into this tree,
and state the number of operations this should take.
(4) (10 points) Clearly describe an algorithm for turning a binary search tree
into a sorted array. Your algorithm should have a running time in
O
(
n
),
where
n
is the number of vertices in the tree. Additionally, your descrip-
tion must be general enough to work for trees of size 2
k
-
1 for all positive
integers
k
.
1
Page 2
(5) (10 points) In this problem, we will explore
spanning trees
.A
spanning
tree
of a graph
G
is a tree that contains every vertex in
G
.A
complete
graph is a graph where every pair of vertices has an edge between them.
An example of a spanning tree of a complete graph of 4 nodes is shown
below. The bold lines denote the spanning tree.
In this problem, we will explore the formula for the number of distinct
spanning trees of a complete graph, which is known as
Cayley’s for-
mula
.
(a) (2 points) How many spanning trees are there in a complete graph
of 3 vertices? Explain your answer.
(b) (3 points) How many spanning trees are there in a complete graph
of 4 vertices? Explain your answer.
(c) (4 points) A
Pr¨
ufer sequence
is a sequence of numbers that uniquely
determines a spanning tree. (You do not need to prove why this is
true.). It is constructed as follows (we start with an empty sequence):
•
Find the vertex with the smallest label that only has one edge
pointing out of it.
•
Write down the label of its single neighbor (i.e. the other node
connecting to this edge) as the next number in our sequence.
•
Remove the vertex we found in the first step, as well as the single
edge associated with it.
•
If there are two nodes remaining; stop. Otherwise, repeat these
three steps.
2
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
