CSC 310 Lab 6, Spring 2016

LEBANESE AMERICAN UNIVERSITY School of Arts and Science Department of Computer Science and Mathematics CSC 310: Algorithms and Data Structures Lab VI 26. Feb. 2016 Problem 1 Given an array of integers, sort it using the bucket sort algorithm. Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be added to the array. Output For each test case, print the sorted array. Sample Input Sample Output 7 25 13 10 30 15 27 37 4 7 6 8 9 6 10 7 15 13 4 6 10 13 15 25 27 30 37 6 7 8 9 4 6 7 10 13 15 Problem 2 Given an array of integers, sort it using the radix sort algorithm. Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be added to the array. Output For each test case, print the sorted array. Sample Input Sample Output 7 25 13 10 30 15 27 37 4 7 6 8 9 6 10 7 15 13 4 6 10 13 15 25 27 30 37 6 7 8 9 4 6 7 10 13 15 Problem 3 Given an array of integers, sort it using the counting sort algorithm. Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be added to the array. Output For each test case, print the sorted array. Sample Input Sample Output 7 25 13 10 30 15 27 37 4 7 6 8 9 6 10 7 15 13 4 6 10 13 15 25 27 30 37 6 7 8 9 4 6 7 10 13 15 Problem 4 Given an array containing both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum. For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6}, then the maximum subarray sum is 7 (see highlighted elements). Note: your solution should be in O(n log n) Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be added to the array. Output For each test case, print the maximum subarray sum. Sample Input Sample Output 8 -2 -5 6 -2 -3 1 5 -6 9 -2 1 -3 4 -1 2 1 -5 4 7 6 Problem 5 Given an array of 1s and 0s where all 1s precede all 0s, find the number of 0s. Note: your solution should be in O(log n) Input Your program will be tested against multiple test cases. Each test case is made up of two lines. The first line contains an integer N representing the number of integers. The second line has N integers to be added to the array. Output For each test case, print the number of 0s. Sample Input Sample Output 6 1 1 1 1 0 0 5 1 0 0 0 0 2 4