Description
CMSC 401 Assignment 1 Inversion Vector
• Your task is to design and implement an algorithm to convert
permutation inversion vector W into the corresponding
permutation A
• For a permutation A of numbers 1..N:
– Inversion vector W of length N has j
th element W[j] defined as:
– W[j] = number of elements in A[1.. j-1] that are larger than A[j]
– 0<=W[j]<=j-1
• To obtain permutation A from permutation inversion vector W
of length N
– Read W from end, fill A from the end with unused elements from
1..N
• Ex: with N=5, W=[0,1,1,1,2] => A=[5,1,2,4,3]
• See also Lecture 04, slides 28-32.
Input-output formats
• Take integers from standard input (System.in):
– Line 1: single integer specifying N: number of
elements in permutation (1<=N<=1000) (N =
length of W = length of A)
– Lines 2 to N+1: line j contains an integer that
goes into W[j-1]
• print permutation A corresponding to the
input inversion vector W to standard output
(System.out), with each integer on a separate line
• As always, do not print any text or blank lines to standard output except the integers
-Example:
-Input:
5
0
1
1
1
2
-Correct Output:
5
1
2
4
3
Submission
• Date due: Thursday, Sept 22th, 11:59 pm
• Upload through Blackboard
– Your submission should be a zip archive
1_FamilyName_FirstName.zip containing
• Java source code in a file cmsc401.java (all low case
letters!)
– The file should have your name in a comment in the first line
– Remember: in Java, class name should match the file name, and
is case sensitive
• Please do NOT use packages
• Do NOT place the file into a folder – just zip the file
CMSC 401 Assignment 2 Optimal Power Line Location
• Power distribution company is planning a main power line from east
to west (x-axis) across its distribution area
• The area has n houses
• The company wants to connect each house directly to the main
power line with smaller power lines in north-south direction (y-axis)
• Your task is to estimate the optimal position (on the y-axis) of the
main power line, so that the total length of smaller power lines is
the shortest.
Assignment 2
Write a program cmsc401.java that
• takes as input
– in the first line, the number of houses n, n>=2, n<1,000,000
– in each consecutive line (from 2nd to (n+1)-th line), the y- coordinate of one house (integers in the range 0 to
1,000,000,000)
• returns as output
– a single number: the y-coordinate where the main power line should be built
– only one number, no comments, prompts etc.
• Use standard I/O to read input (System.in, System.out) and
write the result
• Make sure the program compiles
Example
Input
6
1
8
3
6
2
7
9/27/16 4
y=2
y=3
y=8 y=7
y=1
y=6
y=5
Output
5
Total length of smaller power lines: 15
This is the minimum possible length.
There might be other results with the same minimum
Hints
• Think about the solution over examples
• Consider the y-coordinates of houses as an array of size n
• Design a divide & conquer algorithm like
quicksort
– Use recursive approach with an appropriate Partition- like method
• Try to use the asymptotically fastest method
– Aim at expected linear time O(n)
– Slower methods will get lower score even it is correct
• There may be several correct solutions, return one
of them.
Submission
• Date due: Tuesday, Oct 11th, 11:59 pm
• Upload through Blackboard
– Your submission should be a zip archive
2_FamilyName_FirstName.zip containing
• Java source code in a file cmsc401.java (all low case
letters!)
– The file should have your name in a comment in the first line
– Remember: in Java, class name should match the file name, and
is case sensitive
• Please do NOT create your own packages
• Do NOT place the file into a folder – just zip the file
CMSC 401 Assignment 3 Word Mining
• Assume that you are given a huge file consisting of
billions of emails
• You are asked to point some of the words in this file
by providing the whole sentence that contains these
words
• Assume that you already found out the start and end
positions of the sentences
– A sorted array S[] of numbers indicating positions from the
start of the text
– First letter is at index 1
• Assume that you also parsed the collection and found
the positions of the first letter of the words
– A sorted array of W[] of numbers that contain the positions
Assignment 3
• Your task is, given S[] and W[],
– Find starting and ending position of each sentence that
contains the word of interest
– Design a quick algorithm using one of the data structures
you learned. Assume size N of S[] is much greater than
size M of W[].
• You should not just go through S[] in a loop to find the
sentences, as it will be O(N). It will be slow for huge data even it is linear.
• Hint: A balanced Binary Search Tree can do searches in
O(log(N)).
But
– how to insert data to make the tree balanced?
– how to modify search to get the answer after tree is
constructed?
Assignment 3
Write a program cmsc401.java that
• takes as input
– Line 1: single integer N>=1, size of array S[]
– Line 2: single integer M>=1, size of array W[]
– Lines 3..(N+2): N positive integers in array S[]
indicating the ends of sentences
– Lines (N+3)…(N+M+2): M positive integers in
array W[], positions of the words searched
• returns as output
– Line 1: number of sentences that contain the
words searched
– Following lines: two integers: i) start and end
of the sentence that contains the word
• end: (previous sentence end)+1
-Input:
3
2
25
33
74
19
40
Output:
2
1 25
34 74
The example corresponds to the word ”output” and the text:
No human-oriented output. Please. Such output creates problems in grading.
Submission
• Date due: Tuesday, Nov 15th, 11:59 pm
• Upload through Blackboard
– Your submission should be a zip archive
3_FamilyName_FirstName.zip containing
• Java source code in a file cmsc401.java (all low case letters!)
– The file should have your name in a comment in the first line
– If you use multiple files, the main file must be cmsc401.java
– Remember: in Java, class name should match the file name, and
is case sensitive
• Please do NOT create your own packages
• Do NOT place the file into a folder – just zip the file
• Use standard I/O to read input (System.in, System.out) and output
• Make sure the program compiles
• Do not use any library for BST, create your own.
CMSC 401 Assignment 4 Road Trip
• You are planning to drive from Richmond to L.A.
• You want to spend as little as possible on the gas and motels.
• So you need to pick the best route – with
cheapest motels and smallest cost of gas
• You have done your research and you know:
– cost of an overnight stay in the cheapest motel in
each of the cities on the possible routes
– cost of driving between cities without overnight stays
• Now you need to write a program that will take all
that data, and find the cheapest route
– The route with lowest sum of motel and gas costs
Assignment 4
• Write a program cmsc401.java that reads the database of
gas & motel costs, which is in the format below:
5
7
3 78
4 87
5 98
1 4 98
5 4 45
1 5 140
4 3 87
2 5 150
3 5 109
3 2 73
– The number of cities, N, in the first line. N>=3, N<=1000
– The total number of direct highways between cities, M, in the
second line. M>=2, M<=10000
– Lowest motel price for each of N-2 cities (excluding L.A. and
Richmond), each as a single line of two numbers: city number
(3…N), motel cost (1…200)
– Gas prices for traveling direct highways between two cities,
each as a single line of three numbers: city number (1…N), city
number (1…N), cost of gas for travel between the two cities
(1…200)
– Richmond is city number 1, L.A. is city number 2
– Cost shouldn’t include a motel in Richmond, not in L.A.
Example
Input in correct format
Correct output
388
Green shows the cheapest route from city 1
(Richmond) to city 2 (L.A). Cost is $388:
$140+$150 for gas + $98 for motel
5
7
3 78
4 87
5 98
1 4 98
5 4 45
1 5 140
4 3 87
2 5 150
3 5 109
3 2 73
Remarks
• There will always be at least one way of getting
from city 1 to city 2
• If a cost for gas from city A to B is in the input,
cost for gas from B to A is the same and will not
be in the input
• No other text, comments, questions on output
Submission
• Date due: Thursday, Dec 1st, 11:59 pm
• Upload through Blackboard
– Your submission should be a zip archive
4_FamilyName_FirstName.zip containing
• Java source code in a file cmsc401.java (all low case letters!)
– The file should have your name in a comment in the first line
– If you use multiple files, the main file must be cmsc401.java
– Remember: in Java, class name should match the file name, and
is case sensitive
• Please do NOT create your own packages
• Do NOT place the file into a folder – just zip the file
• Use standard I/O to read input (System.in, System.out) and output
• Make sure the program compiles
