CSCI 3104: Algorithms
Homework 1
1. Algorithms are designed to solve certain computation tasks that are specified by the
expected input and output. For each of the following problems, how would you specify
its input and output? (a) driving direction; (b) course scheduling; (c) Google web
search engine; (d) Amazon item recommendation; (e) Fedex shipment scheduling.
2. Find an online recipe for one of your favorite dishes. Provide the URL and a copy
of the recipe. Are the instructions precise and unambiguous as algorithms? Briefly
explain why.
3. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both
(in which case f = Θ(g)). Briefly explain why.
(a) f(n) = 32n
7 + 48n
3
g(n) = 50n
5 + 40n
4 + 100
(b) f(n) = log(8n
2
) g(n) = log(n
3
)
(c) f(n) = 3n/7 + n
3
g(n) = n
5
log n
(d) f(n) = ( 5
3
)
n
g(n) = 8n
8 + 63 log n
(e) f(n) = (n − 1)! g(n) = n!
4. Write a python program that (1) takes one argument n as input, (2) generates n
random integers in the range of [0, 10n] and sorts the n integers in ascending order
using the selection sort algorithm introduced in Lecture 1, and (3) repeats step (2) for
10 times and prints out the running time (min, max, and average) across the 10 rounds
of sorting.
Name your python code as LastName FirstName HW1.py and submit electronically at moodle. In addition, test your code with n = 103
, 104
, 105
, 106 and report
the running time for each n value. If the program takes too long to run for bigger n,
you do not have to finish it and report the actual running time. Instead, include a
statement estimating the running time based on the running time for smaller n values
and the big-O time complexity analysis. Provide your answers along with your source
code, and specify the type of machine you used for testing (CPU, memory size, OS).
