Exercises
1) Compare between applying Euclid’s algorithm and Middle-school algorithm
for computing gcd(125, 75). Show all steps until you find the answer.
Which algorithm of them performs faster?
2) List 5 characteristics of Algorithms
3) Specify the major two performance measures of an algorithm
4) Assume that computer A frequency is 10 MHz and computer B frequency is
15 GHz. Which computer will run faster when:
1) Computer A runs an algorithm that takes 100 𝑛 log 𝑛 with 𝑛 = 10 millions lines
2) Computer B runs an algorithm that takes 5𝑛2 with 𝑛 = 10 millions lines
Exercises
1) Select one correct answer:
5. The function 𝑛log2 5 evaluates approximately to …
A. 𝑛2.322 B. 𝑛1.585 C. 𝑛2 D. 𝑛0.75
6. The summation σ𝑛𝑖=0 𝑖 evaluates to …
A. 𝜃(𝑛) B. 𝜃(𝑛 log 𝑛) C. 𝜃(𝑛2 ) D. 𝜃(𝑛3 )
7. The summation σ𝑛𝑖=0 𝑖 2 evaluates to …
A. 𝜃(𝑛) B. 𝜃(𝑛 log 𝑛) C. 𝜃(𝑛2 ) D. 𝜃(𝑛3 )
1
8. The summation σ𝑛𝑖=1 evaluates to …
𝑖
A. 𝜃(𝑛) B. 𝜃(log 𝑛) C. 𝜃(𝑛2 ) D. 𝜃(𝑛3 )
Exercises
2- What are the average running times of Insertion-sort and Merge-
Sort? Comment.
3- TRUE or FALSE and correct if FALSE:
4- Fill in the spaces using one of the asymptotic notation (𝑂, Ω, Θ) for each sentence:
1) 2𝑛3 + 10𝑛 + 100 = ⋯ (𝑛3 )
2) 𝑛 lg 𝑛 = ⋯ (𝑛2 )
𝑛2
3) 𝑙𝑔𝑛 = ⋯ (𝑛2 )
4) 𝑛 lg 𝑛 + 𝑛 = ⋯ (𝑛)
Exercises
2- What are the average running times of Insertion-sort and Merge-
Sort? Comment.
3- TRUE or FALSE and correct if FALSE:
4- Fill in the spaces using one of the asymptotic notation (𝑂, Ω, Θ) for each sentence:
1) 2𝑛3 + 10𝑛 + 100 = ⋯ (𝑛3 )
2) 𝑛 lg 𝑛 = ⋯ (𝑛2 )
𝑛2
3) 𝑙𝑔𝑛 = ⋯ (𝑛2 )
4) 𝑛 lg 𝑛 + 𝑛 = ⋯ (𝑛)
5- Explain briefly the main idea of counting sort.
6- Given the following input:
6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2
Apply counting sort:
- Show the contents of list B after termination.
- What is the running time of this algorithm?
7- Explain briefly the main idea of Radix sort. What is the importance of
using a stable sort with it?
8- Show all passes (iterations) when using Radix sort to sort the
following input:
2565, 2500, 1050, 1077, 3010, 3101
9- What is the running time of Radix sort? (general formula and best-case).
Exercises
1) Write the recurrence describing the binary search. Discuss the best-
case and average-case running times.
2) Given the set of values: {3, 15, 10, 8, 12, 9, 18, 6, 2, 7}.
1) How can you apply Binary search?
2) How many comparisons will take place when searching for a value 11?
3) Given the set of values: {10, 15, 8, 12, 9, 18, 6, 2, 7, 20}.
1) Implement a binary search tree
2) How many comparisons will take place when searching for a value 5?
3) What is the average-case searching time for searching?
4) Discuss the worst-case searching time
4) Insert TRUE or FALSE:
1- linear search belongs to divide-and-conquer algorithms.
2- In binary search, the array must be ordered in advance
3- A divide-and-conquer version of powering a number algorithm
takes Θ(𝑛) time
4- Worst-case searching time for a binary search tree is Θ(𝑛)
5- In binary search, searching starts from the first element in the
list.
