Description

Transform-and-conquer are
Transform-an usually very effective, but the less
known among the algorithms of d-Conquer the …-and-conquer family.
● Meet the family
Algorithms ○ Decrease-and-Conquer
○ Divide-and-Conquer

Solve the problem by changing the problem size.

○ Transform-and-Conquer
● Transform-and-Conquer
○ Basic Principles
○ Recursion and Iteration
CSC 6013 – Week 8
Meet the …-and-conquer family
While in military, politics, management, etc., the usage of divide-and-conquer became extremely popular, and effective, in algorithms we have a subdivision of the algorithm techniques:
● Divide-and-conquer
○ When the original problem is broken into complementary parts;
● Decrease-and-conquer
○ When at each time the problem becomes smaller, but not into complementary problems;
● Transform-and-conquer
○ When the problem not always becomes smaller.
This division is acknowledged by great authors
(as our textbook ones: Cormen, Leiserson, Rivest, and Stein), but it is not unanimous.

Transform-and-conquer are
Transform-an usually very effective, but the less
known among the algorithms of d-Conquer the …-and-conquer family.
● Meet the family
Algorithms ○ Decrease-and-Conquer
○ Divide-and-Conquer

Solve the problem by changing the problem size.

○ Transform-and-Conquer
● Transform-and-Conquer
○ Basic Principles
○ Recursion and Iteration
CSC 6013 – Week 8
Transform-and-conquer variants
● Instance Simplification
○ Transform to a simpler or more convenient instance of the same problem;
○ For example, the search on an array can be easier if the array is sorted first;
● Representation Change
○ It remains the same instance, but in a different representation;
○ For example, a graph can change from an adjacency matrix representation into an adjacency list representation;
● Problem Reduction
○ Transform to an instance of a different problem for which a solution is simpler or already available.
Text: Transform-and-Conquer.

Example 2 – Computing the Mode
Search for the longest sequence of the same number to compute the Mode in a sorted array A:
● Start from the first element towards the last (keep track of mode_count and mode value); ○ If the next element has the same value:
■ increase the counting; ○ Else:
■ check if the current_count is larger;
● By the end get the value with the highest count (comparing the last sequence too).
Several Transform-and-Conquer using instance simplification perform pre-sorting.

Example 3 – Balancing Binary Search Trees
● A Binary Search tree is a tree where:
○ the nodes have 0, 1, or 2 children 51
(hence, Binary); 3 3
○ the values stored in each node are
greater than the values stored in 23 64 its left child subtree and smaller 2 1 1 2 than the values stored in its right
child subtree (hence, Search). 11 44 56 72
● A Balanced Binary Search tree is a 0 1 0 0 0 0 0 1 tree where:
○ for all nodes the height of subtrees of 17 74 its left and right children may differ 0 0 0 0 by at most 1 (hence, Balanced).
Text: Binary Search Tree

Example 3 – Balancing Binary Search Trees
● Given a binary search tree, balance it when 51
performing an insertion or removal 3 3
● The brute force solution is based on:
○ Detect unbalancing 23 64
○ For every node compute the 2 1 1 2 height of left and right subtrees,
then balancing it 11 44 56 72
■ High complexity – O(n2 log n) 0 1 0 0 0 0 0 1
○ An instance simplification solution
make sure insertion and removal 17 74
preserves the balance 0 0 0 0
○ Self-balanced trees – e.g., AVL Trees – named after Adelson-Velskii and Landis (1962).
Text: AVL Tree Data Structure.
Example 3 – Balancing Binary Search Trees
● AVL trees performs a check after each insertion or deletion;
● If the tree becomes unbalanced a correction procedure, called rotation is performed:
○ Simple rotation
■ Left rotation or Right rotation:

This is an instance
simplification example.

Another option would be a representation change solution. In this case, the
binary search tree can be changed into a structure allowing more than two
childs for a node – a N-ary tree – e.g., B-trees.

● With or without children;
○ Double rotation
■ Right-left rotation or Left-right rotation:
● With or without children.
Wikipedia: AVL Tree.

This Week’s task
Final Exam
You can start the exam anytime from
Monday 9PM EST to Saturday 8PM EST.
● Go to Module 8 on Canvas and take the Final Exam.
○ The exam is composed by 8 questions;
○ You have 4 hours once you start to take the exam;
○ You will download a .pdf with the 8 questions, and within 4 hours you need to upload a single .pdf with your answers; ● There is about one question about each week topic.
● You can consult all class materials, but not general access to the Internet.
CSC 6013 – Week 8
If something exceptional happens
during the
exam, send me
an email as soon as
possible,
preferably with your answers.
Final Exam
● The exam is composed by 8 questions and you have 4 hours once you start to take the exam:
○ It is probably a good idea to spend 15 minutes at each question, if you got stuck, go to the next one;
● You will download a .pdf with the 8 questions, and within 4 hours you need to upload a single .pdf with your answers:
○ Other formats (docx, jpg, etc) are not acceptable, practice generating pdf files before the exam;
● There is about one question about each week topic and you can consult all class materials, but not general access to the Internet:
○ Study the quizzes, and all other materials before taking the exam and make sure you have four non-interrupted hours to take the exam.
Feel free to type it or hand write it, but you have to submit a single .pdf with your answers.