Question Description
I’m working on a algorithms & data structures exercise and need an explanation and answer to help me learn.
Algorithms Homework 1
When submitting the document, make sure you include all the answers in a single file (such as MSWord) and use the following filename format:YourFullName_HW1.doc
Last week we talked about Divide&Conquer approach. Here are the video recordings.
Your homework:
Among the algorithms covered/mentioned in the lectures, pick one of the algorithms and explain it. Make sure you include a pseudocode (you can take it from the book but you should add comments to it).
For graduate students: 5 minute video recording (with webcam showing your face) is required.
I need content of above requirement to record video for 5 minutes. Please elaborate as much as you can.
Home work 2
- (20 pts) Chapter 1 Slide 5 (middle school procedure) is not an algorithm as is (it needs some polishing), describe what the problem is with that procedure.
- (20 pts) Chapter 2 Slide 24 shows an algorithm for matrix multiplication, how many multiplications are performed in this algorithm as a function of n? Describe how you reached your answer.
- (20 pts) Chapter 3 Slide 24 states that there are two ordering of vertices using DFS. Apply the DFS algorithm on the graph given in Slide 23 and find these orderings. Show steps of your work. For this question always go alphabetically (start with vertex a and pick neighbouring vertices in alphabetical order as explained in class).
- (20 pts) Chapter 4 Slide 25 suggests using the Partition algorithm of Quicksort to solve the k-th smallest problem. Use that approach to find the median of the following array:
- (20 pts) Chapter 5 Slide 23 talks about the closest-pair problem, describe how the number of operations are reduced (for example, which operations are reduced and at the expense of what additional operations).
14, 20, 1, 9, 5, 2, 7, 10, 4. Show your steps. For this question, always pick the first number (of the subarray) as the pivot as explained in class).
Note:
For question 3, always go alphabetically (start with vertex a and pick neighbouring vertices in alphabetical order as explained in class).
For question 4, always pick the first number (of the subarray) as the pivot as explained in class).