跳至主要內容

高级算法作业

XiaoXianYue原创2024年11月20日大约 22 分钟大三上高级算法大作业大三上高级算法大作业

​ img

​ School of Computing, Engineering and Mathematics (CEM)

​ Faculty of Engineering, Environment and Computing (EEC)

CUH500CMD ADVANCED ALGORITHMS | 2024

PORTFOLIO OF CODE | REPORT

NAME: Xiao XianYue

SID: 14553435

STD 1

1. pseudocode

SELECTION_SORT(A)
          FOR i TO length(A)-1
                    min ← i
                    FOR j ← i + 1 TO length(A)
                              IF A[j] < A[min]
                                        min ← j
                    SWAP (A, i, min)
          RETURN A

2. Two Solutions

Solution 1

def selection_sort(arr):
    result = []  # Create a new list for storing the sorted list
    for i in range(len(arr) - 1, 0, -1):  # Iterate through the list from back to front
        min = arr[i]
        for j in range(i):  # Iterate over all elements except i and find the minimum value
            if arr[j] < min:
                min = arr[j]
        result.append(min)  # Add the minimum value to the newly created list
        arr.remove(min)
    result.append(arr[0])  # Add the last remaining element to result(the list)
    return result


print(selection_sort([5, 4, 3, 2, 1]))
image-20241128102748273

Solution 2

def selection_sort(arr):
    for i in range(len(arr)):  # Iterate through the list from front to back
        min_index = i
        for j in range(i + 1, len(arr)):  # Find the smallest value in an unsorted list
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]  # Swap the minimum value with i into the sorted list
    return arr


print(selection_sort([5, 4, 3, 2, 1]))

The one is written according to the pseudo-code above.

image-20241128102827847

3. Explaining the code

Solution 1

  • Firstly,result = []: I create an empty list result to store the final sorted elements. (adding elements one by one)

  • Secondly, I use a outer loop:for i in range(len(arr) - 1, 0, -1):. This loop processes the elements from back to front, accessing the last element of the unsorted list first.

  • Thirdly, min = arr[i]: I set a variable min that is currently used to store the minimum value of the element value of the current unsorted list. Initialize this variable to the element at index i.

  • Fourthly, for j in range(i + 1, len(arr)): I use the inner loop to find the minimum elements in the unsorted list. As stated above, the inner loop is executed i times to compare the smallest value (which is stored as min) in the unsorted list. if arr[j] < min: min = arr[j]

  • Fifthly, result.append(min) adds the minimum value to the end of a sorted list.

  • Sixthly, arr.remove(min). Remove the smallest value found from the original list to prevent the next iteration of the outer for loop from repeatedly adding the same smallest element, which has already been added to result.

  • After len(arr) - 1 times of outer loops, there is only one element left in the unsorted list, and this is the largest element, which is added to the very end of the sorted list.

  • return the sorted list result.

  • Below is a schematic of the flow of the first outer loop.

未命名表单

Solution 2

This is code written according to the given pseudo-code, without having to create a new list and modify it directly on the original list.

  • Firstly, Set up an outer loop that traverses the list from front to back.

  • Secondly, As in solution 1, create a variable min_index to store the minimum value of the current queue.

  • Thirdly, Set up an inner loop that also compares arr[i] one by one with the other elements in the list and finds the smallest one.

  • Find the minimum value and swap places with arr[i]. This is why the outer loop needs to be traversed from front to back. Because the smaller element has to be placed earlier in the queue.

  • Returns the modified original list arr.

  • The flow chart below shows how the list changes after the first outer loop.

report_1

4. Evaluating the code

We try to evaluate both codes in terms of readability and conciseness.

Readability and conciseness

Solution 1:

  •   for i in range(len(arr) - 1, 0, -1):

    The order of traversal of the outer loop: back-to-front traversal is a bit uncommon and can be confusing. Generally the selection ordering is traversed from front to back, which is more in line with most people's understanding.

  •   arr.remove(min)

    The remove method: each time the minimum value is removed it changes the structure of the array, which may not make it easy to understand and may affect efficiency. Removing elements adds complexity to the code.

  •   min = arr[i]

    Actually, it's not good to use min as a variable name! min is a built-in function in Python, which is confusing to the reader.

Solution 2:

  • The traversal order of the outer loop: traversing from front to back is consistent with how people normally do things in order and is easy to understand.
for i in range(len(arr))
  • The code is simple and easy to read. There are no complex delete operations or extra data structures. It follows the basic logic of selective sorting and clearly expresses each step of the operation。
arr[i], arr[min_index] = arr[min_index], arr[i]

We try to evaluate both codes in terms of complexity

Complexity

Solution 1:

  • Time Complexity:

    1. Outer loop: for i in range(len(arr) - 1, 0, -1) This loop traverses the array from back to front, n-1 times, where n is the length of the array.
    2. Inner loop: for j in range(i) This loop iterates through the array from 0 to i-1. In the worst case, the inner loop will be executed at most n times (when i = n-1).
    3. remove(min): Each time arr.remove(min) is called to remove the minimum value, the Python list's remove method needs to scan the entire array to find the element and remove it, with time complexity O(n). In the worst case, this operation is performed n-1 times, with each removal reducing the length of the array.
    4. Combined time complexity: O(n)×O(n)+O(n)×O(n)=O(n2) (worst case)

  • Space complexity: O(n) (because an extra list of results is used)

Solution 2:

  • Space complexity: there is no other storage space O(1)

  • Time Complexity:

    1. outer loop: for i in range(len(arr)) This loop traverses the entire array n times.

    2. inner loop: for j in range(i + 1, len(arr)) This loop iterates from i+1 to n-1 one at a time, and in the worst case the time complexity of the inner loop is O(n²). 3. swap operation: Swapping elements is a constant time operation O(n²).

    3. Swap operation: Swapping elements is a constant time operation O(1).

    4. combined time complexity: the total time complexity of the outer and inner loops is O(n²), so the time complexity of the algorithm is O(n²)

    Overall Solution 2 is less complex than Solution 1.

STD 2

1. Code

Iterative

image-20241128111253478
image-20241128111253478

Recursive

image-20241128111010185

2. Explaining the code

Iterative

class TreeNode:
    """Binary Tree Node Classes"""

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Here I use a class to simulate the attribute of nodes in a binary tree. Assigning values to each node and setting the left and right subtrees of each node.

class BST:
    def __init__(self):
        self.root = None  # Initial binary tree

Create a class that operates on binary trees. Initialise this binary tree to be empty. It is worth noting that the code all uses the root node of the binary tree to represent the entire binary tree.

    def find_i(self, val):
        cur = self.root  # nodes in a binary tree

Use a function to implement the search function to increase the modularity of the code and ease of calling. Create the variable cur initialised to the root node of the binary tree. This means that the following code will traverse the binary tree beginning with the root node. val is the value of the node we need to find.

         while cur:  # If you don't know how many loops there could be, a while loop is appropriate.
            if cur.val > val:  # If the node is larger than the search value, the search value is in the left subtree of the node
                cur = cur.left
            elif cur.val < val:  # If the node is smaller than the search value, the search value is in the right subtree of the node
                cur = cur.right
            else:  # is equal to the search value, the loop ends
                return True
        return False

  • I use a while loop to traverse the binary tree because I don't know how many times we have to do the loop. If I knew exactly how many times the loop was going to be executed, a for loop would be more appropriate.

  • If val is less than the current node value, it means that val exists in the left subtree of the current node. If val is greater than the current node value, it means that val exists in the right subtree of the current node.

  • Until a node with the same value as val is found, return True and the function ends.

  • If while loop ends (cur node is empty, binary tree nodes are all traversed) no corresponding node is found, there is no node in the binary tree with the value val. Returns False.

Manually create a binary tree for searching.

report3

Recursive

Only the following codes are different from Iterative, the logic of all other codes are exactly the same, you can refer to the description above.

    def find_r(self,target):
        """
        Recursively searches for the target in the BST.
        Returns True if found, False if not found, None if invalid input or empty tree.
        """
        if self.root:
            if self.find_r_helper(target, self.root):  # if find_r_helper return True
                return True
            return False  # # if find_r_helper return False
        else:
            return None
  • Create a recursive find function, find_r.
  • If the tree exists, check if find_r_helper finds the corresponding node value.
  • If it does, return True
  • If it does, True. If it doesn't, False.
  • If the tree does not exist, return False

    def find_r_helper(self,target,root):
        if root is None:
            return False

        if target > root.val and root.right:
            return self.find_r_helper(target,root.right)  # Search in the right subtree
        elif target < root.val and root.left:
            return self.find_r_helper(target,root.left)  # Search in the left subtree

        if target == root.val:
            return True
  • Creates a function to find the value of a node find_r_helper.
  • If the incoming tree is empty, return False.
  • If the node value is less than the find value, recursively search its right subtree.
  • If the node value is greater than the lookup value, recursively search the left subtree.
  • If at this level of recursion the node value is equal to the find value, return True and pass it back one level at a time, with find_r_helper returning True at the end.
report4

3. Evaluating the code

We try to evaluate both codes in terms of complexity

  • Time Complexity:

    The time complexity of both solutions is O(logn) (best case): because for each recursion/loop, half the tree of nodes needs to be detected, in line with the definition of the logn function.

  • Space Complexity:

    • Iterative: Only a pointer cur is used to point to the current node, no recursive call stack is needed.O(1)
    • Recursive: Since the depth of the recursion is the most significant source of space consumption, the space complexity is mainly determined by the maximum depth of the recursion.
      • Worst Space Complexity: If the tree degenerates to a chained list (i.e., the height of the tree is n), then the maximum depth of the recursion is n and the space complexity is O(n).
      • Best space complexity: if the tree is balanced (i.e., the height of the tree is log n), then the maximum depth of the recursion is log n and the space complexity is O(logn).

  • To summary, Recursive has a higher space complexity, especially when dealing with trees of greater depth which can lead to StackOverflow. Iterative code is not as elegant as Recursive but has a low space complexity.

STD 3

1. Code

image-20241128120125671
image-20241128120125671

2. Explaining the Code

class GraphAdjMat:

    def __init__(self, vertices: list[int], edges: list[list[int]]):
        self.vertices: list[int] = []
        self.adj_mat: list[list[int]] = []
        for val in vertices:
            self.add_vertex(val)
        for e in edges:
            self.add_edge(e[0], e[1])

vertices for vertex; adj_mat is the adjacency matrix of the graph.

    def size(self) -> int:
        return len(self.vertices)

View the current number of vertices of the graph.

    def add_vertex(self, val: int):
        n = self.size()
        self.vertices.append(val)
        new_row = [0] * (n + 1)
        self.adj_mat.append(new_row)
        for row in self.adj_mat[:-1]: 
            row.append(0)
  • To add a node to the graph:
    • First, get the current number of vertices n.
    • Add the new node value to the vertices list.
    • Create a new row for the adjacency matrix with n + 1 zeros, representing no edges for the new node.
    • Append this new row to the adjacency matrix adj_mat.
    • For all existing rows (except the new one), append a 0 to indicate no connection to the new node.
    def remove_vertex(self, index: int):
        if index >= self.size() or index < 0:
            raise IndexError(f"Index {index} is out of range.")
        self.vertices.pop(index)
        self.adj_mat.pop(index)
        for row in self.adj_mat:
            row.pop(index)
  • To remove a node from the graph:
    • Check if the index is valid; if it's out of bounds (less than 0 or greater than the list length), raise an exception.
    • Remove the vertex at the given index from the vertices list and the corresponding row from the adj_mat.
    • Iterate through the adj_mat and remove the element at the given index from each row.
    def edge_num(self):
        edge_count = 0
        for row in self.adj_mat:
            for edge in row:
                if edge == 1:
                    edge_count += 1
        return edge_count

Iterate over all elements of the edge list that have a value of 1 and store them in edge_count, which is the number of edges in the current graph.

    def add_edge(self, i: int, j: int):
        edge_number = self.edge_num()
        # Check if i or j is out pf bounds and throe an exception if it is
        if i >= self.size() or i < 0 or j >= self.size() or i >= self.size():
            raise IndexError(f"index {i} or {j} is out of range.")
        if i == j:
            raise ValueError(f"Cannot add edge {i} to itself.")
        self.adj_mat[i][j] = 1
        self.adj_mat[j][i] = 1
        if self.edge_num() - edge_number == 1:
            return
        else:
            return False

First, it checks if the vertex index is out of range or less than 0, and throws an exception if it is. Also, a vertex cannot add an edge pointing from itself to itself, otherwise an exception is thrown. Then, set adj_mat[i][j] and adj_mat[j][i] to 1 in the adjacency matrix to indicate that an undirected edge is added. Finally, check if the number of added edges is increased by 1, if yes, the addition is successful, otherwise return False.

   def remove_edge(self, i: int, j: int):
        edge_number = self.edge_num()
        if i >= self.size() or i < 0 or j >= self.size() or i >= self.size():
            raise IndexError(f"index {i} or {j} is out of range.")
        if i == j:
            raise ValueError(f"Cannot add edge {i} to itself.")
        self.adj_mat[i][j] = 0
        self.adj_mat[j][i] = 0
        if edge_number - self.edge_num() == 1:
            return
        else:
            return False

Same logic as adding edges above.

    def print_matrix(self):
        n = self.size()
        print("     " + "   ".join(map(str, range(n))))
        print("index" + "-" * (4 * n - 1))
        for i, row in enumerate(self.adj_mat):
            print(f"{i} |" + "   ".join(map(str, row)))

    def print(self):
        print("Vertex list = ", self.vertices)
        print("adjacency matrix = ")
        self.print_matrix()

print_matrix:

  • First, get the number of vertices (n), which will define the size of the matrix.
  • Next, print the column headers (vertex indices) from 0 to (n-1), making sure each is aligned with 3 spaces for clarity.
  • Add a dividing line to separate the headers from the actual matrix data.
  • Then, go through the adjacency matrix row by row. Each row shows the connections for a specific vertex:
    • Start with the row number on the left, followed by the connection status for each column:
      • Use 1 to show there's an edge.
      • Use 0 if there's no edge.

3. Visualise some code

Initialised to the graph below, with the vertex list and edge list labelled in it.

report 5

Try adding a vertex with a value of 7 and add edges 2-7; 4-7.

Report 6

4. Evaluating the code

We try to evaluate both codes in terms of Modularity and reusability.

  1. Modularity
    • Each function is split into separate methods like add_vertex, add_edge, remove_vertex, and print_matrix, which makes the code easy to follow and work with. It's pretty straightforward to understand what each method does.
    • The methods are short and focused, which makes them easier to debug and keeps the overall structure neat.
  2. Reusability
    • The way the logic is written for adding and removing vertices and edges makes it flexible enough to use in different types of graph implementations.
    • Using an adjacency matrix works well for undirected graphs, but it might need some tweaks if you want to handle directed or weighted graphs.

GOOD MODULARITY AND REUSABILITY!

We try to evaluate both codes in terms of Efficiency

for val in vertices:
    self.add_vertex(val)
for e in edges:
    self.add_edge(e[0], e[1])
  • Using a for loop to add nodes and edges each time the class is initialized would be a slow operation when dealing with large graphs.
def add_vertex(self, val: int):
    n = self.size()
    self.vertices.append(val)
    new_row = [0] * (n + 1)
    self.adj_mat.append(new_row)
    for row in self.adj_mat[:-1]:
        row.append(0)
  • And count the number of vertices self.size every time you call the functions that add vertices and add edges. Wouldn't it be better to just count the number of vertices when initializing?
def remove_vertex(self, index: int):
    if index >= self.size() or index < 0:
        raise IndexError(f"Index {index} is out of range.")
    self.vertices.pop(index)
    self.adj_mat.pop(index)
    for row in self.adj_mat:
        row.pop(index)
  • After deleting the vertices, each row of the entire adjacency matrix must be traversed to delete the elements column by column, which is also a less time-efficient (as O(n)) operation.

POOR EFFICIENCY!!

ADV 1

1. Code

image-20241128120355036

2. Explaining the Code

Only the remove function and the if_left_and_right function are discussed here. The rest of the functions are code given in Aula.

def remove(self, target):

    if self.root is None:  
        return False

if self.root is None, indicates that the binary tree is empty and returns it directly.

    elif self.root.data == target:  
        if self.root.left is None or self.root.right is None:
            root_child = self.root.left or self.root.right
            self.root = root_child  
        else:
            self.root = self.i_delete_node_with_two_children(self.root)
        return True

If the value of the root node in the given tree just equals target:

  • If the left and right child nodes of the root node are both empty, or both are null:
    • Set root_child to store the only child node that exists for the root node (e.g., if the right child exists, root_child equals the right child; if the left child exists, root_child equals the left child. If neither child exists, root_child will be null).
    • Remove the root node and directly replace the original binary tree with root_child as the root node.
  • If both the left and right child nodes of the root exist:
    • Perform operations using the if_left_and_right function. This is because I want to follow the code flow sequentially, and explanations for functions will appear later in the text.
  • Returns True for successful deletion.
   else:
        cur, parent = self.root, None
        while cur and cur.data != target:
            parent = cur
            if target < parent.data:
                cur = cur.left
            elif target > parent.data:
                cur = cur.right

If the value of the root node in the binary tree being traversed does not equal target:

  • Use cur to store the currently traversed node, and use parent to store the node that was traversed before cur, i.e., the parent node of cur.
  • The while loop continues traversing the binary tree. As long as cur is not null and does not equal target, the loop proceeds.
  • In the first step of the loop, assign parent = cur, storing the node obtained in the previous while iteration in parent.
  • If target < parent.data, traverse the left subtree of the current node. If target > parent.data, traverse the right subtree of the current node.
            if cur is None:  
                return  

            if cur.left is None or cur.right is None:
                child = cur.right or cur.left
                if cur.data < parent.data:
                    parent.left = child
                else:
                    parent.right = child
            else:
                self._delete_node_with_two_children(cur)
            return True

After the while loop, the node cur with value target and its parent parent have been found:

The logic of this part of the code is the same as in the first step dealing with the root node. You can refer to the explanation of the first step.

This function handles the case when the node to be deleted has both left and right children. It replaces the node with the smallest value in the right subtree.

  • Input: node (the node to be deleted).
  • Set re_node to the right child of the target node to find the smallest node in the right subtree. Also, store its parent as pre.
  • Use a while loop to find the smallest node by moving left through the tree. pre keeps track of the parent of re_node.
  • Once the smallest node is found, its value replaces the value of the node to be deleted.

If re_node has a right child:

  • If re_node is a left child of its parent, update the parent's left pointer to re_node.right.
  • If re_node is a right child of its parent, update the parent's right pointer to re_node.right.

If re_node has no children:

  • If re_node is a left child, set the parent's left pointer to None.
  • If re_node is a right child, set the parent's right pointer to None.

3. Visualise the code (steps)

Report 7

4. Evaluating the code

Efficiency Evaluation

  • Redundancy in Traversal: The code redundantly checks the left and right children of the node both in remove and in the helper function _delete_node_with_two_children. For example:
    • In remove, we check if cur.left or cur.right is None to determine if the node has one or no children.
    • Then, in _delete_node_with_two_children, we check again to remove the in-order successor node.
  • Space Complexity: The space complexity is O(1) because no additional memory is used other than a few pointers for traversal.
  • Time Complexity: The time complexity is O(h), where h is the height of the tree. In a balanced BST, this is O(logn), but in the worst case (unbalanced), it could be O(n).

Quality Evaluation

  • Function and Variable Names:

    • Function names like remove and _delete_node_with_two_children are clear but could be made more descriptive. For example, _delete_node_with_two_children could be renamed to delete_with_two_children for better readability.
    • Variable names such as cur, parent, and child are standard, but cur could be renamed to current_node for better clarity. Similarly, pre and re_node should be renamed to parent and successor.

  • Input Validation: The code lacks input validation. For instance, there’s no check for invalid input like a None value for target. Input validation could be added to ensure robustness.

  • Code Structure

    • Redundancy: There are redundant checks for nodes with one or no children. These could be refactored into a separate helper function.
    • The logic in _delete_node_with_two_children is functional but could be simplified or split into smaller functions for clarity.

ADV 3

1. Code

Test outcome is in “Explaining the Code”

2. Explaining the Code

  1. Import the required libraries.
import concurrent.futures
import newspaper
from newspaper import Article
import timeit
  1. Non-concurrent version
  • URL List: Defines a list of 5 news website URLs as the crawling targets.
  • Traverse each url. Use the variable result to store a news source object created with newspaper.build.
  • For the first 5 articles (indices 0-4), call the download() and parse() methods to download and parse the article content.
  • Print the extracted titles.
  • Exception Handling: If the target website has fewer than 5 articles, catch an IndexError and print a warning message. This try...except block was added to prevent issues like network errors or other problems from affecting the data retrieval process.
  1. Concurrent version.
  • This part of the logic is much the same as the non-concurrent version.
    with concurrent.futures.ThreadPoolExecutor() as executor:
        future_to_url = {executor.submit(fetch_headlines, url): url for url in URLs}
        for future in concurrent.futures.as_completed(future_to_url):
            url, headlines = future.result()
            print(f'\nThe headlines from {url} are:\n')
            for headline in headlines:
                print(headline)
  • A thread pool (ThreadPoolExecutor) is created to handle multiple URLs at the same time.
  • Tasks for fetching headlines are submitted to the pool using executor.submit().
  • As tasks are completed, their results (URL and headlines) are processed and printed. This allows for efficient parallel execution, reducing the overall runtime.
  1. Performance Comparison
if __name__ == '__main__':
    non_concurrent_time = timeit.timeit("get_headlines()", setup="from __main__ import get_headlines", number=2) / 2
    print(f"Non-concurrent version average time: {non_concurrent_time:.2f} seconds")

    concurrent_time = timeit.timeit("get_headlines_concurrently()", setup="from __main__ import get_headlines_concurrently", number=2) / 2
    print(f"Concurrent version average time: {concurrent_time:.2f} seconds")
  • Non-concurrent runtime, call get_headlines().
  • Concurrent runtime, call get_headlines_concurrently().
  • This step is done by calculating the average runtime of both codes. Below is the test output:
Non-concurrent version average time: 10.25 seconds
Concurrent version average time: 4.12 seconds
  • The non-concurrent version processes each URL serially, resulting in a total runtime that is the sum of each task's runtime.
  • The concurrent version uses a thread pool to process multiple URLs in parallel, downloading and parsing articles at the same time, significantly reducing runtime.
  • The performance advantage of concurrency is even more significant when the number of URLs is large or network latency is high.

3. Evaluating the Code

We try to evaluate both codes in terms of Quality.

  • Advantages:
    • The code accomplishes its goal by retrieving the top 5 news headlines from various websites using both non-concurrent and concurrent methods.
    • The function and variable names are descriptive and easy to understand, such as get_headlines and fetch_headlines.
    • The code logic is reasonable and can handle common errors, such as insufficient articles on a website, through try...except to catch IndexError.
  • Disadvantages:
    • Lack of input validation:
      • The format of the URLs in the input list is not verified for validity.
      • If an invalid URL is passed, the program might throw unhandled exceptions.
    • Redundant code:
      • The error-handling code inside the fetch_headlines function is slightly redundant, such as the two-layer try...except structure (outer layer for URL fetching exceptions, inner layer for article index exceptions), which can be optimized.
上次编辑于: 2024/11/28 09:14:10
贡献者: Xiaoxianyue
默认页脚
Copyright © 2025 XiaoXianYue