ADSA

Homework 1

Google Colab and Python

• Watch how to use Google Colab
• Practice Python3 - notebook and watch lecture
• If you are new to Python, I suggest practicing Python at online platforms such as codewars.org
• If you fear learning new things (including Python), I also suggest that you watch this world’s most popular online course.

Learn to plot functions

• Using free online tools such as Desmos

Read sections 3.1 and 3.2 from CLRS

Please read this with the goal of using the knowledge to do the homework below.

Watch the recorded lectures

• Introduction
• Review insertion sort
• Review merge sort
• Analysis of insertion sort and merge sort
• Asymptotic notations

Question 1

Reorder the following terms from lowest to highest time complexity, using < between terms. If two terms have the same complexity, use an equal sign instead. Assume n>1 and k is a constant.

• O(n²)
• O(kn)
• O(1)
• O(100000 * n)
• O(n!)
• O(lg n)
  • lg is log₂
• O(2n)
• O(n)
• O(k lg n)
• O(n¹⁰⁰⁰⁰⁰)
• O(n * lg n)

Question 2 (CLRS 3.1-3)

• Explain why the statement, “The running time of algorithm A is at least O(n²),” is meaningless.

Question 3 (CLRS 3.1-4)

• Is 2ⁿ⁺¹ = O(2ⁿ)? Explain.
• Is 2²ⁿ = O(2ⁿ)? Explain.

Question 4 (From CLRS 3-3(a))

Rank the following functions by order of growth and describe how you obtained the ranking; i.e. find an arrangement g₁, g₂, …, g_N of the functions satisfying g₁ = Ω(g₂), g₂ = Ω(g₃), …, g_n-1 = Ω(g_N). Also discuss which of the functions are equivalent (by reducing whichever ones can be reduced). Hint: Besides the mathematical analysis, two additional techniques that you MAY use to determine the growth are: (a) plotting the functions, and (b) timing the execution of the functions as shown here.

Help:

• https://atekihcan.github.io/CLRS/P03-03/
• https://atekihcan.github.io/CLRS/E03.01-04/