CSC 310 Lab 9, Spring 2016

LEBANESE AMERICAN UNIVERSITY School of Arts and Science Department of Computer Science and Mathematics CSC 310: Algorithms and Data Structures Lab IX 07. 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 Given an undirected graph G and an integer k, you should determine whether G is k-colorable or not. Input Your program will be tested against multiple test cases. Each test case begins with three integers n, e, and k representing the number of vertices, edges, and colors respectively. The next e lines represent the vertices that are connected by an edge. Output For each test case, print “yes” if G is k-colorable; else print “no”. Sample Input Sample Output 10 15 3 0 1 0 4 0 5 1 2 1 6 2 3 2 7 3 4 3 8 4 9 5 7 5 8 6 8 6 9 7 9 5 10 4 0 1 0 2 0 3 0 4 1 2 1 3 1 4 2 3 2 4 3 4 yes no Problem 3 A magic square is an arrangement of numbers (integers in our case) in a square grid, where the numbers in each row, each column and the numbers in the forward and backward main diagonals, all sum up to the same number. You have been given an incomplete magic square (with a size from 3 to 5). With your coding skills, you must finish the square. It must be a normal magic square and contain integers from 1 to n2 without repeating. Input Your program will be tested against multiple test cases. Each test case begins with an integer n representing the size of the square. The next n lines will each contain n integers representing the numbers in the square. A value of zero indicates an empty cell that needs to be filled up. Output For each test case, print the square after filling it up. Sample Input Sample Output 3 0 7 0 9 0 1 4 3 0 4 1 15 14 4 12 0 0 9 8 0 0 5 13 3 2 16 2 7 6 9 5 1 4 3 8 1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16 Problem 4 Given two integers n and k, you are required to enumerate all binary strings of length n that have exactly k ones. Input Your program will be tested against multiple test cases. Each test case is composed of two integers n and k, representing the length of the string and the number of ones. Output For each test case, print the enumerations. Sample Input Sample Output 3 1 3 2 001 010 100 011 101 110 Problem 5 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 Sample Output 23 17 7 4 2 4 6 6 5 9 3 3 2 8 4 1 7 3