Questions and Answers
Fill in the blank for the pseudocode for an algorithm based on linear search that takes as input a valley list a1 , a2 ,..., an and returns the location of the valley. procedure LinearValley(a1 , a2 ,..., an : valley list) i.for i := 1 to n − 1 ii.if ___ iii.return i iv.return n
ai == 1
What is a loop invariant of LinearValley that you could use to prove the correctness of LinearValley?
At each iteration, the index i will always point to the current position being checked in the valley list.
Fill in the blank for the algorithm based on binary search that takes as input a valley list a1 , a2 ,..., an and returns the location of the valley. procedure BinaryValley(a1 , a2 ,..., an : valley list) i.i := 1 ii.j := n iii.while (i < j) iv.m := ⌊ i+j ___ 2 ⌋ v.if ___ vi.i := m + 1 vii.else viii.j := m ix.return i
2, ai < am
What is a loop invariant of BinaryValley that you could use to prove the correctness of BinaryValley?
Signup and view all the answers
In the worst case, which algorithm uses fewer comparisons on a list of length n? LinearValley or BinaryValley?
Signup and view all the answers
A list of n distinct integers cannot be a valley list if all the numbers are increasing.
Signup and view all the answers
In a valley list, the position of the valley is indicated by the element that equals 1.
Signup and view all the answers
Study Notes
Homework Instructions
- Group work of 1 to 4 students, no external assistance.
- Submission via Gradescope by one representative, due by 11:59 PM on August 18, 2024.
- Grace period of 2 hours allowed.
- Review scanned work before final submission; multiple resubmissions permitted until deadline.
- Extra credit for typed solutions; hand-drawn diagrams accepted.
- Homework grading based on correctness and clarity of presentation.
- Justifications required for each answer, using mathematically sound reasoning.
Key Concepts
- Focus areas: Sorting, Searching, Loop Invariants, Runtimes, Big O notation, Algorithm runtime analysis, Master Theorem.
- Understanding valley lists: A sequence of numbers that first decreases and then increases, defining key characteristics.
Searching the Dark Valley
- Valley List Definition: A list of distinct integers that decreases to a minimum point and then increases; the "valley" is the index where the minimum occurs.
- Example: In the list [3, 2, 1, 6, 7], the valley is at index 3 (value 1).
- Special cases:
- An increasing list has a valley at index 1.
- A decreasing list has a valley at the last index.
Algorithms
-
Linear Search Algorithm (LinearValley):
- Searches each element sequentially to find the valley.
- Pseudocode structure: Loop through indices, check for valley condition, and return the index.
-
Binary Search Algorithm (BinaryValley):
- Efficiently narrows down the search space using a divide-and-conquer approach.
- Pseudocode: Initialize pointers, perform binary search until the valley is found, and return its index.
Loop Invariants
- Essential for proving the correctness of algorithms.
- LinearValley: A specific statement that maintains true throughout the execution of the algorithm, helping ensure the valley is identified correctly.
- BinaryValley: Similar to LinearValley, but focused on the division of search intervals to confirm the valley’s presence.
Comparison of Algorithms
- Analyze the maximum number of comparisons made by each algorithm in the worst-case scenario.
- LinearValley employs O(n) comparisons; BinaryValley has a logarithmic O(log n) complexity.
- Justification for the most efficient algorithm, taking into account the number of comparisons required for a list of length n.
Out of Bounds or In?
- Evaluation of true or false statements based on established mathematical rules.
- Include justifications using limit laws and function properties.
- Reference established formulas for sums, sequences, and factorial calculations.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
This homework assignment for CSE 21 requires students to work in groups of one to four. It must be submitted by Sunday, August 18, 2024, at 11:59 pm, with a strict grace period of only 2 hours.
