Description
COP 3503C Programming Assignment 1
As we learned from the sorted list matching problem that a problem can be solved in various ways and being clever can
improve the performance of an algorithm a lot. In this problem you also need to come up with a solution that can run
within a given run-time.
What should you submit?
Write all the code in a single Main.java file. Submit your Main.java and analysis.txt file to Codegrade platform.
The
content of the analysis.txt file will be discussed at the last part of the assignment description.
Please include the following commented lines in the beginning of your code to declare your authorship of the code:
/* COP 3503C Assignment 1
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules
mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students for explaining any
part of the code in order to better assess your authorship and for further clarification if needed.
Caution!!!
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a
violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who
shared/posted it. Also, getting a part of code from anywhere will be considered as cheating.
Deadline:
See the deadline in Webcourses. The assignment submission will be locked after the deadline. An assignment submitted by
email will not be graded and such emails will not be replied according to the course policy.
What to do if you need clarification on the problem?
I will create a discussion thread in webcourses and I highly encourage you to ask your question in the discussion board.
Maybe many students might have same question as you. Also, other students can reply, and you might get your answer
faster. Also, you can write an email to the TAs and put the course teacher in the cc for clarification on the requirements.
How to get help if you are stuck?
According to the course policy, all the helps should be taken during office hours. Occasionally, we might reply in email.
Problem: Help Gustavo to choose the games!
Gustavo got a Knights arcade game card with T points in it. Knights arcade has n unique games where each game requires
a unique number of points to play. Gustavo is allowed to play only two games and he wants to spend the full T points to
play two games so that no points will remain in the card.
So, he needs to decide whether is it possible or not to play two
games that will cost exactly T points. Given an array of n distinct none zero valuesrepresenting the points needed to play
the games.
Also, given the target points T available on the card. Determine in O(n) time whether or not there exist two
distinct points in the array that sum to T. The given array maybe sorted or may not be already sorted. It will be specified
in the input whether it is sorted or not and you have to fulfill specific requirement based on the sorted status. (For example,
if the array contained 3, 5, 6, 7, and 9 and T = 14, then the method you are to write should return points pair (5,9), since
5+9 = 14. It should return points pair (0,0) for the same array of points if T = 17.)
Input Format (Your code must read from standard input (no file i/o is allowed))
The first line of the input will have a single positive integer k, representing the number of test cases in the inputs. The next
2*k lines will contain the test cases, with two lines being used for each test case.
The first value on the first line of each
test case will be the sorted status (0 means unsorted, 1 means sorted). The next number in the line is n, the size of the
array (the number of games in the Knights arcade).
The rest of the line will contain n distinct none zero integers
representing the points needed to play, each separated by spaces. The second line of each test case will contain a single
integer, T, the target for the problem (The number of points in the game card). Here’s an example input contents:
4
1 5 3 5 6 7 9
14
0 3 1 6 3
11
0 6 4 1 -8 6 45 10
16
1 6 -8 1 4 6 10 45
16
Output Format
For each test case, output a line with one of the following two formats:
Test case #m: Spend X points by playing the games with n1 points and n2 points.
Test case #m: No way you can spend exactly X points.
where m (1 ≤ m ≤ k), represents the appropriate test case. In the output n1 also must be less than n2
Example output for the above inputs:
Test case#1: Spend 14 points by playing the games with 5 points and 9 points.
Test case#2: No way you can spend exactly 11 points.
Test case#3: Spend 16 points by playing the games with 6 points and 10 points.
Test case#4: Spend 16 points by playing the games with 6 points and 10 points.
Specific Restrictions:
Your code must incorporate the following restrictions to receive full credit:
1. If you see that a particular test case is sorted (sorted status = 1), your code must process it with O(n) operation
to receive more than 50% credit on this part. For this part of the implementation, you are not allowed to use
Hashset.
2. For finding the pair in the sorted array, you must implement the following function:
a. _________ getCandidatePair(int A[], int target): This function receives an int
array and the target and returns the pair of ints from the array that can addup
to target. For this purpose, you may consider having another class and return an
object of that class. If a pair does not exist, the function should return the
pair as (0, 0). Note that you are not allowed to print any information in this
function as part of the output.
3. If you see that a particular test case is not sorted (sorted status = 0), your code must process it with O(n)
operation to receive more than 75% credit on this part. If your code works with O(n log n), you can get up to
75% on this part. Note that Arrays.sort() method sometimes can result in O(n^2). The Collections.sort() method
could be a good idea to guarantee O(n log n) sorting.
If you would like to get 100% credit for this part and get
O(n) run-time, then Hashset would be the best option (Note that HashSet insert and lookup O(1)). If you are
unable to find a solution within even O(n log n), then at least solve it with O(n^2) to receive some partial credit.
Submission:
Submit the following files in codegrade. Make sure your code work in codegrade platform.
1. Main.java file that process your file
2. analysis.txt file: In this file you will explain the run-time of your algorithm for the situation of sorted array and
unsorted array. Please have two paragraphs, one for each situation. Mainly explain why do you think it is O(n)
or O(n log n) or O(n^2). Don’t try to argue that your code process this in O(n), if it is not the case!
Rubric (subject to change):
According to the Syllabus, the code will be compiled and tested in Codegrade Platform for grading. If your code does not
compile in Codegrade, we conclude that your code is not compiling and it will be graded accordingly. We will apply a set
of test cases to check whether your code can produce the expected output or not. Failing each test case will reduce some
grade based on the rubric given bellow. If you hardcode the output, you will get -200% for the assignment.
1. If a code does not compile, the code may get 0. However, some partial credit maybe awarded. A code having
compiler error cannot get more than 35% even most of the codes are correct.
2. Passing test cases (exact output format): 50%
3. Fulfilling the O(n) requirements for sorted cases (if passed test cases): 21%
4. Fulfilling requirements for unsorted cases (if passed test cases): 21%
a. O(n) can get full credit 21/21
b. O(n log n) can get 16 out of 21
c. O(n^2) gets points only for passing test cases (rubric#2 above)
5. Analysis file with correct content: 8 pts
Penalty:
6. Note that there can be penalty if you don’t fulfill the function requirement: -8%
7. Not putting header comment: -10%
8. Poor indentation in code and spacing in code: -10%
9. Not putting proper comments on important block of code: -5% (don’t start commenting every line. Only important
block of code)
10. If you use file i/o (if you do not read from standard input): -100%
Some hints:
Remember we have used two trackers for SLMP?
Good Luck!
COP 3503C Programming Assignment 2 BackTracking
What should you submit?
Write all the code in a single Main.java file and Lastname_analysis.txt. The analysis file will briefly discuss the time
complexity of your code.
Please include the following commented lines in the beginning of your code to declare your authorship of the code:
/* COP 3503C Assignment 2
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules
mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students for explaining any
part of the code in order to better assess your authorship and for further clarification if needed.
Caution!!!
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a
violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who
shared/posted it. Also, getting a part of code from anywhere will be considered as cheating.
Deadline:
See the deadline in webcourses. After that the assignment submission will be locked. An assignment submitted by email
will not be graded and such emails will not be replied according to the course policy.
What to do if you need clarification on the problem?
I will create a discussion thread in webcourses and I highly encourage you to ask your question in the discussion board.
Maybe many students might have same question like you. Also, other students can reply and you might get your answer
faster. Also, you can write an email to the TAs and put the course teacher in the cc for clarification on the requirements.
How to get help if you are stuck?
According to the course policy, all the helps should be taken during office hours. Occasionally, we might reply in email.
Problem: Our Word Finder
Given a MxN matrix of characters and a string word, your task will be to find the word in the given matrix. The rule is:
1. The word can be formed in any direction such as:
a. Left to right
b. Right to left
c. Left to right diagonal
d. Right to left diagonal
e. Any combination above
f. Same letter cannot be re-used to form the word
g. Must follow any one of the above directions and their combination while forming the word.
Example:
Consider the following 3X4 matrix.
C B A B
B N O D
M D E E
Let us try to find the following words:
“ABC” is available in the matrix:
C B A B
B N O D
M D E E
BAOED is available in the matrix:
C B A B
B N O D
M D E E
CNE is available in the matrix:
C B A B
B N O D
M D E E
NEC is not available in the matrix
Need is available in the matrix:
C B A B
B N O D
M D E E
NEEDON is not available in the matrix.
Input Format (Your code must read from standard inptut (no file I/o is allowed))
The first line of the input consists of 3 integers, M, N, and S. Here M = number of rows in the matrix, N = number of columns
in the matrix, and S = number of words you need to find from this matrix.
Then M lines represent the rows input characters, where each line has N characters separated by space.
After M lines, there will be S lines of words. You need to find these words in the matrix.
Similarly, K test cases will be provided in the above format.
Sample input1:
3 4 6
C B A B
B N O D
M D E E
ABC
BAOED
CNE
NEC
NEED
NEEDON
Output Format (Your must use standard console output to display your result)
Please get an idea of the output format from the following output for the above input. Also, you can probably find the
same word on the different places in the matrix. However, your target should be identifying the exact one we are looking
for.
To identify this, try to see the patterns based on the test cases from the codegrade and update your code to go the
those particular directions first and match the test cases.
Sample output1 for input 1
Looking for ABC
[C, B, A, ]
[ , , , ]
[ , , , ]
Looking for BAOED
[ , B, A, ]
[ , , O, ]
[ , D, E, ]
Looking for CNE
[C, , , ]
[ , N, , ]
[ , , E, ]
Looking for NEC
NEC not found!
Looking for NEED
[ , , , ]
[ , N, , D]
[ , , E, E]
Looking for NEEDON
NEEDON not found!
Sample input2:
4 4 4
c o m p
a m a p
a p s s
x y z q
mop
comp
omo
maa
Sample output2
Looking for mop
mop not found!
Looking for comp
[c, o, m, p]
[ , , , ]
[ , , , ]
[ , , , ]
Looking for omo
omo not found!
Looking for maa
[ , , , ]
[a, m, , ]
[a, , , ]
[ , , , ]
Specific Restrictions:
Your code must incorporate the following restrictions to receive full credit:
1. You must use backtracking strategy to solve this problem
Submission:
Submit the following files in Codegrade. Make sure your code work in Codegrade platform.
1. Main.java file with the code
2. Lastname_analysis.txt file: This file will very briefly explain the time complexity of your code
Rubric (subject to change):
According to the Syllabus, the code will be compiled and tested in Codegrade Platform for grading. If your code does not
compile in Codegrade, we conclude that your code is not compiling and it will be graded accordingly. We will apply a set
of test cases to check whether your code can produce the expected output or not. Failing each test case will reduce some
grade based on the rubric given bellow. If you hardcode the output, you will get -200% for the assignment.
1. If a code does not compile, the code may get 0. However, some partial credit maybe awarded. A code having
compiler error cannot get more than 35% even most of the codes are correct
2. Coding and applying backtracking strategies: 35%
3. Passing test cases (exact output format): 55%
4. Reading data from file properly: 5%
5. Analysis file with correct content: 5%
Penalty:
6. Not using backtracking: -60%
7. Not putting header comment: -10%
8. Poor indentation in code and spacing in code: -10%
9. Not putting proper comments on important block of code: -5% (don’t start commenting every line. Only important
block of code)
10. Using file i/o would result in penalty : -100%
Some hints:
– Have a wrapper function like we have seen for the maze problem.
– From the wrapper function, call the back tracking worker function for each box in the matrix until you
find a solution or you decide there is no solution. Unlike the maze problem, we don’t know the starting
point of our search. So, we try each box as a starting point.
Good Luck!
COP 3503C Programming Assignment 3 Disjoint Set
What should you submit?
Write all the code in a single Main.java file and submit it. Also submit Lastname_testStrategy.txt. The testing strategy
file will briefly discuss how you have tested your code to make sure your code is really able to solve the problem. Submit
your Main.java and the test strategy file to Codegrade platform.
Please include the following commented lines in the beginning of your code to declare your authorship of the code:
/*
Summer 24
COP 3503C Assignment 3
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules
mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students for explaining any
part of the code in order to better assess your authorship and for further clarification if needed.
Caution!!!
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a
violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who
shared/posted it. Also, getting a part of code from anywhere will be considered as cheating.
Deadline:
See the deadline in webcourses. An assignment submitted by email will not be graded and such emails will not be replied
according to the course policy.
What to do if you need clarification on the problem?
I will create a discussion thread in webcourses and I highly encourage you to ask your question in the discussion board.
Maybe many students might have same question like you. Also, other students can reply and you might get your answer
faster. Also, you can write an email to the TAs and put the course teacher in the cc for clarification on the requirements.
How to get help if you are stuck?
According to the course policy, all the helps should be taken during office hours. Occasionally, we might reply in email.
Problem Description: Destroy the connections
You have vowed to defeat your sworn enemy, but warfare in the 21st century isn’t fought with guns. Knowledge is power,
and knowledge is disseminated through computer networks. Thus, to defeat your sworn enemy, you plan on cutting the
wired connections between pairs of computers to reduce the overall connectivity of your enemy’s network.
We can model a computer network as pairs of connections between computers, also known as an undirected graph. We
can define the connectivity of a network as the sum of the sizes squared of each of the separate components of this graph.
For the example graph shown below, the current connectivity equals 22
+ 62
+ 12
= 41.
If you were to destroy the connection between computers F and G, then the new network would look like this
and its connectivity would only be 22
+ 32
+ 32
+ 12
= 23.
The Problem:
Given a network of n computers, a set of the pairs of computers that are initially connected, and a sequence of steps
where connections are destroyed, one by one, calculate the connectivity (as defined in the problem specification above)
after each connection is destroyed.
The Input (must be read from standard input (no file i/o. use of file i/o will fail all the test cases and you will get zero)):
The first line of input contains three space separated integers, n (1 ≤ n ≤ 105
), m (1 ≤ m ≤ 3×105
), and d (1 ≤ d ≤ m),
representing the number of computers in the enemy network, the number of connections between pairs of computers in
the enemy network, and the number of those connections which you will destroy, respectively. The computers are
numbered 1 through n, inclusive, and the connections are numbered 1 through m respectively.
The following m lines will each contain a pair of distinct integers, u and v (1 ≤ u, v ≤ n, u ≠ v), representing that computers
u and v are connected, initially. (Note: we denote the first of these lines as connection 1, the second as connection 2, and
so forth.)
It is guaranteed that each of the pairs listed will be unique pairs; namely, the same two values of u and v will
never appear on two different lines as separate connections. (Of course, many individual computers will be connected to
more than one other computer, so a particular value u may appear on more than one of these m lines.)
The following d lines will each contain a unique integer in between 1 and m, inclusive, representing a connection number
that gets destroyed. These will appear in the order that they get destroyed.
The Output (standard console output):
Output d+1 lines of output. The first line should be the initial connectivity of the network. The following d lines should
have the connectivity of the network after each connection is destroy, one by one.
Sample Input Sample Output
9 8 2
1 5
2 3
2 6
3 6
6 7
7 8
7 9
8 9
5 //it means 5th connection from the above list
3
41
23
23
3 3 3
1 2
1 3
2 3
3
1
2
9
9
5
3
Implementation Requirements
This assignment is testing the use of the disjoint set data structure. You must use a disjoint set to solve the problem even
though other ways exist. You will have to modify the disjoint set shown in class to solve the given problem. The point of
the assignment is to see if you can figure out how to do that modification on your own.
As always, your code should use good style, including but not limited to: a header comment, reasonable number of internal
comments, good modular break down, good variable names, and utilizing objects and the Java API as appropriate for
solving the problem,
What To Submit
For this assignment, please submit a single Java program named Main.java and Lastname_testStrategy.txt with
brief explanation of your testing strategy
Hints:
1. The code will not be that straightforward, so you need to plan
2. Draw the sample input first and then see how the output numbers are calculated
3. You can use our existing disjoint set code and update it (make sure to use path compression and union by rank
approach. Otherwise, your code may fail larger grading test cases due to optimization issue).
4. The union part of the cycle detection concept we have learned in the class could be useful
5. We mainly use the find and union operations of disjoint sets. As there is not an easy way to break a set when you
remove an edge, it would be best idea not to think in that direction
6. Instead, generate the result bottom up.
a. Make sets based on number of nodes
b. Store all the edges in your data structure (maybe a class or 2d array). Maintaining status (exist/not exist)
for each edge might be useful
i. Don’t use UNION operation during this process. If you do, you will get stuck as you will not be
able to easily remove them
c. Keep the list of index of the edges you are deleting and maintain proper edge status
d. Also, have an array to store the result for each deletion
e. For each deletion index, perform UNION and calculate result
f. In this way, you will generate your result array and just print it
7. Also note that during this process, you will need to maintain the size of a set at the root of each set.
8. Of-course I did not give you the exact details and steps for the solution. However, the above keywords and logics
should help you to think in the proper direction.
Good Luck!
COP 3503C Programming Assignment 4 BFS
What should you submit?
Write all the code in a single Main.java file. Submit your Main.java file.
Please include the following commented lines in the beginning of your code to declare your authorship of the code:
/* COP 3503C Assignment 4
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules
mentioned in syllabus, are also applied in this submission.
The TA and Instructor can call any students for explaining any
part of the code in order to better assess your authorship and for further clarification if needed.
Caution!!!
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a
violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who
shared/posted it. Also, getting a part of code from anywhere will be considered as cheating.
Deadline:
See the deadline in Mimir. The assignment will accept late submission up to 24 hours after the due date time with 10%
penalty. After that the assignment submission will be locked. An assignment submitted by email will not be graded and
such emails will not be replied according to the course policy.
What to do if you need clarification on the problem?
I will create a discussion thread in webcourses and I highly encourage you to ask your question in the discussion board.
Maybe many students might have same question like you. Also, other students can reply and you might get your answer
faster. Also, you can write an email to the TAs and put the course teacher in the cc for clarification on the requirements.
How to get help if you are stuck?
According to the course policy, all the helps should be taken during office hours. Occasionally, we might reply in email.
Problem Description: Tricky Maze
Your friend Gustavo is hopelessly lost in a maze, and you would like to help him get out. Luckily, his cell phone
is fully charged, and you can call him and give him directions to follow. He’s spent so much time lost in the maze,
he insists that you get him out as fast as possible.
The maze can be modeled by a two-dimensional grid with r rows and c columns. Gustavo’s location is labeled
with the character ‘*’ and the one location that allows for escape out of the maze is labeled with the character ‘$’.
In most circumstances, Gustavo can move to the left or right by one square on a single row, or move one square
up or down in a single column. However, there are some exceptions to this rule. Some squares in the grid are
forbidden.
These are marked with the character ‘!’. Other squares are teleportation squares. Each of these are
marked with a capital letter. If Gustavo is on a square with a letter, say ‘A’, he can teleport, in one move, to all
other squares labeled with the letter ‘A’. Same goes for all of the other capital letters. Note that from a
teleportation square, one can always choose not to use the teleportation feature and can still move left, right,
up or down by one square.
Thus, one can travel from a square labeled ‘A’ to an adjacent square labeled ‘B’,
or an adjacent square labeled ‘.’.
The Problem:
Given the size and contents of the maze, figure out the fewest number of moves Gustavo needs to make to get
out of the maze.
The Input (must be standard input (no file i/o)):
The first line of input contains two space separated integers, r (2 ≤ r ≤ 1000) and c (2 ≤ c ≤ 1000), representing
the number of rows and number of columns in the grid, respectively.
The following r lines contain c characters each. The ith line of these lines contains the contents of the ith row of
the grid, from left to right.
It is guaranteed that exactly one of the grid characters will be ‘*’ and exactly one of the grid characters will be
‘$’. All grid characters that represent regular squares will be labeled with the character ‘.’. All forbidden squares
will be represented with the grid character ‘!’.
All other squares will be capital letters, representing various
teleportation squares. If a letter appears in the grid, then it will appear in at least two separate grid squares.
Partial Credit Input Restrictions:
In some of the input cases (enough to allow a maximum score of 70%), no teleportation squares will exist.
In some of the input cases (enough to allow a maximum score of 90%), no letter will appear in the grid more
than 10 times.
In the last set of input cases worth 10% of the grade (to raise your grade from 90% to 100% max), there are no
restrictions on the number of times an individual letter appears in the grid (beyond the size of the grid and the
other grid square requirements).
The Output (standard console output):
If Gustavo can get out of the maze, output a single integer representing the fewest number of moves it will take
him to get out. If he can’t get out, output “Stuck, we need help!”.
Restrictions:
You must have to use the BFS strategy in your solution.
Sample Input Sample Output
3 4
.$!*
.!!.
….
8
4 2
..
*!
!$
..
Stuck, we need help!
6 6
C..$B.
……
!!!!!!
….CB
.*.AAA
C.B.CB
4
What To Submit
For this assignment, please submit a single Java program named Main.java
Hints:
1. The BFS concept, code and then the ElevatorTrouble problem discussed in the class/recording would be your initial
starting point to think about the solution
2. Then the lab problem Knights jump should help you significantly.
3. Based on the above three concepts and codes, try to solve the problem for the first partial credit restriction.
4. Now, if you would like to enhance your code for 100% credit, consider storing all the locations for each letter in a
suitable data structure. During the BFS process, you can simply consider that all the locations of the same letters
are connected.
5. You may need some other logic and variables and list to decide whether you will enqueue the location of a letter or
not during the BFS process..
Good Luck!
COP 3503C Programming Assignment 5
What should you submit?
Write all the code in a single Main.java file. Submit your Main.java file to Codegrade. Also, submit 2 test files
(test_1.txt and test_2.txt) along with your test strategy test_strategy.txt .
In the test strategy, write your test
strategy and discuss about the two test files you have generated and what is the correct output for those test files.
Please include the following commented lines in the beginning of your code to declare your authorship of the code:
/* COP 3503C Assignment 5
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules
mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students for explaining any
part of the code in order to better assess your authorship and for further clarification if needed.
Caution!!!
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a
violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who
shared/posted it. Also, getting a part of code from anywhere will be considered as cheating.
Deadline:
See the deadline on webcoureses. After that the assignment submission will be locked. An assignment submitted by email
will not be graded and such emails will not be replied according to the course policy.
What to do if you need clarification on the problem?
I will create a discussion thread in webcourses and I highly encourage you to ask your question in the discussion board.
Maybe many students might have same question like you. Also, other students can reply and you might get your answer
faster. Also, you can write an email to the TAs and put the course teacher in the cc for clarification on the requirements.
How to get help if you are stuck?
According to the course policy, all the helps should be taken during office hours. Occasionally, we might reply in email.
Problem Description: Treasure Hunts
Monster land has n cities and one capital. The cities are numbered from 1 to n. Some of the cities are connected
by bidirectional roads and each road has a length. It is possible to go from a city to any other city by these roads.
Yeti Monster found an ancient book that has a secret information about the Monster land. The book said that the
land has some very precious treasures. Finding them will make the finder the king of the land. However, the exact
position of the treasures are kept secret.
Further reading the document, Yeti, found some clue. The clue says that
all the treasures are located exactly at a distance L from the capital. The capital is the Sth city in the city list.
As part of more details of the clue: A treasures can be located in a place and the place is either a city or at a point
on a road, if and only if the shortest distance from the place to the capital along the roads of the country equals
exactly L.
Yeti became impatience to know how many treasures are located in the Monster land so that Yeti can become the
king and rule that country. Yeti knows that you are a genius programmer, and you can help! So, help Yeti!
Input specification (Must be read from standard input (no file i/o))
The first line of input contains 3 space separated integers, C (2 ≤C≤105
), R (C-1 ≤ R≤ min(105
, n(n-1)/2), S (1 ≤
S ≤ N), representing the number of cities, number of roads, and the city number that represents the capital,
respectively.
Then the next R lines contain the descriptions of the roads. Each of them contains 3 space separated integers
vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 1 ≤ wi ≤ 1000), where vi, ui are numbers of the cities connected by this road and wi is its
length. The last input line contains integer L (0 ≤ l ≤ 109
) — the distance from the capital to the places where the treasures are
located.
It is guaranteed that:
• between any two cities no more than one road exists.
• each road connects two different cities;
• from each city there is at least one way to any other city by the roads.
The Output (standard output):
Print two numbers — the number of treasures in the cities and the number of treasures on the roads in Monster land.
Partial Credit Options and some hints:
If your code can produce output for the number of treasures in the cities properly, you can get 70% credit for
each test case. We have learned couple of graph algorithms.
You need to decide which algorithm is appropriate
to get this information. Also, make sure to test your code properly. The second number that shows the number
of treasures in the road could be a bit tricky to find.
So, carefully plan. That part will require a couple of if-else
conditions based on the source and destination of each edge, with the min distance available in the vertices of
the edge, the weight of the edge, and the value of L.
Sample Input Sample Output
4 6 1
1 2 1
1 3 5
2 3 1
2 4 1
3 4 1
1 4 2
2
In city: 2
On the road: 1
Explanation:
1 treasure is at city 3
1 treasure is at city 4,
1 treasure is on the road (1,3)
5 6 3
3 1 1
3 2 1
3 4 1
3 5 1
1 2 6
4 5 8
4
In city: 0
On the road: 3
Explanation:
1 treasure is on the road (1, 2)
1 treasure is on the road (4,5) at a
distance 3 from city 4 (towards city 5)
1 treasure is on the road (4,5) at a
distance 3 from city 5 (towards city 4)
Some Restrictions:
– You have to use a known algorithm we have learned in the class as part of this process and need to implement
that algorithm based on the lecture (see lecture note and watch the recording. We have discussed this code in the
class or recording).
– The function/method that implements the algorithm must be named based on the algorithm name
– The lecture version of the code has some extra lines to store and print the result. Your code should not contain
any of those extra lines as those lines are not relevant for this assignment.
What To Submit
See the first page of the assignment about what to submit.
Hints:
1. What algorithm you have learned to find the shortest paths to all the nodes from a single node?
2. Some hints are provided above in the partial credit options
3. Of-course draw the sample graph and see how the output is calculated from the sample graph.
Good Luck!
COP 3503C Programming Assignment 6
What should you submit?
Write all the code in a single Main.java file. Submit your Main.java file to Codegrade platform. Also, submit 2 test
files (test_1.txt and test_2.txt) along with your test strategy test_strategy.
In the test strategy, write your test
strategy and discuss about the two test files you have generated and what is the correct output for those test files.
Please include the following commented lines in the beginning of your code to declare your authorship of the code:
/* COP 3503C Assignment 6
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules
mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students for explaining any
part of the code in order to better assess your authorship and for further clarification if needed.
Caution!!!
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a
violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who
shared/posted it. Also, getting a part of code from anywhere will be considered as cheating.
Deadline:
See the deadline in Webcourses. NO LATE SUBMISSION FOR THIS ASSIGNMENT. An assignment submitted by email
will not be graded and such emails will not be replied according to the course policy.
What to do if you need clarification on the problem?
I will create a discussion thread in webcourses and I highly encourage you to ask your question in the discussion board.
Maybe many students might have same question like you. Also, other students can reply and you might get your answer
faster. Also, you can write an email to the TAs and put the course teacher in the cc for clarification on the requirements.
How to get help if you are stuck?
According to the course policy, all the helps should be taken during office hours. Occasionally, we might reply in email.
Problem Description: Team Building
An instructor teaches two CS2 sections (section 1 and section 2). He is thinking to short list a group of
students for an upcoming contest. As part of the process, n number of candidates from each section has solved
several programming problems.
On the day of the selection, 2n candidates have come to the venue for short listing. He asked the students to
stand in 2 rows of same size. Exactly n students from each section. The candidates are numbered from 1 to n on
each row from left to right.
1 2 3
…..
n
1 2 3
…..
n
Now the instructor will choose the candidates from the rows with the following rules:
1. Candidates should be chosen from left to right.
2. Index of each chosen candidate (excluding the first one taken) will be greater than the index of the
previously chosen candidate.
3. In order to avoid giving preference of a specific section, he will choose the candidates in such a way that
no consecutive chosen candidates belong to the same section (aka row).
4. The first student can be chosen from all 2n students without any constraints.
5. The final resulting group can have any number of candidates.
6. In order to make a perfect group of students, he will choose the students in such a way, that the total
number of problems solved by the students will be the maximum.
So, solve this problem to find the group of students that will maximize the problems solved with all the given
constraints.
Input specification (Must be read from standard input (no file i/o))
The first line of the input contains a single integer n (1≤n≤100000) that represents the number of students in each
row.
The second line of the input contains n integers p1,1,p1,2,…,p1,n,(1≤p1,i≤109), where p1,i is the number of problems
solved by the ith student in the first row.
The third line of the input contains n integers p2,1,p2,2,…,p2,n,(1≤p2,i≤109), where p2,i is the number of problems
solved by the ith student in the second row.
The Output (standard console output):
Print one number — the maximum possible total problem solved by the selected group of students.
Sample Input Sample Output Explanation
5
9 3 5 7 3
5 8 1 4 5
29 The chosen candidates can be these:
3
1 2 9
10 1 1
19
1
7
4
7
Some Restrictions:
– You must have to use Dynamic Programming with bottom up tabulation approach to solve this problem
– The run-time has to be linear O(n)
Hints:
– The code will be very small but require some good understanding of bottom-up tabulation approach of dynamic
programming. So far, we have seen Fibonacci, 0/1 knapsack, LCS, MCM, and some other examples.
These all
should give you some ideas on dynamic programming approaches.
– As you now know dynamic programming, don’t start thinking on brute force approach.
o Have a 2D table based on n and number of rows
o Initialize the first index of row 0 and row 1
o Start updating index 1, row 0 and then then update index 1 or row 1, keep reading the hints to understand how
to decide the numbers for the update.
o Remember, your target is to maximize the total.
o So, while updating an index of row 0 of the table, it should be based on some max of last calculations, and new
calculations. Also note that, an update of row 0 in the table might need information from row 1. Same for row 1.
o You will generally no need to access information other than the previous index and the candiate list’s current
index
o Finally, your final answer will be located in the last index of row 0 or row 1 of the table.
What To Submit
See the first page of the assignment about what to submit.
Good Luck!
