Hire Experts For Answers

Order Now#### Related Study Services

- Homework Answers
- Coursework writing help
- Term paper writing help
- Writing Help
- Paper Writing Help
- Research paper help
- Thesis Help
- Dissertation Help
- Case study writing service
- Capstone Project Writing Help
- Lab report Writing
- Take my online class
- Take my online exam
- Do my test for me
- Do my homework
- Do my math homework
- Online Assignment Help
- Do my assignment
- Essay Writing Help
- Write my college essay
- Write my essay for me

DESCRIPTION

Posted

Modified

Viewed
14

NUS CS3230 Task 2:
You have a rectangular-shaped cake of size r by c. On this cake, there are n rectangular-shaped toppings. The sides of these rectangles are parallel to the sides of the cake.
You are allowed to cut the cake into several pieces according to the following rules:
1. Every cut must be either a vertical line or a horizontal line. No diagonal cuts are allowed.
2. Every cut must increase the number of pieces by 1. Partial cuts (refer to Figure 2 in file) are not allowed.
3. The cuts cannot break up the toppings (i.e. each topping should remain as a single piece). However, cuts along the boundary of the toppings are allowed.
4. At the end of all the cuts, every piece should have at least 1 topping.
Find the maximum number of pieces you can cut the cake into which follows these rules.
Time complexity requirement: Should finish in O(n^2 log n) time

This order does not have tags, yet.

Attachments

Design and Analysis of Algorithms 2021
National University of Singapore CS3230
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm)
For this programming assignment, you will not have to submit any written answers (except for the
challenge). Instead, you will have to submit a program written in Java or C++11 on CodeCrunch at
https://codecrunch.comp.nus.edu.sg/. The portal will stop accepting submissions
after 2 Mar 2021 2359h so please start your assignment early.
Templates will be provided for all the problems. These templates provide a starting point for
your implementation. It is highly recommended (but not required) to use all the templates given to
you. Do not change the file name or the class name of the template, or else your code may be
marked as incorrect. You have to submit your own work. Posting the question or solution in
public repositories are not allowed also counts as a form of plagiarism. Any form of plagiarism
is subject to disciplinary action.
You will not be graded for programming style. However, you may be asked to explain your code
if the marker cannot understand it. Marks will be deducted if there are bugs in your code or if your
algorithm does not meet the time complexity stated in the question. You are strongly encouraged
to design your own test cases to test your code.
If you need any clarification on any of the questions, do post on the LumiNUS forum so that
everyone can see your responses.
For queries related to task 1, contact Rasnayaka Mudiyanselage Sanka Nuwan Bandara Ras-
nayaka (e0147061@u.nus.edu). For queries related to task 2, contact Ling Yan Hao (e0174827@u.nus.edu).
Note: Passing all the test cases on CodeCrunch does not guarantee that you will get full
credit for the assignment. We may add additional test cases while grading your solutions.
https://codecrunch.comp.nus.edu.sg/
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 2
1 Task 1 (2 marks)
1.1 Statement
To multiply two n by n matrices, Strassen’s matrix multiplication runs in O(nlog2 7) time, which is
faster than the naive algorithm which runs in O(n3) time.
However, asymptotic analysis does not take into account the constant factors. For small matri-
ces, Strassen’s algorithm can run significantly slower than the naive approach.
As such, one approach is to switch to naive matrix multiplication for small matrices and use
Strassen’s algorithm for large matrices. In particular, when we perform the recursive step, we
check for the size of the matrix. When the matrix is sufficiently small, we switch to naive matrix
multiplication instead of recursively doing Strassen’s algorithm.
(Side remark: this paradigm of switching to an asymptotically slower algorithm for small inputs
is a common theme. For example, O(n2) sorting algorithms like insertion sort may perform faster
than O(n log n) algorithms like quick sort and merge sort for small inputs. As such, it is common
to use insertion sort for small arrays and quick sort for large arrays. Another example of this
paradigm comes from parallel programming where the overhead of spawning additional threads
makes it more efficient to run sequential algorithms for small inputs.)
You are given two matrices A and B. Your task is to compute the matrix product AB using
Strassen’s algorithm with the above optimization. For this task, we recommend switching to naive
matrix multiplication for matrices of size 64 × 64 or smaller, while using recursive algorithm for
larger matrices.
1.2 Input format
The first line of the input consists of a single integer n, indicating that the matrix are n× n.
After which n lines follow which represents the entries of A. In particular, the i-th line of these
n lines will contain Ai,1, Ai,2, . . . , Ai,n.
Following which, another n lines follow, indicating the entries of B.
1.3 Output format
Output n lines, each consisting of n integers, representing the matrix product AB.
1.4 Constraints
• 1 ≤ n ≤ 1024
• n is a power of 2
• All entries of the matrix A and B are between −100 and 100 inclusive. Note that this does
not mean that the correct output AB will have entries between −100 and 100.
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 3
1.5 Scoring
Your solution should terminate in 20 seconds for C++ or 30 seconds for Java.
Note that your solution will still be manually graded and should properly implement Strassen’s
algorithm. Solutions which pass the sample test case using other techniques will not be given
credit.
1.6 Samples
Sample input
2
1 4
3 2
7 5
9 8
Sample output
43 37
39 31
2 Task 2 (6 marks + 1 mark challenge)
2.1 Statement
You have a rectangular-shaped cake of size r by c. On this cake, there are n rectangular-shaped
toppings. The sides of these rectangles are parallel to the sides of the cake.
You are allowed to cut the cake into several pieces according to the following rules:
1. Every cut must be either a vertical line or a horizontal line. No diagonal cuts are allowed.
2. Every cut must increase the number of pieces by 1. Partial cuts (refer to Figure 2) are not
allowed.
3. The cuts cannot break up the toppings (i.e. each topping should remain as a single piece).
However, cuts along the boundary of the toppings are allowed.
4. At the end of all the cuts, every piece should have at least 1 topping.
Find the maximum number of pieces you can cut the cake into which follows these rules.
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 4
2.2 Input format
The first line of the input contains 3 space-separated integers r, c, n. After which, there are n lines.
Each of these n lines contains 4 space-separated integers x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ r, 0 ≤ y1 <
y2 ≤ c) , indicating that there is a single topping on the rectangular region x1 < x < x2, y1 < y <
y2.
2.3 Output format
Output a single integer- the maximum number of pieces you can cut the cake into.
2.4 Constraints
• 1 ≤ n ≤ 5000
• 1 ≤ r, c ≤ 109
• The region occupied by different toppings are disjoint (i.e. do not overlap).
2.5 Scoring
Full credit (6 marks) will be given for solutions which run in O(n2 log n) time. Solutions which
run in O(n3) time will be given a partial credit of 4 marks. Solutions in C++ should terminate in 1
second and solutions in Java should terminate in 2 seconds on CodeCrunch.
2.5.1 Challenge (1 mark bonus)
Our best solution runs in O(n log n) time. Students who can find this solution will be awarded
1 mark extra credit. To score this 1 mark, submit a written description of your algorithm to-
gether with a time complexity analysis and email it to e0174827@u.nus.edu with the subject
‘CS3230 PA1 Bonus’ before the deadline. There will be no test cases provided for the challenge.
2.6 Samples
Refer to figures 5 and 6 for explanation for the samples.
Sample input 1
3 3 4
0 0 2 1
2 0 3 2
1 2 3 3
0 1 1 3
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 5
Sample output 1
1
Sample input 2
3 3 4
0 0 2 1
2 0 3 1
1 2 3 3
0 1 1 3
Sample output 2
4
Figure 1: This cut is not allowed as the line is not parallel to the sides of the cake.
Figure 2: This is a partial cut and thus it is not allowed.
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 6
Figure 3: Although this cut does not go through the whole cake, it is allowed as it increases the
number of pieces.
Figure 4: This is a disallowed cut as it goes cuts the topping (the shaded region) into two parts.
1 1 2
2
334
4
Figure 5: Sample input 1: We are unable to make any cuts which satisfies the rules. Therefore, the
answer is 1.
1 1 2
334
4
Figure 6: Sample input 2: By making the horizontal cut before the vertical cuts, it is possible to
make 4 cuts such that the 4 toppings are in different parts.
Task 1 (2 marks)
Statement
Input format
Output format
Constraints
Scoring
Samples
Task 2 (6 marks + 1 mark challenge)
Statement
Input format
Output format
Constraints
Scoring
Challenge (1 mark bonus)
Samples
Design and Analysis of Algorithms 2021
National University of Singapore CS3230
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm)
For this programming assignment, you will not have to submit any written answers (except for the
challenge). Instead, you will have to submit a program written in Java or C++11 on CodeCrunch at
https://codecrunch.comp.nus.edu.sg/. The portal will stop accepting submissions
after 2 Mar 2021 2359h so please start your assignment early.
Templates will be provided for all the problems. These templates provide a starting point for
your implementation. It is highly recommended (but not required) to use all the templates given to
you. Do not change the file name or the class name of the template, or else your code may be
marked as incorrect. You have to submit your own work. Posting the question or solution in
public repositories are not allowed also counts as a form of plagiarism. Any form of plagiarism
is subject to disciplinary action.
You will not be graded for programming style. However, you may be asked to explain your code
if the marker cannot understand it. Marks will be deducted if there are bugs in your code or if your
algorithm does not meet the time complexity stated in the question. You are strongly encouraged
to design your own test cases to test your code.
If you need any clarification on any of the questions, do post on the LumiNUS forum so that
everyone can see your responses.
For queries related to task 1, contact Rasnayaka Mudiyanselage Sanka Nuwan Bandara Ras-
nayaka (e0147061@u.nus.edu). For queries related to task 2, contact Ling Yan Hao (e0174827@u.nus.edu).
Note: Passing all the test cases on CodeCrunch does not guarantee that you will get full
credit for the assignment. We may add additional test cases while grading your solutions.
https://codecrunch.comp.nus.edu.sg/
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 2
1 Task 1 (2 marks)
1.1 Statement
To multiply two n by n matrices, Strassen’s matrix multiplication runs in O(nlog2 7) time, which is
faster than the naive algorithm which runs in O(n3) time.
However, asymptotic analysis does not take into account the constant factors. For small matri-
ces, Strassen’s algorithm can run significantly slower than the naive approach.
As such, one approach is to switch to naive matrix multiplication for small matrices and use
Strassen’s algorithm for large matrices. In particular, when we perform the recursive step, we
check for the size of the matrix. When the matrix is sufficiently small, we switch to naive matrix
multiplication instead of recursively doing Strassen’s algorithm.
(Side remark: this paradigm of switching to an asymptotically slower algorithm for small inputs
is a common theme. For example, O(n2) sorting algorithms like insertion sort may perform faster
than O(n log n) algorithms like quick sort and merge sort for small inputs. As such, it is common
to use insertion sort for small arrays and quick sort for large arrays. Another example of this
paradigm comes from parallel programming where the overhead of spawning additional threads
makes it more efficient to run sequential algorithms for small inputs.)
You are given two matrices A and B. Your task is to compute the matrix product AB using
Strassen’s algorithm with the above optimization. For this task, we recommend switching to naive
matrix multiplication for matrices of size 64 × 64 or smaller, while using recursive algorithm for
larger matrices.
1.2 Input format
The first line of the input consists of a single integer n, indicating that the matrix are n× n.
After which n lines follow which represents the entries of A. In particular, the i-th line of these
n lines will contain Ai,1, Ai,2, . . . , Ai,n.
Following which, another n lines follow, indicating the entries of B.
1.3 Output format
Output n lines, each consisting of n integers, representing the matrix product AB.
1.4 Constraints
• 1 ≤ n ≤ 1024
• n is a power of 2
• All entries of the matrix A and B are between −100 and 100 inclusive. Note that this does
not mean that the correct output AB will have entries between −100 and 100.
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 3
1.5 Scoring
Your solution should terminate in 20 seconds for C++ or 30 seconds for Java.
Note that your solution will still be manually graded and should properly implement Strassen’s
algorithm. Solutions which pass the sample test case using other techniques will not be given
credit.
1.6 Samples
Sample input
2
1 4
3 2
7 5
9 8
Sample output
43 37
39 31
2 Task 2 (6 marks + 1 mark challenge)
2.1 Statement
You have a rectangular-shaped cake of size r by c. On this cake, there are n rectangular-shaped
toppings. The sides of these rectangles are parallel to the sides of the cake.
You are allowed to cut the cake into several pieces according to the following rules:
1. Every cut must be either a vertical line or a horizontal line. No diagonal cuts are allowed.
2. Every cut must increase the number of pieces by 1. Partial cuts (refer to Figure 2) are not
allowed.
3. The cuts cannot break up the toppings (i.e. each topping should remain as a single piece).
However, cuts along the boundary of the toppings are allowed.
4. At the end of all the cuts, every piece should have at least 1 topping.
Find the maximum number of pieces you can cut the cake into which follows these rules.
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 4
2.2 Input format
The first line of the input contains 3 space-separated integers r, c, n. After which, there are n lines.
Each of these n lines contains 4 space-separated integers x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ r, 0 ≤ y1 <
y2 ≤ c) , indicating that there is a single topping on the rectangular region x1 < x < x2, y1 < y <
y2.
2.3 Output format
Output a single integer- the maximum number of pieces you can cut the cake into.
2.4 Constraints
• 1 ≤ n ≤ 5000
• 1 ≤ r, c ≤ 109
• The region occupied by different toppings are disjoint (i.e. do not overlap).
2.5 Scoring
Full credit (6 marks) will be given for solutions which run in O(n2 log n) time. Solutions which
run in O(n3) time will be given a partial credit of 4 marks. Solutions in C++ should terminate in 1
second and solutions in Java should terminate in 2 seconds on CodeCrunch.
2.5.1 Challenge (1 mark bonus)
Our best solution runs in O(n log n) time. Students who can find this solution will be awarded
1 mark extra credit. To score this 1 mark, submit a written description of your algorithm to-
gether with a time complexity analysis and email it to e0174827@u.nus.edu with the subject
‘CS3230 PA1 Bonus’ before the deadline. There will be no test cases provided for the challenge.
2.6 Samples
Refer to figures 5 and 6 for explanation for the samples.
Sample input 1
3 3 4
0 0 2 1
2 0 3 2
1 2 3 3
0 1 1 3
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 5
Sample output 1
1
Sample input 2
3 3 4
0 0 2 1
2 0 3 1
1 2 3 3
0 1 1 3
Sample output 2
4
Figure 1: This cut is not allowed as the line is not parallel to the sides of the cake.
Figure 2: This is a partial cut and thus it is not allowed.
Programming Assignment 1 (Due: 2 Mar 2021, 11.59pm) 6
Figure 3: Although this cut does not go through the whole cake, it is allowed as it increases the
number of pieces.
Figure 4: This is a disallowed cut as it goes cuts the topping (the shaded region) into two parts.
1 1 2
2
334
4
Figure 5: Sample input 1: We are unable to make any cuts which satisfies the rules. Therefore, the
answer is 1.
1 1 2
334
4
Figure 6: Sample input 2: By making the horizontal cut before the vertical cuts, it is possible to
make 4 cuts such that the 4 toppings are in different parts.
Task 1 (2 marks)
Statement
Input format
Output format
Constraints
Scoring
Samples
Task 2 (6 marks + 1 mark challenge)
Statement
Input format
Output format
Constraints
Scoring
Challenge (1 mark bonus)
Samples

Explanations and Answers
0

No answers posted

### Post your Answer - free or at a fee

**NB: **Post a homework question for free and get answers - free or paid homework help.

Get answers to: Coding An Algorithm In Java About A Geometry Problem or similar questions only at Tutlance.

Related Questions

- An Assembly Program!!
- Java Median Cut Algorithm
- Lab 3 Assignments
- [Urgent] C++/Java Knapsack Problem
- Translating C++ Into Mars
- Kotlin (Dog Tinder Assignment)
- Project
- Computer Systems Assignment
- Computer Graphics Webgl Javascript Rotating Cubes Assignment
- Intro To Comp Sci Java Program With Linked Lists
- Operating Systems- Cpu Simulation - Threads -Scheduling
- I Need To Run Motif Search Algorithm On A Text File On Mapreduce On Aws
- Python 3 Computer Science Assigment
- Comp Sci: Python Caesar Cipher Script
- Assignment 1: The “Meepo Is You” Game
- Data Structures And Algorithm
- Python Project Containing 4 Tasks
- Beginning C++
- Student Class In Record Manage Program C# Assignment
- Show All Work Done For Each Problem And Code Plus Use Using Python
- Excel Stocks
- Excel Assignment
- Java Project Great Books Program
- Circular Doubly Linked List In Java Program
- Machine Language & Assembly Language Programming
- C# Programming Assignment
- Java Assignment
- Java Priority Queues
- Data Visualization R A3
- Vlookup Excel Project
- Create 2 Html And 1 Ccs File (Information Given)
- Machine Language & Assembly Language Programming
- I Need To Create An Access Database
- C Programming
- Creating A Columns Game In Python (Computer Science)
- Unix Pipes
- I Need To Run A Mapreduce Word Count Program On Aws.can Someone Meet Me On And Help Me With This On Screen Sharing?
- Sql Homework
- Hackerrank Contacts Problem
- Crc Detection And Checksum Comparison
- C++/Aarch64
- C++ Operator Overloading
- C++ Operator Overloading
- ( I Am Currently In Japan So I Am 14 Hrs Ahead Of The Us Right Now...the Deadline Is Approximately 16Hrs Away)
- Geomatics Database Homework W/ Access
- Principles Python Programming 22 Assignments
- C++ Threading
- Data Structures And Algorithm Assessment
- Floating-Point Arithmetic 32-Bitt Calculator.
- Facial Recognition System