Course topics 3 and 4

Self-study (videos and slides in english)

The topics for this week are as follows: (i) Divide and conquer, (ii) Quicksort, (iii) Mergesort

The following links will take you to the video-lectures and the accompanying slides:

Lecture-questions

In the divide and conquer design strategy
Which of the following best describes the relationship between the divide and conquer strategy and recursive algorithms?
Which of the following best describes a data structure for which divide and conquer strategies might be effective?
It is said that Quicksort uses the divide and conquer strategy when processing an array \(A\). What part of Quicksort corresponds to ’dividing’?
The purpose of the Quicksort algorithm is
During Quicksort a partitioning procedure is used. Let the input to the partitioning procedure be array \(A\) and from \(A\) we must partition at least three elements. Which of the following is true? (More than one may be true.)
In Quicksort, partitioning is used to
Of the following statements, which is true regarding the Quicksort algorithm?
It is said that Mergesort uses the divide and conquer strategy when processing an array \(A\). What part of Mergesort corresponds to ’dividing’?
When two sorted arrays are merged,
When two subarrays are merged in Mergesort,
Let the size of an array (or subarray) be the number of elements it contains. The Mergesort algorithm
Regarding Mergesort, which of the following are true. (More than one may be true.)
What is a central question, related to this course, whose answer can be found in this week’s videos?
Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?
Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

Week03 - Glossary

Viikko03 - Sanasto

Submit weekly exercises

Questions to be submitted this week .. _courseweek04:

Course topic 4

Self-study

The topics for this week are all related to Asymptotic analysis and algorithm efficiency: (i) Big-O, Big-Omega, Big-Theta (ii) Best case, worst case, average case

The following links will take you to the video-lectures and the accompanying slides:

Algorithm efficiency of Mergesort and Quicksort

Week04 - Glossary

What can we use the big-O notation ( \(O\) ) to describe?
Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(1)\). Which of the following statements is true?
What can we use the big-Omega notation ( \(\Omega\) ) to describe?
Suppose that algorithms A and B can be used to compute the same thing. Which of the following statements is true? (More than 1 may be true.)
Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(n)\). Which of the following statements is true? (More than one may be true.)
Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(g(n))\) and also to \(\Omega(h(n))\). Which of the following statements is always true?
Which statement is true for insertion sort?
Suppose array \(A\) is input into insertion sort and suppose insertion sort outputs array \(A\) whose elements are sorted from smallest to largest. What is the worst case input \(A\)?
Suppose we have an array \(A\) with numbers. For this collection of numbers let \(A_{best}\) and \(A_{worst}\) correspond to the best and worst input cases for insertion sort. Which of the following is true?
MERGESORT is called with an input array \(A\) having \(n\) elements. Of the following, which is the best upper bound on the number of recursion levels that MERGESORT will use?
Suppose the asymptotic runtime efficiency of QUICKSORT is analyzed when the starting array \(A\) has \(n\) elements. Which of the following are true?
Suppose MERGESORT, QUICKSORT and INSERTIONSORT are being compared. Which of the following are true? (There may be more than one true statement.)
What is a central question, related to this course, whose answer can be found in this week’s videos?
Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?
Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

Week04 - Glossary

Viikko04 - Sanasto

Submit weekly exercises

Questions to be submitted this week