S23-solutions (3)
.pdf
keyboard_arrow_up
School
Rutgers University *
*We aren’t endorsed by this school
Course
112
Subject
Computer Science
Date
Apr 26, 2024
Type
Pages
9
Uploaded by AgentCaribouMaster1086 on coursehero.com
CS112 Data Structures - Final - Spring 2023 Name: _____________________________________ NetID: __________________________ 1 •
WRITE your name
and NetID
on EVERY page. •
DO NOT REMOVE
the staple on your exam.
•
WRITE NEATLY AND CLEARLY. If we cannot read your handwriting, you will not receive credit. Please plan your space usage. No additional paper will be given. •
This exam is worth 150 points. •
This exam has 10 pages, make sure you have all the pages. Problem 1 – Miscellaneous (25 points) a)
(10 points)
Answer TRUE or FALSE for each of the following statements. 1. The worst-case running time to search in a singularly linked list with n
items is O(1) time. False 2. Deleting the first node in a circular linked list with n
items takes O(1) time. True 3. Deleting the first node in a singularly linked list with n
items takes O(n) time. False 4. Insertion into a balanced BST with n
items takes O(log n) time. True 5. The worst-case running time to search for a value in a 2D n x n
array takes O(n) time. False 6. Stacks can be used to represent the line of students waiting for office hours where students are seen in a First-In-First-Out manner. False 7. A BST guarantees O(log n) for searches on a tree with n
items. False 8. Stacks can be used to reverse a list of objects. True 9. The maximum height of a 2-3 tree with n
items is log
2
n. True 10. Union find can be used to determine if two items are connected. True [1 point] each correct b)
(5 points) Assume a linked list of n
integers, where n > 0
. What does the mystery
method print? What is
the running time of the method mystery
in big O notation? [4 points] Prints out the minimum value in the linked list. [1 point] O(n)
CS112 Data Structures - Final - Spring 2023 Name: _____________________________________ NetID: __________________________ 2 c)
(10 points) Assume a sorted array of n
items with duplicates, where n > 0
. Each item could appear at most k times. When searching for an item, the search algorithm is modified to display the first and last indices of the item in the array. If the item is not found the algorithm displays -1 and -1. For example, the search for 36 displays 5 (first index) and 10 (last index). An item appears at most k
times.
Briefly describe the fastest search algorithm to display the first and the last indices of a sequence of non-
distinct items. Your algorithm may not
modify the array or use extra memory. What is the algorithm’s running time in terms of n
and k
? Explain. [0 points] for any algorithm that is takes longer than log n + k Algo [4 points] Use binary search to find the item. [1 point] Scans left until it finds a distinct item, display start index. [1 point] Scans right until it finds a distinct item, display end index. Running time [1 point] binary search takes log n. [1 point] scanning left and right takes at most k checks. [2 point] running time is log n + k
CS112 Data Structures - Final - Spring 2023 Name: _____________________________________ NetID: __________________________ 3 Problem 2 – Priority Queue (25 points)
a)
(7 points) Suppose that you are asked to devise the fastest algorithm to find the second largest integer value in a MAX heap of n
integers with duplicates. Assume that: •
there are at least two distinct values. •
you have direct access to the array that holds the heap items. •
you cannot modify the heap. (i)
(2 points)
Where could the second largest item be in the heap? The second largest value could be anywhere in the heap except at the top (first element) (ii)
(3 points)
Describe the algorithm. Compare every item against the top/max of the heap. (iii)
(2 points) What is the worst-case big O running time? Give a one sentence description in addition to big O. [1 point] O(n) [1 point] In the worst case we will need to compare every item against the top of the heap, and the last item we compare is the second largest. b)
(8 points) Briefly explain how to use a priority queue to implement a stack. •
What kind of priority queue is needed? •
How are the push and pop operations implemented? [2 point] MAX PQ [2 point] Associate each stack item with a key (number or timestamp). Start the key at a value. The last item inserted into the PQ have the largest value and therefore will be the first to be removed.
[2 point] Push: insert item into the PQ and then increment the key. [2 point] Pop: remove the largest value from the PQ c)
(10 points) Implement the fastest algorithm to find the minimum key in a MAX PQ. Hint: the minimum key is one of the leaves. // No points if algorithm takes longer than O(n) // The algo is supposed to investigate the leaves ONLY: indices n/2+1 to n
CS112 Data Structures - Final - Spring 2023 Name: _____________________________________ NetID: __________________________ 4
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Related Questions
this is what I have so far please help and please use my code don't just post some random other persons code in and say it's mine becase that does not help me
MY html below MY CODE
<!DOCTYPE html><html> <head> <title>Contact me</title> </head> <body> <!--Added main tag--> <main> <!--Added nav tag--> <nav> <a href="index.html">Home</a> <a href="contact.html">Contact</a> <a href="about.html">About</a> </nav> <h1>Contact ME</h1> <span>photo of me Joe Mc</span> <br> <picture> <source media="(min-width:650px)" srcset="./images/me1-650.jpg"> <source media="(min-width:465px)" srcset="./images/me1-465.jpg"> <img src="./images/me1.jpg" alt="lake" style="width:auto;"> </picture>…
arrow_forward
the html file is like this
----------------------------
<!DOCTYPE html>
<html lang="en">
<head>
<style>*{ background-color: gray;}a{ text-decoration: none; color: yellow; font-size: 20px;}a:hover{ transition: 1.1px;}input{ background-color: #fff;}
.div1 {
border:2pxoutsetred;
background-color:lightblue;
text-align:center;
}.boxes{ float: left; width: 49%; border: 2px solid black; background-color: gray; color: #fff;}
</style>
<script>
function maxLengthCheck(object) {
if (object.value.length > object.maxLength)
object.value = object.value.slice(0, object.maxLength)
}
function isNumeric (evt) {
var theEvent = evt || window.event;
var key = theEvent.keyCode || theEvent.which;
key = String.fromCharCode (key);
var regex = /[0-9]|\./;
if ( !regex.test(key) ) {
theEvent.returnValue = false;
if(theEvent.preventDefault) theEvent.preventDefault();
}
}
function orderfunction(){
alert("Thank you for ordering from my…
arrow_forward
this "landing "html is like this
-----------------------------
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>store</title>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/css/bootstrap.min.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/js/bootstrap.min.js"></script>
</head>
<body>
<nav class="navbar navbar-default">
<div class="container-fluid">
<div class="navbar-header">
<a class="navbar-brand" href="main.html">
<img…
arrow_forward
I need them to react similarly to what's going on in this gif I also put the problem in here as well that I'm having a hard time with
<!DOCTYPE html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>homework 14</title> <style> /*formatting.css */ .sticky-note-title { /* DON'T EDIT ME */ padding: 1rem; font-size: 2rem;}.sticky-note-body { /* DON'T EDIT ME */ transform: rotate(0); padding: 1rem; font-size: 1.5rem;}.sticky-board { /* DON'T EDIT ME */ margin-top: 2em; display: flex; padding: 3em; flex-wrap: wrap; gap: 1em; justify-content: center;}.sticky-note { flex-shrink: 0; width: 20em; height: 20em;
/* Add styles here */ }#first { transform: rotate(75deg); transition: transform 500ms; }#second { transform: rotate(75deg); transition: transform 500ms; }…
arrow_forward
Using comments in the code, can you provide a line by line explination as to what the below HTML file is doing? The file relates to a WebGL program if that helps you.
Please & thank you
HTML File:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" >
<title>3D Sierpinski Gasket</title>
<script id="vertex-shader" type="x-shader/x-vertex">
#version 300 es
in vec3 aPosition;
in vec3 aColor;
out vec4 vColor;
void
main()
{
gl_Position = vec4(aPosition, 1.0);
vColor = vec4(aColor, 1.0);
}
</script>
<script id="fragment-shader" type="x-shader/x-fragment">
#version 300 es
precision mediump float;
in vec4 vColor;
out vec4 fColor;
void
main()
{
fColor = vColor;
}
</script>
<script type="text/javascript" src="../Common/initShaders.js"></script>
<script type="text/javascript" src="../Common/MVnew.js"></script>
<script type="text/javascript"…
arrow_forward
Which of the following is true? Multiple layers (data) with various coordinate systems cannot be displayed on a map at the same time. It is perfectly acceptable for GIS software to use data with several coordinate systems and to display numerous layers (data) on a map, each of which has a distinct coordinate system. Although you can display different layers of data on a map, each with a distinct coordinate system, your layers might not line up properly. Not the aforementioned
arrow_forward
Can you help me by fixing the code I have here, So that it complies with the question (included in screenshot) Must be in Javascript/HTML
<!DOCTYPE html>
<html lang="en">
<head>
<metacharset="UTF-8">
<metahttp-equiv="X-UA-Compatible"content="IE=edge">
<metaname="viewport"content="width=device-width, initial-scale=1.0">
<title>Document</title>
<script>
functionsum() {
varval1=document.getElementById('tb1').value;
varval2=document.getElementById('tb2').value;
varsum=Number(val1) +Number(val2);
document.getElementById('tb3').value=sum;
}
</script>
</head>
<body>
<inputtype="text"id="tb1">
<inputtype="text"id="tb2">
<inputtype="text"id="tb3">
<buttontype="button"id ="b1"onclick="sum()">Go</button>
</body>
</html>
arrow_forward
what I have so far please help with what you can
<!DOCTYPE html><html> <head> <title>ABOUT</title> </head> <body> <main> <nav> <a href="index.html">Home</a> <a href="contact.html">Contact</a> <a href="about.html">About</a> </nav> <h1>About ME</h1> <picture> <source media="(min-width:650px)" srcset="./images/lake-650.jpg"> <source media="(min-width:465px)" srcset="./images/lake-465.jpg"> <img src="./images/lake.jpg" alt="lake" style="width:auto;"> </picture> <p>Why hello there and welcome!.</p> <p>Hello there my name is Josiah McSweeney and I am a computer engineering student I really enjoy working with computers and exploring what I'm able to do with them I am currently 22 years and I'm working…
arrow_forward
Hello, I am trying to have this list slant like what it does in the code but I need them to be ordered with lowercase letters. Like the first image should look like
a.(image)
b.(image2)
c.(image3)
Here is my code. Thank you!
<!DOCTYPE html><html lang="en">
<head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head>
<body> <ol> <li> Question 3 <ol type="a" <ol <li><img src="exam.gif" alt="Image 1" width="200" height="150"></li> <ol> <li><img src="OIP.jpg" alt="Image 2" width="200" height="150"></li> <ol> <li><img src="Successful.jpg" alt="Image 3" width="200" height="150"></li> </ol>…
arrow_forward
this is what I have so far please help and please use my code don't just post some random other persons code in and say it's mine becase that does not help me
MY html below MY CODE
<!DOCTYPE html><html>
<head><title>Home Page</title></head>
<body><!--Added main tag--><main><!--Added nav tag--><nav><a href="index.html">Home</a><a href="contact.html">Contact</a><a href="about.html">About</a></nav><h1>Welcome to my (about me) site</h1><picture><source media="(min-width:650px)" srcset="./images/me3-650.jpg"><source media="(min-width:465px)" srcset="./images/me3-465.jpg"><img src="./images/me3.JPG" alt="ME" style="width:auto;"></picture>
<h3>HI there this is one of my favorite songs down below.</h3><iframe width="420" height="345"src="https://www.bing.com/search?q=Nirvana%20-%20The%20Man%20Who%20Sold%20The…
arrow_forward
this is what I have so far it's not quite right it looks off and I need help to fix it on the image is what I have and the other is the question with an image of what it should look like
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Part 4 - Positions</title> <style>
/* element selector */ .left-grassp { position:absolute; left:120px; top:-70px; width: 1100px; height: 109vh; background-color:#414046; } .right-grasspp { position: absolute; left:220px; top:1px; width: 4em; height: 100vh; background-color:#414046; } /* class selector */ .right-sidep { position: absolute;…
arrow_forward
SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education
Related Questions
- this is what I have so far please help and please use my code don't just post some random other persons code in and say it's mine becase that does not help me MY html below MY CODE <!DOCTYPE html><html> <head> <title>Contact me</title> </head> <body> <!--Added main tag--> <main> <!--Added nav tag--> <nav> <a href="index.html">Home</a> <a href="contact.html">Contact</a> <a href="about.html">About</a> </nav> <h1>Contact ME</h1> <span>photo of me Joe Mc</span> <br> <picture> <source media="(min-width:650px)" srcset="./images/me1-650.jpg"> <source media="(min-width:465px)" srcset="./images/me1-465.jpg"> <img src="./images/me1.jpg" alt="lake" style="width:auto;"> </picture>…arrow_forwardthe html file is like this ---------------------------- <!DOCTYPE html> <html lang="en"> <head> <style>*{ background-color: gray;}a{ text-decoration: none; color: yellow; font-size: 20px;}a:hover{ transition: 1.1px;}input{ background-color: #fff;} .div1 { border:2pxoutsetred; background-color:lightblue; text-align:center; }.boxes{ float: left; width: 49%; border: 2px solid black; background-color: gray; color: #fff;} </style> <script> function maxLengthCheck(object) { if (object.value.length > object.maxLength) object.value = object.value.slice(0, object.maxLength) } function isNumeric (evt) { var theEvent = evt || window.event; var key = theEvent.keyCode || theEvent.which; key = String.fromCharCode (key); var regex = /[0-9]|\./; if ( !regex.test(key) ) { theEvent.returnValue = false; if(theEvent.preventDefault) theEvent.preventDefault(); } } function orderfunction(){ alert("Thank you for ordering from my…arrow_forwardthis "landing "html is like this ----------------------------- <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>store</title> <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/css/bootstrap.min.css"> <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script> <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/js/bootstrap.min.js"></script> </head> <body> <nav class="navbar navbar-default"> <div class="container-fluid"> <div class="navbar-header"> <a class="navbar-brand" href="main.html"> <img…arrow_forward
- I need them to react similarly to what's going on in this gif I also put the problem in here as well that I'm having a hard time with <!DOCTYPE html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>homework 14</title> <style> /*formatting.css */ .sticky-note-title { /* DON'T EDIT ME */ padding: 1rem; font-size: 2rem;}.sticky-note-body { /* DON'T EDIT ME */ transform: rotate(0); padding: 1rem; font-size: 1.5rem;}.sticky-board { /* DON'T EDIT ME */ margin-top: 2em; display: flex; padding: 3em; flex-wrap: wrap; gap: 1em; justify-content: center;}.sticky-note { flex-shrink: 0; width: 20em; height: 20em; /* Add styles here */ }#first { transform: rotate(75deg); transition: transform 500ms; }#second { transform: rotate(75deg); transition: transform 500ms; }…arrow_forwardUsing comments in the code, can you provide a line by line explination as to what the below HTML file is doing? The file relates to a WebGL program if that helps you. Please & thank you HTML File: <!DOCTYPE html> <html> <head> <meta http-equiv="Content-Type" content="text/html;charset=utf-8" > <title>3D Sierpinski Gasket</title> <script id="vertex-shader" type="x-shader/x-vertex"> #version 300 es in vec3 aPosition; in vec3 aColor; out vec4 vColor; void main() { gl_Position = vec4(aPosition, 1.0); vColor = vec4(aColor, 1.0); } </script> <script id="fragment-shader" type="x-shader/x-fragment"> #version 300 es precision mediump float; in vec4 vColor; out vec4 fColor; void main() { fColor = vColor; } </script> <script type="text/javascript" src="../Common/initShaders.js"></script> <script type="text/javascript" src="../Common/MVnew.js"></script> <script type="text/javascript"…arrow_forwardWhich of the following is true? Multiple layers (data) with various coordinate systems cannot be displayed on a map at the same time. It is perfectly acceptable for GIS software to use data with several coordinate systems and to display numerous layers (data) on a map, each of which has a distinct coordinate system. Although you can display different layers of data on a map, each with a distinct coordinate system, your layers might not line up properly. Not the aforementionedarrow_forward
- Can you help me by fixing the code I have here, So that it complies with the question (included in screenshot) Must be in Javascript/HTML <!DOCTYPE html> <html lang="en"> <head> <metacharset="UTF-8"> <metahttp-equiv="X-UA-Compatible"content="IE=edge"> <metaname="viewport"content="width=device-width, initial-scale=1.0"> <title>Document</title> <script> functionsum() { varval1=document.getElementById('tb1').value; varval2=document.getElementById('tb2').value; varsum=Number(val1) +Number(val2); document.getElementById('tb3').value=sum; } </script> </head> <body> <inputtype="text"id="tb1"> <inputtype="text"id="tb2"> <inputtype="text"id="tb3"> <buttontype="button"id ="b1"onclick="sum()">Go</button> </body> </html>arrow_forwardwhat I have so far please help with what you can <!DOCTYPE html><html> <head> <title>ABOUT</title> </head> <body> <main> <nav> <a href="index.html">Home</a> <a href="contact.html">Contact</a> <a href="about.html">About</a> </nav> <h1>About ME</h1> <picture> <source media="(min-width:650px)" srcset="./images/lake-650.jpg"> <source media="(min-width:465px)" srcset="./images/lake-465.jpg"> <img src="./images/lake.jpg" alt="lake" style="width:auto;"> </picture> <p>Why hello there and welcome!.</p> <p>Hello there my name is Josiah McSweeney and I am a computer engineering student I really enjoy working with computers and exploring what I'm able to do with them I am currently 22 years and I'm working…arrow_forwardHello, I am trying to have this list slant like what it does in the code but I need them to be ordered with lowercase letters. Like the first image should look like a.(image) b.(image2) c.(image3) Here is my code. Thank you! <!DOCTYPE html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title></head> <body> <ol> <li> Question 3 <ol type="a" <ol <li><img src="exam.gif" alt="Image 1" width="200" height="150"></li> <ol> <li><img src="OIP.jpg" alt="Image 2" width="200" height="150"></li> <ol> <li><img src="Successful.jpg" alt="Image 3" width="200" height="150"></li> </ol>…arrow_forward
- this is what I have so far please help and please use my code don't just post some random other persons code in and say it's mine becase that does not help me MY html below MY CODE <!DOCTYPE html><html> <head><title>Home Page</title></head> <body><!--Added main tag--><main><!--Added nav tag--><nav><a href="index.html">Home</a><a href="contact.html">Contact</a><a href="about.html">About</a></nav><h1>Welcome to my (about me) site</h1><picture><source media="(min-width:650px)" srcset="./images/me3-650.jpg"><source media="(min-width:465px)" srcset="./images/me3-465.jpg"><img src="./images/me3.JPG" alt="ME" style="width:auto;"></picture> <h3>HI there this is one of my favorite songs down below.</h3><iframe width="420" height="345"src="https://www.bing.com/search?q=Nirvana%20-%20The%20Man%20Who%20Sold%20The…arrow_forwardthis is what I have so far it's not quite right it looks off and I need help to fix it on the image is what I have and the other is the question with an image of what it should look like <!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Part 4 - Positions</title> <style> /* element selector */ .left-grassp { position:absolute; left:120px; top:-70px; width: 1100px; height: 109vh; background-color:#414046; } .right-grasspp { position: absolute; left:220px; top:1px; width: 4em; height: 100vh; background-color:#414046; } /* class selector */ .right-sidep { position: absolute;…arrow_forward
arrow_back_ios
arrow_forward_ios
Recommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education