CSC 310 Lab 10, Spring 2016

LEBANESE AMERICAN UNIVERSITY School of Arts and Science Department of Computer Science and Mathematics CSC 310: Algorithms and Data Structures Lab X 14. Apr. 2016 Problem 1 Given two sequences of characters, you are required to find the length of the longest common subsequence present in both of them. Input Your program will be tested against multiple test cases. Each test case is composed of two strings S1 and S2 representing the sequences. Output For each test case, print the length of the longest common subsequence. Sample Input Sample Output ABCD BACD AGCAT GAC XMJYAUZ MZJAWXU 3 2 4 Problem 2 On a positive integer, you can perform anyone of the following three steps: 1. Subtract 1 from it. (n = n – 1) 2. If it is divisible by 2, divide it by 2. (if n%2 = 0, then n = n/2) 3. If it is divisible by 3, divide it by 3. (if n%3 = 0, then n = n/3) Given a positive integer n, find the minimum number of steps that take n to 1. For example, if n = 7, it takes 3 steps for it to become 1. 7 – 1 = 6 6 / 3 = 2 2 / 2 = 1 Input Your program will be tested against multiple test cases. Each test case is made up of a single integer n. Output For each test case, print the minimum number of steps needed to take n to 1. Sample Input Sample Output 5 8 9 3 3 2 Problem 3 Given a numerical triangle, you are required to find the maximum total of the sum of numbers from the top to the bottom of the triangle. From each number in the triangle, you can only add to it the number directly below it or the number to the right of the number below it. For example, given the following numerical triangle, 3 7 4 2 4 6 6 5 9 3 The maximum total from top to bottom is 3 + 7 + 4 + 9 = 23. Input Your program will be tested against multiple test cases. Each test case begins with an integer n representing the number of rows in the triangle. The next n lines contain the numbers on each row. Output For each test case, print the maximum total. Sample Input 4 3 7 4 2 4 6 6 5 9 3 3 2 8 4 1 7 3 Sample Output 23 17 Problem 4 Given a sequence of integers S = a1 a2 … an , you are required to find a subsequence of S such that the integers in the subsequence are in increasing order, and the length of the subsequence is maximized. Input Your program will be tested against multiple test cases. Each test case begins with an integer n representing the length of the sequence. The next line contains n integers representing the elements in the sequence. Output For each test case, print the length of the longest increasing subsequence. Sample Input 5 1 2 4 0 3 7 9 10 3 8 6 12 13 16 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 Sample Output 3 4 6