Description
use python to solve
Unformatted Attachment Preview
Northeastern University
CS5800 Algorithms, Spring 2024
Instructor: Hyonho Lee
Assignment 6
(Total Marks: 50 pts)
Due Date: March 25, 2024, 6pm
Name:
Student Number:
Collaborators:
I,
, read and understood Northeastern University’s Academic Integrity Policy (https://osccr.sites.northeastern.edu/academic-integrity-policy/).
1. (20 pts) (Longest palindrome subsequence -Problem 14-2)
A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Write a Python function, longestPalindromeSubsequence(str), which returns a longest
palindrome subsequence of an input string str.
def longestPalindromeSubsequence(str):
## Write Your Code Here ##
longestPalindromeSubsequence(“banana”)
# This should return “anana”
longestPalindromeSubsequence(“character”) # This should return “carac”
1
2. (30 pts) (Printing neatly – Problem 14-4)
Consider the problem of neatly printing a paragraph with a monospaced font (all characters
having the same width). The input, text, is a string consisting of n words separated by a space.
Word lengths are l1 , l2 , …, ln measured in characters, which are to be printed neatly on a number
of lines that hold a maximum of max characters each. No word exceeds the line length, so that
li ≤ max for i = 1, 2, …, n.
The criterion of “neatness” is as follows. If a given line contains words i through j, where i ≤ j,
and exactly one space appears between
words, then the number of extra space characters at the
P
end of the line is max − j + i − jk=i lk , which must be nonnegative so that the words fit on the
line. The goal is to minimize the sum, over all lines except the last, of the cubes of the numbers
of extra space characters at the ends of lines.
Write a Python function, printNeatly(text, max), which neatly prints a given text. Treat
any punctuation mark as a part of a word. For example, I’m a student. consists of 3 words with
lengths 3 (I’m), 1 (a) and 8 (students.). Assume that the value of max is always greater than or
equal to the maximum length of a word in text.
def printNeatly(text, max):
## Write Your Code Here ##
printNeatly(“Dynamic programming is not that difficult.”, 15)
# The above should print 4 lines as below:
#
# Dynamic
# programming
# is not that
# difficult.
printNeatly(“Algorithm is my favorite subject.”, 16)
# The above should print 3 lines as below:
#
# Algorithm is
# my favorite
# subject.
2
Practice Exercises
(The following questions will not be graded. Do not submit solutions. But similar questions
may appear in the exams.)
Exercise 14.1-2 (15.1-2 of the 3rd Ed.)
Exercise 14.1-3 (15.1-3 of the 3rd Ed.)
Exercise 14.2-1 (15.2-1 of the 3rd Ed.)
Exercise 14.3-2 (15.3-2 of the 3rd Ed.)
Exercise 14.3-5 (15.3-5 of the 3rd Ed.)
Exercise 14.4-5 (15.4-5 of the 3rd Ed.)
Exercise 14.4-6 (15.4-6 of the 3rd Ed.)
Problem 14-1 (15-1 of the 3rd Ed.) (Longest simple path in a directed acyclic graph)
Problem 14-5 (15-5 of the 3rd Ed.) (Edit distance)
Problem 14-6 (15-6 of the 3rd Ed.) (Planning a company party )
3
Purchase answer to see full
attachment
