1 Introduction
AMS 325 Homework 4 (Python Mini-projects)
Due: Oct. 20th, 2023
In this homework, you will embark on two mini-projects that will challenge you to translate mathematical concepts into functional Python code. While the contexts of the tasks are Conway’s Game of Life and the PageRank algorithm, the primary objective is to hone your programming skills and deepen your understand- ing of how mathematical algorithms can be effectively implemented and analyzed using computational tools. You will write Python modules and scripts using NumPy, SciPy, and Matplotlib. Additionally, you will employ GitHub for version control and submission of your source codes. You can also try to harness the power of generative AI tools, such as ChatGPT and GitHub Copilot, for your coding. GitHub Copilot can assist with auto-completion and enhancing the documentation of your code. If you leverage ChatGPT for significant portions of your code, ensure you share the chat history to showcase your interaction with the AI. The depth and thoughtfulness of your prompts and interactions with ChatGPT will be evaluated as an integral part of your submission.
2 Task 1: PageRank Algorithm
The PageRank algorithm, originally used by Google Search to rank web pages in their search engine results, is a way of measuring the importance of website pages. It works by counting the number and quality of links to a page to determine a rough estimate of the website’s importance. By implementing the PageRank algorithm, you will gain insights into the mathematical and computational aspects of web search algorithms.
For this task, you will implement the PageRank algorithm using a simplified model.
Test Case: PageRank of Small Web Structure
Consider a small web consisting of 6 pages. The links between these pages are as follows: 1. Page A links to pages B and C.
2. Page B links to pages C and D.
3. Page C links to page A.
4. Page D links to pages B and E.
5. Page E links to pages B, D, and F. 6. Page F links to page E.
This can be visualized as a directed graph where nodes represent web pages and directed edges represent links from one page to another.
Adjacency Matrix Representation:
Based on the above structure, the adjacency matrix A (before normalization) is:
Programming Help
0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0
A=0 1 0 0 1 0 0 1 0 1 0 1
Where rows and columns correspond to pages A, B, C, D, E, and F respectively. Implementation:
1. Initialization:
• Normalize the columns of A so that they sum to 1, resulting in the matrix M.
2. PageRank Iteration:
• Initialize a vector r of size 6 with all entries equal to 61 . This represents the initial rank of the
• Update the rank using the formula: r′ = αM r + (1 − α)s where α is the damping factor (typically
set to 0.85) and s is a vector of size 6 with all entries equal to 16 .
• Iterate the above step until r converges (i.e., the difference between consecutive r values is below
a threshold of 1e − 6). 3. Analysis:
• Compare the PageRank results with the eigenvector of M corresponding to the largest eigenvalue. They should be closely related.
• Visualize the rank of the pages after each iteration to see how they converge. Verification: To verify the correctness of your implementation:
• Ensure that the columns of your matrix are normalized so that they sum to 1.
• For α = 1, the PageRank values should match the principal eigenvector of the matrix. This is because, at α = 1, the PageRank algorithm becomes equivalent to the power iteration method for finding the principal eigenvector. If you set α to this value and your PageRank values don’t match the principal eigenvector, there might be an issue with your implementation.
• Test your implementation with other matrices. Create a matrix representing a different web structure and see if your implementation gives reasonable results.
• Monitor the convergence of your algorithm. If the rank values oscillate or don’t converge, there might be an issue with your implementation.
Documentation: Ensure that your code is well documented. This includes:
• Proper docstrings for each function, explaining its purpose, inputs, and outputs.
• Comments throughout the code to explain critical or complex sections.
• A brief overview at the beginning of your script, explaining its overall purpose and any assumptions made.
• The damping factor, ‘alpha‘, is crucial. It represents the probability that a web surfer will continue
clicking on links. A typical value is 0.85, but it’s worth experimenting with other values.
• The matrix’s columns must be normalized to ensure the sum is 1. This ensures that the matrix represents a valid transition matrix for the Markov chain.
Use the ‘numpy.linalg.eig‘ function to compute the eigenvector of the matrix for verification.
Monitor the difference between consecutive rank values to determine convergence. A threshold of ‘1e-6‘ is a good starting point.
Task 2: Conway’s Game of Life
In this task, you will implement and visualize Conway’s Game of Life. This zero-player game is a classic example of cellular automata, where the evolution of the game is determined by its initial state, requiring no further input. The game consists of an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent.
Conway’s Game of Life is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. The game consists of an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent.
The rules of the game are as follows:
1. Underpopulation: Any live cell with fewer than two live neighbors dies.
2. Stasis: Any live cell with two or three live neighbors lives on to the next generation. 3. Overpopulation: Any live cell with more than three live neighbors dies.
4. Reproduction: Any dead cell with exactly three live neighbors becomes a live cell.
To simulate an infinite grid, the edges of the grid are wrapped. This means that cells on the top edge have neighbors on the bottom edge, cells on the left edge have neighbors on the right edge, and vice versa.
For testing purposes, you can use a known pattern, such as the “Glider” pattern, as an initial configura- tion.
..X X.X .XX
In the above, ‘X‘ represents a live cell and ‘.‘ represents a dead cell. The Glider pattern is a small pattern that moves diagonally across the grid. In the implementation of Conway’s Game of Life, cells can be in one of two states: alive or dead. These states can be conveniently represented using boolean variables. Specifically, a value of True can represent a live cell, while a value of False can represent a dead cell. This binary representation simplifies the computation and visualization processes. For instance, when initializing the grid or checking the state of a cell, you can directly use these boolean values to determine the cell’s state. Furthermore, when visualizing the grid, cells with a value of True (alive) can be colored black, and cells with a value of False (dead) can be colored white.
Write a Python script named game_of_life.py that can be executed from the command line as follows: python game_of_life.py 100
• 100 is the value for k, the number of evolution steps. The script should:
1. Initialization:
• Initialize a grid of size at least 20 × 20.
• Place the “Glider” pattern or any other known configuration from the Wikipedia page near the middle in the grid.
浙大学霸代写 加微信 cstutorcs
2. Evolution:
• Define a function evolve(grid) that takes the current grid as input and returns a new grid repre-
senting the next step in the evolution based on the rules mentioned above.
• Use a loop to evolve the grid for k steps, based on the value of k passed in the command line.
3. Visualization:
• Visualize the grid using Matplotlib every 10th step. Alive cells might be colored black, and dead
cells white.
• Create a gif or video of the evolution from the initial state to the final state at a frame rate of 10 frames per second.
4. Output:
• Save the final state of the grid as an image game_of_life.png.
• Save the gif or video of the evolution as game_of_life.gif or game_of_life.mp4.
5. Error Handling:
• Ensure that the value of k passed from the command line is a positive integer. If not, display an appropriate error message and exit the program.
• Handle any potential exceptions that might arise during file operations, such as saving the image or gif, and display a relevant error message.
You might find the following functions useful: numpy.zeros, numpy.random.choice, matplotlib.pyplot.imshow, matplotlib.animation.FuncAnimation.
To handle the command line arguments, consider using the sys.argv list from the sys module.
To wrap the edges of the grid and simulate an infinite grid, you can use the modulo operator % with the grid size. This ensures that cells on the edges have neighbors on the opposite edges, creating a toroidal effect.
The animation.FuncAnimation function from matplotlib can be used to create the animation of the grid’s evolution. To save the animation as a gif or mp4, you can use the animation.FuncAnimation.save method with appropriate writer settings. For example, PillowWriter can be used for saving as gif and FFMpegWriter for saving as mp4.
When evolving the grid, consider using a copy of the grid to store the new state to ensure that all cells are updated simultaneously based on the original state.
Submission Instruction
1. GitHub Repository:
• Create a private git repository on github.com.
• Push your Python script, named game_of_life.py, to the repository.
• Add a README file to your repository, elucidating the files and the procedure to run the code.
2. Code Documentation:
• Ensure that your code is well-formatted and well documented with pertinent comments to demon- strate your understanding.
• Ensure that the files are appropriately named for easy identification.
Grading Rubric
Code Correctness (60%): Your code’s correctness for both mini-projects will be evaluated. Each mini-project contributes 30
Documentation (15%): This includes the help texts, comments within your code, and the README file in your GitHub repository. Proper documentation demonstrates your understanding and ensures that others can follow your work.
Report (15%): Your report should be concise, well-structured, and should effectively communicate your approach, results, and any challenges or lessons learned.
Git Usage (10%): Proper use of git, including regular commits with meaningful commit messages, will be evaluated. This ensures version control and demonstrates your progress and thought process.
• If you’ve utilized GitHub Copilot or other AI tools, make sure to provide thorough documentation and verification within the code.
3. Sharing on GitHub:
• Share your github repository with the ams325 account on github.
• Ensure that your last commit is timestamped before the deadline. 4. Report Submission:
• Compose a concise 1–2 page report and upload the PDF file of the report onto Brightspace. • The report should encapsulate:
– The URL of your github repository shared with the ams325 account.
– A succinct description of the algorithm you employed.
– A discussion on how the code was tested, verified, and the results. Include any lessons learned
and plots seamlessly embedded.
– If you’ve engaged with AI tools like ChatGPT for generating significant portions of the code,
incorporate a link to the detailed chat history manifesting your interactions.
• You can use Microsoft Word, Google Doc, or a LaTeX-based software to craft your report.
5. Uploading Visuals:
• Upload all figures and movies generated from your code onto Brightspace.
It is paramount that you write the code independently. Generating initial code with AI tools is allowed with detailed chat history demonstrating your understanding and detailed explanation about how you verified the code in the report. Plagiarism, in any form, will not be tolerated. Do not copy full code solutions from any other source.
程序代写 CS代考 加微信: cstutorcs