APCSP_SemReview_Algorithms
.pdf
keyboard_arrow_up
School
BASIS San Antonio Shavano *
*We aren’t endorsed by this school
Course
101
Subject
Computer Science
Date
Apr 26, 2024
Type
Pages
79
Uploaded by SuperBison2227 on coursehero.com
1.
For which of the following situations would it be best to use a heuristic in order to find a solution that runs in a
reasonable amount of time?
(A)
Appending a value to a list of
elements, which requires no list elements be examined.
(B)
Finding the fastest route that visits every location among
locations, which requires
possible routes be
examined.
(C)
Performing a binary search for a score in a sorted list of
scores, which requires that fewer than
scores be
examined.
(D)
Performing a linear search for a name in an unsorted database of
people, which requires that up to
entries be examined.
2.
Suppose a large group of people in a room were all born in the same year. Consider the following three algorithms,
which are each intended to identify the people in the room who have the earliest birthday based on just the month
and day. For example, a person born on February 10 is considered to have an earlier birthday than a person born on
March 5. Which of the three algorithms will identify the correct people?
I.
All the people in the room stand up. All standing people form pairs where possible, leaving at most one
person not part of a pair. For each pair, the person with the earlier birthday remains standing, while the
other person in the pair sits down. If there is a tie, both people sit down. Any individual not part of a pair
remains standing. Continue doing this until only one person remains standing. That person has the earliest
birthday.
II.
All the people in the room stand up. All standing people form pairs with another standing person that they
have not previously been paired with where possible, leaving at most one person not part of a pair. For
each pair, the person with the earlier birthday remains standing, while the other person in the pair sits
down. If there is a tie, both people in the pair remain standing. Any individual not part of a pair remains
standing. Continue doing this until only one person remains standing or all persons standing have the same
birthday. Anyone still standing has the earliest birthday.
III.
Beginning with the number 1, ask if anyone was born on that day of any month. Continue with the
numbers 2, 3, and so on until a positive response is received. If only one person responds, that person has
the earliest birthday. If more than one person responds, determine which person was born in the earliest
month, and that person or those persons have the earliest birthday.
(A)
I only
(B)
II only
(C)
I and II
(D)
II and III
AP COMPUTER SCIENCE PRINCIPLES
Test Booklet
Quiz - Big Idea 3 - Algorithms
AP Computer Science Principles
Page 1 of 79
3.
A student is creating an algorithm to display the distance between the numbers
num1
and
num2
on a number
line. The following table shows the distance for several different values.
Value of
num1
Value of
num2
Distance Between
num1
and
num2
5
2
3
1
8
7
-3
4
7
Which of the following algorithms displays the correct distance for all possible values of
num1
and
num2
?
(A)
Step 1:
Add
num1
and
num2
and store the result in the variable
sum
.
Step 2:
Take the absolute value of
sum
and display the result.
(B)
Step 1:
Subtract
num1
from
num2
and store the result in the variable
diff
.
Step 2:
Take the absolute value of
diff
and display the result.
(C)
Step 1:
Take the absolute value of
num1
and store it in the variable
absNum1
.
Step 2:
Take the absolute value of
num2
and store it in the variable
absNum2
.
Step 3:
Add
absNum1
and
absNum2
and display the result.
(D)
Step 1:
Take the absolute value of
num1
and store it in the variable
absNum1
.
Step 2:
Take the absolute value of
num2
and store it in the variable
absNum2
.
Step 3:
Subtract
absNum1
from
absNum2
and display the result.
4.
A certain game keeps track of the maximum and minimum scores obtained so far. If
num
represents the most
recent score obtained, which of the following algorithms correctly updates the values of the maximum and the
minimum?
Test Booklet
Quiz - Big Idea 3 - Algorithms
Page 2 of 79
AP Computer Science Principles
(A)
If
num
is greater than the minimum, set the minimum equal to
num
.
Otherwise, if
num
is greater than
the maximum, set the maximum equal to
num
.
(B)
If
num
is less than the minimum, set the minimum equal to
num
.
Otherwise, if
num
is greater than the
maximum, set the maximum equal to
num
.
(C)
If
num
is less than the minimum, set the minimum equal to
num
.
Otherwise, if
num
is less than the
maximum, set the maximum equal to
num
.
(D)
If
num
is greater than the minimum, set the minimum equal to
num
.
Otherwise, if
num
is less than the
maximum, set the maximum equal to
num
.
5.
The figure below shows four grids, each containing a robot represented as a triangle. The robot cannot move to a
black square or move beyond the edge of the grid.
Which of the following algorithms will allow the robot to make a single circuit around the rectangular region of
black squares, finishing in the exact location and direction that it started in each of the four grids?
Test Booklet
Quiz - Big Idea 3 - Algorithms
AP Computer Science Principles
Page 3 of 79
(A)
Step 1:
Keep moving forward, one square at a time, until the square
to the right of the robot is black.
Step 2:
Turn right and move one
square forward.
Step 3:
Repeat steps 1 and 2 three more times.
(B)
Step 1:
Keep moving forward, one square at a time, until
the square to
the right of the robot is no
longer black.
Step 2:
Turn right and move one
square forward.
Step 3:
Repeat steps 1 and 2 three more times.
(C)
Step 1:
Move forward three squares.
Step 2:
Turn right and move one square forward.
Step 3:
If the square to the right of the robot is black, repeat steps 1 and 2.
(D)
Step 1:
Move forward three squares.
Step 2:
Turn right and move one square forward.
Step 3:
If the square to the right of the robot is not black, repeat steps 1 and 2.
6.
A programmer is creating an algorithm that will be used to turn on the motor to open the gate in a parking garage.
The specifications for the algorithm are as follows.
•
The gate should not open when the time is outside of business hours.
•
The motor should not turn on unless the gate sensor is activated.
•
The motor should not turn on if the gate is already open.
Which of the following algorithms can be used to open the gate under the appropriate conditions?
(A)
Check if the time is outside of business hours. If it is, check if the gate sensor is activated. If it is, check if the
gate is closed. If it is, turn on the motor.
(B)
Check if the time is during business hours. If it is, check if the gate sensor is activated. If it is, check if the
gate is open. If it is, turn on the motor.
(C)
Check if the time is during business hours. If it is, check if the gate sensor is activated. If it is not, check if
the gate is open. If it is not, turn on the motor.
(D)
Check if the time is during business hours. If it is, check if the gate sensor is activated. If it is, check if the
gate is open. If it is not, turn on the motor.
Test Booklet
Quiz - Big Idea 3 - Algorithms
Page 4 of 79
AP Computer Science Principles
7.
Three different numbers need to be placed in order from least to greatest. For example, if the numbers are ordered 9,
16, 4, they should be reordered as 4, 9, 16. Which of the following algorithms can be used to place any three
numbers in the correct order?
(A)
If the first number is greater than the last number, swap them. Then, if the first number is greater than the
middle number, swap them.
(B)
If the first number is greater than the middle number, swap them. Then, if the middle number is greater than
the last number, swap them.
(C)
If the first number is greater than the middle number, swap them. Then, if the middle number is greater than
the last number, swap them. Then, if the first number is greater than the last number, swap them.
(D)
If the first number is greater than the middle number, swap them. Then, if the middle number is greater than
the last number, swap them. Then, if the first number is greater than the middle number, swap them.
Test Booklet
Quiz - Big Idea 3 - Algorithms
AP Computer Science Principles
Page 5 of 79
8.
Which of the following algorithms display all integers between 1 and 20, inclusive, that are not divisible by 3 ?
Select
two answers.
(A)
Step 1:
Set
x
to 0.
Step 2:
Increment
x
by 1.
Step 3:
If
x
is not divisible by 3, then display
x
.
Step 4:
Repeat steps 2 and 3 until
x
is 20.
(B)
Step 1:
Set
x
to 0.
Step 2: If
x
is divisible by 3, then display
x
.
Step 3:
Increment
x
by 1.
Step 4: Repeat steps 2 and 3 until
x
is greater than 20.
(C)
Step 1:
Set
x
to 1.
Step 2: If
x
is divisible by 3, then do nothing; otherwise display
x
.
Step 3:
Increment
x
by 1.
Step 4: Repeat steps 2 and 3 until
x
is 20.
(D)
Step 1:
Set
x
to 1.
Step 2: If
x
is divisible by 3, then do nothing; otherwise display
x
.
Step 3:
Increment
x
by 1.
Step 4: Repeat steps 2 and 3 until
x
is greater than 20.
9.
A teacher has a goal of displaying the names of 2 students selected at random from a group of 30 students in a
classroom. Any possible pair of students should be equally likely to be selected. Which of the following algorithms
can be used to accomplish the teacher’s goal?
Test Booklet
Quiz - Big Idea 3 - Algorithms
Page 6 of 79
AP Computer Science Principles
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
Consider the following multiplication problem: Given an integer list (an array) of size n, we
want to calculate the product of all numbers in the list and display the result.
(a) Define an instance of a problem in general.
(b) Specify two different instances of the multiplication problem defined above.
(c) What is the solution for each instance in part (b). How did you come up with that
solution?
arrow_forward
In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem. Following is the problem statement: There are n people standing in a circle waiting to be executed. The counting out begins at some point (rear) in the circle and proceeds around the circle in a fixed direction. In each step, a certain number (k) of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1…
arrow_forward
Problem 1. Construct a non-recursive procedure capable of reversing a single linked list
of n elements, which runs in O(n) time. Can the same be achieved in (n) time? If so,
construct it.
arrow_forward
The Longest Subsequence Problem is a well-studied problem in Computer Science, where given a sequence of distinct positive integers, the goal is to output the longest subsequence whose elements appear from smallest to largest, or from largest to smallest. For example, consider the sequence S = [9,7,4,10,6,8,2,1,3,5]. The longest increasing subsequence of S has length three ([4,6,8] or [2,3,5]), and the longest decreasing subsequence of S has length five([9,7,4,2,1] or [9,7,6,2,1]). And if we have the sequence S = [531,339,298,247,246,195,104,73,52,31], then the length of the longest increasing subsequence is 1 and the length of the longest decreasing subsequence is 10.
Question:
Let S be a sequence with ten distinct integers. Prove by Contradiction that there must exist an increasing subsequence of length 4 (or more) or a decreasing subsequence of length 4 (or more).
Hint: for each integer k in the sequence you found in the first part, define the ordered pair (x(k), y(k)), where x(k)…
arrow_forward
Sudoku is a popular logic puzzle that uses a 9 by 9 array of squares that are organized into 3 by 3 subarrays. The puzzle solver must fill in the squares with the digits 1 to 9 such that no digit is repeated in any row, any column, or any of the nine 3 by 3 subgroups of squares.
Initially, some squares are filled in already and cannot be changed. For example, the following might be a starting configuration for a Sudoku puzzle:
Create a class SudokuPuzzle.java Download SudokuPuzzle.java that has the attributes
• board—a 9 by 9 array of integers that represents the current state of the puzzle, where 0 indicates a blank square
• start—a 9 by 9 array of boolean values that indicates which squares in board are given values that cannot be changed and the following methods:
• SudokuPuzzle—a constructor that creates an empty puzzle
• toString—returns a string representation of the puzzle that can be printed
• addInitial(row, col, value)—sets the given square to the given value as an…
arrow_forward
Algorithm design with sorting. Each of n users spends some time on a social media site. For each i = 1, . . . , n, user i enters the site at time ai and leaves at time bi ≥ ai. You are interested in the question: how many distinct pairs of users are ever on the site at the same time? (Here, the pair (i, j) is the same as the pair (j, i)).Example: Suppose there are 5 users with the following entering and leaving times:
Then, the number of distinct pairs of users who are on the site at the same time is five: these pairs are (1, 2), (1, 3), (2, 3), (4, 6), (5, 6). (Drawing the intervals on a number line may make this easier to see).(a) Given input (a1 , b1),(a2 , b2), . . . ,(an, bn) as above in no particular order (i.e., not sorted in any way), describe a straightforward algorithm that takes Θ(n2)-time to compute the number of pairs of users who are ever on the site at the same time, and explain why it takes Θ(n2)-time. [We are expecting pseudocode and a brief justification for its…
arrow_forward
Merge sort is an efficient sorting algorithm with a time complexity of O(n log n). This means that as the number of elements (chocolates or students) increases significantly, the efficiency of merge sort remains relatively stable compared to other sorting algorithms. Merge sort achieves this efficiency by recursively dividing the input array into smaller sub-arrays, sorting them individually, and then merging them back together.
The efficiency of merge sort is primarily determined by its time complexity, which is , where n is the number of elements in the array. This time complexity indicates that the time taken by merge sort grows logarithmically with the size of the input array. Therefore, even as the number of chocolates or students increases significantly, merge sort maintains its relatively efficient performance.
Regarding the distribution of a given set of x to y using iterative and recursive functions, the complexity analysis depends on the specific implementation of each…
arrow_forward
The ColumnChoice problem takes as input a two-dimensional array A[1..m, 1..n] of
Os and 1s with m rows and n columns along with a non-negative integer k < n. It asks
whether there exists a subset SC {1, ..., n} of k columns such that for each row i e {1,..., m}
there exists at least one column j e S where A[i, j] = 1. Prove that ColumnChoice is NP-
complete.
arrow_forward
Exercise 3.
Given the following recurrence relation:
T(1) = 1
T(n) = T(n − 1) + n2 for n ≥ 2
Indicate a methodology you can use to evaluate a closed form expression
Provide the closed form expression and show the procedure to obtain it
Provide a recursive algorithm in pseudo code to calculate a generic T(n)
Provide an analysis of the algorithm above
arrow_forward
A certain recursive algorithm takes an input list of n elements. Divides the list into Vn
sub-lists, each with yn elements. Recursively solves each of these yn smaller sub-
instances. Then spends an additional 0(n) time to combine the solutions of these sub-
instances to obtain the solution of the main instance.
As a base case, if the size of the input list is at most a specified positive constant, then
the algorithm solves such a small instance directly in 0(1) time.
a) Express the recurrence relation that governs T(n), the time complexity of this
algorithm.
b) Derive the solution to this recurrence relation: T(n) = 0(?).
Mention which methods you used to derive your solution.
arrow_forward
1. Analyze the word finder with wild card characters scenario to form
the algorithm and compute the time complexity.
You are given a list of characters with size n, m. You need to read
character data provided as input into this list. There is also a list of p
words that you need to find in the given problem. You can only search
in left, right, up and down direction from a position. There are two wild
characters *' and '+' ,if there is any instance of wild card characters for
example '+' appears you can match whatever character in your word that
you are searching at this position (only one character). Similarly, if you
got wildcard *' you can skip any number of characters ( A sequence of
characters not necessary same in between the characters) but the last
character should be matched in the given data. This means you are not
allowed to match a first and last character with *' wildeard.
Input:
The first line of the input will give you two integers n and m. From the
next line you will get…
arrow_forward
A magic square of order n is an arrangement of the integers from 1 to n2 in an n × n matrix, with each number occurring exactly once, so that each row, each column, and each main diagonal has the same sum Design and implement an exhaustive-search algorithm for generating all magic squares of order n.
arrow_forward
PLEASE USE PYTHONGiven a jungle matrix NxM:jungle = [ [1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1,]]Where 0 means the block is dead end and 1 means the block can be used in the path fromsource to destination.Task:Starting at position (0, 0), the goal is to reach position (N-1, M-1).Your program needs to build and output the solution matrix – a 4x4 matrix with 1’s inpositions used to get from the starting position (0,0) to the ending position (N-1,M-1)with the following constraints:You can only move one space at a timeYou can only in two directions: forward and down.You can only pass thru spaces on the jungle matrix marked ‘1’If you cannot reach the ending position – print a message that you’re trapped in thejungleAlgorithm:If destination is reachedprint the solution matrixElseMark current cell in the solution matrixMove forward horizontally and recursively check if this leads to a solution If there is no solution, move down and recursively check if this leads to a solution If…
arrow_forward
We consider an improvement for the linear search by organizing the list based upon
frequency of access. What is not one of the three often used heuristics involving
maintaining this frequency as discussed in our lecture?
move to front
mark and replace
transpose
order by count
all of these
none of these
arrow_forward
develop an implementation TwoSumFaster that uses a linear algorithm to count the pairs that sum to zero after the array is sorted (instead of the binary-search-based linearithmic algorithm). Then apply a similar idea to develop a quadratic algorithm for the 3-sum problem.
arrow_forward
Question 2:
The game of "FastestPath" consists of a path (a 1-D array) with n positive integers to represent n
cities in a path (except the first index which has always value 0). The aim of the game is to move
from the source city (located at index 0) to destination (located at last index) in the shortest time.
The value at each index shows the travel time to enter the city located in the corresponding index.
Here is a sample path where there are 6 cities (n is 6):
|0 5 |90 | 7 61 | 12
Always start the game from the first city and there are two types of moves. You can either move
to the adjacent city or jump over the adjacent city to land two cities over. The total travel time of
a game is the sum of the travel times of the visited cities.
In the path shown above, there are several ways to get to the end. Starting in the first city, our time
so far is 0. We could travel to city 2, then travel to city 4, then travel to last city for a total travel
time of 90 + 61 + 12 = 163. However, a…
arrow_forward
Please do not give solution in image formate thanku.
Write a Python code for the following scenario :
1: Use Breadth First Search and Recursive Best First Search and implement the algorithms in Python. The program should be able to dynamically take in start and goal nodes from the user at run time. Compare to interpret the results in terms of the algorithm working, performance & shortest path if obtained relevant to the given problem
2: Print the minimum connections that keep the whole network up and running. For each incremental depth limit, the corresponding node generating sequence should be legibly printed in the result
Consider Heuristic Value as :
The edge cost is an approximation towards the transmission cost between any pair of nodes. For heuristic design, consider all the possible paths between any arbitrary node n to the goal node. The average of the total transmission cost across all these paths is the heuristic value h(n)
Consider the following undirected graph…
arrow_forward
The intersection of two sets contains the list of elements that are common to both, without
repetition. As such, you are required to write an algorithm that finds and returns the intersection
of two sets A and B. The sets A and B and the resulting intersection set are all lists. Assume
the size of A is n and that of B is m.
(a) Write an iterative algorithm that finds the intersection.
(b) Prove the correctness of your algorithm; i.e. state its loop invariant and prove it by induc-
tion.
(c) Analyze the time complexity of your algorithm.
(d) Think of a way to enhance the complexity of your algorithm by sorting both lists A and
B before calculating their intersection. Write the enhanced version and prove that it has a
better time complexity.
arrow_forward
1. Write an algorithm to determine whether a given element x belongs to a set S := {s1, . . . , sn}.
arrow_forward
Devise an algorithm that matches the lower bound, i.e., sorts a list in which
each paper is within k slots of its proper position in e (n log k) time. Hint: See
Exercise 6.5-8 on page 166 of Introduction to Algorithms, Third Edition.
arrow_forward
4. Consider the function IndexEqual(A,i.j) that returns true if there exists an index x (i sx sj)
such that A[x] = x; otherwise, retums false. You may assume A is a sorted integer array in
which every element is unique.
a. Write an efficient recursive algorithm for IndexEqual(A,i.j).
b. What is the situation resulting in the best-case running time of your function, and give
an expression for that running time?
c. What is the situation resulting in the worst-case running time of your function, and give
an expression for that running time in terms of n, where n=j-i+1?
arrow_forward
Assuming that quick sort algorithm presented selects the first element in the list as the pivot.
(A) Give a list of n items (for example, an array of 10 integers) representing a scenario.
(B) Give a list of n items (for example, an array of 10 integers) representing the worst-case scenario.
(C) Give a list of n items (for example, an array of 10 integers) representing the best-case scenario.
arrow_forward
Question 6:
Professor Holmes has come up with a new sorting algorithm. He calls it Trinary Sort and
"claims" that it is asymptotically faster than Merge Sort, despite the fact both the algorithms
operate using similar logic. But, unlike Merge Sort, Trinary Sort splits the input array into
(roughly) 3 equal parts at each step of the recursion as long as the array is splittable (i.e., has
at least 3 elements). Trinary Sort's merge subroutine, similar in principle to the one used by
Merge Sort, takes 3 sorted subarrays and merges them to produce a single sorted array. Given
all of this, answer the following questions.
(a)
In Merge Sort, the merge subroutine makes n-1 comparisons to merge 2 arrays
of size n/2, which takes (n) time. How many comparisons will the merge subroutine of
Trinary Sort make to merge 3 arrays of size n/3? What would be the (...) bound on
the running time for this subroutine?
(b)
What is the (...) bound on the running time of the Trinary Sort algorithm?
Come up with…
arrow_forward
Computer Science
Write the PSEUDOCODE for an algorithm that takes as input a list of numbers that are sorted in nondecreasing order, and finds the location(s) of the most frequently occurring element(s) in the list. If there are more than one element that is the most frequently occurring, then return the locations of all of them. Analyze the worst-case time complexity of this algorithm and give the O() estimate. (A list is in nondecreasing order if each number in the list is greater than or equal to the number preceding it.)
arrow_forward
In python,
The Longest Subsequence Problem is a well-studied problem in Computer Science, where given a sequence of distinct positive integers, the goal is to output the longest subsequence whose elements appear from smallest to largest, or from largest to smallest. For example, consider the sequence S= [9,7,4,10,6,8,2,1,3,5]. The longest increasing subsequence of S has length three ([4,6,8] or [2,3,5]), and the longest decreasing subsequence of S has length five([9,7,4,2,1] or [9,7,6,2,1]). And if we have the sequence S = [531,339,298,247,246,195,104,73,52,31], then the length of the longest increasing subsequence is 1 and the length of the longest decreasing subsequence is 10.
Question:
Find a sequence with nine distinct integers for which the length of the longest increasing subsequence is 3, and the length of the longest decreasing subsequence is 3. Briefly explain how youconstructed your sequence.
arrow_forward
Design an algorithm to find min and max-The algorithm should do, at most, about 3n/2 comparisons (in the worst case scenario) for problems of size n elements.- The algorithm is supposed to take in a list, assumed to be integers.- The list given to the algorithm is unsorted.
arrow_forward
To add the two polynomials, we assume that the singly linked lists' nodes are organized in decreasing order of the variable x's exponents.The goal is to generate a new list of nodes reflecting the sum of P1 and P2. This is accomplished by combining the COEFF fields of nodes with comparable powers of variable x in lists P1 and P2, and then adding a new node in the resultant list P1 + P2. The procedure's core is presented below.P1 and P2 are the beginning pointers of the singly linked lists that symbolize polynomials P1 and P2. Furthermore, PTR1 and PTR2 are two temporary pointers that are originally set to P1 and P2, respectively.
Procedure code should be written.
arrow_forward
Design a reduction algorithm that solves the below problem; Describe your algorithm with clear pseudocode, and mention the time and space efficiency class of your algorithm in terms of the size of the input
Also, identify the pre/post-processing steps
Problem:
input: a list L of comparable objectsoutput: an element of L that appears more than once in L, or None if no such element exists
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
- Consider the following multiplication problem: Given an integer list (an array) of size n, we want to calculate the product of all numbers in the list and display the result. (a) Define an instance of a problem in general. (b) Specify two different instances of the multiplication problem defined above. (c) What is the solution for each instance in part (b). How did you come up with that solution?arrow_forwardIn computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem. Following is the problem statement: There are n people standing in a circle waiting to be executed. The counting out begins at some point (rear) in the circle and proceeds around the circle in a fixed direction. In each step, a certain number (k) of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1…arrow_forwardProblem 1. Construct a non-recursive procedure capable of reversing a single linked list of n elements, which runs in O(n) time. Can the same be achieved in (n) time? If so, construct it.arrow_forward
- The Longest Subsequence Problem is a well-studied problem in Computer Science, where given a sequence of distinct positive integers, the goal is to output the longest subsequence whose elements appear from smallest to largest, or from largest to smallest. For example, consider the sequence S = [9,7,4,10,6,8,2,1,3,5]. The longest increasing subsequence of S has length three ([4,6,8] or [2,3,5]), and the longest decreasing subsequence of S has length five([9,7,4,2,1] or [9,7,6,2,1]). And if we have the sequence S = [531,339,298,247,246,195,104,73,52,31], then the length of the longest increasing subsequence is 1 and the length of the longest decreasing subsequence is 10. Question: Let S be a sequence with ten distinct integers. Prove by Contradiction that there must exist an increasing subsequence of length 4 (or more) or a decreasing subsequence of length 4 (or more). Hint: for each integer k in the sequence you found in the first part, define the ordered pair (x(k), y(k)), where x(k)…arrow_forwardSudoku is a popular logic puzzle that uses a 9 by 9 array of squares that are organized into 3 by 3 subarrays. The puzzle solver must fill in the squares with the digits 1 to 9 such that no digit is repeated in any row, any column, or any of the nine 3 by 3 subgroups of squares. Initially, some squares are filled in already and cannot be changed. For example, the following might be a starting configuration for a Sudoku puzzle: Create a class SudokuPuzzle.java Download SudokuPuzzle.java that has the attributes • board—a 9 by 9 array of integers that represents the current state of the puzzle, where 0 indicates a blank square • start—a 9 by 9 array of boolean values that indicates which squares in board are given values that cannot be changed and the following methods: • SudokuPuzzle—a constructor that creates an empty puzzle • toString—returns a string representation of the puzzle that can be printed • addInitial(row, col, value)—sets the given square to the given value as an…arrow_forwardAlgorithm design with sorting. Each of n users spends some time on a social media site. For each i = 1, . . . , n, user i enters the site at time ai and leaves at time bi ≥ ai. You are interested in the question: how many distinct pairs of users are ever on the site at the same time? (Here, the pair (i, j) is the same as the pair (j, i)).Example: Suppose there are 5 users with the following entering and leaving times: Then, the number of distinct pairs of users who are on the site at the same time is five: these pairs are (1, 2), (1, 3), (2, 3), (4, 6), (5, 6). (Drawing the intervals on a number line may make this easier to see).(a) Given input (a1 , b1),(a2 , b2), . . . ,(an, bn) as above in no particular order (i.e., not sorted in any way), describe a straightforward algorithm that takes Θ(n2)-time to compute the number of pairs of users who are ever on the site at the same time, and explain why it takes Θ(n2)-time. [We are expecting pseudocode and a brief justification for its…arrow_forward
- Merge sort is an efficient sorting algorithm with a time complexity of O(n log n). This means that as the number of elements (chocolates or students) increases significantly, the efficiency of merge sort remains relatively stable compared to other sorting algorithms. Merge sort achieves this efficiency by recursively dividing the input array into smaller sub-arrays, sorting them individually, and then merging them back together. The efficiency of merge sort is primarily determined by its time complexity, which is , where n is the number of elements in the array. This time complexity indicates that the time taken by merge sort grows logarithmically with the size of the input array. Therefore, even as the number of chocolates or students increases significantly, merge sort maintains its relatively efficient performance. Regarding the distribution of a given set of x to y using iterative and recursive functions, the complexity analysis depends on the specific implementation of each…arrow_forwardThe ColumnChoice problem takes as input a two-dimensional array A[1..m, 1..n] of Os and 1s with m rows and n columns along with a non-negative integer k < n. It asks whether there exists a subset SC {1, ..., n} of k columns such that for each row i e {1,..., m} there exists at least one column j e S where A[i, j] = 1. Prove that ColumnChoice is NP- complete.arrow_forwardExercise 3. Given the following recurrence relation: T(1) = 1 T(n) = T(n − 1) + n2 for n ≥ 2 Indicate a methodology you can use to evaluate a closed form expression Provide the closed form expression and show the procedure to obtain it Provide a recursive algorithm in pseudo code to calculate a generic T(n) Provide an analysis of the algorithm abovearrow_forward
- A certain recursive algorithm takes an input list of n elements. Divides the list into Vn sub-lists, each with yn elements. Recursively solves each of these yn smaller sub- instances. Then spends an additional 0(n) time to combine the solutions of these sub- instances to obtain the solution of the main instance. As a base case, if the size of the input list is at most a specified positive constant, then the algorithm solves such a small instance directly in 0(1) time. a) Express the recurrence relation that governs T(n), the time complexity of this algorithm. b) Derive the solution to this recurrence relation: T(n) = 0(?). Mention which methods you used to derive your solution.arrow_forward1. Analyze the word finder with wild card characters scenario to form the algorithm and compute the time complexity. You are given a list of characters with size n, m. You need to read character data provided as input into this list. There is also a list of p words that you need to find in the given problem. You can only search in left, right, up and down direction from a position. There are two wild characters *' and '+' ,if there is any instance of wild card characters for example '+' appears you can match whatever character in your word that you are searching at this position (only one character). Similarly, if you got wildcard *' you can skip any number of characters ( A sequence of characters not necessary same in between the characters) but the last character should be matched in the given data. This means you are not allowed to match a first and last character with *' wildeard. Input: The first line of the input will give you two integers n and m. From the next line you will get…arrow_forwardA magic square of order n is an arrangement of the integers from 1 to n2 in an n × n matrix, with each number occurring exactly once, so that each row, each column, and each main diagonal has the same sum Design and implement an exhaustive-search algorithm for generating all magic squares of order n.arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
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