Spring 2025 For this assignment you are expected to work independently, but you can share ideas and charts on Edstem. Goal The goal of this project is to identify major events that have large scale impact on Internet connectivity for individual networks or even entire countries. In this project we will learn: 1. How to leverage tools and resources, so that we can understand how a large-scale event is reflected on Internet connectivity data 2. How to perform measurements so we can measure multiple aspects of the event’s impact Task 1 First you will need to find public information about an event that had an impact on Internet connectivity for individual AS or entire countries. Example types of events are DDoS attacks, prefix hijacking, political developments, social unrest, social media censorship, an earthquake, or other physical phenomena. A specific example event is the development that took place in Myanmar and it was accompanied with Internet disruptions after midnight (UTC) on 1st February 2021. Here is a related news article. We will be using this event as an illustrated example in the project description, but please identify different events to work with. Where to find events Below we list resources that can help you find information about similar events. Of course, you are more than welcome to expand your search on the news or on additional tools and resources. • Ioda Internet Outage Detection and Analysis provides multiple events, and a feed as well. We can use the Ioda system to find information specifically for the Myanmar event and impacted ASes MPT (AS9988) and Mytel (AS136255) as shown here. • Oracle Internet Intelligence. Using the Oracle Internet Intelligence to learn about the Myanmar event as shown here. • Google traffic disruptions We can leverage the Google traffic disruptions to find out more about the Myanmar event as shown here. • Netblocks.org provides reports of disruption events. Task 1 deliverables 1. Describe in a short essay of 10-15 sentences the event that took place. 2. Identify the time period the event took place. 3. Identify the AS numbers (and associated entities or organization names) of the networks that were involved/impacted. 4. Identify a metric that is associated with the control plane behavior of one impacted AS. Briefly justify why your metric is relevant. Task 2 Study the control plane behavior of the impacted AS before, during and after the event took place. Task 2 deliverables 1) Use the PyBGPstream library to study/track this metric. Example metrics are the number of prefixes that are advertised by an origin AS, the duration between Announcement and Withdrawal for a prefix, the AS path and any changes it is associated with, change of origin AS for a prefix, advertisements with conflicting multiple origin AS for a single prefix, etc. Of course, feel free to come up with your own metric that better reflects the behavior of the AS you are studying. We will need to be able to run your code and reproduce your result. Submitting hardcoded values (instead of code that pulls data, processes it, and produces your metric values) is not acceptable and will result in a 0 for the entire project. If you need a code snippet example to get started, the below example code snippet shows how to grab data for a specific time period. https://bgpstream.caida.org/docs/tutorials/pybgpstream#moas2) Show a line graph with the metric of your choice before, during and after the event took place. The goal of this graph is to show that an aspect of the control plane behavior of a network is clearly atypical during the event. So, the x-axis of the line graph will reflect time (in a timescale of your choice), and the y-axis will show your metric. Resources • PyBGPstream • Public service for IP to AS mapping. • Python library for efficient longest prefix matching if you are given a list of origin AS and prefixes and you want a quick lookup. What to Submit To submit this project, submit your Jupyter Notebook file to the Canvas assignment page. Per the Edstem post on “How to Submit”, you will submit your Jupyter Notebook file directly to Canvas as GTLogin_iweec.ipynb — do not zip the file! Tip on Using Python notebook: Opened it in VSCode and install the Jupyter plugin for VSCode. NOTE: GTLogin should be replaced with your ID you use to log into Canvas (e.g., smith7 as in smith7_iweec.ipynb) 1. Your submission must have all the graphs generated on the page before saving! 2. Make sure your Jupyter Notebook file works in the virtual machine! That is the environment we will use to grade it. 3. When done, submit to Canvas. Then, in the VM, log into Canvas and download your submission and test it out to make sure it works there. Make sure your submission is uploaded correctly. There are no late submissions allowed, per the Syllabus. Rubric NOTE: The rubric below reflects a 100-point scale that will be adjusted to be the corresponding X% of potential extra credit. Task1 — 40 total points 1. 25 points 2. 5 points 3. 5 points 4. 5 points Task 2 – 60 total points 1. 50 points 2. 10 points Honor Code/Academic Integrity/Plagiarism Please refer to the Georgia Tech Honor Code located here: https://policylibrary.gatech.edu/student-affairs/academic-honor-code We strictly enforce Section 3. Student Responsibilities including these prohibited actions: – Unauthorized Access: Possessing, using, or exchanging improperly acquired written or verbal information in the preparation of a problem set, laboratory report, essay, examination, or other academic assignment. – Unauthorized Collaboration: Unauthorized interaction with another Student or Students in the fulfillment of academic requirements. – Plagiarism: Submission of material that is wholly or substantially identical to that created or published by another person or persons, without adequate credit notations indicating the authorship. – False Claims of Performance: False claims for work that has been submitted by a Student. What you can and cannot share 1. For this project, you can share graphs generated by the experiments 2. You may share your ideas for which event to study. 3. You are not permitted to share the raw data or code from which these graphs are generated 4. You cannot share your Jupyter Notebook ipynb file! 5. Also, do not share any data you record during experiments
Spring 2025 In this assignment, we will explore Internet Measurements, a field of Computer Networks which focuses on large scale data collection systems and techniques that provide us with valuable insights and help us understand (and troubleshoot) how the Internet works. There are multiple systems and techniques that focus on DNS measurements, BGP measurements, topology measurements, etc. There are multiple conferences in this area, which we invite you to explore and keep up with the papers that are published. The IMC conference is one of the flagship conferences in this area: ACM Internet Measurement Conference A gentle introduction into the Internet Measurement field is to work with large scale BGP measurements and data to study topics such as: • Characterizing growth of the Internet using various measures, such as number of advertised prefixes, the number of Autonomous Systems, the percentage growth of prefixes advertised by Autonomous System, and the dynamics of Autonomous System path lengths • Inferring problems related to short-lived Announcement and Withdrawals, • Inferring possible DDoS attacks by identifying community countermeasures such as “Remote Triggered Blackholing” Introduction In this project we will use the BGPStream tool and its Python interface PyBGPStream to understand the BGP protocol and interact with BGP data. The goal is to gain a better understanding of BGP and to experience how researchers, practitioners, and engineers have been using BGPStream to gain insight into the dynamics of the Internet. If you are interested in going deeper, you can use these same tools to observe and analyze real-time BGP data or download and analyze other historical BGP data. CS6250 Computer Networks BGP Measurements ProjectProject Overview and Background The zip file accompanying this assignment contains the code and data needed to implement the functions in the file bgpm.py. You will submit only bgpm.py to Gradescope and all your code for the project must be contained within bgpm.py. This project description, in combination with the comments in bgpm.py, comprise the complete requirements for the project. There are two complete sets of data included in the zip file and the provided test harness in check_solution.py will test each of your functions against both sets of data. You are welcome to copy and modify check_solution.py to better suit your development and debugging workflow, but you will have the best chance of success with the hidden data set used for grading if your final submission passes all the tests in the unmodified check_solution.py. This project is designed to work in the class VM where the BGPStream libraries are installed. Your code will need to run without modification in the course VM. Some of the functions will have runtimes of several minutes. There is a lot of data to process, so the best way to speed up those functions is by focusing on the efficiency of your implementation. It is possible, but not supported, to install BGPStream and PyBGPStream on your local machine. Please don’t ask TA staff for help if you decide to do this. Gradescope imposes a hard time limit of 40 minutes for a grading session. We have no control over this and will not be able to make any allowances if your submission does not complete within that time limit. Required Background For this project, we will be using BGPStream, an open-source software framework for live and historical BGP data analysis, supporting scientific research, operational monitoring, and postevent analysis. BGPStream and PyBGPStream are maintained by the Center for Applied Internet Data Analysis (CAIDA). CS6250 Computer Networks BGP Measurements ProjectRead the resources A high-level overview about how the BGPStream tool was developed was published by CAIDA in BGPStream: A Software Framework for Live and Historical BGP Data Analysis. This paper provides useful background and practical examples using BGPStream, so be sure to read it. Additionally, you should read African peering connectivity revealed via BGP route collectors, which provides a practical illustration of how the BGP collection system works. Run Example Code Snippets All the tasks are to be implemented using the Python interface to BGPStream. You are strongly encouraged to browse the following resources to familiarize yourself with the tool, and to run the example code snippets: – PyBGPStream API: https://bgpstream.caida.org/docs/api/pybgpstream – PyBGPStream API Tutorial: https://bgpstream.caida.org/docs/tutorials/pybgpstream – PyBGPStream Repository: https://github.com/CAIDA/pybgpstream – Official Examples: https://github.com/CAIDA/pybgpstream/tree/master/examples Important Note As will become apparent when you peruse the above documentation and tutorial information, the majority of BGPStream use cases involve gathering data – either live or historical – directly from the Route Collectors (which we refer to simply as “collectors”). The code for accessing a collector or set of collectors directly usually looks like this: stream = pybgpstream.BGPStream( record_type=”updates”, from_time=”2017-07-07 00:00:00″, until_time=”2017-07-07 00:10:00 UTC”, collectors=[“route-views.sg”, “route-views.eqix”], filter=”peer 11666 and prefix more 210.180.0.0/16″ ) Each of the parameters to pybgpstream.BGPStream() winnows the data retrieved from the collector(s). Because we are using pre-cached historical data in this project, you will not need to specify a collector or a time range. You also don’t need to use any additional filtering. CS6250 Computer Networks BGP Measurements ProjectFor this project, you can use set up and configure your streams with: stream = pybgpstream.BGPStream(data_interface=”singlefile”) stream.set_data_interface_option(“singlefile”, type, fpath) where type is one of [“rib-file”, “upd-file”]1 and fpath is a string representing the path to a specific cache file. When processing multiple files, you will create one stream per file. Familiarize Yourself with the BGP Record Format and BGP Attributes It is critical that you understand the BGP record format, especially the meaning and content of the fields (data attributes). A detailed explanation of BGP records and attributes can be found in RFC 4271: A Border Gateway Protocol 4 (BGP-4). It’s also worth spending some time exploring the provided data using the BGPReader command line tool (“a command line tool that prints to standard output information about the BGP records and the BGP elems that are part of a BGP stream”). Doing so will be particularly helpful in understanding how the fields described in RFC 4271 and elsewhere map to the BGP record and BGP elem concepts used by BGPStream and PyBGPStream. Because PyBGPStream allows you to extract the BGP attributes from BGP records using code, you will not have to interact with the BGP records in this format, but it is, nevertheless, helpful to see some examples using BGPReader to understand the fields. The next section shows Here, we will show sample command line output from BGPReader for illustration purposes: # read records from an update file, filtering for IPv4 only bgpreader -e –data-interface singlefile –data-interface-option upd-file=./rrc04/update_files/ris.rrc04.updates.1609476900.300.cache –filter ‘ipv 4’ # read records from a rib file, filtering for IPv4 only bgpreader -e –data-interface singlefile –data-interface-option rib-file=./rrc04/rib_files/ris.rrc04.ribs.1262332740.120.cache –filter ‘ipv 4’ 1 You can see a complete list of types by running: bgpreader –data-interface singlefile -o? CS6250 Computer Networks BGP Measurements ProjectUpdate Example The box below contains an example of an update record. In the record, the “|” character separates different fields. In yellow we have highlighted the type (A stands for Advertisement), the advertised prefix (210.180.224.0/19), the path (11666 3356 3786), and the origin AS (3786). update|A|1499385779.000000|routeviews|routeviews.eqix|None|None|11666|206.126.236.24|210.180.224.0/19|206. 126.236.24|11666 3356 3786|11666:1000 3356:3 3356:2003 3356:575 3786:0 3356:22 11666:1002 3356:666 3356:86|None|None RIB Example The following is a Routing Information Base (RIB) record example. Consecutive “|” characters indicate fields without data. R|R|1445306400.000000|routeviews|routeviews.sfmix|||32354|206.197.187.5|1.0.0.0/24|206.197.187.5|3235 4 15169|15169||| CS6250 Computer Networks BGP Measurements ProjectSetup Do not rely on the directory layout of the provided data. Gradescope does not mirror the directory layout from the provided files. Specifically, in your final submission, do not directly access the filesystem in any way and do not import all or part of either os or pathlib. All filesystem interaction will occur via PyBGPStream and the file paths will be taken from the Python list in the parameter named cache_files that is passed to each function. Cache Files / Snapshots Locate the directory rrc04/rib_files included with this assignment. This directory contains RIB dump files. Each filename (e.g., ris.rrc04.ribs.1262332740.120.cache) includes the collector’s name (ris.rrc04), the type of data (ribs), and the Unix timestamp of the data (1262332740, which you can convert to a date via either of the two above links). Each of the cache files is a snapshot of BGPM data collected by the collector at the time of the timestamp. In the rest of this assignment the term “snapshot” refers to the data in a particular cache file. Do not pull your own data. Your solution will be graded using cached data only. You will need to write code to process the cache files. Each entry in cache_files is a string containing the full path to a cache file. To access a given path, your code will need to set up the appropriate data interface in your BGPStream() constructor: stream = pybgpstream.BGPStream(data_interface=”singlefile”) stream.set_data_interface_option(“singlefile”, type, fpath) where type is one of [“rib-file”, “upd-file”] and fpath is a string representing the path to a specific cache file. When processing multiple files, you will create one stream per file. Tip: Your code shouldn’t make assumptions about the number of cache files. CS6250 Computer Networks BGP Measurements ProjectTask 1. Understanding BGP Routing table Growth In this task you will measure the growth over time of Autonomous Systems and advertised prefixes. The growth of unique prefixes contributes to ever-growing routing tables handled by routers in the Internet core. As optional background reading, please read the seminal paper On Characterizing BGP Routing Table Growth. Task 1A: Unique Advertised Prefixes Over Time This task will use cache files from the rib_files subdirectories. These are RIB files, so you will pass “rib-file” in your call to set_data_interface_option(). Using the data from cache files, measure the number of unique advertised prefixes over time. Each file is an annual snapshot. Calculate the number of unique prefixes within each snapshot by completing the function unique_prefixes_by_snapshot(). Make sure that your function returns the data structure exactly as specified in bgpm.py. Task 1B: Unique Autonomous Systems Over Time This task will use cache files from the rib_files subdirectories. These are RIB files, so you will pass “rib-file” in your call to set_data_interface_option(). Using the data from the cache files, measure the number of unique Autonomous Systems over time. Each file is an annual snapshot. Calculate the number of unique ASes within each snapshot by completing the function unique_ases_by_snapshot(). Make sure that your function returns the data structure exactly as specified in bgpm.py. Note: Consider all paths in each snapshot. Here, we consider all AS that appear in the paths (not only the origin AS). You may encounter corner cases of paths with the following form: “25152 2914 18687 {7829,14265}”. In this case, consider the AS in the brackets as a single AS. So, in this example, you will count 4 distinct ASes. CS6250 Computer Networks BGP Measurements ProjectTask 1C: Top-10 Origin AS by Prefix Growth This task will use cache files from the rib_files subdirectories. These are RIB files, so you will pass “rib-file” in your call to set_data_interface_option(). Using the data from the cache files, calculate the percentage growth in advertised prefixes for each AS over the entire timespan represented by the snapshots by completing the function top_10_ases_by_prefix_growth(). Make sure that your function returns the data structure exactly as specified in bgpm.py. Consider each origin AS separately and measure the growth of the total unique prefixes advertised by that AS from its first appearance to its last appearance. To compute this, for each origin AS: 1. Identify the snapshots where the origin AS first appears and last appears in the dataset. Note: An AS is not guaranteed to appear in every snapshot, nor it is guaranteed to appear in the first and last snapshots. 2. Calculate the percentage increase of the advertised prefixes, using the identified first and the last snapshot appearances. For example, assuming 5 given cache files, let’s say AS X first appeared in the 2nd snapshot and last appeared in the 4th and advertised the following number of prefixes: [0, 124, 215, 512, 0] The percentage increase would then be: (512−124) 124 = 3.13 or 313% 3. Report the top 10 origin AS that experienced the largest growth, and sort those from smallest to largest. Note: There are no ties, so don’t worry about implementing tie-breaking. Edge case: When calculating the prefixes originating from an origin AS, you may encounter paths of the following form: “25152 2914 18687 {7829,14265}”. This is an edge case, and it should affect only a small number of prefixes. In this case, you consider the entire set of AS “{7829,14265}” as the origin AS. CS6250 Computer Networks BGP Measurements ProjectTask 2: Routing Table Growth: AS-Path Length Evolution Over Time In this task you will measure if an AS is reachable over longer or shorter path lengths as time progresses. Towards this goal you will measure the AS path lengths, and how they evolve over time. This task will use cache files from the rib_files subdirectories. These are RIB files, so you will pass “rib-file” in your call to set_data_interface_option(). Using the data from the cache files, calculate the shortest path for each origin AS in each snapshot by completing the function shortest_path_by_origin_by_snapshot(). Make sure that your function returns the data structure exactly as specified in bgpm.py. For each snapshot, you will compute the shortest AS path length for each origin AS in the snapshot by following the steps below: – Identify each origin AS present in the snapshot. For example, given the path “11666 3356 3786”, “3786” is the origin AS. – For each origin AS, identify all the paths for which it appears as the origin AS. – Compute the length of each path by considering each AS in the path only once. In other words, you want to remove the duplicate entries for the same AS in the same path and count the total number of unique AS in the path. – Example: Given the path “25152 2914 3786 2914 18313”, ”18313” is the origin AS and ”2914” appears twice in the path. This is a path of length 4. – Among all the paths for an AS within the snapshot, compute the shortest path length. – Filter out all paths of length 1. – Corner cases: The data that we are working with are real data, which means that there may be few corner cases. In the vast majority of cases, paths have a straightforward form of “25152 2914 3786”, but you might encounter corner cases such as: a. If an AS path has a single unique AS or a single repeated AS (e.g., “25152 25152 25152”), the path has length 1 and should be ignored b. An AS path entry that looks like “{2914,14265}” is an aggregate or AS_SET and constitutes a single AS path entry. It does not need to be parsed in any way. You can read more about aggregation in RFC 4271. CS6250 Computer Networks BGP Measurements ProjectExample: The length of the AS path “25152 2914 18687 {2914,14265} 2945 18699” is 6. Example: The length of the AS path “25152 2914 18687 18687 {18687}” is 4. The entries “18687” and “{18687}” are distinct, so you only deduplicate “18687”. c. You can ignore all other corner cases.CS6250 Computer Networks BGP Measurements ProjectTask 3: Announcement-Withdrawal Event Durations In this task, we will measure how long prefix Announcements last before they are withdrawn. This matters because, when a prefix gets Advertised and then Withdrawn, this information propagates and affects the volume of the associated BGP traffic. Optional background reading on this topic can be found in The Shape of a BGP Update. This task will use cache files from the update_files subdirectories. These are update files, so you will pass “upd-file” in your call to set_data_interface_option(). Using the data from the cache files, we will measure how long prefix Announcements last before they are withdrawn by completing the function aw_event_durations(). Make sure that your function returns the data structure exactly as specified in bgpm.py. In defining Announcement Withdrawal (AW) events, we will only consider explicit withdrawals. An explicit withdrawal occurs when a prefix is advertised with an (A)nnouncement and is then (W)ithdrawn. In contrast, an implicit withdrawal occurs when a prefix is advertised (A) and then re-advertised (A) – usually with different BGP attributes. To compute the duration of an Explicit AW event for a given peerIP/prefix, you will need to monitor the stream of (A)nnouncements and (W)ithdrawals separately per peerIP/prefix pair. – Example: Given the stream: A1 A2 A3 W1 W2 W3 W4 for a specific peerIP/prefix pair, you have an implicit withdrawal A1-A2, another implicit withdrawal A2-A3, and, finally, an explicit withdrawal (and AW event) A3-W1. W1-W2, W2-W3, and W3-W4 are all meaningless, as there’s no active advertisement. The duration of the AW event is the time difference between A3 and W1. Again, we are only looking for last A and first W. – Example: Given the stream: A1 A2 A3 W1 W2 W3 W4 A4 A5 W4 for a specific peerIP/prefix pair, we have two AW events at A3-W1 and A5-W4. – We consider only non-zero AW durations. CS6250 Computer Networks BGP Measurements ProjectTask 4: RTBH Event Durations In this task you will identify and measure the duration of Real-Time Blackholing (RTBH) events. You will need to become familiar with Blackholing events. Good resources for this include RFC 7999, Section 2, BGP communities: A weapon for the Internet (Part 2), and the video Nokia – SROS: RTBH – Blackhole Community. This task will use cache files from the update_files_blackholing subdirectories. These are update files, so you will pass “upd-file” in your call to set_data_interface_option(). Using the data from the cache files, we will identify events where prefixes are tagged with a Remote Triggered Blackholing (RTBH) community and measure the time duration of the RTBH events by completing the function rtbh_event_durations(). Make sure that your function returns the data structure exactly as specified in bgpm.py. The duration of an RTBH event for a given peerIP/prefix pair is the time elapsed between the last (A)nnouncement of the peerIP/prefix that is tagged with an RTBH community value and the first (W)ithdrawal of the peerIP/prefix. In other words, we are looking at the stream of Announcements and Withdrawals for a given peerIP/prefix and identifying only explicit withdrawals for an RTBH tagged peerIP/prefix. To identify and compute the duration of an RTBH event for a given peerIP/prefix, you will need to monitor the stream of (A)nnouncements and (W)ithdrawals separately per peerIP/prefix pair. – Example: Given the stream: A1 A2 A3(RTBH) A4(RTBH) W1 W2 W3 W4 for a specific peerIP/prefix pair, A4(RTBH)-W1 denotes an RTBH event and the duration is calculated by taking the time difference between A4(RTBH) and W1. – Note: There can be more than one RTBH event in a given stream. For example, in the stream A1 A2 A3(RTBH) A4(RTBH) W1 W2 W3 W4 A5(RTBH) W5, there are two RTBH events: A4(RTBH)-W1 and A5(RTBH)-W5. CS6250 Computer Networks BGP Measurements Project– Example: Given the stream A1 A2 A3(RTBH) A4 A5 W1 W2 for a specific peerIP/prefix pair, the announcement A3(RTBH) followed by A4 is an implicit withdrawal. There is no explicit withdrawal and, thus, no RTBH event. – In case of duplicate announcements, use the latest. – Consider only non-zero duration events.CS6250 Computer Networks BGP Measurements ProjectSubmission Submit bgpm.py to Gradescope. Grading Rubric Points Task to be completed 10 Task 1A 10 Task 1B 10 Task 1C 30 Task 2 20 Task 3 20 Task 4 100 Total PointsHonor Code / Academic Integrity / Plagiarism Please refer to the Georgia Tech Honor Code located here: https://policylibrary.gatech.edu/student-affairs/academic-honor-code We strictly enforce Section 3. Student Responsibilities including these prohibited actions: – Unauthorized Access: Possessing, using, or exchanging improperly acquired written or verbal information in the preparation of a problem set, laboratory report, essay, examination, or other academic assignment. – Unauthorized Collaboration: Unauthorized interaction with another Student or Students in the fulfillment of academic requirements. – Plagiarism: Submission of material that is wholly or substantially identical to that created or published by another person or persons, without adequate credit notations indicating the authorship. – False Claims of Performance: False claims for work that has been submitted by a Student. CS6250 Computer Networks BGP Measurements ProjectIn addition, the usage of AI tools such as ChatGPT in assisting and/or completing part or all of your project is explicitly prohibited. Even if they are used for just one task, that constitutes an academic integrity violation and you will receive a 0 for the entire project. The same holds true if you are found to have accessed and utilized external resources such as non-CAIDA GitHub repositories containing partial or complete solutions, other student solutions (past or present), or solutions uploaded to sites like CourseHero. Even if said resources are used for just one task, that constitutes an academic integrity violation and you will receive a 0 for the entire project. Official resources and those referenced in the project document such as the official Python documentation, official CAIDA documentation, code examples, repositories, etc. do not need to be cited. If you reference unofficial coding/programming resources such as W3Schools, Stack Overflow, etc. please cite them in your code. If you are struggling with certain tasks, ask for help from your peers and/or the teaching staff on Ed Stem, come to office hours, and if all else fails, move on to other tasks so you can at least get partial points on the project. That is far better than receiving a 0 for the entire project due to an academic integrity violation.
Spring 2025 In this project you will explore a vulnerability of the Border Gateway Protocol (BGP). Specifically, your goal is to recreate a BGP Hijacking attack where a “rogue” AS (autonomous system) hijacks a prefix from another AS, thereby “stealing” traffic. As discussed in Lesson 4, “An AS is a connected group of one or more IP prefixes run by one or more network operators which has a SINGLE and CLEARLY DEFINED routing policy.” An AS can be an Internet Service Provider (ISP), an IXP (where ISP’s and CDN’s exchange local traffic), or a CDN (e.g., Netflix and Google). Each AS has border routers that utilize BGP to exchange routing information with one another. The prefixes advertised by BGP are used to implement routing policies, which makes cooperation amongst ASs very important. The flexibility and scalability that BGP allows, however, comes with a cost in security. From Wikipedia: By design, routers running BGP accept advertised routes from other BGP routers by default. This allows for automatic and decentralized routing of traffic across the Internet, but it also leaves the Internet potentially vulnerable to accidental or malicious disruption, known as BGP hijacking. Due to the extent to which BGP is embedded in the core systems of the Internet, and the number of different networks operated by many different organizations which collectively make up the Internet, correcting this vulnerability (such as by introducing the use of cryptographic keys to verify the identity of BGP routers) is a technically and economically challenging problem. What Is BGP Hijacking? BGP hijacking occurs when an attacker attempts to re-route (steal) traffic by issuing a BGP Route Advertisement for an IP prefix that is owned or controlled by another AS. Such an attack causes routing disruptions and connectivity issues for individual hosts, networks, and sometimes even entire countries. A simple search will turn up lots of information about notable public incidents. Because BGP favors shorter routes and more specific routes by design, a hijacking event can occur (either deliberately or by accident) when an AS advertises a prefix for which it is not the true originator and that prefix: • duplicates a correct advertisement, but has a shorter path • is more specific than another correct advertisement 3 What happens when BGP is hijacked? When a hijack occurs, it can cause: • dropped traffic (causing disruption), • re-routed traffic (allowing an attacker to, for example, steal credentials), and/or • increased latency (causing performance degradation) Even though the victim AS thinks the route is shorter, the reality is it may be a lot longer than the previous advertised routes. The best-case scenario of an attack is that the hijacked route will only increase latency by steering traffic to a much longer route. The worst case scenario of an attack is that an attacker re-routes traffic to a malicious site to steal confidential information. BGP hijacking in the real world Attackers can use BGP hijacking in the real world to steal confidential data or electronic assets, such as when a Russian government-controlled telecom re-routed large chunks of network traffic belonging to MasterCard, Visa, and more than two dozen other financial services in 2017 or when hackers stolen almost $2m from South Korean cryptocurrency platform KLAYswap in 2022. Hijack incidents can also occur when routes “leak” by mistake, such as when AS55410 (controlled by Vodafone Idea Ltd.) mistakenly announced over 30,000 BGP prefixes causing a 13x spike in inbound traffic to their network or when Con Edison “stole the Internet” for most of a full day. Read What is BGP hijacking? For a terrific overview. 4 Goal In this project, which is based on the BGP Path Hijacking Attack Demo included in the Mininet project, we will explore some of the vulnerabilities of Border Gateway Protocol (BGP). In particular, we will see how BGP is vulnerable to abuse and manipulation through a class of attacks called BGP hijacking attacks. A malicious AS can mount these attacks through false BGP announcements from a rogue AS, causing victim ASes to route their traffic bound for another AS through the malicious AS. This attack succeeds because the false advertisement exploits BGP routing behavior by advertising a shorter path to reach a particular prefix, which causes victim ASes to attempt to use the newly advertised (and seemingly better!) route. In this project you will explore a vulnerability of the Border Gateway Protocol (BGP). Specifically, your goal is to recreate a BGP Hijacking attack where a “rogue” AS (autonomous system) hijacks a prefix from another AS, thereby “stealing” traffic. 5 BGP Hijacking Simple Demo This is a demo to help better understand BGP Hijacking on mininet. Part 1: Background reading Please read the resources, and example BGP router configurations. And the project slide. A. Browse this paper as a reference for subsequent tasks and for some important background on Prefix Hijack Attacks. B. Refer to this resource on configuring a BGP router with Quagga. Also, the FRR docs for zebra can be helpful as well. C. The “BGP Bible” is here https://www.cisco.com/c/en/us/td/docs/ios/iproute_bgp/command/reference/irg_book.html Part 2: Demonstration using a Mininet Topology and simulated prefixes/paths The demo creates the network topology shown below, consisting of four ASes and their peering relationships. AS4 is the malicious AS that will mount the attack. Once again, we will be simulating this network in Mininet, however there are some important distinctions to make from our previous projects. In this setup, each object is not a single host, but an entire autonomous system. In each AS, a router runs a routing daemon (quagga), communicates with other ASes using BGP (bgpd), and configures its own isolated set of routing entries in the kernel (zebra). Each AS router has multiple IP addresses, to connect to the hosts in the AS and to other routers. 6 NOTE: In this topology solid lines indicate peering relationships, and the dotted boxes indicate the prefix advertised by that AS. STEPS TO START DEMO As part of completing this project, 1. Download and unzip the project files. This should create a directory named BGPHijacking (the “Project Directory”). The file permissions and ownership should be correct, but if not, adjust them appropriately. It’s okay to freely discuss this aspect of the project on Edstem. 2. For some of the steps below, you will use the sudo command. You might be asked to enter your password. If sudo asks you to enter a password, use “mininet.” 3. Open a terminal in the Project Directory. Type: sudo python ./bgp.py. After loading the topology, the Mininet CLI should be visible. Keep this terminal open throughout the experiment. 4. Open a second terminal in the Project directory. You will use this terminal to access R1’s routing daemon (bgpd). Do that by executing the following command: ./connect.sh 5. The connect.sh script uses run.py to connect to the bgpd shell on the router specified in the variable $router. Accessing the bgpd shell will start quagga, which will ask for a password. The password is: “en”. Once you have authenticated, you will have access to the administration shell and R1 routing table. When you get the bgpd-R1# prompt, type the following command: sh ip bgp 6. You should see output very much like the screen grab below. Notice that AS1 has chosen the path via AS2 and AS3 to reach the prefix 13.0.0.0/8. NOTE: It may take a minute for the routes to settle. Try the command until you see all three routes. 7. Next, verify that network traffic is traversing this path. Open a third terminal in the Project Directory (keeping all other terminals open). In this terminal, you will start a script that continuously makes web requests from a host within AS1 to a web server in AS3. Type in the following: ./website.sh 8. Now, you will start a rogue AS (AS4) that will connect directly to AS1 and advertise the same 13.0.0.0/8 prefix. This will allow AS4 to hijack the prefix due to the shorter AS Path 7 Length. Open a third terminal in the Project Directory (keeping all other terminals open) and type the following: ./start_rogue.sh 9. Return to the third terminal window and observe the continuous web requests. After the BGP routing tables converge on this simple network, you will see the attacker start responding to requests from AS1, rather than AS3. 10. You should also return to the second terminal and rerun the command to print the routing table. You should now see the fraudulent advertisement for the 13.0.0.0/8 prefix in the routing table, in addition to the longer unused path to the legitimate owner of the route. 11. Finally, stop the attack by switching to the fourth terminal and typing: ./stop_rogue.sh 12. You should notice a fast reconvergence to the original legitimate route in the third terminal window, which should now be delivering the original traffic. Additionally, you can check the BGP routing table again to see that the original path is being traversed. 8 BGP Hijacking Attack This is the graded part of the project. Part 1: Simple BGP Hijacking on a customized topology Your task is to replicate a different topology and attack scenario to demonstrate the effects of a Prefix Hijack Attack. Your goal is to impersonate true origin AS1 using the false origin AS6. IMPORTANT NOTE: It’s recommended to build your attack scenario off the demo files. Make a backup of your demo files so you can refer to them as you modify the files. STEPS FOR YOUR ATTACK SCENARIO Topology for the project’s hijack scenario (Figure 2 in the paper) 1. First, according to the topology above taken from Figure 2 in the referenced paper. Draw a topology map using any drawing tool of your choice. See Slide 7 of the presentation slides for an example of the level of detail desired in your topology diagram. You may hand-draw your topology with pencil and paper and scan or photograph your drawing. All configuration values drawn on the map must be legible! Save your topology diagram in PDF format with the name fig2_topo.pdf. You must use this filename as part of your submission to receive credit for your diagram. We find that if you do your diagram first, the following steps will be much easier! 2. We recommend making a copy of the code provided to you in the Project files (the full demo folder). This will make it easier to complete this project, and you will likely find it 9 more approachable if you spend time exploring the demo code and fully understanding how each part works rather than immediately trying to edit the code. 3. Next, refer to the topology above or in the paper, and create/edit the necessary files to reconstruct the topology. (TIPS: BGP message won’t be propagated before establishing connectivity between nodes) Please figure out all the config files and python/shell scripts to edit to carry out the attack on the topology. After modifying all the necessary files, you should be able to use the commands from the demo to recreate the attack on the new topology you built in the Project Directory. You can assume the following: • All links are bidirectional peering links. • Each AS advertises a single prefix: AS1: 11.0.0.0/8, AS2: 12.0.0.0/8, AS3: 13.0.0.0/8, AS4: 14.0.0.0/8, AS5: 15.0.0.0/8, AS6: 11.0.0.0/8 • The number of hosts in each AS is the same as in the provided code (the demo). • You don’t need to modify the helper scripts (run.py, webserver.py, connect.sh), and you should read through all the shell scripts. 4. Do not change passwords in zebra and conf files. If you change the passwords, the autograder will fail, resulting in 0 for the assignment. All passwords need to follow the demo and be ‘en’ 5. Do not change the names of the config files, follow the pattern when creating new config files. 6. When complete, you should be able to use the commands from the demo to start a Rogue AS and demonstrate a similar change in routing table information as was shown in the demo and see the screen printout (website.sh) as in the demo. Your goal is to impersonate true origin AS1 using the false origin AS6. The attack should be observed on hosts connected to AS5. 10 Part 2: Advanced BGP Hijacking on a customized topology Your task is to demonstrate an advanced BGP Hijacking based on the topology you just created. Your goal is to also observe the attack on the whole network (besides the true origin). STEPS FOR YOUR ATTACK SCENARIO Topology for the project’s hijack scenario (Figure 2 in the paper) 1. After completing part 1, you should be able to see the attack on hosts connected to AS5. But for hosts connected to, say AS2, they won’t be affected. Why? (You may use “./website.sh h2-1” to check it) 2. Your goal is to also see the attack on hosts connected to other AS, using AS6 as a false origin (basically, impersonate AS1 and hijack the whole network). 3. Please read the start_rogue_hard.sh, this is used to carry out the advanced attack. Create/edit necessary configs according to the start_rogue_hard.sh script. 4. After completion, you should observe hosts connected to AS2. (All the hosts connected to AS other than AS1 should be able to see the attack) 5. You may use “./website.sh h[2-5]-[1,2]” to check it 6. You must use AS6 as the false origin, you should not modify start_rogue_hard.sh. 7. Tips: o Try to understand the BGP protocol, different type of BGP Hijacking, and the rationale behind prefix hijacking. o Only config modification is needed for this part. You should be able to reuse your bgp.py and other scripts from part 1. o You are free to modify the prefix AS6 is broadcasting. 11 Appendix: Configuration Debugging Tips • Ensure connectivity between routers suing Zebra before working on the BGP messages. • When viewing the BGP Tables note the “Status codes”. Give your topology enough time to converge before recreating the hijack simulation portion. It may take a minute or so for your topology to fully converge. You may continue to check the BGP Tables to determine whether the topology has converged • The order that you set up your peering links using addLink() matters. In previous projects, we manually selected which port on the switch to use. There is an optional parameter to the addLink() call which allows you to specify which switch port to use. In this project, you will not use those options. Therefore, the order of the links matters. • Some of the commands in the boilerplate code may not be necessary to complete the graded part. Some of it is there just so that you know it exists. • Check for more descriptive errors in the /logs directory. See the zebra files for the location of additional log files. • Run “links” on the Mininet CLI terminal to see if all links are connected and OK. • Run “net” on the Mininet CLI terminal to see if your ethernet links are connected as you expect. • Run “ifconfig -a” on all routers and hosts to ensure that all IP addresses are assigned correctly. • Run “sh ip bgp” and “sh ip bgp summary” on all routers. • The command pingall may not work and that is fine. • The website.sh may sometimes hang intermittently. If this happens restart the simulation. We are aware of this issue, and we keep this in mind as we grade your submission. You will not lose points if website.sh hangs so long as we are eventually able to run the simulation. • Again, read all the provided scripts. 12 What to Turn In: Your BGP Hijacking on a more complex topology For this project you need to turn in all the files that are necessary for your code to run. Please submit your code to Gradescope. Be sure to use the -r option so your conf and logs subdirectories are part of the zip file Use the following command to zip for t: zip -r bgph.zip BGPHijacking/ You need to make sure the pdf file fig2_topo.pdf is present inside your BGPHijacking directory along with all files and directories to run the attack scenario you created. Run the above zip command when above your project folder. Zip the directory BGPHijacking. All the files and folders needed must be in the BGPHijacking folder – zip the files in the VM using the Linux command is recommended. Please submit the zip archive to Gradescope section “BGP Hijacking”. And please note that: • Improper zip structure will result in Gradescope autograder failure, please adjust the folder structure and resubmit if you encounter “Sanity Test Failure” on Gradescope • The correct folder structure should show “BGPHijacking/” as a folder in front when uploading onto Gradescope • Please note that the autograder may take up to 10 minutes to process your assignment. As the deadline approaches and traffic increases, the grading time may be further delayed, and in some cases, the system may time out. To avoid these issues, we strongly recommend submitting your assignment early. We are not responsible for delays caused by last-minute submissions. 13 WHAT YOU CAN AND CAN NOT SHARE While discussion of the project, in general, is always permitted on Edstem, you are not permitted to share your code generated for the graded part. You may quote snippets of the unmodified skeleton code provided to you when discussing the project. • You may not share the topology diagram you created in. (private post to instructors is always OK) • You may not share your IP addresses publicly (private post to instructors is always OK) • Sharing of completed code pseudo code is ok, but if in doubt, please make a private post to the instructors. 14 RUBRIC (out of 150 points) 5 pts Fig 2 Topo Diagram For turning in the correctly named Topology diagram file: fig2_topo.pdf Please use legible configuration values! Even autograder give full points on the diagram, we will manually deduct points of this part if it’s not legible. 125 pts BGPHijacking Part 1 For accurately recreating the topology, links, router configuration, and attack per the instructions. Partial credit is available for this rubric item as follows: 10 points for efforts in router configuration (zebra/bgp). 30 points for accurately recreating the topology, links, connectivity. 40 points for seeing default message when you run website.sh, on hosts h[1-5]-[1,2], we will randomly choose some hosts to test. 40 points for seeing attack message with website.sh h5-1 after running start_rogue.sh, and default message on other hosts. 5 points for seeing default message after stop_rogue.sh is run. 20 pts BGPHijacking Part 2 20 points for seeing default message on h1-1, and attack message on other hosts (h[2-5]-[1,2]). We will randomly choose some hosts to test. [1] This Project inspired by a Mininet Demo originally presented at SIGCOMM 2014. Bibliography Cloudflare. (n.d.). Retrieved 2020, from cloudflare.com: https://www.cloudflare.com/learning/security/glossary/bgp-hijacking/
Spring 2025 In this project, you will use Software Defined Networking (SDN) principles to create a configurable firewall using an OpenFlow enabled Switch. The Software Defined Networking (OpenFlow) functionality allows you to programmatically control the flow of traffic on the network. This project has two phases (and one optional phase) as follows: 1. Mininet Tutorial – This phase is a brief overview of Mininet. There are no deliverables for this phase and may be skipped, especially if you completed the Optional Simulating Networks project (Project 0). You will find this information in Appendix D. 2. Wireshark Tutorial – This phase is a brief introduction to packet capture using Wireshark/tshark. You will examine the packet format for various traffic to learn of the different header values used in Phase 3. There is a deliverable of a simple packet capture file. 3. SDN Firewall – This phase involves completing code to build a simple traffic blocking firewall using OpenFlow with the POX Controller based on rules passed to it from a configuration file. In addition, you will create a set of rules to test the firewall implementation. Part 0: Project References You will find the following resources useful in completing this project. It is recommended that you review these resources before starting the project. • IP Header Format – https://erg.abdn.ac.uk/users/gorry/course/inet-pages/ip-packet.html • TCP Packet Header Format – https://en.wikipedia.org/wiki/Transmission_Control_Protocol • UDP Packet Header Format – https://en.wikipedia.org/wiki/User_Datagram_Protocol • The ICMP Protocol – https://en.wikipedia.org/wiki/Internet_Control_Message_Protocol • IP Protocols – https://en.wikipedia.org/wiki/List_of_IP_protocol_numbers • TCP and UDP Service and Port References – https://en.wikipedia.org/wiki/List_of_TCP_and_UDP_port_numbers • Wireshark – https://www.wireshark.org/docs/wsug_html/ • CIDR Calculator – https://account.arin.net/public/cidrCalculator • CIDR – https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing There are a few videos describing various aspects of the project: • Project Description – https://youtu.be/Kl4nRgoeLxw • Wireshark Tutorial – https://youtu.be/AnTi1m0imVk • IP Network Address / Subnets / CIDR – See Edstem • How to Manually Test – https://youtu.be/dj323mdA3sg 3 Part 1: Files Layout Unzip the SDNFirewall-Fall2024zip file into your Virtual Machine. You can extract to any folder on your system. Do this by running the following command: unzip SDNFirewall-Fall2024.zip This will extract the files for this project into a directory named SDNFirewall at your current path (it is recommended that your use the mininet root directory to aid in troubleshooting (cd ~ ). The following files will be extracted: • cleanup.sh – this file called by using following command line: ./cleanup.sh This file will clean up the Mininet Environment and kill all zombie Python and POX processes. • sdn-topology.py – this file creates the Mininet topology used in this assignment. This is like what you created in the Simulating Networks project. When evaluating your code against the ruleset specified in this project, do not change it. However, you are encouraged to make your own topologies (and rules) to test the firewall. Look at the start-topology.sh file to see how to start a different topology. • ws-topology.py – this file is substantially like sdn-topology, but it does not call the POX Controller. You will use this during the Wireshark exercise. • setup-firewall.py – this file sets up the frameworks used in this project. DO NOT MODIFY THIS FILE. This file will create the appropriate POX framework and then integrates the rules implemented in sdnfirewall.py into the OpenFlow engine. It will also read in the values from the configure.pol file and validate that the entries are valid. If you make changes to this file, the autograder will likely have issues with your final code as the autograder uses the unaltered distribution version of this file. • start-firewall.sh – this is the shell script that starts the firewall. This file must be started before the topology is started. It will copy files to the appropriate directory and then start the POX OpenFlow controller. This file is called by using following command line: ./start-firewall.sh • start-topology.sh – this is the shell script that starts the Mininet topology used in the assignment. All it does is call the sdn-topology.py file with superuser permissions. This file is called by using following command line: ./start-topology.sh • test-client.py – this is a python test client program used to test your firewall. This file is called using the following command line: python test-client.py PROTO SERVERIP PORT SOURCEPORT where PROTO is either T for TCP, U for UDP, or G for GRE, SERVERIP is the IP address of the server (destination), PORT is the destination port, and optionally SOURCEPORT allows you to configure the source port that you are using. Example: python test-client.py T 10.0.1.1 80 • test-server.py – this is a python test server program used to test your firewall. This file is called using the following command line: python test-server.py PROTO SERVERIP PORT where PROTO is either T for TCP, U for UDP, G for GRE, SERVERIP is the IP address of the server (the server you are running this script on), and PORT is the service port. Example: python test-server.py T 10.0.1.1 80 • test-suite – This is a student developed test script that was developed in 2021 that can be used to test your implementation AFTER YOU FINISH BOTH THE IMPLEMENTATION FILES. The test cases in the main folder will be used to evaluate your implementations for the first run. An alternate configuration and 4 topology will also be used to evaluate your implementations. This will be like, but not identical to what is found in the extra sub-folder. See Appendix A for information on how to use the test suite. Project Deliverables • configure.pol – this file is where you will supply the configuration to the firewall that specifies the traffic that should either be blocked or allowed (override blocks). The format of this file will be specified later in this document. This file is one of the deliverables that must be included in your ZIP submission to Canvas. • sdn-firewall.py –This file implements the firewall using POX and OpenFlow functions. It receives a copy of the contents of the configure.pol file as a python list containing a dictionary for each rule and you will need to implement the code necessary to process these items into POX policies to create the firewall. This file is one of the deliverables that must be included in your ZIP submission to Canvas. • packetcapture.pcap – This will be the packet capture completed in Part 4. This file is one of the deliverables that must be included in your ZIP submission to Canvas. Part 2: Mininet If you did not complete the Simulating Networks Optional Project, you may want to review the “Mininet Review” section in Appendix D to learn about the different aspects of how a mininet network is setup, including how to configure the physical topology and assignment of addresses to hosts and switches. Part 3: Wireshark Wireshark is a network packet capture program that will allow you to capture a stream of network packets and examine them. Wireshark is used extensively to troubleshoot computer networks and in the field of information security. We will be using Wireshark to examine the packet headers to learn how to use this information to match traffic that will be affected by the firewall we are constructing. tshark is a command line version of Wireshark that we will be using to capture the packets between mininet hosts and we will use Wireshark for the GUI to examine these packets. However, you will be allowed to use the Wireshark GUI if you would like in doing the packet capture. Please watch the Wireshark Tutorial Video if you would like to follow along in time for a live packet capture. • Step 1: Open up a Terminal Window and change directory to the SDNFirewall directory that was extracted in Part 1. • Step 2: The first action is to start up the Mininet topology used for the Wireshark capture exercise. This topology matches the topology that you will be using when creating and testing your firewall. To start this topology, run the following command: sudo python ws-topology.py This will startup a Mininet session with all hosts created. If you use sdn-topology.py, you will get a controller error. Ctrl-C and redo step 2 to get the correct topology. 5 • Step 3: Start up two xterm windows for hosts us1 and us2. After you start each xterm window, it is recommended that you run the following command in each xterm window as you load them to avoid confusion about which xterm belongs to which host: export PS1=”hostname >” replacing hostname with the actual hostname. Type in the following commands at the Mininet prompt. This is optional, but helps with identifying which xterm window belongs to which host. us1 xterm & (then run export PS1=”us1 >” in the xterm window that pops up) us2 xterm & (likewise, run export PS1=”us2 >” in the second xterm window) • Step 4: In this step, we want to start capturing all the traffic that traverses through the ethernet port on host us1. We do this by running tshark (or alternatively, wireshark) as follows from the mininet prompt: us1 sudo tshark -w /tmp/packetcapture.pcap This will start tshark and will output a pcap formatted file to packetcapture.pcap to the tmp directory. Note that this file is created as root, so you will need to change ownership to mininet to use it in future steps – chown mininet:mininet /tmp/packetcapture.pcap If you wish to use the Wireshark GUI instead of tshark, you would call us1 sudo wireshark &. You may use this method, but the TA staff will not provide support for any issues that may occur. YOU WILL SUBMIT THIS FILE AS A PART OF YOUR SUBMITTAL. • Step 5: Now we need to capture some traffic. Do the following tasks in the appropriate xterm window: in us1 xterm: ping 10.0.1.2 (hit control C after a few ping requests) In us2 xterm: ping 10.0.1.1 (likewise hit control C after a few ping requests) In us1 xterm: python test-server.py T 10.0.1.1 80 In us2 xterm: python test-client.py T 10.0.1.1 80 After the connection completes, in the us1 xterm, press Control-C to kill theserver. In us1 xterm: python test-server.py U 10.0.1.1 8000 In us2 xterm: python test-client.py U 10.0.1.1 8000 In us1 xterm: press Control C to kill the server In Mininet Terminal: press Control C to stop tshark • Step 6: At the mininet prompt, type in exit and press enter. Next, do the chown command as described in step 4 above to your packet capture. You may also close the two xterm windows as they are finished. Copy the /tmp/packetcapture.pcap to your project directory. This file is the deliverable for this phase of the project. See the instructions in Step 4 that describe how you will need to change ownership of this file in order to change or move it. 6 • Step 7: At the bash prompt on the main terminal, run: sudo wireshark Go to the File => Open menu item, browse to the /tmp directory and select the pcap file that you saved using tshark. You will get a GUI that looks like the example packet capture. You will have a numbered list of all the captured packets with brief information consisting of source/destination, IP protocol, and a description of the packet. You can click on an individual packet and will get full details including the Layer 2 and Layer 3 packet headers, TCP/UDP/ICMP parameters for packets using those IP protocols, and the data contained in the packet. Example Packet Capture – Host us1 making web request to Host us2 Note the highlighted fields. You will be using the information from these fields to help build your firewall implementation and ruleset. Note the separate header information for TCP. This will also be the case for UDP packets. Also, examine the three-way handshake that is used for TCP. What do you expect to find for UDP? ICMP? Example TCP Three-Way Handshake Please examine the other packets that were captured to help you familiarize yourself with Wireshark. 7 Part 4: SDN Firewall Implementation Details Using the information that you learned above in running Wireshark, you will be creating two files – one is a firewall configuration file that will specify different header parameters to match in order to allow or block certain traffic that will define the actions of the firewall and the second is the implementation code to create the OpenFlow Flow Modification objects that will create the firewall using the parameters given in the firewall configuration file. Part 4a: Specifications of configure.pol The configure.pol file is used by the firewall implementation code to specify the rules that the firewall will use to govern a connection. You do not need to code this first, but the format of the file is important to understand as your implementation code will need to use these items. The format of the file is a collection of lines that have the proper format: Rule Number, Action, Source MAC, Destination MAC, Source IP Network Address, Destination IP Network Address, Protocol, Source Port, Destination Port, Comment/Note o Rule Number = this is a rule number to help you track a particular rule – it is not to be used at all in your firewall implementation except to help you find rules that cause an error. DO NOT USE FOR PRIORITY. o Action = Block or Allow Block rules will block traffic that matches the remaining parameters of this rule. Allow rules will override Block rules to allow specific traffic to pass through the firewall (see below for an example). The entry is a string in (Block,Allow) and is validated by the parser. o Source / Destination MAC address in form of xx:xx:xx:xx:xx:xx (example: 00:a2:c4:3f:11:09) or a “-“ if you are not matching this item. You may use MAC Addresses to match an individual host. In the real world, you would use it to match a particular piece of hardware. The MAC address of a particular host is defined inside the sdn-topology.py file. The parser will verify that the MAC Address is in a proper form. If not, an error will be thrown. o Source / Destination IP Network Address in form of xxx.xxx.xxx.xxx/xx in CIDR notation or a “-“ if you are not matching this item. IMPORTANT NOTE: THIS MUST BE A VALID NETWORK ADDRESS. Thus, if you specify a subnet mask of /24, it means the first 24 bits will be the network address and the last 8 bits will be 0. Thus, for a host 10.0.10.10/24, the NETWORK ADDRESS will be 10.0.10.0/24. If you specify 10.0.10.10/24, you will get an error. If you want to specify a single host, then your netmask will be all 1s for the 32-bits of the address (i.e., a /32). The parser for the file will validate that you have a proper IP Address given, but will not parse to see if it is a valid network address. You will get a POX error if it is not a valid Network Address. The IP address of a particular host is defined inside the sdn-topology.py file. 8 o Protocol = integer IP protocol number per IANA (0-254) or a “-“ if you are not matching this item.. An example is ICMP is IP Protocol 1, TCP is IP Protocol 6, etc. o Source / Destination Port = if Protocol is TCP or UDP, this is the Application Port Number per IANA. For example, web traffic is generally TCP Port 80. Do not try to use port numbers to differentiate the different elements of the ICMP protocol. If you are not matching this item or are using an IP Protocol other than TCP or UDP, this field should be a “-“. o Comment/Note = this is for your use in tracking rules. Special Notes About Firewall Configurations: o Any field not being used for a match should have a ‘-‘ character as its entry. A ‘-‘ means that the item is not being used for matching traffic. It is valid for any rule element except for Action, Rulnenum, or Comment to have a ‘-‘ specified. Note that if you pass a “-“ to one of the match items in your code, you will crash POX. o All fields are passed as a string, so you must do type conversions as necessary. o You should not use a subnet mask smaller than /24. Using a /16 to cover all the subnets is not allowed. o Do not use 0.0.0.0/0 to address the internet as a whole. This may have unexpected behavior in POX. There is an easier way to match the world than using 0.0.0.0. Hint: Think about what a “-“ means. o When should I use MAC vs IP Addresses? You will want to interchange them in this file to test the robustness of your implementation. It is valid to specify a Source MAC address and a Destination IP Address. Example Rules (included in the project files: 1,Block,-,-,10.0.0.1/32,10.0.1.0/24,6,-,80,Block 10.0.0.1 host from accessing a web server on the 10.0.1.0/24 network 2,Allow,-,-,10.0.0.1/32,10.0.1.125/32,6,-,80,Allow 10.0.0.1 host to access a web server on 10.0.1.125 overriding rule What do these rules do? The first rule basically blocks host hq1 (IP Address 10.0.0.1/32) from accessing a web server on any host on the us network (the subnet 10.0.1.0/24 network). The web server is running on the TCP IP Protocol (6) and uses TCP Port 80. The second rule overrides the initial rule to allow hq1 (IP Address 10.0.0.1/32) to access a web server running on us5 (IP Address 10.0.1.125/32) By definition – from the sdn-topology.py file: This class defines the Mininet Topology for the network used in this project. This network consists of the following hosts/networks: Headquarters Network (hq1-hq5). Subnet 10.0.0.0/24 US Network (us1-us5). Subnet 10.0.1.0/24 India Network (in1-in5). Subnet 10.0.20.0/24 9 China Network (cn1-cn5). Subnet 10.0.30.0/24 UK Network (uk1-uk5). Subnet 10.0.40.0/24 In Part 5, you will be given a set of firewall conditions that you will need to create the configure.pol needed for your submission. You may create temporary rulesets to help you complete Part 5b below. Part 4b: Implementing the Firewall in Code After reviewing the format of the configure.pol file, you will now code a generic implementation of a firewall that will use the values provided from the configuration file (passed to you as dictionary items). As it is provided, the firewall implementation code blocks no traffic. You must implement code that does the following: o Create an OpenFlow Flow Modification object o Create a POX Packet Matching object that will integrate the elements from a single entry in the firewall configuration rule file (which is passed in the policy dictionary) to match the different IP and TCP/UDP headers if there is anything to match (i.e., no “-“ should be passed to the match object, nor should None be passed to a match object if a “-“ is provided). o Create a POX Output Action, if needed, to specify what to do with the traffic. Please reference code examples in Appendix C, or you may refer to the POX API documentation (WARNING, this is long and the API is confusing). You will need to rewrite the rule = None to reference your Flow Modification object. Your code will go into a section that will repeat itself for every line in the firewall configuration file that is passed to it. The “rule” item that is added to the “rules” list is an OpenFlow Modification object. The process of injecting this rule into the POX controller is handled automatically for you in the start-firewall.py file. TIP: If your implementation code segment is more than 25-30 lines, you are making it too difficult. The POX API can provide many features that are not used in this project. The Appendix provides all of the information that you will need to code the project. Key Information: o policies is a python list that contains one entry for each rule line contained in your configure.pol file. Each individual line of the configure.pol file is represented as a dictionary object named policy. This dictionary has the following keys: o policy[‘mac-src’] = Source MAC Address (00:00:00:00:00:00) or “-“ o policy[‘mac-dst’] = Destination MAC Address (00:00:00:00:00:00) ) or “-“ o policy[‘ip-src’] = Source IP Address (10.0.1.1/32) in CIDR notation ) or “-“ o policy[‘ip-dst’] = Destination IP Address (10.0.1.1/32) ) or “-“ o policy[‘ipprotocol’] = IP Protocol (6 for TCP) ) or “-“ 10 o policy[‘port-src’] = Source Port for TCP/UDP (12000) ) or “-“ o policy[‘port-dst’] = Destination Port for TCP/UDP (80) ) or “-“ o policy[‘rulenum’] = Rule Number (1) o policy[‘comment’] = Comment (Example Rule) o policy[‘action’] = Allow or Block Use these to match traffic. Please note that all fields are strings and may contain a ‘-‘ character. You may either use policy[‘ip-dst’] or the split policy[‘ip-dst-address’]/[policy[‘ip-dst-subnet’] in your implementation (the split was requested by prior semesters), but realize that if you use the ip-dstaddress and ip-dst-subnet, you will need to carefully check your implementation to ensure that it is blocking the addresses you intend to block. o You will need to assume that all traffic is IPV4. It is acceptable to hardcode this value. Do not hardcode other values. Your code should be generic enough to handle any possible configuration. o Hints: o The difference between an Allow or a Block is dependent on an Action and the Priority. o You don’t necessarily need an action. See Appendix C for a discussion of what happens to a packet after it is matched. o There should be two priorities – one for ALLOW and one for BLOCK. Separate them sufficiently to override any exact matching behavior that the POX controller implements). It is suggested one priority be 0 or 1 and the other one above 10000. The reasoning for this is discussed in Appendix C. o Outputting extra print debug lines will not adversely impact the autograder. o Remember, you may be tested with IP Protocols outside of 1, 6, and 17. Don’t hardcode. Part 5: Configuration Rules You will need to submit a configure.pol file to create policies that implement the following scenarios. You may implement your rules in any manner that you want, but it is recommended using this step as an opportunity to check your firewall code implementation. The purpose of these rules is to test your firewall and to help determine how traffic flows across the network (source vs destination, protocols, etc). DO NOT block all traffic by default and only allow traffic specified. You will lose many points because the firewall is open by default and only blocks the traffic that is specified. Firewall Rules for Fall 2024: • Task 1: Host cn4 has a TCP-based worm virus. Block cn4 from initiating network communications to any host on the internet (world) over the TCP Internet Protocol. You need not block ICMP or UDP. (one rule max) • Task 2: Host cn5 has had a security incident and needs to be completely isolated from the network so it has no connectivity (incoming or outgoing) to any other host on the internet (world). (two rules max) 11 • Task 3: Allow the hosts on the Headquarters network to be reachable via an ICMP ping from the world (including all but the China subnet (to avoid conflicts with Tasks 1 and 2 above). In addition, the corporate subnets should not be pingable from the internet (world). However, to satisfy the first half of this task, you must allow the Headquarters network to be able to ping the US, UK, and India subnets. Can you explain why this must happen? (six rules typically) The China network is exempted from this rule because any overrides that you may do here will override aspects of Task 1 or Task 2 above. • Task 4: Do not allow any response back from a TCP web server (http and https) from host cn3 to any other host on the internet (world). (two rules max) • Task 5: (CIDR Notation Rule) The servers located on hosts us3 and us4 run a micro webservice on TCP Port 9250 9520 that processes financial information. Access to this service should be blocked from hosts uk2, uk3, uk4, uk5, in4, in5, us5, and hq5. Please use the minimal CIDR notation that will bracket the subset of hosts for each rule (it should NOT be broader than /28). (four rules typical) • Task 6: A rogue Raspberry Pi has been found on the network that has cloned the Network Address of host us1. Block this device from accessing any other hosts on the internet (world) on the UDP Internet Protocol. (one rule max) Note that when testing this rule, the IP address for host us1 may differ from the published topology. In this case, you want to address the particular hardware device. • Task 7: Block the internet (world) from accessing TCP Port 25 on any corporate subnets. The behavior of access to TCP Port 25 amongst members of the corporate subnets is undefined and you may handle it as you wish. (five rules max) What to Turn In You need to submit your copy of packetcapture.pcap, sdn-firewall.py and configure.pol from your project directory using the instructions from the Piazza Post “How to Submit / Zip Our Projects. To recap, zip up the two files using the following command, replacing gtlogin with your GT Login that you use to log into Canvas: zip gtlogin_sdn.zip packetcapture.pcap configure.pol sdn-firewall.py The key to properly zipping the project is to NOT zip up the directory. ZIP only the files you are included. You may also include an additional text file if you have comments, criticisms, or suggestions for improvement for this project. If you wish to provide this information, add it to your ZIP file with the name comments.txt. This is completely optional. Please check your submission after uploading. As usual, we do not accept resubmissions past the stated deadlines. What you can and cannot share Do not share the content of your sdn-firewall.py, configure.pol, or packetcapture.pcap with your fellow students, on Ed Discussions, or elsewhere publicly. You may share any new topologies, testing rulesets, or testing frameworks, as well as packet captures that do not address the requirements of Part 4b. 12 Rubric For the Summer 2024 Semester, this project is worth a total of 100 points which is distributed in the following fashion: • 5 points for submitting a version of sdn-firewall.py that indicates effort was done. • 5 points for submitting a version of configure.pol that indicates effort was done. • 15 points for submitting a version of packetcapture.pcap that indicates effort was done. • 25 points for testing your configure.pol file with a known-good implementation. • 25 points for testing your configure.pol with your implementation. • 25 points for testing your implementation with a known-good configure.pol. 13 Appendix A: How to Test Host Connectivity Part A: How to Test Manually When you are developing your implementation or troubleshooting a firewall rule, you will want to test by hand. Unfortunately this process is a bit difficult. 1,Block,-,-,10.0.0.1/32,10.0.1.0/24,6,-,80,Block 10.0.0.1 from accessing a web server on the 10.0.1.0/32 network Startup Procedure: o Step 1: Open two terminal windows or tabs on the VM and change to the SDNFirewall directory. o Step 2: In the first terminal window, type in: ./start-firewall.sh configure.pol If you get the following error, run chmod +x start-firewall.sh and chmod +x start-topology.sh This should start up POX, read in your rules, and start up an OpenFlow Controller. You will see something like this in your terminal window: TA Note: Note that you will not see the “List of Policy Objects imported from configure.pol” and the “Added Rule” lines until after you complete Step 3 below. o Step 3: In the second terminal window, type in: ./start-topology.sh This should start up mininet and load the topology. You should see the following: This will start the firewall and set the topology. You do not need to repeat Steps 1-3 unless you are 14 done testing, need to restart the firewall, or need to restart mininet. When you are done with testing all of the rules you intend to use, type in “quit” in the mininet window, close all of the extraneous xterm windows generated, and run the mininet cleanup script ./cleanup.sh How to test connectivity between two hosts: o Step 1: To test the rule shown above, we want to use host us1 as server/destination and host hq1 as the client. The rule we are testing involves the hq1 host attempting to connect to the web server port (TCP Port 80) on host us1. At the mininet prompt, type in the following two commands on two different lines: hq1 xterm & us1 xterm & Two windows should have popped up. You can always identify which xterm is which by running the command: ip address from the bash shell. This will give you the IP address for the xterm window, which will then let you discover which xterm window belongs to which host. o Step 2: In the xterm window for us1 (which is the destination host of the rule – remember that the destination is always the server), type in the following command: python test-server.py T 10.0.1.1 80 This sets up the test server for us1 that will be listening on TCP port 80. The IP Address specified is always the IP address of the machine you are running it on. If you attempt to start the test-server on a machine that does not have the IP address that is specified in the command, you will get the following error: OSError: [Errno 99] Cannot assign requested address. o Step 6: In the xterm window for hq1 (which is the source host of the rule – remember that the source is always the client), type in the following command: python test-client.py T 10.0.1.1 80 This will start up a client that will connect to the TCP Port 80 on the server 10.0.1.1 (destination IP address) and will send a message string to the server. However, if the firewall is set to block this connection, you will never see the message pass on either of the client or the server. Examples of Connection Status: • The two windows below depict a successful un-blocked connection between the client and the server. 15 • A blocked connection will look like this (note that the client may take a while to timeout): You may hit Control C to kill both the server and the client. • A timed out connection is shown below. The difference between a timed-out connection on how the connection was blocked or if it was blocked on a different side of the connection. • If you get an error that says “No route to destination”, you have blocked the routing protocol. Ensure that you do not have a Unspecified Prerequisite Error 16 Repeat this process for every rule you wish to test. If you feel that after some initial testing that your implementation and ruleset is good, you may then proceed to using the automated test suite. Part B: Automated Testing Suite The automated Test Suit was developed by a student in Summer 2021 (htian66) and has been updated to match the current version of this project. There are two test suites – one that tests your implementation with the configure.pol you created that matches the rules in Part 5, and the second that is a generic test of your implementation with a different topology and provided configuration policy. The first test suite will be the exact same one used in the autograder that will be used after you turn the project into Canvas. How to test normal cases: 1. Change to the test-scripts directory 2. Copy your `sdn-firewall.py` and `configure.pol` into this directory. 3. Run ./start-firewall.sh configure.pol as usual. 4. Open a new window, run sudo python test_all.py. 5. Total passed cases are calculated. Wrong cases will be displayed. For example, `2: us1 -> hq1 with U at 53, should be True, current False` means the connection from client us1 to host hq1 using UDP at hq1 53 port is failed, which should be successful. The first number is the index (0-based) of testcases. True indicates that a connection was made or was expected. False indicates the opposite condition. How to test alternte cases: 1. Change to the test-scripts directory 2. Copy your `sdn-firewall.py` file into the alt folder. Change to the alt directory. 3. Run ./start-firewall.sh (you do not need to specify your configure.pol file 4. Open a new window, run sudo python test_all.py in the test-suite/alt folder. 5. Total passed cases are calculated. Wrong cases will be displayed. For example, `2: us1 -> hq1 with U at 53, should be True, current False` means the connection from client us1 to host hq1 using UDP at hq1 53 port is failed, which should be successful. The first number is the index (0-based) of testcases. True indicates that a connection was made or was expected. False indicates the opposite condition. 17 Appendix B: Troubleshooting Information General Coding Issues o Watch for type mismatches. o Do not run “pip3 install pox”. The pox module installed by pip is not the library used in this project. o This project is virtually impossible to use the Debug utilities inside of VSCode or Pycharm since it requires running under the mininet framework. For debugging, it is suggested that you use print statements in your code to help determine where issues may be occurring. o You do NOT need to reparse or revalidate any of the data provided in the dictionary other than possibly changing the type from strings. o If you use Visual Studio code, add the following to your workspace settings: “python.autoComplete.extraPaths”: [ “/home/mininet/pox/” ], Also, with Visual Studio code, it sometimes “recommends” _dl_type and other names prepended with a _. Note that this is incorrect – the name is dl_type, not _dl_type. Firewall Implementation (sdn-firewall.py) Errors and Issues o Pay attention to the Fields ignored due to unspecified prerequisites warning. Do not ignore this message or your firewall will overblock (i.e., it ignores the field specified). Remember that there are items required when you specify TCP or UDP, and when you specify IPV4. o If you get a struct.pack or struct.unpack error message, take a look at https://github.com/att/pox/blob/7f76c9e3c9bc999fcc97961d408ab0b71cbc186d/pox/OpenFlo w/libOpenFlow_01.py for more information. Also, the struct.pack error might reference how to fix (i.e., not an integer, EthAddr(), etc). o The following error means that you should check your output action: “TypeError: ord() expected string of length 1, but int found” o If you find that all traffic is blocked, double check the unspecified prerequisite warning. o Note that you may have issues with certain rules that don’t seem to work when you first start the firewall. This is typically caused by starting the Spanning Tree. You may run “pingall” to overcome this before testing. This can be enabled in the autograder utility. Mininet/Topology Issues o On the topology terminal window, if you get an error message that states “Unable to contact Remote Controller”, it means that the POX controller had crashed and normally shows that there is a bug in your implementation code. Look at the windows where you started the firewall. o If you get the following error message, please run the cleanup.sh utility: “Exception: Error creating interface pair (s1-eth0,hq1-eth0): RTNETLINK answers: File exists” 18 Appendix C: POX API Excerpt This section contains a highly modified excerpt from the POX Manual (modified to remove extraneous features not used in this project and to provide clarifications). You should not need to use any other POX objects for this project. TA Comments are highlighted. Everything on these pages is important to complete the project. Excerpted and modified from: https://noxrepo.github.io/pox-doc/html/ Object Definitions: Flow Modification Object The main object used for this project is a “Flow Modification” object. This adds a rule to the OpenFlow controller that will affect a modification to the traffic flow based on priority, packet characteristic matchin, and an action that will be done to the traffic that is matched. IF AN OBJECT is matched, it is pulled from the network stream and will only be forwarded, modified, or redirected if you do an action. If you do not specify an action and the packet is matched, the packet will basically be dropped. The following class descriptor describes the contents of a flow modification object. You need to define the match, priority, and actions for the object. class ofp_flow_mod (ofp_header): def __init__ (self, **kw): ofp_header.__init__(self) self.header_type = OFPT_FLOW_MOD self.match = ofp_match() self.priority = OFP_DEFAULT_PRIORITY self.actions = [] Match Structure OpenFlow defines a match structure – ofp_match – which enables you to define a set of headers for packets to match against. The match structure is defined in pox/OpenFlow/libOpenFlow_01.py in class ofp_match. Its attributes are derived from the members listed in the OpenFlow specification, so refer to that for more information, though they are summarized in the table below. You should create a match object and attach it to the flow modification object. 19 Attribute Meaning dl_src Ethernet/MAC source address (Type of EthAddr) dl_dst Ethernet/MAC destination address (Type of EthAddr) dl_type Ethertype / length (e.g. 0x0800 = IPv4) (Type of Integer) nw_proto IP protocol (e.g., 6 = TCP) or lower 8 bits of ARP opcode (Type of integer) nw_src IP source NETWORK address (Type of String) nw_dst IP destination NETWORK address (Type of String) tp_src TCP/UDP source application port (Type of Integer) tp_dst TCP/UDP destination application port (Type of Integer) TA Note: (IMPORTANT_ If you use VSCode or Pycharm, it may make the recommendation to use _dl_src and _dl_dst. These are not valid. Please use what is specified above. Attributes may be specified either on a match object or during its initialization. That is, the following are equivalent: matchobj = of.ofp_match(tp_src = 5, dl_type = 0x800,dl_dst = EthAddr(“01:02:03:04:05:06”)) #.. or .. matchobj = of.ofp_match() matchobj.tp_src = 5 matchobj.dl_type = 0x800 matchobj.dl_dst = EthAddr(“01:02:03:04:05:06”) IMPORTANT NOTE ABOUT IP ADDRESSES TA Note: What isn’t very clear by this documentation is that nw_* is expecting a network address. If you are calling out an IP Address like 10.0.1.1/32, it is an acceptable response to nw_*. However, if you are calling out a subnet like 10.0.1.0/24, the IP address portion of the response MUST BE the Network Address. From Wikipedia: IP addresses are described as consisting of two groups of bits in the address: the most significant bits are the network prefix, which identifies a whole network or subnet, and the least significant set forms the host identifier, which specifies a particular interface of a host on that network. This division is used as the basis of traffic routing between IP networks and for address allocation policies. (https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing) Thus for a /24 network, the first 24 bits of the address comprises the network address. Thus, it would be 10.0.1.0. For a /25 network, there would be two networks in the 10.0.1.x space – a 10.0.1.0/25 and a 10.0.1.128/25. 20 Your implementation code does NOT need to convert the given IP Address into a network – you can assume that any given address in a possible configuration file must be valid. However, your configure.pol file MUST be using the proper form if you are using a CIDR notation other than /32. Why would you do this? To reduce the number of rules needed. You may use this for the 5th rule from Part 6. Note that some fields have prerequisites. Basically this means that you can’t specify higher-layer fields without specifying the corresponding lower-layer fields also. For example, you can not create a match on a TCP port without also specifying that you wish to match TCP traffic. And in order to match TCP traffic, you must specify that you wish to match IP traffic. Thus, a match with only tp_dst=80, for example, is invalid. You must also specify nw_proto=6 (TCP), and dl_type=0x800 (IPv4). If you violate this, you should get the warning message ‘Fields ignored due to unspecified prerequisites‘. This question also presents itself as “What does the Fields ignored due to unspecified prerequisites warning mean?” Basically this means that you specified some higher-layer field without specifying the corresponding lower-layer fields also. For example, you may have tried to create a match in which you specified only tp_dst=80, intending to capture HTTP traffic. You can’t do this. To match TCP port 80, you must also specify that you intend to match TCP (nw_proto=6). And to match on the TCP protocol, you must also match on IPV4 type (dl_type=0x800). OpenFlow Actions The final aspect needed to fully implement a flow modification object is the action. With this, you specify what you want done to a port. This can include forwarding, dropping, duplicating and redirecting, or modify the header parameters. For the purposes of this project, we are only dealing with forwarding of match traffic to its destination. But please note that for a Software Defined Network system, you can do all sorts of actions including round robin server, DDOS blocking, and many other possible options. Output Forward packets out of a physical or virtual port. Physical ports are referenced to by their integral value, while virtual ports have symbolic names. Physical ports should have port numbers less than 0xFF00. Structure definition: class ofp_action_output (object): def __init__ (self, **kw): self.port = None # Purposely bad — require specification 21 port (int) the output port for this packet. This is a bit misleading because it can confuse you with the application “port” for TCP/UDP. For openflow, this port represents the physical swith port that the host is plugged into. However, you do NOT know which physical port on which switch a host is connected to. Thus, you will need to use one of the virtual ports to define what you want to happen: • of.OFPP_IN_PORT – This action will send the port back to the sender (i.e., the port it came into the network on) • of.OFPP_NORMAL – Process the packet and handle via a normal L2/L3 legacy switch configuration (i.e., send traffic to its destination without modification) – See https://studyccna.com/layer-3-switch/ for information on how normal L2/L3 legacy switches work. • of.OFPP_FLOOD – This action will cause the traffic to be sent out to all ports except the source (IN_PORT) and any ports that have flooding turned off. This is very chatty and can be used to do network based attacks (see UDP Amplifications). This should be avoided. • of.OFPP_ALL – output all OpenFlow ports except the source (IN_PORT). This is the same as FLOOD but it includes ports that have had flood turned off. • of.OFPP_CONTROLLER – This action sends the packet to the switch controller. What happens with the port depends on the state of the switch controller. Thus it may work, but also may not work, based on the current state of the switch. Think carefully about the definitions given above for output actions. Remember that if you match a packet, no action (i.e., packet will be dropped) will be done unless you set an output action as the packet is pulled from the stream until it is resolved. Example: Sending a FlowMod Object The following example describes how to create a flow modification object including matching a destination IP Address, IP Type, and Destination IP Port, and setting an action that would redirect the matching packet out to physical switch port number 4 (note that you generally DO NO KNOW what physical switch port to use. rule = of.ofp_flow_mod() rule.match = of.ofp_match() rule.match.dl_type = 0x800 rule.match.nw_dst = “192.168.101.101/32” rule.match.nw_proto = 6 rule.match.tp_dst = 80 rule.priority = 42 rule.actions.append(of.ofp_action_output(port = of.OFPP_????)) Flow Modification Objects work as thus: 1. Packet enters the system and is examined by the Flow Modification Objects (1 for each rule in your configuration ruleset) 2. The packet will then be examined to see if the different header items match the items specified for that rule. 22 3. If the packet matches all the applicable items, it is pulled from the stream for you to program an action for it (forward it, readdress it, change it). If you don’t do an action for it, the package is essentially dropped. If the packet does not match all the applicable header items, it continues to the next Flow Modification rule to test it. If it isn’t matched by any rules, it is passed on to the specific destination. For this project, you are making a flow modification object and action while using a matching pattern that can match any or all of the different parameters of the header. Make your implementation generic. 23 Appendix D: Review of Mininet Mininet is a network simulator that allows you to explore SDN techniques by allowing you to create a network topology including virtual switches, links, hosts/nodes, and controllers. It will also allow you to set the parameters for each of these virtual devices and will allow you to simulate real-world applications on the different hosts/nodes. The following code sets up a basic Mininet topology similar to what is used for this project: #!/usr/bin/python from mininet.topo import Topo from mininet.net import Mininet from mininet.node import CPULimitedHost, RemoteController from mininet.util import custom from mininet.link import TCLink from mininet.cli import CLI class FirewallTopo(Topo): def __init__(self, cpu=.1, bw=10, delay=None, **params): super(FirewallTopo,self).__init__()# Host in link configuration hconfig = {‘cpu’: cpu} lconfig = {‘bw’: bw, ‘delay’: delay}# Create the firewall switch s1 = self.addSwitch(‘s1’) hq1 = self.addHost(‘hq1′,ip=’10.0.0.1′,mac=’00:00:00:00:00:1e’, **hconfig) self.addLink(s1,hq1) us1 = self.addHost( ‘us1′, ip=’10.0.1.1′, mac=’00:00:00:01:00:1e’, **hconfig) self.addLink(s1,us1) This code defines the following virtual objects: • Switch s1 – this is a single virtual switch with the label ‘s1’. In Mininet, you may have as many virtual ports as you need – for Mininet, “ports” are considered to be a virtual ethernet jack, not an application port that you would use in building your firewall. • Hosts hq1 and us1 – these are individual virtual hosts that you can access via xterm and other means. You can define the IP Address, MAC/Hardware Addresses, and configuration parameters that can define cpu speed and other parameters using the hconfig dictionary. • Links between s1 and hq1 and s1 and us1 – consider these like an ethernet cable that you would run between a computer and the switch port. You can define individual port numbers on each side (i.e., port on the host and port on the virtual switch), but it is advised to let Mininet automatically wire the network. Like hosts, you can define configuration parameters to set link speed, bandwidth, and latency. 24 REMINDER – PORTS MENTIONED IN MININET TOPOLOGIES ARE WIRING PORTS ON THE VIRTUAL SWITCH, NOT APPLICATION PORT NUMBERS. Useful Mininet Commands: • For this project, you can start Mininet and load the firewall topology by running the ./start-topology.sh from the project directory. You can quit Mininet by typing in the exit command. • After you are done running Mininet, it is recommended that you cleanup Mininet. There are two ways of doing this. The first is to run the sudo mn -c command from the terminal and the second is to use the ./cleanup.sh script provided in the project directory. Do this after every run to minimize any problems that might hang or crash Mininet. • You can use the xterm command to start an xterm window for one of the virtual hosts. This command is run from the mininet> prompt. For example, you can type in us1 xterm & to open a xterm window for the virtual host us1. The & causes the window to open and run in the background. In this project, you will run the test-*-client.py and test-*-server.py in each host to test connectivity. • The pingall command that is run from the mininet> prompt will cause all hosts to ping all other hosts. Note that this may take a long time. To run a ping between two hosts, you can specify host1 ping host2 (for example, us1 ping hq1 which will show the result of host us1 pinging hq1). • The help command will show all Mininet commands and dump will show information about all hosts in the topology.
Spring 2025In this assignment, you will work with probabilistic models known as Bayesian networks to efficiently calculate the answer to probability questions concerning discrete random variables.### ResourcesYou will find the following resources helpful for this assignment.*Canvas Videos:* Lecture 5 on Probability Lecture 6 on Bayes Nets*Textbook:* 4th edition: Chapter 12: Quantifying Uncertainty Chapter 13: Probabilistic Reasoning 3rd edition: Chapter 13: Quantifying Uncertainty Chapter 14: Probabilistic Reasoning ### Setup #### ❗❗❗ **Critical:** Only 7 Submissions Allowed On Gradescope for this Assignment.⚠️⚠️⚠️1. Clone the project repository from Github“` git clone [your URL] “`Substitute your actual username where the angle brackets are.2. Navigate to `assignment_3/` directory3. Activate the environment you created during Assignment 0“` conda activate ai_env “`In case you used a different environment name, to list of all environments you have on your machine you can run `conda env list`.4. Run the following command in the command line to install and update the required packages“` pip install torch torchvision -f https://download.pytorch.org/whl/torch_stable.html pip install –upgrade -r requirements.txt “` 5. For Mac OSX users with apple silicon, if you have error related to `xgboost`, you may also need to install `xgboost`. “` conda install py-xgboost “` ### Submission #### ❗❗❗ **Critical:** Only 7 Submissions Allowed On Gradescope for this Assignment.⚠️⚠️⚠️ Please include all of your own code for submission in `submission.py`.**Important: There is a TOTAL submission limit of 7 on Gradescope for this assignment. This means you can submit a maximum of 7 times during the duration of the assignment. Please use your submissions carefully and do not submit until you have thoroughly tested your code locally.****If you’re at 6 submissions, use your last submission wisely. The submission marked as ‘Active’ in Gradescope will be the submission counted towards your grade.**### RestrictionsYou are not allowed to use following set of modules from ‘pgmpy’ Library.>- pgmpy.sampling.* >- pgmpy.factor.* >- pgmpy.estimators.* >-## Part 1 Bayesian network tutorial:_[35 points total]_To start, design a basic probabilistic model for the following system:James Bond, Q (Quartermaster), and M (Head of MI6) are in charge of the security system at MI6, the Military Intelligence Unit of the British Secret Service. MI6 runs a special program called “Double-0”, where secret spy agents are trained and deployed to gather information concerning national security. A terrorist organization named “Spectre” is planning an espionage mission and its aim is to gain access to the secret “Double-0” files stored in the MI6 database. Q has designed a special security system to protect the secret “Double-0” files. In order to gain access to these files, Spectre needs to steal from MI6 a cipher and the key to crack this cipher. Q stores this cipher in his personal database, which is guarded by heavy security protocols. The key to cracking the cipher is known only to M, who is protected by Bond.### 1a: Casting the net_[10 points]_Thus, Spectre can carry out their mission by performing the following steps: >- Hire professional hackers who can write programs to launch a cyberattack on Q’s personal database. >- Buy a state-of-the-art computer called “Contra” to actually launch this cyberattack. >- Hire ruthless mercenaries to kidnap M and get access to the key. >- Make sure Bond is not available with M at the time of the kidnapping. >- Use the cipher and key to access the target “Double-0” files.Sensing the imminent danger, MI6 has hired you to design a Bayes Network for modeling this espionage mission, so that it can be avoided. MI6 requires that you use the following name attributes for the nodes in your Bayes Network: >- “H”: The event that Spectre hires professional hackers >- “C”: The event that Spectre buys Contra >- “M”: The event that Spectre hires mercenaries >- “B”: The event that Bond is guarding M at the time of the kidnapping >- “Q”: The event that Q’s database is hacked and the cipher is compromised >- “K”: The event that M gets kidnapped and has to give away the key >- “D”: The event that Spectre succeeds in obtaining the “Double-0” filesBased on their previous encounters with Spectre, MI6 has provided the following classified information that can help you design your Bayes Network: >- Spectre will not be able to find and hire skilled professional hackers (call this false) with a probability of 0.5. >- Spectre will get their hands on Contra (call this true) with a probability of 0.3. >- Spectre will be unable to hire the mercenaries (call this false) with a probability of 0.2. >- Since Bond is also assigned to another mission, the probability that he will be protecting M at a given moment (call this true) is just 0.5! >- The professional hackers will be able to crack Q’s personal database (call this true) without using Contra with a probability of 0.55. However, if they get their hands on Contra, they can crack Q’s personal database with a probability of 0.9. In case Spectre can not hire these professional hackers, their less experienced employees will launch a cyberattack on Q’s personal database. In this case, Q’s database will remain secure with a probability of 0.75 if Spectre has Contra and with a probability of 0.95 if Spectre does not have Contra. >- When Bond is protecting M, the probability that M stays safe (call this false) is 0.85 if mercenaries conduct the attack. Else, when mercenaries are not present, it the probability that M stays safe is as high as 0.99! However, if M is not accompanied by Bond, M gets kidnapped with a probability of 0.95 and 0.75 respectively, with and without the presence of mercenaries. >- With both the cipher and the key, Spectre can access the “Double-0” files (call this true) with a probability of 0.99! If Spectre has none of these, then this probability drops down to 0.02! In case Spectre has just the cipher, the probability that the “Double-0” files remain uncompromised is 0.4. On the other hand, if Spectre has just the key, then this probability changes to 0.65.Use the description of the model above to design a Bayesian network for this model. The `pgmpy` package is used to represent nodes and conditional probability arcs connecting nodes. Don’t worry about the probabilities for now. Use the functions below to create the net. You will write your code in `submission.py`.Fill in the function `make_security_system_net()`The following commands will create a BayesNet instance add node with name “node_name”:BayesNet = BayesianNetwork() BayesNet.add_node(“node_name”)You will use `BayesNet.add_edge()` to connect nodes. For example, to connect the parent and child nodes that you’ve already made (i.e. assuming that parent affects the child probability):Use function `BayesNet.add_edge(,)`. For example:BayesNet.add_edge(“parent”,”child”)After you have implemented `make_security_system_net()`, you can run the following test in the command line to make sure your network is set up correctly.“` python probability_tests.py ProbabilityTests.test_network_setup “`### 1b: Setting the probabilities_[15 points]_Now set the conditional probabilities for the necessary variables on the network you just built.Fill in the function `set_probability()`Using `pgmpy`’s `factors.discrete.TabularCPD` class: if you wanted to set the distribution for node ‘A’ with two possible values, where P(A) to 70% true, 30% false, you would invoke the following commands:cpd_a = TabularCPD(‘A’, 2, values=[[0.3], [0.7]])**NOTE: Use index 0 to represent FALSE and index 1 to represent TRUE, or you may run into testing issues.**If you wanted to set the distribution for P(G|A) to be| A |P(G=true given A)| | —— | —– | | T | 0.75| | F | 0.85|you would invoke:cpd_ga = TabularCPD(‘G’, 2, values=[[0.15, 0.25], [ 0.85, 0.75]], evidence=[‘A’], evidence_card=[2])**Reference** for the function: https://pgmpy.org/_modules/pgmpy/factors/discrete/CPD.htmlModeling a three-variable relationship is a bit trickier. If you wanted to set the following distribution for P(T|A,G) to be| A | G |P(T=true given A and G)| | — | — |:—-:| |T|T|0.15| |T|F|0.6| |F|T|0.2| |F|F|0.1|you would invokecpd_tag = TabularCPD(‘T’, 2, values=[[0.9, 0.8, 0.4, 0.85], [0.1, 0.2, 0.6, 0.15]], evidence=[‘A’, ‘G’], evidence_card=[2, 2])The key is to remember that first entry represents the probability for P(T==False), and second entry represents P(T==true).Add Tabular conditional probability distributions to the bayesian model instance by using following command.bayes_net.add_cpds(cpd_a, cpd_ga, cpd_tag)You can check your probability setups in the command line with“` python probability_tests.py ProbabilityTests.test_probability_setup “`and probability values: “` python probability_tests.py ProbabilityTests.test_security_system_probabilities“` ### 1c: Probability calculations : Perform inference_[10 points]_To finish up, you’re going to perform inference on the network to calculate the following probabilities:>- What is the marginal probability that the “Double-0” files get compromised? >- You just received an update that the British Elite Forces have successfully secured and shut down Contra, making it unavailable for Spectre. Now, what is the conditional probability that the “Double-0” files get compromised? >- Despite shutting down Contra, MI6 still believes that an attack is imminent. Thus, Bond is reassigned full-time to protect M. Given this new update and Contra still shut down, what is the conditional probability that the “Double-0” files get compromised?You’ll fill out the “get_prob” functions to calculate the probabilities: – `get_marginal_double0()` – `get_conditional_double0_given_no_contra()` – `get_conditional_double0_given_no_contra_and_bond_guarding()`Here’s an example of how to do inference for the marginal probability of the “A” node being True (assuming `bayes_net` is your network):solver = VariableElimination(bayes_net) marginal_prob = solver.query(variables=[‘A’], joint=False) prob = marginal_prob[‘A’].valuesTo compute the conditional probability, set the evidence variables before computing the marginal as seen below (here we’re computing P(‘A’ = false | ‘B’ = true, ‘C’ = False)):solver = VariableElimination(bayes_net) conditional_prob = solver.query(variables=[‘A’],evidence={‘B’:1,’C’:0}, joint=False) prob = conditional_prob[‘A’].values__NOTE__: `marginal_prob` and `conditional_prob` return two probabilities corresponding to `[False, True]` case. You must index into the correct position in `prob` to obtain the particular probability value you are looking for.If you need to sanity-check to make sure you’re doing inference correctly, you can run inference on one of the probabilities that we gave you in 1a. For instance, running inference on P(M=false) should return 0.20 (i.e. 20%). However, due to imprecision in some machines it could appear as 0.199xx. You can also calculate the answers by hand to double-check.## Part 2: Sampling_[65 points total]_For the main exercise, consider the following scenario.There are three frisbee teams who play each other: the Airheads, the Buffoons, and the Clods (A, B and C for short). Each match is between two teams, and each team can either win, lose, or draw in a match. Each team has a fixed but unknown skill level, represented as an integer from 0 to 3. The outcome of each match is probabilistically proportional to the difference in skill level between the teams.Sampling is a method for ESTIMATING a probability distribution when it is prohibitively expensive (even for inference!) to completely compute the distribution.Here, we want to estimate the outcome of the matches, given prior knowledge of previous matches. Rather than using inference, we will do so by sampling the network using two *Markov Chain Monte Carlo* models: (2c) `Gibbs sampling` and (2d) `Metropolis-Hastings` .### 2a: Build the network._[10 points]_For the first sub-part, consider a network with 3 teams : the Airheads, the Buffoons, and the Clods (A, B and C for short). 3 total matches are played. Build a Bayes Net to represent the three teams and their influences on the match outcomes.Fill in the function `get_game_network()`Assume the following variable conventions:| variable name | description| |———|:——:| |A| A’s skill level| |B | B’s skill level| |C | C’s skill level| |AvB | the outcome of A vs. B (0 = A wins, 1 = B wins, 2 = tie)| |BvC | the outcome of B vs. C (0 = B wins, 1 = C wins, 2 = tie)| |CvA | the outcome of C vs. A (0 = C wins, 1 = A wins, 2 = tie)|Use the following name attributes:>- “A” >- “B” >- “C” >- “AvB” >- “BvC” >- “CvA”Assume that each team has the following prior distribution of skill levels:|skill level|P(skill level)| |—-|:—-:| |0|0.15| |1|0.45| |2|0.30| |3|0.10|In addition, assume that the differences in skill levels correspond to the following probabilities of winning:| skill difference (T2 – T1) | T1 wins | T2 wins| Tie | |————|———-|—|:——–:| |0|0.10|0.10|0.80| |1|0.20|0.60|0.20| |2|0.15|0.75|0.10| |3|0.05|0.90|0.05|You can check your network implementation in the command line with“` python probability_tests.py ProbabilityTests.test_games_network “`### 2b: Calculate posterior distribution for the 3rd match._[5 points]_Suppose that you watched two of the three games and observed the following outcome:>- A beats B >- A draws with CCalculate the posterior distribution for the outcome of the **BvC** match in `calculate_posterior()`.Let’s first use the inference engine, **VariableElimination**, provided by the `pgmpy` library to perform inference. This result will be the ground truth for you to test your estimation in `2c) Gibbs` and `2d) MH`, where you are NOT allowed to use the inference engine there.You can check your posteriors in the command line with“` python probability_tests.py ProbabilityTests.test_posterior “`**NOTE: In the following sections, we’ll be arriving at the same values by using sampling-based methods.**#### Hints Regarding sampling for Part 2c, 2d, and 2e*Hint 1:* In both Metropolis-Hastings and Gibbs sampling, you’ll need access to each node’s probability distribution and nodes. You can access these by calling:A_cpd = bayes_net.get_cpds(‘A’) team_table = A_cpd.values AvB_cpd = bayes_net.get_cpds(“AvB”) match_table = AvB_cpd.values*Hint 2:* While performing sampling, you will have to generate your initial sample by sampling uniformly at random an outcome for each non-evidence variable and by keeping the outcome of your evidence variables (`AvB` and `CvA`) fixed.*Hint 3:* You’ll also want to use the random package, e.g. `random.randint()` or `random.choice()`, for the probabilistic choices that sampling makes. ### 2c: Gibbs sampling _[15 points]_Implement the Gibbs sampling algorithm, which is a special case of Metropolis-Hastings. You’ll do this in `Gibbs_sampler()`, which takes a Bayesian network and initial state value as a parameter and returns a sample state drawn from the network’s distribution.The function should just consist of a “single iteration” of the algorithm. “Single iteration” means this function only generate just one new sample based on the previous sample you have. The new sample is chosen with some distribution you have to compute by written down the equation. If an initial value is not given (initial state is None or and empty list), default to a state chosen uniformly at random from the possible states.Your sampling process could look like something below:“` state_chosen := randomly chosen index from init_state tuple if state_chosen = A: (derive your formula yourself) (Don’t use VariableElimination or other inference engine, or you will have 600 sec timeout issue on Grade Scope) prob = [your formula] sample new state with the prob else if state_chosen = B: … else if … “`Note: **DO NOT USE the given inference engines or `pgmpy` samplers to run the sampling method**, since the whole point of sampling is to calculate marginals without running inference.“YOU WILL SCORE 0 POINTS ON THIS ASSIGNMENT IF YOU USE THE GIVEN INFERENCE ENGINES FOR THIS PART”You may find [this](https://github.gatech.edu/omscs6601/assignment_3/blob/master/resources/gibbs.pdf) helpful in understanding the basics of Gibbs sampling over Bayesian networks. Please note that there is a typo in this material: on page 3, $P( eg c|r,s,w) = 0.5556$ instead of 0.6923.### 2d: Metropolis-Hastings sampling_[15 points]_ Now you will implement the independent Metropolis-Hastings sampling algorithm in `MH_sampler()`, which is another method for estimating a probability distribution. The general idea of MH is to build an approximation of a latent probability distribution by repeatedly generating a “candidate” value for each sample vector comprising of the random variables in the system, and then probabilistically accepting or rejecting the candidate value based on an underlying acceptance function. Unlike Gibbs, in case of MH, the returned state can differ from the initial state at more than one variable. This [paper](https://github.gatech.edu/omscs6601/assignment_3/blob/master/resources/MetropolisHastingsSampling.pdf) provides a nice intro. You may need to download and view the file locally, as there are some issues with GitHub’s rendering.This method should just perform a “single iteration” of the algorithm. If an initial value is not given, default to a state chosen uniformly at random from the possible states.Note: **DO NOT USE the given inference engines to run the sampling method**, since the whole point of sampling is to calculate marginals without running inference.“YOU WILL SCORE 0 POINTS IF YOU USE THE PROVIDED INFERENCE ENGINES, OR ANY OTHER SAMPLING METHOD”### 2e: Comparing sampling methods_[19 points]_Now we are ready for the moment of truth.Given the same outcomes as in 2b, A beats B and A draws with C, you should now estimate the likelihood of different outcomes for the third match by running Gibbs sampling until it converges to a stationary distribution. We’ll say that the sampler has converged when, for “N” successive iterations, the difference in expected outcome for the 3rd match differs from the previous estimated outcome by less than “delta”. `N` is a positive integer, `delta` goes from `(0,1)`. For the most stationary convergence, `delta` should be very small. `N` could take values like 10,20,…,100 or even more. Play it out yourself!Use the functions from 2c and 2d to measure how many iterations it takes for Gibbs and MH to converge to a stationary distribution over the posterior. See for yourself how close (or not) this stable distribution is to what the Inference Engine returned in 2b. And if not, try tuning those parameters(N and delta). (You might find the concept of “burn-in” period useful).You can choose any N and delta (with the bounds above), as long as the convergence criterion is eventually met.Repeat this experiment for Metropolis-Hastings sampling.Fill in the function `compare_sampling()` to perform your experimentsWhich algorithm converges more quickly? By approximately what factor? For instance, if Metropolis-Hastings takes twice as many iterations to converge as Gibbs sampling, you’d say that Gibbs converged faster by a factor of 2. Fill in `sampling_question()` to answer both parts. You only need to comment out or delete “raise NotImplementedError” and modify `choice` and `factor`.### 2f: Return your name #### ❗❗❗ **Critical:** Only 7 Submissions Allowed On Gradescope for this Assignment.⚠️⚠️⚠️ _[1 point]_A simple task to wind down the assignment. Return your name from the function aptly called `return_your_name()`. ~~~~~~~~
SPRING 2025This assignment will cover some of the concepts discussed in the Adversarial Search lectures. You will be implementing game playing agents for a variant of the game Isolation.We are also implementing this through Jupyter Notebook, so you all may find it useful to spend some time getting familiar with this software. During the first week of classes, there was an assignment [Assignment 0](https://github.gatech.edu/omscs6601/assignment_0/) that spends some time going through Python and Jupyter. If you are unfamiliar with either Python or Jupyter, please go through that assignment first!### Table of Contents – [Setup](#setup) – [Jupyter](#jupyter) – [Jupyter Tips](#jupyter-tips) – [FAQ](#faq) – [IDE](#IDE) ## SetupFor this assignment, we **highly** recommend you to create a new environment **just** for this one assignment.“` conda create -n ai_env_a2 python=3.9 “`Activate the environment: “` conda activate ai_env_a2 “`In case you used a different environment name, to get a list of all environments you have on your machine, you can run `conda env list`.Install correct package versions that will be used for visualising the game board.“` cd assignment_2 pip install -r requirements.txt “` ## JupyterYou may wish to install the `ipykernel`. This can be done via:“` python -m ipykernel install –user –name ai_env_a2 –display-name “Python 3.9 (AI-A2)” “`Further instructions are provided in the `notebook.ipynb`. Run:“` jupyter notebook “`Once started you can access [http://localhost:8888](http://localhost:8888/) in your browser. ## Jupyter TipsHopefully, [Assignment 0](https://github.gatech.edu/omscs6601/assignment_0/) got you pretty comfortable with Jupyter or at the very least addressed the major things that you may run into during this project. That said, Jupyter can take some getting used to, so here is a compilation of some things to watch out for specifically when it comes to Jupyter in a sort-of FAQs-like style**1. My Jupyter notebook does not seem to be starting up or my kernel is not starting correctly.** Ans: This probably has to do with activating virtual environments. If you followed the setup instructions exactly, then you should activate your conda environment using `conda activate ` from the Anaconda Prompt and start Jupyter Notebook from there.**2. I was running cell xxx when I opened up my notebook again and something or the other seems to have broken.** Ans: This is one thing that is very different between IDEs like PyCharm and Jupyter Notebook. In Jupyter, every time you open a notebook, you should run all the cells that a cell depends on before running that cell. This goes for cells that are out of order too (if cell 5 depends on values set in cell 4 and 6, you need to run 4 and 6 before 5). Using the “Run All” command and its variants (found in the “Cell” dropdown menu above) should help you when you’re in a situation like this.**3. The value of a variable in one of my cells is not what I expected it to be? What could have happened?** Ans: You may have run a cell that modifies that variable too many times. Look at the “counter” example in assignment 0. First, try running `counter = 0` and then `counter += 1`. This way, when you print counter, you get counter = 1, right? Now try running `counter += 1` again, and now when you try to print the variable, you see a value of 2. This is similar to the issue from Question 2. The order in which you run the cells does affect the entire program, so be careful. ## FAQ **1. What depth does the server call my search algorithms with?** Ans: The server will not pass a depth value to your CustomPlayer; whatever you set as the default parameter value will be used on Gradescope. Modifying this default value is extremely important in changing the performance of your agent.**2. How does Gradescope set up and run each game?** Ans: Gradescope will run 20 games in order to determine the win ratio. Your player (CustomPlayer) will be K1 for 10 of those games and K2 for 10 of those games. Each player has 1 second to make each move and the first two moves (i.e. each player’s starting location) will be randomized.**3. Can we use multithreading of multiprocessing?** Ans: Sorry, we will not allow multithreading or multiprocessing on this Assignment. It isn’t necessary to successfully complete the Assignment.**4. I have a question about the isolation API or the workings of the framework. Where should I learn more?** Ans: Firstly, watch the recorded YouTube video of assignment 2 where isolation API is covered. If this video and the docstrings inside isolation.py leave you with more questions, feel free to post a question on Ed and a TA will respond as soon as possible with clarifications, or come to office hours to discuss further.**5. Can I add more functions to replace some of the existing functions? Can I import other packages as well?** Ans: No. Please do not add any more functions or imports. You should be able to finish the assignment by replacing the `NotImplementedError`.**A more in-depth FAQ will be posted on Ed** ## IDEIn case you are willing to use IDE (e.g. Pycharm) to implement your assignment in `.py` file. Please run:“`bash python helpers/notebook2script.py submission “`You will get autogenerated `submission/submission.py` file where you can write your code. However, make sure you have gone through the instructions in the `notebook.ipynb` at least once.
Spring 2025 In the lectures, you learned about Distance Vector (DV) routing protocols, one of the two classes of routing protocols. DV protocols, such as RIP, use a fully distributed algorithm to find shortest paths by solving the Bellman-Ford equation at each node. In this project, you will develop a distributed Bellman-Ford algorithm and use it to calculate routing paths in a network. This project is similar to the Spanning Tree project, except that we are solving a routing problem, not a switching problem. In “pure” distance vector routing protocols, the hop count (the number of links to be traversed) determines the distance between nodes. Some distance vector routing protocols, that operate at higher levels (like BGP), must make routing decisions based on business valuations. These protocols are sometimes referred to as Path Vector protocols. We will explore this by using weighted links (including negatively weighted links) in our network topologies. We can think of Nodes in this simulation as individual Autonomous Systems (ASes), and the weights on the links as a reflection of the business relationships between ASes. Links are directed, originating at one Node, and terminating at another. Part 0: Getting Started You should review some materials on Bellman-Ford. Some resources include: • Wikipedia (https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) • “Computer Networking: A Top-Down Approach” by Kurose and Ross o 7 th edition discusses the algorithm on pages 384-385 in Chapter 5 (“The Network Layer: Control Plane”) Download and unzip the Project Files for Distance Vector from Canvas in the Assignments section. This project can be completed in the class VM or on your local machine using Python 3.10.x. You must be sure that your submission runs properly in Gradescope. Part 1: Files Layout The DistanceVector directory contains the following files: • DistanceVector.py – This is the only file you will modify. It is a specialization (subclass) of the Node class that represents a network node (i.e., router) running the Distance Vector algorithm, which you will implement. • Node.py – Represents a network node, i.e., a router. • Topology.py – Represents a network topology. It is a container class for a collection of DistanceVector Nodes and the network links between them. 3 • run_topo.py – A simple “driver” that loads a topology file (see *Topo.txt below), uses that data to create a Topology object containing the network Nodes, and starts the simulation. • *Topo.txt – These are valid topology files that you will pass as input to the run.sh script (see below). Topologies should end with “.txt”. • BadTopo.txt – This is an invalid topology file, provided as an example of what not to do, and so you can see what the program says if you pass it a bad topology. • output_validator.py – This script can be run on the log output from the simulation to verify that the output file is formatted correctly. It does not verify that the contents are correct, only the format. • run.sh – A helper script that runs some basic system checks, the topology, and the validator, a wrapper for run_topo.py and output_validator.py . Part 2: TODOs There are a few TODOs in DistanceVector.py: A. Review the methods already implemented in Node.py. a. Because DistanceVector is a subclass of Node, consider how you might use the existing methods to complete the TODOs in this list. b. Do NOT modify Node.py. B. Decide on how each node will represent its distance vector. a. Consider what might be the simplest data structure to keep track of path weights (i.e., the distance vector). b. The distance vector variable should be local to the Node, i.e., defined in the init function as a variable accessible via the `self` object (i.e. self.mylist). C. Implement the Bellman-Ford algorithm. a. Each Node will: i. send out an initial message to its neighbors ii. process messages received from other nodes iii. send updates to other nodes as needed b. Initially, a node only knows of: i. itself and that it is reachable at cost 0, ii. its neighbors and the weights on its links to its neighbors c. NOTE: a node’s links are unidirectional. d. NOTE: The Bellman-Ford algorithm implementation should terminate naturally without external intervention. D. Write a logging function that is specific to your distance vector structure. a. You should use the self.add_entry function to help with logging. b. You should assume that the logging function only knows itself. i. Do NOT access the topology for logging; logging should happen at the Node level. 4 Part 3: Testing and Debugging To run your algorithm on a specific topology, execute the run.sh bash script: ./run.sh *Topo Substitute the correct, desired filename for *Topo. Don’t use the .txt suffix on the command line. This will execute your implementation of the algorithm in DistanceVector.py on the topology defined in *Topo.txt and log the results (per your logging function) to *Topo.log . NOTE: You should not include the full filename of the topology when executing the run.sh script. For example, to run the algorithm on topo1.txt you should only specify topo1 as the argument to run.sh. For this project, you may create as many topologies as you wish and share them on Ed Discussion. We encourage sharing new topologies with log outputs. Topologies with format errors will get an error back when you try to run them. We’ve included four good topologies for you to use in testing and one bad topology to demonstrate invalid topology. The provided topologies do not cover all the edge cases; your code will be graded against more complex topologies. Part 4: Assumptions and Clarifications A. Node behavior: a. The direction of a link indicates how traffic will flow; two nodes connected with a link may pass messages regardless of traffic direction. i. Example: Node B has an incoming link from Node A, but has no outgoing link to Node A, Node B will send its distance vector to node A to “advertise” other nodes it can reach (Nodes C and D). b. A Node’s distance vector is comprised of the nodes it can reach via its outgoing links (including to itself at distance = 0). i. A Node will never advertise a negative distance to itself. (Important for negative cycles.) c. A Node advertises its distance vector to its upstream neighbors. d. Nodes do not implement poison-reverse. 5 B. Edge and Path weights: a. Edge weight values may be between -50 and 50, inclusive. b. The edge weight value type is an integer. c. There is no upper limit for path weights. d. The lower limit for path weights is “-99”, which is equivalent to “negative infinity” for this project. C. Negative cycles: a. A Node can forward traffic through a negative cycle. b. Negative cycles are a series of directed links that originate and terminate at a single node, where the sum of the link weights is less than 0. i. This can lead to a negative “count-to-infinity” problem. Therefore, your implementation must be able to detect negative cycles to terminate on its own. ii. Any node that can reach a destination node and infinitely traverse a negative cycle enroute will set the distance to that node to -99. 1. Your implementation only needs to detect and record these traversals appropriately; it does not need to mitigate them. iii. A Node can advertise a negative distance for other nodes (but not for itself). iv. A Node that receives an advertisement with a distance of -99 from a downstream neighbor should also assume that it can reach the same destination at infinitely low cost (-99). v. Example: Traffic from Node F to Node D can route through A->B->C->A indefinitely to reach an extremely low (very negative) value. c. A Node will not forward traffic destined to itself. i. Example: The below topology will not result in a count-to-infinity problem, as there are no possible pairs of source and destination nodes where traffic could indefinitely traverse a negative cycle. Node A will not forward traffic for Node A, and similarly for Nodes B and C. 6 D. Topologies used in grading: a. We will be using many topologies to test your project. This includes but is not limited to: o topologies with and without cycles (loops), including odd length cycles o topologies of varying sizes, including topologies with more than 26 nodes o topologies with nodes with names longer than one character o topologies with multiple paths to different nodes o topologies that include any combination of positive weights, zero weight, and negative weight o topologies with negative cycles, meaning a node may reach another at infinitely low cost o topologies with Nodes that do not have incoming or outgoing links ▪ All nodes will be connected but: • some may have both incoming and outgoing links • some may only have incoming links • some may only have outgoing links b. We will NOT test your submission against the following topologies (which means your algorithm does not need to account for them): o topologies with more than one link from the same origin to the same destination (multi-graphs) o topologies with portions of the network disconnected from each other (partitioned networks) o topologies that do not require intermediate steps (such as a topology with a single node) o topologies with a valid path between two indirectly linked nodes with no cycle with an actual total cost of ≤ -99 (topologies will respect that -99 is “negative infinity” for this project) Part 5: Correct Logs for Provided Topologies Below are the correct final logs for the provided topologies. We are providing them to help you identify correct behavior with respect to negative cycles and the assumptions in the instructions. We are only providing the final round; each topology should produce at least 2 rounds of output. SimpleTopo: A:(A,0) (B,1) (C,3) (D,3) B:(B,0) (A,1) (C,2) (D,2) C:(C,0) (B,2) (A,3) (D,0) D:(D,0) (C,0) (B,2) (A,3) E:(E,0) (D,-1) (C,-1) (B,1) (A,2) 7 SingleLoopTopo: A:(A,0) (D,5) (E,6) (B,6) (C,16) B:(B,0) (A,2) (D,7) (C,10) (E,0) C:(C,0) D:(D,0) (E,1) (B,1) (A,3) (C,11) E:(E,0) (B,0) (A,2) (D,7) (C,10) SimpleNegativeCycle: AA:(AA,0) (AD,-2) (AE,-1) (AB,0) (CC,-99) AB:(AB,0) (AA,-1) (AD,-3) (CC,-99) (AE,-2) AD:(AD,0) (AE,1) (AB,2) (AA,1) (CC,-99) AE:(AE,0) (AB,1) (AA,0) (AD,-2) (CC,-99) CC:(CC,0) (AB,0) (AA,-1) (AD,-3) (AE,-2) ComplexTopo: ATT:(ATT,0) (CMCT,-99) (TWC,-99) (GSAT,-8) (UGA,-99) (VONA,-11) (VZ,-3) CMCT:(CMCT,0) (TWC,-99) (ATT,1) (VONA,-10) (GSAT,-7) (UGA,-99) (VZ,-2) DRPA:(DRPA,0) (EGLN,1) (GT,-1) (UC,-1) (CMCT,-99) (TWC,-99) (ATT,13) (OSU,-1) (VONA,2) (GSAT,5) (UGA,-99) (PTGN,1) (VZ,10) EGLN:(EGLN,0) (GT,-2) (UC,-2) (DRPA,1) (CMCT,-99) (OSU,-2) (TWC,-99) (ATT,13) (PTGN,0) (VONA,3) (GSAT,5) (UGA,-99) (VZ,11) GSAT:(GSAT,0) (VONA,-3) (VZ,5) (UGA,-99) (ATT,7) (CMCT,-99) (TWC,-99) GT:(GT,0) (UC,0) (EGLN,2) (OSU,0) (DRPA,3) (PTGN,2) (CMCT,-99) (VONA,5) (TWC,-99) (ATT,15) (VZ,13) (GSAT,7) (UGA,-99) OSU:(OSU,0) (UC,0) (GT,0) (EGLN,2) (PTGN,2) (VONA,5) (DRPA,3) (VZ,13) (GSAT,7) (CMCT,-99) (ATT,15) (UGA,-99) (TWC,-99) PTGN:(PTGN,0) (OSU,-1) (UC,-1) (GT,-1) (EGLN,1) (VONA,3) (VZ,11) (GSAT,5) (DRPA,2) (ATT,13) (UGA,-99) (CMCT,-99) (TWC,-99) TWC:(TWC,0) (CMCT,-99) (ATT,1) (VONA,-10) (VZ,-2) (GSAT,-7) (UGA,-99) UC:(UC,0) (GT,0) (EGLN,2) (OSU,0) (PTGN,2) (DRPA,3) (VONA,5) (CMCT,-99) (VZ,13) (GSAT,7) (TWC,-99) (ATT,15) (UGA,-99) UGA:(UGA,0) (ATT,50) (CMCT,-99) (TWC,-99) (GSAT,42) (VONA,39) (VZ,47) VONA:(VONA,0) (VZ,8) (GSAT,2) (ATT,10) (UGA,-99) (CMCT,-99) (TWC,-99) VZ:(VZ,0) (ATT,2) (CMCT,-99) (TWC,-99) (GSAT,-6) (UGA,-99) (VONA,-9) 8 Part 6: Spirit of the Project The goal of this project is to implement a simplified version of a network protocol using a distributed algorithm. This means that your algorithm should be implemented at the network node level. Each network node only knows its internal state, and the information passed to it by its direct neighbors. Declaring global variables will be a violation of the spirit of the project. The skeleton code we provide you runs a simulation of the larger network topology. For simplicity, the Node class defines a link to the overall topology. This means it is possible using the provided code for one Node to access another Node’s internal state. This goes against the spirit of the project and is not permitted. If you have questions about whether your code is accessing data it should not, please ask on Ed Discussion or during office hours! You should not use any global variables for managing any data relating to the Nodes. However, you may use a global variable as a setting. I.E.: NEGATIVE_INFINITY = -99 Part 7: FAQs Q: May I import a python module into DistanceVector.py? For example, may I use import collections, typing, etc. A: Your solution should not require any outside Python modules. Please do not import any other modules. Q: What is the best way to format and process node messages? A: There is no right or wrong way to format messages. For best results keep things simple. Q: Is it required that the distance vectors displayed in my log files be alphabetized? A: Look at the finish_round function in Toology.py. Note how the DVs are alphabetized each round, and this is reflected in the provided correct output logs. The nodes within individual vectors are not required to be sorted. Q: Should my solution include an implementation of split horizon? A: That is not a requirement for this project. Q: What if there really is a valid path between two indirectly linked nodes with no cycle and the total cost is -99 or less? A. We will not test your submission against a topology that does this. However, from the “Assumptions and Clarifications”, note: “a Node seeing an advertised vector of -99 from a downstream neighbor can assume this means it can reach that same destination at infinitely low cost (-99).” 9 What to Turn In To complete this project, submit ONLY your DistanceVector.py file to Gradescope as a single file. Do not modify the name of DistanceVector. You can make an unlimited number of submissions to Gradescope. Your last submission will be your grade unless you activate a different submission. There are some very important guidelines for this file you must follow: A. Ensure that your submission self-terminates. If your submission runs indefinitely (i.e., contains an infinite loop) or throws an error at runtime, it will not receive full credit. Manually killing your submission via console commands or interrupts is NOT an acceptable means of termination. B. Remove any print statements from your code before turning it in. Print statements left in the simulation, particularly for inefficient but logically sound implementations, have drastic effects on run-time. Ideally, your submission should take less than 10 seconds to process a topology. If your leave print statements in your code and they adversely affect the grading process, your work will not receive full credit. (Feel free to use print statements during the project and during debugging but remove them before you submit.) C. Ensure your logs are formatted properly. Logging is the only way that we can verify that your algorithm is running correctly. The output validator will catch most formatting mistakes, but you should inspect your output manually to make sure it matches the requested format. (See the TODO comment for logging located in DistanceVector.py for format details.) a. Incorrectly formatted logs will fail the auto grader and will receive no credit. We will not be manually inspecting incorrectly named/formatted/etc. logs due to the number of students in the class. D. Ensure your solution generates completely correct output. Partial credit for individual topologies will not be awarded, even if the distance vector logs are “mostly correct.” E. Check your submission after uploading. As usual, we do not accept resubmissions past the stated deadlines. What you can and cannot share Do not share the content of your DistanceVector.py file with your fellow students, on Ed Discussion, or elsewhere publicly. You may share any log files for any topology, and you may also share new topologies. Additionally, code that you write that is not required for turn-in, like testing suites may be shared. It may be a good idea to share a “correct” log for a particular topology, if you have one, when you share the code for that topology. 10 When sharing log files, leave alphabetization on so that your classmates can use the diff tool to see if you are getting the same log outputs as they are. All work must be your own, and consulting Distance Vector Routing solutions, even in another programming language or just for reference, are considered violations of the honor code. Do not reference solutions on Github! Do not use IDE extensions (like Github Copilot) that write or recommend blocks of code to you (autocomplete for function names is fine). For more information see the Syllabus Definition of Plagiarism. We have worked hard to provide you with all the material you need to complete this project without help from Google/Stack Overflow (Searching basic Python syntax is fine). Don’t risk an honor code violation for the project. Rubric 40 pts Provided Topologies (4 total) For correct Distance Vector results (log file) on the provided topologies. 60 pts Unannounced Topologies (4 total) For correct Distance Vector results (log file) on topologies that you will not see in advance. They are slightly more complex than the provided ones and test some edge cases. GRADING NOTE: There is no partial credit for individual topologies; each topology is either “passed” or “failed”. As with previous projects in this course, due to the size of the class, we will not accept resubmissions, modifications to old submissions past the deadline, etc.
Spring 2025Search is an integral part of AI. It helps in problem solving across a wide variety of domains where a solution isn’t immediately clear. Your task is to implement several search algorithms that will calculate a route between two points in Romania while seeking to minimize time and space cost. We will be using an undirected network representing a map of Romania (and an optional Atlanta graph used for the Race!).### Table of Contents – [Setup](#setup) – [Dependencies](#dependencies) – [Jupyter](#jupyter) – [Jupyter Tips](#jupyter-tips) – [Submission](#submission) – [Custom Tests](#custom-tests) ### SetupCreate a conda environment if you have not already. For example:“` conda create –name a1_env python=3.9 -y “`Activate the environment:“` conda activate a1_env “`In case you used a different environment name to create the conda environment, you can list all environments you have on your machine by running `conda env list`. You can always refer back to the instructions provided in Assignment 0 for managing conda environments. ### DependenciesInstall the necessary libraries for this assignment after activating your conda environment and navigating to the correct directory.“` pip install -r requirements.txt “` ## JupyterTo open the Jupyter Notebook, run:“` jupyter notebook “`This should automatically open the `notebook.ipynb` as a Jupyter Notebook. If it doesn’t automatically open, you can access the Jupyter Notebook at [http://localhost:8888](http://localhost:8888/) in your browser. ## Jupyter TipsHopefully, [Assignment 0](https://github.gatech.edu/omscs6601/assignment_0/) got you pretty comfortable with Jupyter or at the very least addressed the major things that you may run into during this project. That said, Jupyter can take some getting used to, so here is a compilation of some things to watch out for specifically when it comes to Jupyter in a sort-of FAQs-like style**1. My Jupyter notebook does not seem to be starting up or my kernel is not starting correctly.**Ans: This probably has to do with activating virtual environments. If you followed the setup instructions exactly, then you should activate your conda environment using `conda activate ` from the Anaconda Prompt and start Jupyter Notebook from there.**2. I was running cell xxx when I opened up my notebook again and something or the other seems to have broken.**Ans: This is one thing that is very different between IDEs like PyCharm and Jupyter Notebook. In Jupyter, every time you open a notebook, you should run all the cells that a cell depends on before running that cell. This goes for cells that are out of order too (if cell 5 depends on values set in cell 4 and 6, you need to run 4 and 6 before 5). Using the “Run All” command and its variants (found in the “Cell” dropdown menu above) should help you when you’re in a situation like this.**3. The value of a variable in one of my cells is not what I expected it to be? What could have happened?**Ans: You may have run a cell that modifies that variable too many times. Look at the “counter” example in assignment 0. First, try running `counter = 0` and then `counter += 1`. This way, when you print counter, you get counter = 1, right? Now try running `counter += 1` again, and now when you try to print the variable, you see a value of 2. This is similar to the issue from Question 2. The order in which you run the cells does affect the entire program, so be careful. ## SubmissionYou will submit multiple files from the directory `submission` to Gradescope after following the instructions in `notebook.ipynb`. ## Custom TestsThere are a series of custom tests provided if you would like to run them through the terminal instead of Jupyter Notebook. They are:1. `search_basic_tests.py`: Sample basic tests, visualizes the Romania graph. 2. `search_submission_tests_grid.py`: Visualizes the search as a grid. 3. `search_romania_tests.py`: More comprehensive tests on the Romania graph than `search_basic_tests`. 4. `search_atlanta_tests.py`: Tests for the Atlanta graph. 5. `search_case_visualizer.py`: For visualizing specific failed cases of interest on the Romania graph.To run a full test, you can do something like:“` python search_romania_tests.py “`To run a specific test, you can do something like:“` python search_romania_tests.py SearchRomaniaTests.test_bfs_romania “`See the code for each test file for more detailed instructions and descriptions.
Spring 2025 In the lectures, you learned about Spanning Trees which are used to prevent forwarding loops in a network. In this project, you will add to those concepts by developing a distributed algorithm that can run on an arbitrary layer 2 topology. We will simulate the communications between the switches with Messages. This project is NOT an implementation of the standard Spanning Tree Protocol, so be sure not to reference any outside material or concepts that could lead you astray. Referencing any outside material1 is also a violation of the Honor Code. If you have questions about the project, post them on Ed Stem. Part 1: Setup Download the project files from Canvas. You can do this project on your host system if it has Python 3.11.x. The project does not have any dependencies outside of Python. You must be sure that your submission runs properly in Gradescope. Gradescope is the environment where your project will be graded. Gradescope and the VM are the only valid environments for this course. Part 2: Files Layout There are many files in the SpanningTree directory, but you should only modify Switch.py. The files in the project skeleton are described below. DO NOT modify these files. All of your work must be in Switch.py ONLY. You should study the other files to understand the project framework. • Topology.py – Represents a network topology of layer 2 switches. This class reads in the specified topology and arranges it into a data structure that your Switch can access. This class also adjusts the topology if any changes are indicated within the XXXTopo.py class. • StpSwitch.py – The StpSwitch is the parent class to your Switch. It provides other helpful methods you may need. Be sure to read the comments within this class before starting the project. • Message.py – This class represents a message format you will use to communicate between switches, similar to the course lectures. Specifically, you will create and send messages in Switch.py by declaring a message as: msg = Message(claimedRoot, distanceToRoot, originID, destinationID, pathThrough, timeToLive) and assigning the correct value to each input. Message format may NOT be changed. See the comments in Message.py for more information about the variables. 1 Searching general Python syntax is fine but do not search any material related to the Spanning Tree algorithm 3 • run.py – A “main” file that loads a topology file (see XXXTopo.py below), uses that to create a Topology object containing Switches, and runs the simulation. • XXXTopo.py, etc. – These are topology files that you will pass as input to the run.py file. Part 3: TODOs This is an outline of the code you must implement in Switch.py with suggestions for implementation. Keep in mind that certain update rules will take precedence over others. A. Decide on the data structure(s) that you will use to keep track of the spanning tree. 1. The collection of active links across all switches is the resulting spanning tree. 2. The data structures may be variable(s) needed to track each switch’s own view of the tree. A switch only has access to its member variables. A switch may not access its neighbor’s information – to learn information from a neighbor, the neighbor must send a message. 3. This is a distributed algorithm. The switch can only communicate with its direct neighbors. It does not have an overall view of the topology as a whole (do not access self.topology). 4. An example data structure should include, at a minimum: a. a variable to store the switch ID that this switch sees as the root, b. a variable to store the distance to the switch’s root, c. a list or other datatype that stores the “active links” (only the links to neighbors that are in the spanning tree). d. a variable to keep track of which neighbor it goes through to get to the root (a switch should only go through one neighbor, if any, to get to the root). 5. More variables may be used to track data as needed to build the spanning tree and will depend on your specific implementation. B. Implement processing a message from an immediate neighbor. 1. You do not need to worry about sending the initial messages. You only need to worry about the sending and processing of subsequent messages. 2. For each message a switch receives, the switch will need to: a. Determine whether an update to the switch’s root information is necessary and update accordingly. I. The switch should update the root stored in its data structure if it receives a message with a lower claimedRoot. 4 II. The switch should update the distance stored in its data structure if a) the switch updates the root, or b) there is a shorter path to the same root. b. Determine whether an update to the switch’s active links data structure is necessary and update accordingly. The switch should update the activeLinks if: I. The switch finds a new path to the root (through a different neighbor). In this case, the switch should add the new link to activeLinks and removes the old link from activeLinks II. The switch receives a message with pathThrough = TRUE but does not have that originID in its activeLinks list. In this case, the switch should add originID to its activeLinks list. III. The switch receives a message with pathThrough = FALSE but the switch has that originID in its activeLinks. In this case, the switch should remove originID from its activeLinks list c. Determine when the Switch should send messages to its neighbors and send the messages. I. The message FIFO queue is maintained in Topology.py. The switch implementation does not interact with the FIFO queue directly, but uses the send_message function, and receives messages as arguments in the process_message function. II. When sending messages, pathThrough should only be TRUE if the destinationID switch is the neighbor that the originID switch goes through to get to the claimedRoot. Otherwise, pathThrough should be FALSE. III. The switch should continue sending messages to its neighbors until the ttl (time to live) on the Message being processed is 0. You need to decrement the ttl every time you process a Message. Note: This is one place where this project deviates from the STP algorithm you learned in the lectures. 3. Other variables may be helpful for determining when to update the root information or the activeLinks data structure and can be added to your data structure and updated as needed, depending on your implementation. 4. Once this logic is complete, you will need to understand a few other things about the topologies to understand your final log results. For certain topologies, switches 5 may be dropped while the algorithm is running. In this case, your algorithm should adjust accordingly and create a Spanning Tree for the new topology. The Topology class will restart the message process if a drop occurs (this is handled for you). The final Spanning Tree should match the results of the new Topology, not the starting one. a. The switch that is dropped should never split the original topology. That means that the final Topology will remain connected. b. The switch that is dropped could be the original root, your algorithm should adapt accordingly. c. The Topology file will include the ttl_limit and drops. The ttl_limit is the starting ttl for each message in the Topology. The drops indicate which switch(es) will be dropped. d. You do not need to access the ttl_limit. This will be given to each message at the start of the process. You need to decrement the ttl to 0 to trigger the Topology’s drop process. C. Write a logging function. 1. The switch should only output the links that are in the spanning tree. 2. Follow the below format (# – #). Unsorted or non-standard formatting will result in penalties. Examples of correct logs with the correct format have been provided to you in the project directories. 3. Sorted: Not sorted: 1 – 2, 1 – 3 1 – 3, 1 – 2 2 – 1, 2 – 4 2 – 4, 2 – 1 3 – 1 3 – 1 4 – 2 4 – 2 Part 4: Testing and Debugging To run your code on a specific topology (SimpleLoopTopo.py in this case) and output the results to a text file (out.txt in this case), execute the following command: python run.py SimpleLoopTopo “SimpleLoopTopo” is not a typo in the example command – don’t include the .py extension. We have included several topologies with correct solutions for you to test your code against. You can (and are encouraged to) create more topologies and test suites with output files and share them on Ed Discussion. There will be a designated post where students can share these files. 6 You will only be submitting Switch.py – your implementation must be confined to modifications of that file. We recommend testing your submission against a clean copy of the rest of the project files prior to submission. You may add print statements to facilitate debugging during your development process, but they should be removed or commented out prior to submission. Part 5: Assumptions and Clarifications You may assume the following: A. All switch IDs are positive integers, and distinct. 1. These integers do not have to be consecutive. 2. They will not always start at 1. 3. There is no maximum value beyond language (Python) limitations (but your code does not need to check for this). B. Tie breakers: If there are multiple paths of equal distance to the same root, the switch should choose the path through the neighbor with the lowest switch ID. 1. Example: switch 5 has two paths to root switch 1, through switch 3 and switch 2. Each path is 2 hops in length. Switch 5 should select switch 2 as the path to the root and disable forwarding on the link to switch 3. C. There is a single distinct solution spanning tree for each topology. This is guaranteed by the first two assumptions (A and B). D. All switches in the network will be connected to at least one other switch, and all switches are able to reach every other switch. It will always be possible to form a tree that spans the entire topology. E. There will be only 1 link between each pair of directly connected switches. You do not need to consider how STP would behave with redundant links. F. A switch may always communicate with its neighbors. When a switch treats a link as inactive, the link can still be used during the simulation. “Inactive” simply means that the link will not be used for forwarding normal network traffic. G. The solution implemented in Switch.py should terminate without intervention. When there are no more messages in the queue to process, the simulation will log the 7 output and terminate. Your algorithm should stop sending messages when the ttl on the Message being processed is 0. H. Your solution should not require any outside Python modules. Do not import any other modules. What to Turn In Submit ONLY your Switch.py file to Gradescope as a single file. Do not modify the name of Switch.py. You may make an unlimited number of submissions to Gradescope before the deadline. Your last submission will be your grade unless you activate a different submission. Before submission: a. Make sure your logging format is correct. Invalid format will be marked as incorrect. b. Remove all print statements from your code before turning it in. Print statements can have drastic effects on runtime. Your submission must take less than 30 seconds per topology. If print statements in your code adversely affect the grading process, your work will not receive full credit. c. Your algorithm must converge upon the Spanning Tree within the Topology’s ttl_limit. d. Make sure your Switch.py works in Gradescope. Gradescope will give you immediate feedback, along with your grade, so we will not accept re-grade requests related to incorrect submissions. e. Make sure your Switch.py has Linux-style line endings. Windows may try to put CRLF at the end of lines. If it works in Gradescope, it is fine. f. Helper functions: Helper functions are fine as long as the names don’t conflict with anything already in the project. If it works in Gradescope, it is fine. After submission: g. Make sure your submission uploaded correctly. Late submissions will not be accepted. h. Your grade in Gradescope will be your grade for this project, with some caveats: a. Any Honor Code violations will result in a 0 and be referred to OSI. b. Any attempt to bypass or distort the autograder will result in a 0 and will be referred to OSI. i. Please Note: If Gradescope receives your submission but it fails to run, we can re-run that submission after the deadline. In this case, you will miss out on the chance to get feedback before the deadline. This can happen if too many students are submitting the project at the same time, so be sure to start early. If Gradescope is overloaded, you can re-submit at a later time to get feedback. 8 j. If, for some reason, you cannot submit your code to Gradescope and you are up against the submission deadline, create a Private post on Ed Discussion with an attachment of your Switch.py. What you can and cannot share Honor Code/Academic Integrity: Do NOT share any code from Switch.py with your fellow students, on Ed Discussion, or publicly in any form, even after the course ends. You may share log files for any topology, and you may share any code you write that will not be turned in, such as new topologies or testing suites. All work must be your own, and consulting Spanning Tree Protocol solutions, even in another programming language or just for reference, are considered violations of the honor code. Do not reference solutions on Github! Do not use IDE extensions (like Github Copilot or any AI) that write or recommend blocks of code to you (autocomplete for function names is fine). For more information see the Syllabus Definition of Plagiarism. We provide you with all the materials you need to complete this project without help from Google/Stack Overflow (Searching basic Python syntax is fine). Do not risk an honor code violation for a very doable project. Start early, ask questions in Ed Discussion, and attend TA chat sessions if needed. Rubric 10 pts Correct Submission For turning in the correct file with the correct name. You receive 10 FREE points for reading the instructions. 30 pts Provided Topologies For correct Spanning Tree results (log files) on the provided topologies. 60 pts Hidden Topologies For correct Spanning Tree results (log files) on the four topologies that you will not have access to. These cases are used to prevent students from hard coding a solution.
Banks need to efficiently handle numerous transactions every day, such as processing withdrawals, deposits, and loan applications. Many of these tasks involve prioritizing certain transactions over others. For example: – A high-value loan application may need immediate attention. – A request from a customer with a large balance may need to be given high priority. In this assignment, you will simulate a bank transaction manager by implementing a priority queue using a heap-based data structure. Your program will handle tasks based on their priority, ensuring the most important transactions are addressed first. Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 12/03. +5% Bonus Points: students whose final submission to Gradescope is before 5:00 PM Central Time on Friday 12/06 and who pass ALL immediate tests will receive an additional 2.5 points toward this assignment, up to a maximum total of 50 points. 30 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 15 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 0 points Manual Grading Feedback: There will not be any manual grading for this assignment. 50 points MAXIMUM TOTAL SCORELearning Objectives After completing this assignment, you should be able to: ● Understand the functionality of heaps and priority queues. ● Implement a heap-based priority queue in Java. ● Simulate real-world bank transaction management using heap operations. ● Continue to practice developing and writing tester methods. ● Develop and implement a nontrivial comparison method for comparison of objects along different axes depending on inputs, including a comparison based on values of an enum. Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is NOT ALLOWED for this assignment. You must complete and submit P10 individually. ● The ONLY external libraries you may use in your program are: java.util.NoSuchElementException ● Use of any other packages (outside of java.lang) is NOT permitted. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● You are allowed to define additional private helper methods. ● Only BankManagerTester may contain a main method. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● All other sources must be cited explicitly in your program comments, in accordance with the Appropriate Academic Conduct guidelines. ● Any use of ChatGPT or other large language models must be cited AND your submission MUST include screenshots of your interactions with the tool clearly showing all prompts andresponses in full. Failure to cite or include your logs is considered academic misconduct and will be handled accordingly. ● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope. Need More Help? Check out the resources available to CS 300 students here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Appropriate Academic Conduct, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ How do I cite my sources? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P10 Bank Transaction Manager. a. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. b. Do not create a project-specific package; use the default package. 2. Download five (5) Java source file(s) from the assignment page on Canvas: a. TransactionHeap.java (does NOT include a main method) b. BankManager.java (does NOT include a main method) c. Account.java (does NOT include a main method) d. Tester.java (includes a main method) e. Transaction.java (does NOT include a main method)1. Account We provide the file Account.java to help you out in implementing your code. It stores some basic information about accounts including the account number and their balance. 2. Heap Implementation We provide the TransactionHeap.java skeleton to help you out in implementing your code. It is related to max-heap implementation. It uses an array-based structure to represent the binary heap. The main heap operations include: – insert: Adds a new transaction while maintaining the heap property. – remove: Removes the highest-priority transaction while maintaining the heap property. – heapify: Adjusts the heap to maintain its property after insertions or removals. 3. Transaction class In the file Transaction.java, you need the following fields: – type: “Loan Application”, “Withdrawal Request” and “Deposit”. – priority: such as “Low”, “Normal”, “High” and “Urgent”. – amount: the amount of money to be processed. – user: the Account object associated with this transaction We also provide certain priority rules based the type of transaction: ● Loan application: Banks prioritize processing loan applications over other transactions, unless the difference between your loan amount and your balance amount is too great. We assume that up to 3 times is acceptable. Once this amount is exceeded, the loan application is considered unreasonable and will be given the lowest priority.● Deposit: The bank prioritizes depositing over withdrawal requests and unreasonable loan applications. ● Withdrawal request: Withdrawal request is only better than the unreasonable loan application. You need to help the bank assign the priorities according to the type of transaction. For the same priority, you can further prioritize the transactions by the account balance. Transaction.java makes use of enums, please read the paragraph below for more details. 3.1 A brief aside on comparing with Enums Enums as a construct in Java implement the Comparable interface, meaning they already have a compareTo() written for them. (See Enum Type and java.lang.Enum.) They are compared based on their ordinal values. That is, the enum value with the ordinal value 0 is less than the enum value with the ordinal value 1. Enums are assigned an ordinal value, usually implicitly, when declared: the first listed enum value gets an ordinal value of 0, the second gets an ordinal value of 1, and so forth. You can experiment with the example here to better understand comparing enums and ordinal values. 4. Manager program We provide the file BankManager.java to help you out in establishing the transaction manager program. Here you need to add various transactions with different amounts and priorities. Don’t forget that customer balances are important. The manager program should also be able to display the current pending transaction queues in order. 5. Testing In the file BankManagerTester.java, you need to verify: – Correct implementation of the heap function. – Priorities are correctly assigned according to given rules. – The manager program is working. All of the immediate tests on Gradescope will be on your testers. Knowing that you wrote a good tester is a good way to ensure that your other code is correct, especially without any immediate feedback from us. You’ve been practicing this skill ALL semester, you got this!Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, make a final submission of your source code to Gradescope. For full credit, please submit the following files (source code, not .class files): ● TransactionHeap.java ● BankManager.java ● BankManagerTester.java ● Transaction.java Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default this will be your most recent submission. Students whose final submission (which must pass ALL immediate tests) is made before 5pm on the Wednesday before the due date will receive an additional 5% bonus toward this assignment. Submissions made after this time are NOT eligible for this bonus, but you may continue to make submissions until 10:00PM Central Time on the due date with no penalty.
Okay no we’re not. But if we were, this is how we’d keep track of who’s winning. Hierarchical data structures allow us to efficiently maintain a sorted data structure, so our first attempt at this will be using a Binary Search Tree to maintain a leaderboard of the players of a game. Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 11/24. +5% Bonus Points: students whose final submission to Gradescope is before 5:00 PM Central Time on WED 11/27 and who pass ALL immediate tests will receive an additional 2.5 points toward this assignment, up to a maximum total of 50 points. 12 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 20 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 13 points Manual Grading Feedback: TAs or graders will manually review your code, focusing on algorithms, use of programming constructs, and style/readability. 50 points MAXIMUM TOTAL SCORELearning Objectives After completing this assignment, you should be able to: ● Describe the structure and functionality of a Binary Search Tree. ● Implement a Binary Search Tree with the relevant recursive algorithms for adding, removing, and traversing nodes. ● Demonstrate the utility of the Iterator, Iterable, and Comparable interfaces. Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is NOT ALLOWED for this assignment. You must complete and submit P09 individually. ● The ONLY external libraries you may use in your program are: java.util.Iterator, java.util.NoSuchElementException ● Use of any other packages (outside of java.lang) is NOT permitted. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● You are allowed to define additional private helper methods. ● Only Game and LeaderboardTester may contain a main method. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● All other sources must be cited explicitly in your program comments, in accordance with the Appropriate Academic Conduct guidelines. ● Any use of ChatGPT or other large language models must be cited AND your submission MUST include screenshots of your interactions with the tool clearly showing all prompts and responses in full. Failure to cite or include your logs is considered academic misconduct and will be handled accordingly. ● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope.Need More Help? Check out the resources available to CS 300 students here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Appropriate Academic Conduct, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ How do I cite my sources? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P09 Leaderboard. a. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. b. Do not create a project-specific package; use the default package. 2. Download two (1) PROVIDED Java source files from the assignment page on Canvas. You will not modify these files at all: a. BSTNode.java b. Game.java 3. Download three (3) INCOMPLETE Java source files from the assignment page. You must complete these files: a. Player.java – implements the Comparable interface b. Leaderboard.java – implements the Iterable interface c. LeaderboardTester.java 4. Create one (1) new Java source file within that project’s src folder: a. LeaderboardIterator.java – implements the Iterator interfaceImplementation Requirements Overview In this project you will implement an application that maintains a leaderboard of the players of a PvP (player-vs-player) game, ordered by their scores in that game. Players may challenge other players in the game, which may result in changes to the leaderboard. We are NOT providing additional documentation beyond this writeup and the comments in the provided code. Provided Classes The following classes are provided in their entirety. You do not need to implement anything in them. ● BSTNode – a generic Binary Search Tree node. ● Game – a class which maintains a given game’s Leaderboard across PvP challenges. Classes You Will Implement You will completely or partially implement the following classes: ● Player – represents a single player of the game, including their name and numeric score. This class is nearly complete, but you must make these objects Comparable to other Players and complete the compareTo() method. ● Leaderboard – a binary search tree consisting of BSTNode. We have provided the public interface to this data structure, but the real work is done in the protected recursive helper methods, which you must implement. ● LeaderboardIterator – Leaderboard’s toString() method relies on an enhanced for loop, which in turn requires an iterator. This iterator must begin at the Player with the smallest score in the leaderboard, and iterate through the entirety of the leaderboard in increasing order. ● LeaderboardTester – a tester class for your BST implementation. Organization of the Leaderboard The core data structure in this project is the Leaderboard, which is a Binary Search Tree of Player objects. The BST orders the Players by their score (and breaks ties using the Players’ names), so the minimum value in the BST is the Player with the smallest score and the maximum value is the Player with the largest score. We are providing you with a generic BSTNode class. Your Leaderboard must be built out of BSTNode (note Player, not T), and you will implement the relevant algorithms in the Leaderboard class. You will also need to implement Comparable for Player, which is the comparison method that you will use in Leaderboard.Implementation Details and Suggestions Begin by adding the required interfaces to your classes: ● Player must be Comparable (to what type?) ● Leaderboard must be Iterable (over what type?) ● LeaderboardIterator must be an Iterator (over what type?) 1. Implement compareTo() and Tests Once Player is Comparable, you will need to complete the required compareTo() method according to the description in the comments. At this time you should also implement the first three tester methods in LeaderboardTester: ● testCompareToDiffScore ● testCompareToSameScoreDiffName ● testCompareToEqual The comments in the file are intended to provide some direction, but you are welcome to add additional tests as you see fit. 2. Implement Leaderboard and Tests We recommend implementing the methods in the order below. Testing and debugging the latter methods will be significantly easier if you know the structure of your BST is correct, and implementing the earlier methods will help you get the structure correct. After implementing each of these methods, implement the relevant tester methods in LeaderboardTester, and test your implementation thoroughly! If you wait until the very end to test, you will have lots of weird and confusing bugs. See the next subsection for implementation/testing hints. 1. getMinScoreHelper and getMaxScoreHelper 2. countHelper 3. lookupHelper and the following test methods: a. testLookupRoot b. testLookupLeft c. testLookupRight d. testLookupNotPresent 4. addPlayerHelper and the following test methods: a. testAddPlayerEmpty b. testAddPlayer c. testAddPlayerDuplicate 5. nextHelper and the following test methods: a. testGetNextAfterRootb. testGetNextAfterLeftSubtree c. testGetNextAfterRightSubtree 6. removeHelper and the remaining test methods Note that you may NOT add ANY loops (of any kind) in the Leaderboard class. You MUST implement the above methods recursively. The loop present in the toString() method is the only permitted loop. 2.1 Some Hints ● Draw LOTS of pictures! ● Write tests as you go along. If you save testing for last you will be sad. ● You MAY use the addPlayer() method to construct a tree for other testers, but for the lookup tests in particular (since you won’t have completed that method yet) you will probably want to check out the provided getRoot() method in Leaderboard. You can add ONE player to the tree (we’ve provided the code for this), and then set up the rest of the tree by using the BSTNode methods setLeft() and setRight(). ○ Note that doing this will NOT affect the size field, so if you need to know how many nodes are present, you’ll need to use count() instead. ● For most of the Leaderboard tests, it is easiest if you use nearly identical Players that only differ by one aspect (e.g. all players are named “A” but have different scores, or all players have the default 1500 score but different names). This makes keeping track of the correct ordering easier. ● Remember: in every node, the left and right subtree should also be a valid binary tree. That is, if you were to just yank out any left or right node anywhere in the tree (with its descendants), they could stand alone as a valid binary search tree. ● If you are writing really long methods, you are probably overthinking it. My longest method by far is removePlayerHelper, clocking in at about 40 lines with comments and whitespace, and it’s about twice as long as anything else in the class. 3. Implement the Iterator The LeaderboardIterator implements the Iterator interface and iterates through all values in the tree in increasing order. This means that a full run of for (Player p : leaderboard) System.out.println(p); should begin with leaderboard.getMinScore() and end with leaderboard.getMaxScore(), and include leaderboard.size() number of different lines. YOU MAY CHOOSE the implementation details of this class (constructor, data fields, etc) as long as it conforms to the following requirements:1. Implements the Iterator interface 2. Constructed and initialized by Leaderboard’s iterator() method 3. First call to next() returns leaderboard.getMinScore() 4. Can call next() without an exception exactly leaderboard.size() number of times 5. When hasNext() returns false, calling next() causes a NoSuchElementException Your Leaderboard class must also support use of an enhanced for loop as shown above. 4. [OPTIONAL] Run the Game Now that your code is completed, you should be able to successfully run the Game.java code supported by your Leaderboard. Check out the sample output on the assignment page if you want to verify that everything is working as expected! Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, make a final submission of your source code to Gradescope. For full credit, please submit the following files (source code, not .class files): ● Player.java ● Leaderboard.java ● LeaderboardIterator.java ● LeaderboardTester.java Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default this will be your most recent submission.
In this programming assignment, we will be covering stacks and queues. You must be familiar with music streaming services that use a queue to hold songs that you can play. You are going to implement a similar queue in JukeBox! You will use stacks for the album tracklist. You are also going to be implementing a shuffle method, just like Spotify! Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 11/17. +5% Bonus Points: students whose final submission to Gradescope is before 5:00 PM Central Time on WED 11/20 and who pass ALL immediate tests will receive an additional 2.5 points toward this assignment, up to a maximum total of 50 points. 15 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 20 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 10 points Manual Grading Feedback: TAs or graders will manually review your code, focusing on algorithms, use of programming constructs, and style/readability. 50 points MAXIMUM TOTAL SCORELearning Objectives After completing this assignment, you should be able to: ● Describe the functionality of a Stack and Queue data structure and explain its operational details when implemented using a linked list. ● Predict edge case situations for stack and queue usage and verify that your implementation handles them correctly. ● Implement a simple Jukebox to play music using your stack and queue data structures. ● Implement meaningful unit tests to verify the correctness of a data structure Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is NOT ALLOWED for this assignment. You must complete and submit P08 individually. ● The ONLY external libraries you may use in your program are: java.util.ArrayList (in all files), java.util.Collections (JukeBox.java), java.util.NoSuchElementException (Album.java, JukeBox.java, JukeBoxTester.java) ● Use of any other packages (outside of java.lang) is NOT permitted. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● You are allowed to define additional private helper methods. ● Only JukeBoxTester.java may contain a main method. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● All other sources must be cited explicitly in your program comments, in accordance with the Appropriate Academic Conduct guidelines. ● Any use of ChatGPT or other large language models must be cited AND your submission MUST include screenshots of your interactions with the tool clearly showing all prompts and responses in full. Failure to cite or include your logs is considered academic misconduct and will be handled accordingly.● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope. Need More Help? Check out the resources available to CS 300 students here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Appropriate Academic Conduct, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ How do I cite my sources? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P08 Jukebox. a. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. b. Do not create a project-specific package; use the default package. 2. Download five (5) Java source file(s) from the assignment page on Canvas: a. StackADT.java b. QueueADT.java c. LinkedNode.java d. Song.java e. JukeBoxTester.java (includes a main method) 3. Create four (4) Java source file(s) within that project’s src folder: a. LinkedStack.java (implements StackADT) b. LinkedQueue.java (implements QueueADT) c. Album.java d. JukeBox.java1. Stack and Queue Interfaces These files define a simple interface for a stack and a queue implemented using a linked list, outlining operations such as adding an item, removing an item, checking the top/front item, verifying if the data structure is empty, and seeing if it contains a specific item. 2. Testing Your Code The provided JukeBoxTester skeleton file contains stub tester methods for all the various classes you implement in this assignment. ● Test as you go, and you can add private tester methods to your tester class. If your initial classes are not implemented correctly, the later ones will not work correctly either. ● Recommend drawing diagrams to understand the workings of the data structures so you can figure out their behavior before you start implementing them. ● If you haven’t already, consider spending some time learning how to use your IDE’s debugger tool. It is very helpful for following the execution of your code, especially as we get into more complex programs. There is a tutorial for Eclipse’s debugger linked on our resources page. 3. LinkedQueue and LinkedStack You will need to implement both a stack and a queue using a linked list data structure constructed from LinkedNodes. Follow the details in the interfaces to get a better idea of how to approach doing this. It would be a good idea to write the tester methods for these data structures and ensure they are working as expected. Further classes will be built using them, getting the functionalities correct here will make debugging easier later. Both data structures make use of the LinkedNode class which provides a basic structure for each element in the linked list, including its data and link to the next element. NOTE: LinkedStack and LinkedQueue contain methods NOT defined in StackADT and QueueADT. Don’t forget to implement them! 4. Song and Album The Song class holds metadata for the songs, this class has been provided to you. The Album class allows you to add songs to an album, remove them, or preview the first song of the album. The Album class utilizes the stack class you implemented in the previous section to hold songs. Once done, complete the corresponding tester methods to ensure they are working properly.5. Jukebox Once you have the Album class ready, move on to the JukeBox class that puts everything together. It contains a queue of songs. Adding an Album empties the stack into the queue. You can add individual songs to the queue as well. You can call shuffle on the queue, and play the songs. Remember to protect against exceptions! No exceptions except those EXPLICITLY stated in the Javadocs should be thrown at any time. 6. Generating Your Own Javadocs (Optional) You can generate your own Javadocs! Generating Javadocs is an important part of learning how to document your code, and can be a useful skill to know when creating your projects. If you wish, you can use the javadoc command to generate HTML files for your commented code. Simply run the command from a terminal and open the generated HTML file in a browser to view your Javadocs. Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, make a final submission of your source code to Gradescope. For full credit, please submit the following files (source code, not .class files): ● LinkedStack.java ● LinkedQueue.java ● Album.java ● JukeBox.java ● JukeBoxTester.java Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default, this will be your most recent submission. Students whose final submission (which must pass ALL immediate tests) is made before 5PM on the Wednesday before the due date will receive an additional 5% bonus toward this assignment. Submissions made after this time are NOT eligible for this bonus, but you may continue to make submissions until 10:00PM Central Time on the due date with no penalty.
Welcome to The Future, where instead of convenient things like accessible public transport and trains, we have the gig economy… and the Hyperloop. In the Hyperloop you’ll travel in one of a series of linked pods, which can be first class or economy and maintain a list of passengers (up to a hard limit). For realism, they also have a (low) probability of catastrophic malfunction! The Hyperloop Manager you’ll be completing provides the Hyperloop operators with the ability to track and control the active pods, remove malfunctioning pods, and ensure everything works as well as possible. Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 11/10. 15 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 20 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 10 points Manual Grading Feedback: TAs or graders will manually review your code, focusing on algorithms, use of programming constructs, and style/readability. 50 points MAXIMUM TOTAL SCORELearning Objectives After completing this assignment, you should be able to: ● Explain how data is stored in a doubly-linked list, including how additional elements are added in locations other than the head or tail of the list ● Identify how an Abstract Data Type influences the structure of an implementation ● Implement meaningful unit tests to verify the correctness of a data structure Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is ALLOWED for this assignment, BUT you must register your partnership before the autograder is released. If you do not do so, you must complete this assignment individually or be subject to Academic Misconduct sanctions. ● The ONLY external libraries you may use in your program are: Pod.java – java.util.Arrays, java.util.Random All other classes – only relevant exceptions ● Use of any other packages (outside of java.lang) is NOT permitted. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● You are allowed to define additional private helper methods. ● Only LoopStationTester may contain a main method. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● All other sources must be cited explicitly in your program comments, in accordance with the Appropriate Academic Conduct guidelines. ● Any use of ChatGPT or other large language models must be cited AND your submission MUST include screenshots of your interactions with the tool clearly showing all prompts and responses in full. Failure to cite or include your logs is considered academic misconduct and will be handled accordingly.● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope. Need More Help? Check out the resources available to CS 300 students here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Appropriate Academic Conduct, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ How do I cite my sources? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P07 Hyperloop. a. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. b. Do not create a project-specific package; use the default package. 2. Download five (5) Java source file(s) from the assignment page on Canvas: a. ListADT.java (abstract data type) b. LinkedNode.java (instantiable class) c. Pod.java (instantiable class) d. MalfunctioningPodException.java (custom CHECKED exception) e. LoopStationTester.java (skeleton code for tester, includes a main method) 3. Create two (2) Java source file(s) within that project’s src folder: a. Track.java (instantiable, implements ListADT) b. LoopStation.java (instantiable, manages several Tracks)1. Testing Your Code The provided LoopStationTester file contains only FOUR tester methods, focused on the high-level methods in the LoopStation class. LoopStation requires that the methods in Track be working correctly! ● Test as you go, and add private tester methods to your tester class to help ensure that Track is working as expected. If methods in Track are not correct, LoopStation will not work correctly either. ● The crux method in this assignment is likely to be the clearMalfunctioning() method in LoopStation, which will rely heavily on Track’s remove() method. Draw diagrams and ensure you know how to remove from all possible locations in a doubly-linked list BEFORE you begin implementing! ● If you haven’t already, consider spending some time learning how to use your IDE’s debugger tool. It is very helpful for following the execution of your code, especially as we get into more complex programs. There is a tutorial for Eclipse’s debugger linked on our resources page. 2. Pod objects The Hyperloop you will be implementing contains a series of Pod objects. We’ve provided these for you in their entirety, but you might want to add a toString() method to help with debugging. There is no specified format for this, as it’s not a required method, but you might consider something like the Arrays.toString() of the passenger list, followed by a * if the Pod is currently not functional. Note that the Pod object’s isFunctional() accessor method has a 1-in-20 chance of CAUSING the Pod to malfunction, which in turn will cause every other Pod method to throw an exception. You’re free to use this method if you like, but be aware that using it may cause other problems that you’ll need to take into consideration in your tester methods! It’s very much in your interest to figure out a more creative solution to determining whether a Pod is currently functional. 3. Track – a doubly-linked list In class you implemented a singly-linked list. Now you’ll implement a doubly-linked list yourself! This variety of linked list is composed of nodes which maintain not only a reference to the next element in the list, but also the previous element, so that you can move through the list in either direction. NOTE: Track contains three (3) methods NOT defined in ListADT. Don’t forget to implement these!4. LoopStation and management tasks Once you have a working Track class, move on to the LoopStation and its associated tester methods. This will maintain a set of three different Tracks and move Pods between them. It will also have the ability to detect and remove malfunctioning pods. Remember to protect against exceptions! No exceptions except those EXPLICITLY stated in the Javadocs should be thrown at any time. Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, make a final submission of your source code to Gradescope. For full credit, please submit ONLY the following files (source code, not .class files): ● Track.java ● LoopStation.java ● LoopStationTester.java Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default this will be your most recent submission. Students whose final submission (which must pass ALL immediate tests) is made before 5pm on the Wednesday before the due date will receive an additional 5% bonus toward this assignment. Submissions made after this time are NOT eligible for this bonus, but you may continue to make submissions until 10:00PM Central Time on the due date with no penalty.
So far your approaches to solving various problems in programming involve iteration. However, sometimes, depending on the problem, a recursive approach is simpler in implementation than a completely iterative solution. (You may not believe this right now as you are learning and wrestling with the concept, but it’s a great and vital programming tool.) In this assignment you will solve three different problems about partitions of N using recursion. If you don’t know what a partition of N is, we will break it down for you in Section 2.1. The problems you are solving are relevant to many different applications such as number theory, graphs, and even abstract algebra! (Each of these with possible applications in CS topics like graphics and cryptography (security)!) Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 10/27. +5% Bonus Points: students whose final submission to Gradescope is before 5:00 PM Central Time on WED 10/30 and who pass ALL immediate tests will receive an additional 2.5 points toward this assignment, up to a maximum total of 50 points. 17 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 14 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 14 points Manual Grading Feedback: TAs or graders will manually review your code, focusing on algorithms, use of programming constructs, and style/readability. 50 points MAXIMUM TOTAL SCORELearning Objectives After completing this assignment, you should be able to: ● Formulate a recursive solution to a problem by describing the base cases, recursive cases, and how to decompose it into smaller subproblems ● Implement a recursive solution to a problem by making recursive calls to solve the subproblems, and combining the results ● Compare the recursive formulations of similar problems ● Explain why recursion can be a useful problem-solving tool ● Develop unit tests to verify the correctness of your algorithms Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is ALLOWED for this assignment, BUT you must register your partnership before the autograder is released. If you do not do so, you must complete this assignment individually or be subject to Academic Misconduct sanctions. ● The ONLY external libraries you may use in your program are: java.util.ArrayList – All four (4) source files java.util.Random – PartitionCalculatorTester.java ● Use of any other packages (outside of java.lang) is NOT permitted. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● You are allowed to define additional private helper methods. ● Only PartitionCalculatorTester may contain a main method. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● All other sources must be cited explicitly in your program comments, in accordance with the Appropriate Academic Conduct guidelines.● Any use of ChatGPT or other large language models must be cited AND your submission MUST include screenshots of your interactions with the tool clearly showing all prompts and responses in full. Failure to cite or include your logs is considered academic misconduct and will be handled accordingly. ● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope. Need More Help? Check out the resources available to CS 300 students here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Appropriate Academic Conduct, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ How do I cite my sources? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P06 Calculating Partitions. a. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. b. Do not create a project-specific package; use the default package. 2. Download three (3) Java source files from the assignment page on Canvas: a. Partition.java (does NOT include a main method) b. PartitionCalculatorTester.java (includes a main method) c. TesterUtility.java (does NOT include a main method)3. Download two (2) more starter files from the assignment page on Canvas: a. partitions.csv (contains the answers for the first 2 problems) b. permutedPartitions.csv (contains the answers for the last problem) 4. Create one (1) Java source file within that project’s src folder: a. PartitionCalculator.java (does NOT include a main method) 1. Provided Starter Code We provided several files to help you out in implementing your code, in particular, Partition.java and TesterUtility.java. Before you start implementing code, read over them CAREFULLY as they will help you with both of the recursive methods and testers. Here we provide a brief overview of them. 1.1 Partition class The provided Partition class represents a collection of numbers which will (hopefully, eventually) add up to the given value N. You do not need to implement any methods in this class, but you should fully read the javadoc comments in the provided source code file, in order to understand the methods available to you. They will be very important to complete the main recursive methods. Each Partition object tracks the numbers currently assigned to it and their sum, as well as a boolean indicating whether the order of those numbers is significant. (The order will only be significant for Problem 3 later.) Consider this toString() output of two partial Partitions of 5, with their orderMatters set to false: Partition of N=5: [1, 2] -INVALID Partition of N=5: [2, 1] -INVALID p1.equals(p2): true Since neither of these Partitions have contents that add up to their specified N value, they are both considered “invalid” partitions of N. To make them valid, they will need to have more numbers added to them. However, in their current state, they are considered equal, since both contain one 1 and one 2. It’s also totally okay to add numbers to the Partition that make its total greater than N! If I call addNumber(3) on the first partition, this is just “overfilling” and results in an invalid Partition: Partition of N=5: [1, 2, 3] -INVALID While Partition doesn’t come with its own isValid() method, you can determine if any given Partition is valid for yourself in exactly the same way that Partition’s toString() does, since you have accessor methods for all of Partition’s values (except orderMatters, which you can set directly for this assignment).The most important methods to familiarize yourself with in the Partition class are: ● The constructor, which initializes an empty partition of N ● The getSum() and getN() accessor methods, which will help you compare the current state of the partition to its goal state ● The addNumber() method, which allows you to add a new number to the partition ● The copyOf() method, which creates a new DEEP copy of the partition so you can work from the same starting state but in a different direction – say, by adding a value to one copy but not the other 1.2 Tester Utility class The TesterUtility class contains methods which will help you determine expected values for your tester methods and compare generated partition lists. ● The getPartitionCount() and getPartitions() methods read expected values in from the provided CSV files – so make sure those files are correctly located in your PROJECT FOLDER, not the src directory or any other subdirectory. ● The comparePartitionsLists() method is effectively a complicated equals method for lists of partition objects, determining whether both lists contain equivalent partitions when order does or doesn’t matter (and it never matters for the order of the Partitions themselves). 2. Calculating Partitions of N 2.1 Definitions Let’s start with some definitions and observations that are vital to working through the problem. ● A partition of N is a set of positive integers (i.e. whole numbers > 0), that when summed together equals N. For all N > 1, there are more than one partition. ○ Ex. n = 5 → [3,2] ○ Ex. n = 3 → [1,1,1] ○ Ex. n = 6 → [6] ● A set of positive integers is considered a VALID partition of N if and only if all they add up to N. ○ Ex. n = 4 → [2,1] – is NOT VALID, (2+1= 3) ○ Ex. n = 10 → [4,3,2] – is NOT VALID, (3+2+4 = 9) ○ Ex. n = 7 → [2,2,2,1] – is VALID, (2+2+2+1 = 7) ○ Ex. n = 2 → [1,1] – is VALID, (1+1 = 2) ○ Ex. n = 13 → [13] – is VALID (13 = 13)● A set of positive integers is considered overfilled if the sum of all the numbers is greater than the N value. ● Two partitions of N are considered the SAME if they have the same N value and same numbers, regardless of order. (Ex. [1,3,1] and [3,1,1] are considered the same partition of n = 5.) 2.2 [Problem 1] – Count the number of Partitions The first recursive method that you are required to write solves the following problem: Given a value N, return the total number of partitions for that value N. PartitionCalculator.java needs a method with the signature below: public static int numOfPartitions(int N) For example if we call numOfPartitions(5), the return value is 7 (as there are only 7 unique partitions of 5): 1. [5] 2. [4,1] ⇔ [1,4] 3. [3,2] ⇔ [2,3] 4. [3,1,1] ⇔ [1,3,1] ⇔ [1,1,3] 5. [2,2,1] ⇔ [2,1,2] ⇔ [1,2,2] 6. [2,1,1,1] ⇔ [1,2,1,1] ⇔ [1,1,2,1] ⇔ [1,1,1,2] 7. [1,1,1,1,1] We strongly recommend implementing a private, recursive helper method for this problem. Build solutions using the Partition objects – and remember, you can make MULTIPLE recursive calls from a single method! You’ll almost certainly need to create multiple Partition objects over the course of solving this problem, even though the public-facing method involves only integer values. ➔ Remember to account for the cases where a number (like 1) is used more than once or not at all in a given Partition. How can you accomplish this with NO LOOPS? We’re NOT worried about efficiency for this program; the concern here is recursive thinking. As long as you have a fully recursive solution, it can be as inefficient as it needs to be. (Stuck? See Tips & Hints.) This method MUST be recursive OR make a call to a recursive helper method. (We will check this as a part of manual grading.) Using a loop of any kind will result in loss of ALL manual points for this method, even if there is a recursive call. There are several tester methods associated with this method, be sure to implement them as you go! (Testing information can be found in Section 3.)2.3 [Problem 2] – Calculate all of the Partitions The second recursive method that you are required to write solves the problem below: Given a value N, return all of the partitions for that value N. PartitionCalculator.java needs a method with the signature below. public static ArrayList calculatePartitions(int N) For example if we call calculatePartitions(4), there are a total of 5 of them, the returned list should contain the following partitions (in any order): 1. [4] 2. [3,1] ⇔ [1,3] 3. [2,2] 4. [2,1,1] ⇔ [1,2,1] ⇔ [1,1,2] 5. [1,1,1,1] You’ve very nearly solved this problem in the previous method; now instead of COUNTING those Partitions you’ve created, we’re actually going to save the Partition objects themselves. This method MUST be recursive OR make a call to a recursive helper method. (We will check this as a part of manual grading.) You should be able to accomplish this WITHOUT needing a looping construct. Using a loop of any kind will result in loss of ALL manual points for this method, even if there is a recursive call. There are several tester methods associated with this method, be sure to implement them as you go! 2.4 [Problem 3] – Calculate all permutations of Partitions The second recursive method that you are required to write solves the problem below: Given a set of all partitions for value N, return all permutations of each partition given. You can assume that you are given a complete set of Partitions as input. PartitionCalculator.java needs a method with the signature below. public static ArrayList calculateAllPermutations(ArrayList partitions) For example, if we call calculatePartitions() passing it the list of partitions of 4 that we generated in Problem 2, the returned list should contain the following nine (9) partitions with orderMatters = true (in any order):1. [4] 2. [3,1] 3. [1,3] (Note: no longer “the same as” [3,1]!) 4. [2,2] 5. [2,1,1] 6. [1,2,1] 7. [1,1,2] 8. [1,1,1,1] This method MUST be recursive OR make a call to a recursive helper method. (We will check this as a part of manual grading.) You MAY need a looping construct to complete this method. Make sure that this loop is NOT redoing any work that the recursion is doing. If the loop does redo work accomplished by recursion, you will lose points in manual grading. There are several tester methods associated with this method, be sure to implement them as you go! 2.5 Tips & Hints ● Start with the “trivial” cases (base cases) first – and be aware that there may be more than one! After you figure out a base case, try to solve a problem that is one step above that base case, that is, after one recursive call you will hit the base case. Then add one more step above that, and so on. You should start seeing a pattern to how the problem is solved. ● Several ArrayList methods utilize equals(). Partition.java overrides that method to make it easy to utilize those methods! Make sure a Partition’s orderMatters is set to the correct value for the given problem, or equals() may give you some unexpected results. You may access/set that value directly in this program; that’s fine. ● To help with figuring out how to use/join the return value of recursive call(s), assume they return the correct answer. This helps you focus on JUST the current problem at hand and not all of the smaller sub-problems. ● Use the debugger tool! Tutorial on how to use the one in Eclipse can be found here. ● Test as you go! And draw lots of diagrams and pictures as you work through stuff! ● Note there are multiple different ways you can approach these problems using recursion. The idea is you need to explore all possibilities in a structured manner. Some solutions might start at the shortest length partition while others might start at the longest length partition. ● If the base case does not work, then the recursive case will not work. ● Usually at around n=4 or n=5 is when you can start seeing if the recursive case is not working properly.3. Testing The provided tester file contains the signatures and Javadoc method headers describing the required tester methods. You are HIGHLY encouraged to use methods provided in TesterUtility. If calling some of these methods results in an IOException, make sure that the provided csv files are in the base folder of your project (NOT in the src folder). NOTE: The csv files only contain the number of partitions for N between [1, 50]; the partitions for N between [1, 35]; and the permutations of partitions for N between [1, 12]. A recursive implementation very likely has a HIGH time complexity, so we do not recommend going past these values. To give you a benchmark, Problem 3 with N = 12 takes several minutes to complete on my machine! 3.1 On Fuzz Testing The new randomized testing technique we will introduce is called fuzz testing or fuzzing. Fuzzing means generating a large number of random inputs for your program and checking that the program behaves as expected. Using many random inputs allows you to exercise a bunch of the different code paths in your implementation – ideally, we would exercise every possible path control flow could follow in your program with many different inputs, including edge cases. As an aside, fuzz testing was invented here at UW-Madison and is celebrating its 30th year (the professor is actually still here at the university) – it is a widely used technique for finding security vulnerabilities. 3.1.1 Fuzz Testing numOfPartitions() Here are the following requirements for this test: ● Generate a random number of times to test the method between [100, 199]. ● For each test, generate a new random N value for a test case in the range [1,50]. ● Test that the method returns the correct value. If it does not for ANY of tests, the implementation fails. 3.1.2 Fuzz Testing calculatePartitions() Here are the following requirements for this test: ● Generate a random number of times to test the method between [1, 20]. ● For each test, generate a new random N value for a test case in the range [1,35]. ● Test that the method returns the correct value. If it does not for ANY of tests, the implementation fails.Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, make a final submission of your source code to Gradescope. For full credit, please submit the following files (source code, not .class files): ● PartitionCalculator.java ● PartitionCalculatorTester.java Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default this will be your most recent submission. Students whose final submission (which must pass ALL immediate tests) is made before 5pm on the Wednesday before the due date will receive an additional 5% bonus toward this assignment. Submissions made after this time are NOT eligible for this bonus, but you may continue to make submissions until 10:00PM Central Time on the due date with no penalty.
This assignment focuses on building a simple library management system in Java, where you will create a Library class to manage a collection of Book objects. The system allows for adding, removing, updating, and searching for books. It also includes functionalities to test the library’s operations and demonstrate its usage, giving you hands-on experience with object-oriented programming concepts such as encapsulation and array manipulation. Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 09/29. +2.5 points Bonus Points: students whose final submission to Gradescope has a timestamp earlier than 5:00 PM CDT on WED 10/02 will receive an additional 2.5 points toward this assignment, up to a maximum total of 50 points. 25 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 10 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 10 points Manual Grading Feedback: TAs or graders will manually review your code, focusing on algorithms, use of programming constructs, and style/readability. 50 points POINTS_POSSIBLELearning Objectives After completing this assignment, you should be able to: ● Implement a custom data type in Java by following a given design structure with private data fields and public methods ● Demonstrate the utility of defining a constructor and accessor/mutator methods by validating the implementation in a separate tester class ● Identify and use appropriate methods from Java’s ArrayList class to store objects of your custom data type Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is NOT ALLOWED for this assignment. ● The ONLY external libraries you may use in your program are: java.util.ArrayList java.util.Random Use of any other packages (outside of java.lang) in submitted files is NOT permitted. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● You are allowed to define additional private helper methods in any class. ● Only the Driver class and Tester class may contain a main method. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope.Need More Help? Check out the resources here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Academic Conduct Expectations and Advice, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ What do I do about hardware problems? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P03 Library Management System 1. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. 2. Do NOT create a project-specific package; use the default package. 2. Create two (2) Java source files within that project’s src folder: 1. Book.java (does NOT include a main method) 2. Library.java (does NOT include a main method) 3. Download three (3) Java source files from the assignment page on Canvas: 1. LibraryDriver.java (includes a main method) 2. LibraryTester.java (includes a main method) You do not need to modify anything or submit the LibraryDriver.java. It is only for your own benefit. If you add the downloaded files to the project right away, you’ll probably see quite a few errors, because they assume there are methods in your source files that don’t exist yet, but don’t worry! You’ll fix that shortly.Implementation Requirements Overview The Javadocs for the classes you will write in their entirety are found here: ● Book ● Library The Book and Library define a simple Library Management System. The Library contains a class that manages a collection of books, allowing for functionality such as adding, removing, finding, and updating books. It also includes methods to retrieve the total number of books and print all books in the library. The Book file defines a Book class, which represents a book with a title and an author, and includes accessor and mutator methods to retrieve and modify these attributes. Together, these classes provide a basic framework for managing a library’s book collection. In this program, you are required to complete both of these instantiable classes, as well as 1 tester file (for better code organization). We’ve provided a couple of example tests to get you started in each of the tester files, but be sure to complete them so that your code passes all tests by the time you make your final submission to Gradescope. The Book Class and its tester methods In this step we are going to create our first class called Book. Please refer to the Book JavaDoc for the correct field and method names of this class. 1. Define private fields according to the Book JavaDoc: ● The Book class should have five (5) private fields: ● String title ● String author ● int yearOfPublication ● String publisher ● int numberOfPages 2. Each of these fields should be private, meaning they can only be accessed or modified through methods, and non-static, meaning that each Book object has its own value for each field. 3. Create a constructor: ● The constructor should take 5 parameters (one for each field) and initialize the corresponding fields. For validating our arguments, we need to apply some validity checks. If the yearOfPublication is negative or more than the current year, an IllegalArgumentException should be thrown with an appropriate message. If thenumber numberOfPages, an IllegalArgumentException should be also thrown with the appropriate message. 4. Implement the accessor methods: ● For each field, write a public method that returns the value of that field. ● For example, getTitle() should return the value of title. 5. This is a good point to start implementing your tester methods: ● In the LibraryTester.java, start with the constructor and accessor method testers: ● Create a Book object using the constructor and test if the values you provided are returned correctly by the accessor methods. ● We have provided for help the first tester method testGetTitle()for getTitle() to help you get started. 6. Implement the tester methods for the mutators: ● After creating a Book object, use the mutator methods to modify some fields (for example, change the Author name and check if it was actually changed). ● We have provided for help the tester method testSetTitle()for setTitle() to help you get started. 7. Implement the mutator methods: ● For each field, write a public method that allows the field to be modified. ● For example, setTitle(String newTitle) allows you to change the value of title. ● Again, we need to implement some validity checks before passing the arguments to the fields. We need to make sure that there is no negative year or a future year (more than 2024) passed as an argument for yearOfPublication, otherwise an IllegalArgumentException should be thrown.Negative values should also be checked for numberOfPages and an IllegalArgumentException should be thrown. Tips: ● Pay attention to naming conventions: method names and fields are in lowerCamelCase, and the class name is in UpperCamelCase. ● Keep the tests simple; you only need to check if the accessors and mutators are functioning correctly. The Library Class and its tester methods In this step we are going to create our second class called Library. Please refer to the Library JavaDoc for the correct field and method names of this class. 1. Create an ArrayList to store the books: ● In Library.java, create a private field called books which is an ArrayList of Book objects. This will be used to store all books in the library. 2. Implement getTotalBooks() and getAllBooks().To help you get started we have provided the tester method testGetTotalBooks().● This method should return the total number of books in the library using books.size(). 3. Implement testAddMultipleBooks() in the LibraryTester.java. To help you get started we have provided the tester method testAddBook(): ● In LibraryTester.java, create a Library object and add a few Book objects to it in order of the year they were published, from the older to the newer. ● Use getTotalBooks() to verify that the books were added correctly. 4. Implement addBook(Book book) in the Library.java: ● This method should add a new book to the books list ordered by the year the book was published, from the older to the newer. 5. Implement testRemoveOneOfManyBooks() in the LibraryTester.java. We have provided testRemoveBookByTitle() for help: ● Add a few books to the library, remove one by title, and check if the total number of books decreased and the arraylist is as expected after removing the book. 6. Implement removeBookByTitle(String title) in the Library.java: ● This method should remove the first book that matches the given title. 7. Implement testFindBooksByAuthor() and testFindBooksByMultipleAuthors() in the LibraryTester.java : ● Add multiple books by different authors and use this method to verify that it correctly returns the list of books by the specified author or authors. 8. Implement findBooksByAuthor(String author) in the Library.java: ● This method should return an ArrayLlist of books written by the given author. 9. Implement testUpdateBookTitle() and testUpdateMultipleBookTitles() in the LibraryTester.java: ● Add a book, update its title and return true if that was done successfully or false otherwise. Follow the same logic for multiple books. 10. Implement updateBookTitle(String oldTitle, String newTitle) in the Library.java: ● This method should find a book by its current title and update it to the new title. 11. Implement testUpdateBookAuthor() and testUpdateMultipleBookAuthors() in the LibraryTester.java: ● Add a book, update its author and return true if that was done successfully or false otherwise. Follow the same logic for multiple books. 12. Implement updateBookAuthor(String title, String newAuthor) in the Library.java: ● This method should find a book by its current title and update the author. 13. Implement printAllBooks(): ● This method should print the title and author of every book in the library. Tips: ● Use ArrayList methods such as add(), remove(), and size() to manage the collection of books.● For searching and updating, iterate over the list and use equalsIgnoreCase() to compare titles and authors. ● Use the compareBooks() method to compare the expected and actual list of books in your tests. Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, submit your source code through Gradescope. For full credit, please submit ONLY the following files (source code, not .class files): ● Book.java ● Library.java ● LibraryTester.java Do NOT submit LibraryDriver.java for grading; this class is for your benefit only and may result in you losing points if it is submitted. Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default, this will be your most recent submission. Students whose final submission (which must pass ALL immediate tests) is made before 5pm on the Wednesday before the due date will receive an additional 5% bonus toward this assignment. Submissions made after this time are NOT eligible for this bonus, but you may continue to make submissions until 10:00PM Central Time on the due date with no penalty.
In this program, you will be developing a graphical implementation of a walking animation: By cycling through the frames of this “walk cycle”, you’ll give the figure the appearance of walking in a window on your screen. You’ll create a few figures that will walk (or not) independently, and you’ll eventually make your program clickable and sensitive to key presses, as a (relatively gentle) introduction to working with a graphical user interface. This is a very long writeup, but it is intended to be followed as a walkthrough. You will add and remove code over the course of creating this program – pay close attention to how each of these operations modifies your code! We’ll be revisiting GUIs later, in P05. Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM on 09/15. +5% Bonus Points: students whose final submission to Gradescope is before 5:00 PM Central Time on WED 09/18 and who pass ALL immediate tests will receive an additional 2.5 points toward this assignment, up to a maximum total of 50 points. 25 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 20 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 50 points MAXIMUM TOTAL SCORELearning Objectives After completing this assignment, you should be able to: ● Initialize (create) and use custom objects and their methods in Java ● Describe how null references can be detected in a perfect-size array ● Create a simple program with a graphical user interface using our Utility frontend for the Processing library ● Explain how and when the code in GUI “callback” methods runs Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is NOT ALLOWED for this assignment. You must complete and submit P02 individually. ● The ONLY external libraries you may use in your program are: java.util.Random java.io.File processing.core.PImage Use of any other packages (outside of java.lang) is NOT permitted. ● NOTE: The automated tests in Gradescope do not have access to the full Processing library. If you use any methods in your program besides those provided in the Utility class, your code may work on your local machine but FAIL the automated tests. This program can be completed successfully using ONLY these two methods from the Processing library. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● All methods must be static. You are allowed to define additional private helper methods. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● All other sources must be cited explicitly in your program comments, in accordance with the Appropriate Academic Conduct guidelines. ● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope.● Any use of ChatGPT or other large language models must be cited AND your submission MUST include screenshots of your interactions with the tool clearly showing all prompts and responses in full. Failure to cite or include your logs is considered academic misconduct and will be handled accordingly. Need More Help? Check out the resources available to CS 300 students here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Appropriate Academic Conduct, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ How do I cite my sources? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P02 Walking Simulator. a. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. b. Do not create a project-specific package; use the default package. 2. Create one (1) Java source file(s) within that project’s src folder: a. WalkingSim.java (includes a main method) All methods in this GUI program will be static methods, as this program focuses on procedural programming; in future GUI programs we’ll be using the graphics library more like it is intended to be used (that is, in an Object Oriented way!). Note that the following instructions are Eclipse-specific, but IntelliJ and other IDE users should be able to extrapolate.1.1 Download the Processing jar file Download the p02core.jar file from Canvas 1 , which contains: 1. the core Processing library (this one’s using build 4.0.1; we’ll use the current 4.3 build later this semester), 2. a custom Utility class to make Processing easier for you to use right now, 3. and a custom object class we’ll explore later. Copy the JAR file into your project folder or drag it into the project in the sidebar in Eclipse, and refresh the Package Explorer panel in Eclipse if you don’t see it there yet. Right click the JAR file in the project and select Build Path > Add to Build Path from the menu. The JAR should now appear as a Referenced Library in your project: A screenshot of the Eclipse Project Explorer showing a project called P02 Walking Sim set up with a build path that references p02core.jar If the “Build Path” entry is missing when you right click on the jar file in the Package Explorer: 1. Right-click on the project and choose “Properties” 2. Click on the “Java Build Path” option in the left side menu 3. From the Java Build Path window, click on the “Libraries” tab 4. Add the p02core.jar file located in your project folder by clicking “Add JARs…” from the right side menu 5. Click on the “Apply” button 1.2 Check your setup To test that the jar file was added correctly to your build path, find your main method in the WalkingSim class and add the following method call: Utility.runApplication(); // starts the application If everything is working properly, you should see a blank window with the text “P02 Walking Simulator” in the top bar as shown below, and an error message in the console that we’ll resolve shortly: 1 For Mac users with Chrome: this download may be blocked. If you’re opposed to switching to Firefox (omg please switch) go to “chrome://downloads/” and click on “Show in folder” to open the folder where the jar file is located.A screenshot of a blank P02 Walking Simulator window. ERROR: Could not find method named setup that can take arguments [] in class WalkingSim. If you have any questions or difficulties with this setup, please check Piazza or talk to a TA or peer mentor before continuing. Note that the provided jar file will ONLY work with Java 17, so if you’re working with another version of Java, you’ll need to switch now. 1.3 Download the walk cycle images Finally, download the images.zip file and unzip it; it contains 8 images of a figure walking as on the first page. (Make SURE you unzip the file before continuing; if you try to use the zip file directly, it won’t work.) Add this folder to your project folder in Eclipse, either by importing it or drag-and-dropping it into the Package Explorer directly: 2. Utility framework and overview of Walker class Using the Processing library in its pure form requires a bit more understanding of Java and Object-Oriented Programming than you have right now, so we’ve provided an interface called Utility so it’s a bit easier to just jump into. This allows you to set up a GUI program in a way that’s very similar to the text-based programs you’ve been writing so far.Later this semester, you’ll use the real thing! But for now: think of this as training wheels. As you’re writing your code for this program, you may want to refer to the Appendix at the end of this document for a full listing of the methods available to you in the Utility class, as well as the Walker class javadocs. 2.1 Callback methods overview A graphical user interface still works slightly differently – it relies on callback methods. These are methods that another method calls; you won’t call them from your code, the GUI library will. Later in this program, you’ll implement the following callback methods: ● setup() : called automatically when the program begins. All data field initialization should happen here, any program configuration actions, etc. This method is only ever called once. ● draw() : runs continuously as long as the application window is open. Draws the window and the current state of its contents to the screen. ● mousePressed() : called automatically whenever the mouse button is pressed. ● keyPressed() : called automatically whenever a keyboard key is pressed. The code that YOU write won’t ever call these methods; you’re just going to set them up so that Processing can use them while your program is running. 2.2 Walker class overview The Walker class is the data type for the walking figure object that you’ll create and use in your application. Make sure to read the descriptions of the methods – not just the summaries at the top of the page – to understand how these methods work. You will not be implementing any of these methods. They are provided for you in their entirety in the jar file you’ve already downloaded and added to your code. All you need to do is use them! 3. Adding to the Walking Simulator display window In this next section, you’ll begin filling out some of those callback methods in the WalkingSim class. 3.1 Define the setup() and draw() callback methods When you created your blank window, we noted an error related to the lack of a setup() method. Let’s take care of that error next.1. Create a public static method in WalkingSim named setup, with no parameters and no return value. 2. Next, run your program. The error message should now read: ERROR: Could not find method named draw that can take arguments [] in class WalkingSim. 3. Solve that error by adding another public static method to WalkingSim named draw with no parameters and no return value. 4. Note that Utility.runApplication() calls setup() once and then keeps calling draw() repeatedly until the application ends – so when those methods don’t exist, you get errors in your console, even though these two methods are never called within your code. a. Add a print statement (System.out.println()) with some test output to the setup() method. How many times does that get printed when you run the program? b. Now add a print statement to draw(). How many times does THAT get printed? c. Delete or comment out the print statements from 4a and 4b now, we don’t need them (and they’ll probably get annoying if you leave them in). Logically, we’ll be organizing our code so that the setup() method contains only code initializing variables we’ll need for the program, and the draw() method contains only code affecting what’s being displayed in the application window. 3.2 Set the background color For fun, let’s make the background color of your application window a different randomly-generated color every time you run the program. 1. Add two private static fields to your WalkingSim class: a Random variable called randGen, and an int variable called bgColor. These variables must be declared OUTSIDE of any method but still INSIDE the WalkingSim class. The top of the class is a good place to put them. 2. In setup(), initialize the randGen field to a new Random object. Then use randGen to generate a random integer value with no enforced bounds, and store the value in bgColor. This way we’re only generating ONE random color every time we run the program. 3. Move to the WalkingSim.draw() method, and call Utility.background() method with your bgColor static variable as the single argument. 4. Now, every time you run the program, the background will be a different color! Try running it a few times and see what kinds of colors you get. We’re practicing good code organization: the call to Utility.background() affects the contents of the window, so it belongs in the WalkingSim.draw() method. The setup() method only initializes variables like bgColor and shouldn’t affect the display window at all.3.3 Draw one walker to the middle of the screen Now let’s start adding some objects to our application. 1. Add the following import statements to your WalkingSim class: a. import java.io.File; b. import processing.core.PImage; 2. Create a private static PImage field named frame to your WalkingSim class. For now, we’re only going to load in the first frame of our walk cycle animation. 3. Since we’re initializing variables in setup(), initialize your frame field there by calling Utility.loadImage(“images” + File.separator + “walk-0.png”); and storing the result in frame. 4. To draw this image to the screen, go into the WalkingSim.draw() method and add a call to the Utility.image() method, which draws a PImage object at a given (x,y) position on the screen. (See the Utility class documentation for more information, but notably, the top-left corner is (0,0) and the bottom right is (800,600).) To drop the image at the center of the screen: Utility.image(frame, 400, 300); 5. Notice the importance of adding this line AFTER you call Utility.background() – if you call it before calling Utility.background(), the background color will simply get drawn over your image and you won’t be able to see it. If you run your program now, it should look something like the screenshot below, which shows our single frozen walker centered on a randomly-generated purple background (your background will probably be a different color): ➡️Before you continue, delete or comment out the code declaring or using the frame field. It was just there to be educational.4. Animation This is where it gets fun. 4.1 Load all frames of the walk cycle You’ve only loaded a single animation frame so far, but we’ll need the others to really make this work. 1. Where your frame was, add a private static array of PImages called frames. This will be a perfect-size array of images that we’ll index into “circularly” – that is, the indexes will be accessed in the order 0, 1, … frames.length – 1, 0, 1, … 2. In the setup() method, initialize the frames array to the length specified by the static field Walker.NUM_FRAMES – this value is provided by the Walker class. 3. Initialize each element of the frames array in the setup() method by adding its index number into the image name, as “images”+File.separator+”walk-“+index+”.png”, and loading the image as before. 4. To test that you’ve done this correctly, try replacing the first argument of Utility.image() in your WalkingSim.draw() method with frames[3]. If all goes well, you should see a figure in a slightly different position than you did before! 4.2 Create an array of Walkers Let’s set up the program for multiple independent Walkers. 1. Create a private static Walker array field named walkers right below your frames array. This will also be a perfect-size array (that is, we’re not going to maintain a size for it). 2. In the setup() method, initialize the walkers field to a new array of Walker objects with a capacity of 8 (you may hard-code this value). Add a single reference to a Walker object to the first index (you’ll add more Walkers later). You can use the no-argument Walker constructor here. 3. In the draw() method, update your call to Utility.image() to reference the PImage at the walker’s current frame index in the frames array, as well as its current x and y coordinates (hint: check out the get methods in the Walker class – specifically getPositionX() and getPositionY()). Verify that your window still looks mostly like the screenshot at the end of section 3.3, above. That’s boring. Let’s change that.4.3 Populate your walkers array Back to the random number generator! 1. In your setup() method, generate a random number between 1 and the length of the walkers array (inclusive). Remove that single Walker from the first index, and add the randomly generated number of Walkers to the array instead. (Leave the rest of the values null.) a. Hint: use the two-argument Walker constructor with randomly-generated coordinates for the x and y values, between 0 and Utility.width() or Utility.height(). b. If you use the same coordinates for each call (or the no-argument constructor), your Walkers will all end up on top of each other! Make sure to generate new positions for each Walker object you add. 2. Your draw() method now needs to draw ALL of the non-null values from your walkers array every time it runs. Replace the call to Utility.image() for the single Walker with a loop that calls draw on each of the array’s Walkers – and NOT on any indexes that don’t have Walkers. Now you should see something a little more interesting, like this randomly-generated green background with FOUR walkers scattered around the window: 4.4 Where’s the mouse? One more step before we can get animating: 1. Every Walker has two methods to tell you where it is on the screen: getPositionX() and getPositionY(). These are object methods, which means calling them on different Walkers will get you different results (unless those two Walkers are in exactly the same location).2. Every PImage has two attributes (public fields), .width and .height, to give you the dimensions of the image. All of our frames have the same width and height values. 3. Note that the reported (x,y) position of the Walker object corresponds to the center of the image within the display window: 4. The Utility class provides two methods to tell you where the mouse is relative to the application window at any given time: Utility.mouseX() and Utility.mouseY(). a. IMPORTANT: the (x,y) coordinates of the application window probably don’t align to your expectations for how (x,y) coordinates work. Try adding a print statement to your draw() method to display Utility.mouseX() and Utility.mouseY(), and watch how they change as you move your mouse around the screen. Where is (0,0)? 5. Create a public static method named isMouseOver that expects a single Walker parameter and returns a boolean value. Use the methods and attributes defined above to implement this method so that it returns true if and only if the mouse is currently hovering over any part of one of the Walker images (not including its edges!) 6. To test your implementation, add a loop to your draw() method to check whether the mouse is over any of the non-null Walker objects in your walkers array, and print the message “Mouse is over a walker!” when the method returns true. For extra debugging help, you might want to print out the index of the Walker the mouse is currently over, to verify that it’s the one you expect! You should only see this message appear in the console when you are hovering your mouse over one of the figures. You can keep that last bit of test output or not, as you like. You’ll need the loop going forward, though. 4.5 Get those walkers walking Now you’re going to define another callback method – this one will be called automatically whenever the user clicks the mouse. 1. Create a public static method named mousePressed with no parameters and no return value. 2. In mousePressed(), add a loop to check whether the mouse is over any of the non-null objects in your walkers array. (Use that method you wrote in 4.4!) For only the lowest-index Walkerthat the mouse is over, call the setWalking(boolean) object method from the Walker class to set that particular Walker’s isWalking status to true. 3. In the WalkingSim.draw() method, check whether each of your non-null walkers isWalking – and if it is, call its update() method. This advances its current frame index (slowly!) through the frames array. 4. Run your code. Try clicking on one of the figures; only that one figure should begin moving as though it is walking. If you click on another, it should start moving, too! But only in place. If your walkers begin moving right away, check to make sure that you’re only calling update() when a walker isWalking. 4.6 Traveling walkers Time to make the walkers actually move across the window! 1. In your draw() method, before you call Utility.image() to draw each of your non-null walkers, check to see whether that Walker is currently walking (hint: use the isWalking() method). 2. If that Walker IS walking, update its x-coordinate to be 3 pixels to the right – use the getPositionX() and setPositionX() methods. 3. To prevent everyone from walking off the right of the window forever, make sure to wrap the x-coordinate back around to zero when it goes off the edge of the screen (hint: use modulo!). Play around with that 3-pixel value – what happens when you increase it? Make it negative? What if you were to move the y-coordinate instead? (Just make sure you put everything back to what we specified before submitting to Gradescope.) 5. Final touches: keyboard interaction To finish the program, you’ll add a little bit of key-pressing on the keyboard, just to get some experience with this Processing capability. 5.1 Adding more walkers At the moment, you’re stuck with the random number of walkers that your code generates to begin with. This will allow you to add some more, up to the capacity of your walkers array, using one last callback method. 1. Create a public static method named keyPressed with a single char parameter and no return value. The value of the char parameter will be the character corresponding to the key on the keyboard that was pressed.2. If the user types an ‘a’, and there are any remaining null elements of the walkers array, add a new Walker object at a random position on the screen to the next available element in the walkers array. Like the others, it should not start walking until the user clicks on it. 3. If the user types an ‘s’, ALL non-null Walkers in the program must STOP walking. You can use the setWalking(boolean) method here again, this time with an argument of false. Try it out! The only testing we will have you do for this program is interacting with it yourself, to see whether the behavior you observe corresponds to what we’ve described here. Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, make a final submission of your source code to Gradescope. For full credit, please submit the following files (source code, not .class files): ● WalkingSim.java Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default this will be your most recent submission. Students whose final submission (which must pass ALL immediate tests) is made before 5pm on the Wednesday before the due date will receive an additional 5% bonus toward this assignment. Submissions made after this time are NOT eligible for this bonus, but you may continue to make submissions until 10:00PM Central Time on the due date with no penalty.Appendix: The Utility class Listed here are the Processing variables and methods available to you on this programming assignment in Gradescope. While you are encouraged to explore the Processing library on your own as we continue with the semester, be aware that Processing is huge and we will only be able to make a small portion of its functionality available on Gradescope for any given assignment. In P02, you MUST interface with Processing by way of the Utility class. Gradescope’s Utility class includes the following static methods: ● void background(int) – sets the background color of the window ● int height() – returns the height of the application window in pixels ● void image(PImage, float, float) – draws an image to the application window, centered at the given (x,y) position ● char key() – returns the char representation of the key being pressed on the keyboard ● PImage loadImage(String) – creates and returns a PImage representation of an image file at the provided relative path location (e.g. “images/walk-2.png”) ● int mouseX() – returns the current x coordinate of the cursor in the application window ● int mouseY() – returns the current y coordinate of the cursor in the application window ● void runApplication() – begins the GUI program’s execution ● int width() – returns the width of the application window in pixels
Overview The United States is heading into its presidential election season, so in the spirit of the season we’d like to begin the semester by building a simple candidate management system for an election (any election). For this programming assignment, you’ll be creating a collection of utility methods to help manage a collection of candidates running against each other. You’ll be able to add a candidate (in alphabetical order), drop a candidate from the race, determine whether someone’s already running, and find the winner and lowest-polling candidates. Each candidate is represented in our program as follows: candidate NAME PARTY affiliation number of VOTES For the purposes of your instructional staff’s sanity, all examples within this assignment will be for the highly contentious race for Bestest Pokemon. This assignment is intended to be completed using primarily your prior knowledge from BEFORE CS300! Plan to get started as soon as possible; more help will be available to you the earlier you seek it out. Grading Rubric 5 points Pre-assignment Quiz: accessible through Canvas until 11:59PM CT on 09/08. +5% Bonus Points: students whose final submission to Gradescope is before 5:00 PM Central Time on WED 09/11 and who pass ALL immediate tests will receive an additional 2.5 points toward this assignment, up to a maximum total of 50 points. 20 points Immediate Automated Tests: accessible by submission to Gradescope. You will receive feedback from these tests before the submission deadline and may make changes to your code in order to pass these tests. Passing all immediate automated tests does not guarantee full credit for the assignment. 15 points Additional Automated Tests: these will also run on submission to Gradescope, but you will not receive feedback from these tests until after the submission deadline. 10 points Manual Grading Feedback: TAs or graders will manually review your code, focusing on algorithms, use of programming constructs, and style/readability. 50 points MAXIMUM TOTAL SCORELearning Objectives After completing this assignment, you should be able to: ● Comfortably implement a procedural program using static methods in Java ● Explain the protocols used with oversize arrays ● Verify the correctness of a static method which uses arrays by designing and implementing a boolean tester method in Java Additional Assignment Requirements and Notes Keep in mind: ● Pair programming is NOT ALLOWED for this assignment. You must complete and submit P01 individually. ● The ONLY external libraries you may use in your program are: java.util.Arrays (ONLY in the tester class) java.lang.reflect.InvocationTargetException (ONLY as provided) ● Use of any other packages (outside of java.lang) is NOT permitted. ● You are allowed to define any local variables you may need to implement the methods in this specification (inside methods). You are NOT allowed to define any additional instance or static variables or constants beyond those specified in the write-up. ● You are allowed to define additional private helper methods. ● Only ElectionManagerTester may contain a main method. ● All classes and methods must have their own Javadoc-style method header comments in accordance with the CS 300 Course Style Guide. ● Any source code provided in this specification may be included verbatim in your program without attribution. ● All other sources must be cited explicitly in your program comments, in accordance with the Appropriate Academic Conduct guidelines. ● Any use of ChatGPT or other large language models must be cited AND your submission MUST include screenshots of your interactions with the tool clearly showing all prompts and responses in full. Failure to cite or include your logs is considered academic misconduct and will be handled accordingly. ● Run your program locally before you submit to Gradescope. If it doesn’t work on your computer, it will not work on Gradescope.Need More Help? Check out the resources available to CS 300 students here: https://canvas.wisc.edu/courses/427315/pages/resources CS 300 Assignment Requirements You are responsible for following the requirements listed on both of these pages on all CS 300 assignments, whether you’ve read them recently or not. Take a moment to review them if it’s been a while: ● Appropriate Academic Conduct, which addresses such questions as: ○ How much can you talk to your classmates? ○ How much can you look up on the internet? ○ How do I cite my sources? ○ and more! ● Course Style Guide, which addresses such questions as: ○ What should my source code look like? ○ How much should I comment? ○ and more! Getting Started 1. Create a new project in Eclipse, called something like P01 Election Manager. a. Ensure this project uses Java 17. Select “JavaSE-17” under “Use an execution environment JRE” in the New Java Project dialog box. b. Do not create a project-specific package; use the default package. 2. Download one (1) Java source file from the assignment page on Canvas: a. ElectionManagerTester.java (includes a main method) 3. Create one (1) Java source file within that project’s src folder: a. ElectionManager.java (does NOT include a main method) All methods in this program will be static methods, as this program focuses on procedural programming.Implementation Requirements Overview Your ElectionManager.java program must contain the following methods, described in detail on this javadoc page. ● public static boolean containsCandidate(String[][] candidates, int numCandidates, String name, String party) ● public static int addCandidate(String[][] candidates, int numCandidates, String name, String party, int numVotes) ● public static int dropCandidate(String[][] candidates, int numCandidates, String name, String party) ● public static String findWinner(String[][] candidates, int numCandidates) ● public static String findLowestPollingCandidate(String[][] candidates, int numCandidates) All of these methods use an oversize array, defined by a two-dimensional (n x 3) array of Strings and an integer value denoting the compact number of initialized (non-null) values in the first dimension of the array. That is, if the integer value numCandidates is 5, I would expect there to be length-3 arrays of Strings at candidates[0] through candidates[4], and any other indexes in candidates will be null. These methods are UTILITY methods – the ElectionManager program does not “run”, as it has no main method. Another class will create and maintain the list of candidates, and call the methods in ElectionManager when it needs to. For this assignment, you’ll only be calling the methods to TEST them from your tester class. An Aside: Using Javadocs to build a program The Javadoc page linked above is automatically generated by the IDE, using the contents of Javadoc-style comments in the program source code. When creating this assignment, I wrote ElectionManger with comments for the class (a “class header” comment) and each method (a “method header” comment) in the following style: /** * Determines whether the given candidate, specified uniquely by name and party, * is present in the given list of candidates. * * @param candidates A two-dimensional oversize array containing the current * list of candidates as [name, party, numVotes]. This input value is assumed to * conform to the standards of oversize arrays, and is assumed to be in alphabetical * order by candidate name. * @param numCandidates The current size of the candidates oversize array at the * time of input. This value is assumed to be accurate.* @param name The name of the candidate to search for * @param party The party affiliation of the candidate to search for * @return true if a candidate with the given name AND party affiliation is present * in the list; false otherwise */ Both class and method header comments begin with a /** (two asterisks) and end with a */ – note that if you only use one asterisk at the beginning, this creates a multiline comment, not a Javadoc comment. This is important documentation, and you will be required to do the same for all classes and methods you write in this course. You are welcome to use any text from the writeups, verbatim, in your comments. You are not required to generate HTML javadoc pages, but you can if you want to! At the top of the javadoc page you will find a summary of the data fields (when there are any) and methods in the class, and if you either click on their names or scroll down, you will find the full detailed description of what these methods are supposed to do, what parameters they expect, and what they should return. Most – if not all – of our programming assignments this semester will use these generated Javadoc pages to communicate the requirements of the assignment to you, so if you have any questions about how to use them, this is the time to ask. Implementation Details and Suggestions Add the methods listed on the javadoc page as stub methods – methods containing only a default return statement – to your class file, and then turn to the tester file before you go any further. public static int sampleMethod() { return 0; // this is an example stub method that returns an int } The only way to begin, is by beginning A link to the ElectionManagerTester.java starter file can be found on the assignment page, so we haven’t provided a Javadoc file for it. A few test methods have been provided for you in their entirety, along with some implementation-level comments to give you a guide in constructing your test methods. While there are a LOT of tester methods, they should all be pretty short. Use the provided methods as a model for setting up your own, and don’t be afraid to use Arrays class methods as a shortcut for verifying the state of the 2-dimensional array after a method call. Method 1: Contains Candidate We’ve provided one tester here (testDoesContain()) which verifies the behavior of the containsCandidate() method from ElectionManager when the candidate name/party we’re asking about is present in the list.Read the documentation for containsCandidate() and review the provided implementation for testDoesContain(), and then answer the following questions: 1. Which of the test variables from testDoesContain() can you use to test that a candidate is NOT present in the candidateList? Which ones will you need to change? 2. What is the expected return value of containsCandidate() for a name/party combination that is not present in the list? a. What if the NAME matches but not the PARTY? 3. Should containsCandidate() modify the array if the name/party combination is not present? With these answers, go ahead and implement the testDoesNotContain() test method. Now, implement the containsCandidate() method itself, and finish out testContainsEmpty() (which should test whether an empty candidateList – with length > 0 but size == 0 – contains any given candidate; hint: it does not). If you’ve done everything correctly up to this point, you should be able to run ElectionManagerTester in your IDE and get output that begins with: testContainsEmpty : true testDoesNotContain : true testDoesContain : true If so: hooray! Time to continue. Otherwise, check your tests and method implementation; something’s going wrong and it’s a good idea to fix that before you go on. ➡️You may ALSO wish to make a partial submission to Gradescope at this point, and at the end of each of the following sections – this way, you can see whether you’re passing any immediate tests related to the containsCandidate() method, AND you’ll have a secure record of your work to this point. If your computer crashes or you accidentally delete your files, you can always re-download your most recent Gradescope submission! Method 2: Add Candidate Again you have a provided test here (testAddToNonEmpty()); review it and the documentation for addCandidate() before you continue. You will need to implement: 1. testAddToEmpty – add to a length > 0 1 but size == 0 list of candidates 2. testAddCandidateErrors – add a duplicate candidate or a candidate with negative votes 1 Note: at no point in this assignment does a length 0 array make sense. Arrays are assumed to have length > 0.3. testAddToFull – add to a list of candidates with length == size, which contains no null values As well as the addCandidate() method itself. We recommend implementing at least one of the TODO testers before you implement the method itself. You’re absolutely welcome to use the containsCandidate() method in your implementation of addCandidate(), by the way. Again, verify that you pass ALL of the add method tests before you continue. Method 3: Drop Candidate Same deal; this time the tests you’re responsible for are: 1. testDropOnlyCandidate – remove a candidate from a list with size == 1 2. testDropFirstCandidate – remove the first candidate in a list with size > 1. Verify that the resulting array has been modified appropriately – it should still be a compact, oversize array! Method 4: Find Winner This method returns a String value. Pay close attention to how we’ve analyzed the actual return value in the provided testClearWinner() method – MOST of YOUR tests shouldn’t need to go this in-depth with the analysis, but you may wish to reference this on future assignments. 1. testUncontestedWinner – check the winner on a list with size == 1, which should return the single candidate’s name and party with 100.0% of the votes 2. testContingentElection – check the winner when no one candidate has > 50% of the votes, which should return “CONTINGENT” Method 5: Find Lowest Polling Candidate The only twist here is that we haven’t provided ANY of the tester methods, so you should DEFINITELY write at least one before you implement the method itself. 1. testUncontestedLowestPolling – if the list has 0 or 1 candidates, this method isn’t particularly meaningful; verify that it returns “UNCONTESTED” 2. testLowestUniqueVoteCount – find the lowest vote count on a list with size >= 2 and all candidates have unique vote counts 3. testLowestVoteCountTied – find the lowest vote count on a list with size >= 2 and at least two candidates are tied for lowest number of votes At this point, you should finally see the line at the end of your output read ALL TESTS: true If it does, you are done!!Assignment Submission Hooray, you’ve finished this CS 300 programming assignment! Once you’re satisfied with your work, both in terms of adherence to this specification and the academic conduct and style guide requirements, make a final submission of your source code to Gradescope. For full credit, please submit the following files (source code, not .class files): ● ElectionManager.java ● ElectionManagerTester.java Additionally, if you used generative AI at any point during your development, you must include screenshots showing your FULL interaction with the tool(s). Your score for this assignment will be based on the submission marked “active” prior to the deadline. You may select which submission to mark active at any time, but by default this will be your most recent submission. Students whose final submission (which must pass ALL immediate tests) is made before 5pm on the Wednesday before the due date will receive an additional 5% bonus toward this assignment. Submissions made after this time are NOT eligible for this bonus, but you may continue to make submissions until Thursday 10:00 PM Central Time on the due date with no penalty.
QUESTION 1 [55 Marks] Climate change stands as one of the most urgent challenges confronting our planet today. To effectively comprehend and address this critical issue, access to precise and comprehensive data regarding global temperatures and other climate-related factors is indispensable. In this regard, you serve as a data analyst at the National Aeronautics & Space Administration (NASA) and are engaged in researching Earth’s climate and temperature. Your work involves utilizing datasets sourced from satellites and groundbased sensors. You have been entrusted with a dataset “earth_surface_temperatures .csv” encompassing surface temperature data for various countries worldwide, spanning from Dec 1743 to December 2020. Your mission is to conduct an in-depth Exploratory Data Analysis (EDA) on this dataset. This analysis aims to extract insights and answer crucial questions about the data by delving into trends and patterns. To achieve this, you are expected to: a. Identify and rectify any missing values in the data using appropriate techniques. [5 Marks] b. Transform the Years and Month columns into a single column labeled “Date” in the MM-YYYY format, with a datetime64[ns] data type. For example, the year 1848 and month 5 should be unified as a single value, such as 5-1848. [5 Marks] c. Detect and investigate extreme temperature values that might be regarded as outliers. [5 Marks] d. Compute summary statistics for temperature, monthly variation, and anomaly values, including mean, median, standard deviation, and range. [5 Marks] e. Identify the countries included in the dataset and calculate their average temperature values. [5 Marks] f. Determine the overall trend in global temperatures over the years and visualize this trend using a suitable chart. [5 Marks] g. Identify the months with the highest and lowest temperatures for each country and find out whether there are noticeable seasonal patterns in the temperature data. [5 Marks] h. Explore the variation in temperature anomalies on a monthly basis and identify any months with consistently high or low anomalies across the years. [5 Marks] i. Choose five countries and compare the trends in their temperatures over the years, seeking any similar temperature patterns. [5 Marks] j. Explore the potential correlation between temperature and monthly variation or anomaly values. Calculate correlation coefficients and create scatterplots to investigate this relationship. [5 Marks] k. Provide an intriguing insight from the dataset by utilizing data visualization techniques such as histograms, box plots, or heatmaps to represent the data’s distribution, trends, and relationships. [5 Marks] QUESTION 2 [45 Marks] As a member of the retail analytics team, you have been contacted by the Category Manager at a retail store, who desires to gain a deeper understanding of the customers who buy chips and their purchasing habits within the region through valuable insights that will eventually be used to inform the store’s strategic plan for the chip category in the upcoming six months. You have received the following e-mail from your manager. Greetings! I am following up on our earlier conversation with a few pointers to help you succeed in this task. Here are the key areas you will be working on and what we’re looking for in each one: Firstly, examine the transaction data (“transaction_data“ file) and look for inconsistencies, missing data, outliers, correctly identify category items, and numeric data across all tables. If you notice any anomalies, please make the necessary changes in the dataset and save it for further analysis. Having clean data will make it easier for us to conduct an effective analysis. Secondly, examine the customer data (“purchase_behaviour” file) for similar issues and check for null values. Once you’re satisfied with the data, merge the transaction and customer data together for analysis, ensuring that you save your files along the way. Thirdly, conduct data analysis and identify customer segments. Define the metrics, such as total sales, drivers of sales, and the source of the highest sales. Explore the data, create charts and graphs, and note any interesting trends and insights you find. Finally, deep dive into customer segments and recommend which segments we should target. Determine if packet sizes are relative and form an overall conclusion based on your analysis. Here is the task: Your task is to provide a data-driven strategic recommendation for the upcoming category review. To achieve this, you must first analyze the current purchasing trends and behaviors to understand the customer segments and their chip purchasing behavior. To describe the customers’ purchasing behavior, you need to identify relevant metrics. The client has a specific interest in understanding the chip purchasing behavior of different customer segments. To begin the task, download the comma-separated values (CSV) data files provided to you and conduct preliminary data checks, including: • Generating and interpreting high-level data summaries. • Identifying any outliers and, if necessary, removing them (if applicable). • Verifying the data formats and correcting them, if needed (if applicable). In addition to the preliminary data checks, it is essential to extract additional features, such as pack size and brand name, from the data. Defining relevant metrics of interest is also crucial to gaining insights into the chip purchasing behavior of different customer segments. Your ultimate goal is to formulate a strategic recommendation for the Category Manager, based on your findings. Therefore, it is essential that your insights have a commercial application and can be used to inform decision-making. Lastly, a detailed report on your analysis findings, no longer than 3-4 pages, is required. The report should include any relevant visualizations you have created, as well as your recommendation to the Category Manager, to inform the store’s strategic plan for the chip category. Do not include any technical aspects of your analysis, such as coding, in the report. Note: This is an open-ended case study and can be approached in various ways, allowing for flexibility and creativity in the analysis process. Additional Pointers (column description of purchase behavior): LIFESTAGE: Customer attribute that determines if they have a family or not, and at what stage of life they are in. For instance, it considers whether their children are in preschool, primary or secondary school. PREMIUM_CUSTOMER: Customer segmentation approach that distinguishes shoppers based on the price point and product types they purchase. Its purpose is to determine whether customers are willing to pay more for brand or quality or prefer to purchase the most economical options.For this assignment, you will: (0 pts) Get started with Python (60 pts) Implement Decision Tree with Discrete Attributes (40 pts) Credit Risk Prediction Part 0: Getting Started with Python As in all the homeworks this semester, you will be using Python. So let’s get started first with our Python installation. Python Installation and Basic Configuration First off, you will need to install a recent version of python 3 in here. There are lots of online resources for help in installing Python. Alternatively, there is a nice collection called Anaconda, that comes with Python plus tons of helpful packages that we may use down the line in this course: Anaconda: which has install instructions for Windows, Linux, and Mac OSX. Installing Python Libraries (optional) You will may need to install python libraries. To manage your Python installations, we recommend pip. Pip is a tool for installing and keeping track of python packages. It is a replacement for easy_install which is included with python. It’s a bit smarter than easy_install, and gives better error messages, so you probably want to use it. You can install pip and the two packages we currently need by running these commands: > easy_install pip > pip install -r reqs.pip Then, you may install other Python libraries such as NumPy by typing ‘pip install numpy’ Part 1: Implement Decision Tree with Discrete Attributes (60 pts) In this assignment, you will implement the decision tree algorithm for a classification problem in python 3. We provide the following three files: a) data1.csv – You will load the file, build a tree, and evaluate its performance. The first row of the file is the header (including the names of the attributes). In the remaining rows, each row represents an instance/example. The first column of the file is the target label. b) part1.py – You will implement several functions. Do not change the input and the output of the functions. c) test1.py – This file includes unit tests. Run this file by typing ‘pytest -v test1.py’ in the terminal to check whether all of the functions are properly implemented. No modification is required. Part 2: Credit Risk Prediction (40 pts) Let’s assume that you work for a credit card company. Given the sample credit dataset (credit.txt) as a training set, your job is to build a decision tree and make risk prediction of individuals. The target/class variable is credit risk described as high or low. Features are debt, income, marital status, property ownership, and gender. Task 2-1: Draw your decision tree and report it. You may use visualization tools (e.g., Graphviz) or use text. You might find it easier if you turn the decision tree on its side, and use indentation to show levels of the tree as it grows from the left. For example: outlook = sunny | humidity = high: no | humidity = normal: yes outlook = overcast: yes outlook = rainy | windy = TRUE: no | windy = FALSE: yes Feel free to print out something similarly readable if you think it is easier to code. Apply the decision tree to determine the credit risk of the following individuals: Name Debt Income Married? Owns Property Gender Tom low low no Yes Male Ana low medium yes Yes female Report a snapshot of your decision tree, and predicted credit risk of Tom and Ana. Task 2-2: How does your decision tree change if Sofia’s credit risk is high instead of low as recorded in the training data? Given the decision tree constructed from the original dataset, if existing, name any feature not playing a role in the decision tree. What to turn in: Submit to Canvas your part1.py, and a pdf document for part2. This is an individual assignment.For this assignment, you will: (70 pts) Implement linear regression with gradient descent (30 pts) Make predictions by using your implementation Part 1: Implement linear regression with gradient descent In this problem, you will implement the linear regression algorithm in python3. We provide the following files: a) linear_regression.py – You will implement several functions. As we discussed in class, implement the functions by using vectorization. You may refer to matrix calculus here: https://en.wikipedia.org/wiki/Matrix_calculus Do not change the input and the output of the functions. b) test.py – This file includes unit tests. Run this file by typing ‘pytest -v test.py’ in the terminal as you did in homework 1 in order to check whether all of the functions are properly implemented. No modification is required. Part 2: Make predictions by using your implementation Given training and test sets, you will make predictions of test examples by using your linear regression implementation (linear_regression.py). We provide the following file: a) application.py – write your code in this file. Do not change X and y. Please play with the parameters alpha and number of epochs to make sure your testing loss is smaller than 1e-2 (i.e., 0.01). Report your parameters, training loss and testing loss. In addition, based on your observations, report a relationshp between alpha and number of epochs. Note that a single epoch means the single time you see all examples in the training set. What to turn in: Submit to Canvas your linear_regression.py, application.py and a pdf document for part 2. This is an individual assignment.Part 1. Softmax regression [60 points] In this part, you will implement softmax regression (in problem1.py) with stochastic gradient descent in python3. We provide the following files: a) problem1.py – You will implement several functions of softmax regression. Do not change the input and the output of the functions. b) test1.py – This file includes unit tests. Run this file by typing ‘pytest -v test1.py’ in the terminal. No modification is required. Part 2. Adding CNN and fully connected layers to recognize handwritten digits on PyTorch [40 points] In this part, you will deal with the MNIST Database [1]. The MNIST Database is a collection of samples of handwritten digits from many people, originally collected by the National Institute of Standards and Technology (NIST), and modified to be more easily analyzed computationally. We will use a tutorial and sample software provided: • Read and run a tutorial [2] to be familiar with how to add CNN layers into PyTorch. • Download hw4-part2.ipynb and run it to be familiar with the code. Currently it contains two fully connected layers with softmax. • Your job is to add one CNN layer with one pooling layer before the two fully connected layers with softmax. Refer to the detailed instruction about the CNN layer. The main difference between the tutorial and this given hw4_part2.ipynb is the input image of hw4_part2.ipynb has only 1 channel (i.e., gray scale). Report results of two fully connected layers without CNN and with CNN. • Then, experiment with at least 3 alternative network topologies and hyper-parameters (e.g., different # of CNN/fully-connected layers, # of epochs, # of hidden units, learning rate, batch size, and different activation functions). • Save and summarize the results and report them. • Through the experiment, what is the best configuration? What prediction accuracy on the test set you got? What did you learn? What to turn in: Submit to Canvas your problem1.py and pdf document for part 2. This is an individual assignment. [1] MNIST Database: https://pytorch.org/vision/stable/generated/torchvision.datasets.MNIST.html [2] Tutorial: https://pytorch.org/tutorials/beginner/blitz/cifar10_tutorial.html
