闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSCI 4041 Algorithms and Data Structures - Spring 2025

Homework 3 - Heaps and Hash Tables

Due Date: Friday, March 21, 2025 by 11:59pm.

Instructions: This is an individual homework assignment. You may work together to discuss concepts, but the solutions must be your own work. Submit your answers on Canvas, which is linked to Gradescope (be sure to correctly map the page for each problem). We will not grade *Practice Problems*, however, you are responsible for knowing how to solve them in order to prepare for quizzes and exams. This homework is divided into two parts. Part A focuses on written problems involving heaps and hash tables. Part B involves programming and using a priority queue.

Part A - Heaps and Hash Tables (Written Problems)

Problem H3.1: Heapsort (20 points)

This problem explores the question of finding the k-largest elements in an array of size n. Con-sider the HEAPSORT algorithm as described in Section 6.4. Also consider the BUILD-MAX-HEAP, BUILD-MIN-HEAP, and MIN-HEAPIFY algorithms described in Section 6.3. The two algorithms below result in the k largest items ending up in ascending order in A[1:k]. Assume k < n.

K - MAX - A (A , n , k )

1. HEAPSORT (A , n )

2. for i = 1 to k

3. exchange A [ i ] with A [n - k + i ]

K - MAX - B (A , n , k )

1. BUILD - MIN - HEAP (A , k )

2. for i = k +1 to n

3. if A [1] < A [ i ]

4. exchange A [1] with A [ i ]

5. MIN - HEAPIFY (A , 1)

6. HEAPSORT (A , k )

Answer the following questions:

(a) Execute both algorithms for the array A = [4, 3, 2, 2, 6, 1, 7] and k = 3. Show how the array changes after each line of code (You do not need to show changes within other heap functions).

(b) Analyze the worst case runtime for each algorithm. Which algorithm has a slower growing asymptotic runtime?

1. BUILD - MAX - HEAP (A , k +1)

2. for i = k +1 to n

3. if A [ k +1] < A [ i ]

4. exchange A [ k +1] with A [ i ]

5. MAX - HEAP - INCREASE - KEY (A , k +1 , A [ k +1])

6. HEAPSORT (A , k )

Call this K-MAX-C. Does it correctly return the sorted k-largest items? Explain your reasoning. What problem might the choice of heap solve with respect to the two algorithms?

(d) Prove: K-MAX-B is correct.

(e) Prove or disprove: K-MAX-A is stable. (*Practice Problem*)

Problems H3.2 - H3.3: Heap Algorithms

For each of the algorithm descriptions in the problems below do the following:

(i) Write the algorithm using pseudocode or another language of your choice. You can use any of the heap algorithms from the textbook, including those in Section 6.5.

(ii) Briefly and informally analyze the runtime for your algorithm considering best, worst, and average cases. This should be a quick justification rather than a formal proof.

(iii) Briefly and informally justify that your algorithm is correct. You may assume that algorithms from the textbook are correct. This should be a quick outline of a proof rather than a formal proof.

Write, analyze the runtime, and argue for the correctness of the following algorithms. (Remember A.heap-size might be different than the array size n. Also, be sure to modify or set A.heap-size if necessary.)

Problem H3.2: (20 points)

(a) MAX-HEAP-REMOVE(A, index) - Remove the item with index index from a max heap in O(lg n) time. Your algorithm should maintain the heap structure. The algorithm returns True if the item is removed and False otherwise.

(b) MAX-HEAP-SEARCH(A, val) - Finds an item in the heap. This should return the index of the item if found and -1 otherwise.

Problem H3.3: (20 points)

(a) HAS-MIN-HEAP-PROPERTY(A) - Returns True if A is a min-heap and False otherwise.

(b) MIN-HEAP-MERGE(A, B) - Merges two min heaps of the same size together (i.e. A.heap-size = B.heap-size). Returns a new min-heap C which contains the elements of A and B.

(c) HAS-BINARY-SEARCH-TREE-PROPERTY(A) - Let A be a min-heap. The algorithm returns True if A is also a binary search tree and False otherwise. (*Practice Problem*)

(d) BST-TO-MAX-HEAP(A) - Let A be a binary search tree that has the same indexing structure as a heap (See Figure 6.1 in the textbook). A.tree-size holds the number of items in the binary search tree. The algorithm converts the binary search tree into a max heap. (*Practice Problem*)

Problems H3.4 - H3.5: Dynamic Hash Tables

Assume you are creating a hash table that uses chaining. Recall that the load factor from Section 11.2 is defined as α(n) = m/n , where n is the number of inserted items in a hash table and m is the number of slots.

• Too high of an α means more collisions. Too low of an α means we are wasting space. Let αL be our lower bound and αH be our upper bound on α so that αL ≤ α(n) < αH.

• Let k be a specific chosen value. Suppose that every time our load factor is greater than or equal to αH, we increase the size of the hash table. In this case, we multiply the number of slots in the hash table by k. Every time our load factor is less than to αL, we divide of slots in the hash table by k. This system leads to the following equations.

◦ αL = k/αH.

◦ If αH ≤ a(n), then mnew = k(mold).

◦ If a(n) < αL, then mnew = (mold)/k.

Problems H3.4: (10 points)

(a) Let T be a hash table that has m = 100 slots and contains n = 125 items. Whenever we reach our upper bound, we double the number of slots in the hash table (e.g. k = 2). Let αH = 2.

i. Calculate the load factor α(n). Calculate αL.

ii. How many items would you need to add to T before α reaches or exceeds αH?

iii. Assume that after adding x items into the hash table, n has grown such that α(n) = αH. Therefore, we will double the number of slots in T. What is our new m and α(n)? This should match our αL defined above.

iv. How many more items do we need to add before we double the table size again?

v. Graph the function α(n) *(Practice Problem)*

(b) Modify the following algorithms assuming a defined αH and k. You can access these constants directly in your algorithms. CHAINED-HASH-INSERT(T, x) and CHAINED-HASH-DELETE(T, x) are described in the textbook in Section 11.2.

i. CHAINED-HASH-INSERT(T, x) - increase the size of the hash table if α exceeds or is equal to αH.

ii. CHAINED-HASH-DELETE(T, x) - decrease the size of the hash table if α becomes less than αL. (*Practice Problem*)

Problems H3.5: (10 points)

(a) Describe the worst case runtime for CHAINED-HASH-INSERT(T, x). Describe the best case. Describe the average case.

(b) Theorem 11.2 states that the average-case runtime for searching in a hash table with chaining is Θ(1 + α). Using this theorem along with our modifications to delete and insert, prove the following:

Prove: Let αL,αH ∈ R + , If αL ≤ α(n) ≤ αH, then the average-case runtime of search with chaining is Θ(1).

(Hint: What is the asymptotic runtime of α(n)?)

Part B - Priority Queue (Programming Problem)

Submission: Submit the following file to “Homework 3B” submission on Gradescope.

• priority queue.py

Problem H3.6: Update Priority (20 points)

Instructions: Many advanced algorithms require the update of a key in a priority queue. For example, Dijkstra’s single source shortest path algorithm described in Section 22.3 of our textbook takes advantage of the MAX-HEAP-INCREASE-KEY described in Section 6.5. The update of a key, however, needs to be efficient to improve the runtime requirements. For this problem, we will extend a heap to create a priority queue. Using our priority queue, we can update an item’s key in O(lg n) time. This is because we also ensure that each time we lookup an index by id, the algorithm runs in O(1) time.

Task: You are given a set of tasks to add to a priority queue. Each task has an id and a priority key. You are provided with the following base code:

• H3 6.py - This file has example code for testing your implementation. (You will not need to modify this file)

• binary heap.py - This file implements a binary heap. (You will not need to modify this file).

• task.py - This file defines the task object. (You will not need to modify this file) Below are a description of the methods:

◦ get id() - Returns the id of a task.

◦ get name() - Returns the name of the task.

◦ get key() - Returns the key of a task, which represents a task’s priority. The higher the key is, the higher the priority.

◦ set key(key) - Changes the priority of a task.

• priority queue.py - This file implements a priority queue, which inherits from a binary heap.(You will need to modify and submit this file.) Extend the heap functionality to create a priority queue. Our priority queue expects that item.get id(), item.get key(), and item.set key() exist, therefore, allowing the use of the Task object.

You will need to implement the following methods:

◦ extract max() - Take the top item off of the heap, and maintain the heap property. The method should run in O(lg n) time.

◦ insert(item) - Add the item to the heap in the correct location based off the item’s priority (e.g. item.get key()). The method should run in O(lg n) time.

◦ lookup by id(id) - Return the index of the item in the heap structure. If the id is not found, -1 is returned. The method should run in O(1) time.

◦ update priority(id, key) - Looks up an item in the heap, set’s the key for that item, and maintains the heap property. The method should run in O(lg n) time.

◦ on index changed(item, index) - This method may be helpful for monitoring when an item’s index changes during the heapify() method of the binary heap.

Testing: To test the program you can run H3 6.py, which creates a priority queue and calls the methods you implemented. You can test your program with the following command:

python3 H3_6 . py

You should see the following output based on a hypothetical scenario involving CSCI 4041:

Tasks :

------------------------------

Id : Name ( Priority )

------------------------------

1 : Study for midterm . ( 20 )

2 : Email professor . ( 21 )

3 : Start homework . ( 20 )

4 : Study induction for midterm . ( 19 )

5 : Start homework problem H3 .1. ( 18 )

6 : Email professor and TAs . ( 25 )