SCC111 Software Development PART-I SUMMER PROJECT
PART-I SUMMER PROJECT
Assessment Mode: IN LAB DEMO IN YOUR WEEK 25 LAB SESSION
MOODLE SUBMISSION
GITHUB LINK SUBMISSION
AIMS
In this final term of your first year, there is a single task: a single cross-module project that is designed to
bring together all you have learned since you joined us in October. This project represents the final piece of practical coursework for your first year and constitutes 33% of the coursework assessment for the year. Time to show us what you can do!
You have a choice of projects to undertake, to be selected from the choices below. You need to pick just one of these projects. Read each of them carefully before choosing which project to undertake. Please note that the projects state which programming language you must use for that project. These projects have been designed to build on what you have learned in SCC.111, SCC.121 and SCC.131 (where applicable). Note that some projects are unavailable / have different requirements for students not studying SCC.131 (such as those studying for Computer Science and Mathematics or Management and IT degree).
GETTING SUPPORT
You should attend your timetabled SCC1x1 lab session in weeks 21-24 inclusive for support, where staff
and teaching assistants will be present to provide guidance, feedback and to answer your questions. Please note that your week 25 session will be reserved for you to demonstrate the functionality of your work. Staff will not be able to provide support during the Week 25 lab session.
The FAST hub will also be available daily if you need additional drop-in support. See Moodle for more details.
1
SUBMISSION AND ASSESSMENT
This work will be assessed by a member of academic staff after you follow the instructions below to submit
your work. This assessment will be further informed by a practical demonstration of your work. You will be
asked to present your work in your Week 25 lab session. Be prepared to take the lead in demonstrating your project, and to answer questions about it.
-
You MUST submit your code to Moodle by the advertised deadline in a .zip file.
-
You MUST demonstrate your work by downloading your Moodle submission and running it IN YOUR
OWN WEEK 25 TIMETABLED LAB SESSION.
-
You MUST share your private GitHub repository by the advertised deadline using the version control submission instructions below.
-
You MUST ensure that your project can be compiled and executed FROM THE COMMAND LINE ON A LAB PC, without using an IDE. (If the project you selected has further instructions on how to do compile and run your project, you must follow them.)
-
The standard University regulation on permitting late submission of coursework DOES NOT APPLY TO THIS COURSEWORK ASSIGNMENT.
FAILURE TO ADHERE TO THE ABOVE WILL RESULT IN A FAIL MARK (F4) BEING RECORDED.
VERSION CONTROL SUBMISSION
You are expected to use git version control for your project, and this is reflected in the marking scheme. Tosubmit your private GitHub repository for assessment, you must do the following:
1. Invite the scc1x1-2024 user as a collaborator to your GitHub repository, as demonstrated in SCC111 lectures. Remember you can invite a user through the Settings -> Collaborators page on your GitHub repository.
2. Submit the FULL URL of your project GitHub repository. We will provide precise details closer to the submission time
2
MARKING SCHEME
Your work will be marked based on the following categories. Your final grade will be determined based on a
weighted mean of these grades according to the weighting shown in the table below.
Project Functionality 70%
• See individual project descriptions below for indicative levels of the functionality required.
Code Structure and Elegance 10%
-
Modularity of code
-
Use of appropriate data types and libraries
-
Use of appropriate language constructs (arrays,
loops, functions, methods, classes)
Code Style 10%
-
Appropriate comments, code indentation
-
Appropriate name/ scope of variables and
functions/methods
Use of Git version control 10%
-
Clean and regular commits
-
Appropriate commit messages
In all cases a grade descriptor (A, B, C, D, F) will be used to mark your work in each category. The following sections provide an indication of the level of functionality expected.
Students may also award of a distinction (+) category overall if they feel a piece of work exhibits clearly outstanding practice. If you feel your work warrants a distinction for going significantly above and beyond
3
the specification, it is your responsibility to state and demonstrate this during your Week 25 lab session.
PLAGIARISM
This project should be entirely your own work. In this context, that means that it is reasonable to discuss
ideas with others, but you should not expect to study the code of another student, or to let them study yours. Code examples taken from the lecture notes are acceptable, as well as, small sections of code (a few lines, for example) from the internet - but if it is in your code, you should be able to understand and confidently explain what it does and how it works. The use of AI tools to write code on your behalf is regarded as equivalent to copying code from any external source.
4
PROJECT 1: NONOGRAMS (LANGUAGE: JAVA)
PROJECT OVERVIEW
Nonograms, also known as hanjies, are a type of graphical logic puzzle. In their simplest form, they take a
piece of single colour pixel art and present the player with only information about the number of contiguous pixels on each row and column of that image. Based on this information, the player must use logic to deduce and reconstruct the original image.
Figure 1: A screenshot of a 15x15 pixel incomplete nonogram.
The numbers at the top and left of the image represent the number of pixels that are shaded on the respective row or column. Each value states the number of pixels that are shaded in a contiguous block (a block with no gaps). If multiple values are shown, then each contiguous block must be separate by at least one pixel that is not shaded. The order of the values given for each row/column is also consistent with the order of the contiguous blocks of pixels.
For example, in the diagrams above a yellow square indicates an unknown value. A black square is shaded, and white square is not shaded. We can see that the 7th row has a single value (15) stated. As there are only 15 squares on the row, all the pixels on that row must be shaded, as in the solution. The 8th row has the values (1,1,1,1,1,1,1) meaning that the solution for that row has 7 single pixels shaded, each separate by
5
Figure 2: A screenshot of a 15x15 pixel completed nonogram.
a non-shaded square, as in the solution.
More advanced puzzles also support an additional colour, such that there are three colours overall. In this case, the rules are the same, but the number values are also coloured to indicate which colour each contiguous block of pixels should be. Also, contiguous blocks of pixels may be separated by any change in colour (not necessarily just white). See here for an example.
THE TASK
Your challenge is to write an interactive nonogram puzzle game. The program should:
-
Generate and visualize a nonogram grid containing the correct informational values given an image represented by a two-dimensional boolean array.
-
Interactively allow the user to shade/unshade each square.
-
Determine if the user has solved the puzzle by shading in the correct squares.
-
Students studying SCC131 should also allow any single colour Windows Bitmap (.bmp) image file to be
read into your program from which the puzzle can be generated. We have provided some sample images alongside this specification. You should parse this .bmp file from first principles (i.e. without the use of any image specific library functions or classes) to determine which pixels are set or unset in the image.
6
GETTING STARTED
If you’re unfamiliar with nonograms, you’ll need to do some research to learn the rules of these puzzles.
Also, you’ll need to understand more about the format of Windows .bmp files. To get started, we recommend that you:
-
Visit the Hanjie website and try to complete some of the easy and moderate examples:
http://www.hanjie.co.uk/hanjie1.php -
Refresh your knowledge of the Swing classes we discussed in lectures and consider which graphical components and layout manager might help you!
-
Research the basic Java classes that allow you to open, read and write bytes from files. This tutorial provides a nice introduction: https://www.tutorialspoint.com/java/java_files_io.htm
-
Study the section below that outlines the simplified format of a Windows Bitmap file. This will help you to interpret the bytes that you read from the file.
WINDOWS BITMAP (.BMP) FILE FORMAT
The Windows Bitmap format is one of the simplest ways to record image data in a file. It does not makeuse of compression, so its files can get quite large, but the way in which the data is stored is much simpler than other formats such a JPEG or GIF.
Windows BMP allows for graphical data to be stored at any image width, height, or colour depth (the number of bits used to represent the colour of each pixel). As such, all this information is also stored in the file itself, before the pixel data. This is very common in file formats and is known as a file header. The following diagram illustrates a simplified view of the Windows BMP file. (See this article for a more detailed overview of the full specification for those of you that are interested!).
The left-hand column shows which byte in the file is being described (0 is the first byte, 1 is the next byte etc). The next columns describe what data is held in that location, and the final column illustrates the content using the ‘elephant.bmp’ file provided alongside this specification.
Note that many fields use multiple bytes. Such fields are all represented using unsigned, little-endian values. i.e. the least significant byte comes first, and the most significant is last. The pixel data itself uses however
7
Figure 3: File Format of a Windows BMP file
Figure 4: Example elephant.bmp
8
many bits are defined in the BITS_PER_PIXEL field to represent each pixel. The order of the pixels in left-to-right, bottom-to-top. Each row is also padded with zeros to ensure each row of pixels starts on a multiple of 4 bytes.
e.g. in the example above, the first 0xF0 0x00 bytes indicate that the first four pixels on the bottom row of the image are “colour 1” and the remaining 11 pixels are “colour 0”. The row is than padded to a multiple of four bytes with the following 0x00, 0x00 byes. The values 0x15 0xB8 then describe the next row up.
MARKING SCHEME
Marks will be awarded according to the marking scheme shown at the start of this document. Marks for the
‘Functionality’ section will be awarded based on individual merit, but the following table gives an indicative
overview of the level of functionality expected for each grade band:
SCC Major Students Studying SCC.111, SCC.121 and SCC.131
-
A Working program that meets the criteria for a B, plus:
-
Allows loading of arbitrary Windows Bitmap images of any size.
-
Supports puzzles containing at least two colours.
-
-
B Working program that meets the criteria for a C, plus:
-
Allows the users to load single colour 15x15 pixel Windows BMP files to solve.
-
Highlights any incorrect squares when the puzzle is completed.
-
-
C Working program that meets the criteria for a D, plus:
-
Dynamically computes and displays the numbers at the top and left-hand side of the puzzle.
-
Image to solve is hardcoded inside an array in the program.
-
Determines when game is complete, with an indicative message.
-
9
D
F
SCC Joint
A
B
Working program that:
-
Displays at least a 5x5 grid of squares.
-
Allows users to change colour of each square between unknown, white and black when
clicked.
No working program demonstrated, or program does not meet any requirements listed above.
Major Students Studying SCC.111 and SCC.121 only Working program that meets the criteria for a B, plus:
• Supports puzzles containing at least two colours.
Working program that meets the criteria for a C, plus:
-
Dynamically computes and displays the numbers at the top and left-hand side of the puzzle.
-
Determines when game is complete, with an indicative message.
Working program that meets the criteria for a D, plus:
-
Maintains image to solve as an array (or similar)
-
Allows users to change colour of each square between unknown,
white and black when clicked.
Working program that:
• Displays at least a 5x5 grid of squares.
No working program demonstrated, or program does not meet any requirements listed above.
C
D
F
10
STAR AWARD
An A+ is also available, for students wishing to really push their limits! To attain this, we will be looking
for students who can not only allow the user to solve the puzzle, but to implement, from first principles, an efficient program that can also automatically solve any given nonogram loaded from a windows bitmap.
Note: This is not for the faint hearted! The computational complexity of this task grows very quickly... Attempts to use a brute force algorithm on a 15x15 will take a long, long time...
11
PROJECT 2: SOCIAL NETWORKS (LANGUAGE: JAVA)
PROJECT OVERVIEW
When users engage with social media, they form connections that can emerge into complex social networks.
Online social networks can influence opinion on wide-ranging topics from politics to culture to marketing and advertising. By analysing such networks, we can understand more about how information (and disinformation) flows.
In social networks, such as X and LinkedIn, there is the idea of a person following another person. The concept that one person follows another can be thought of as a binary relation, for example “Xenia follows Rahul”. Social networks use this “follows” relation for various purposes, for example, to show content that might be relevant to a person.
This project will focus on analysing a fictious social network called “Dapper” which is described below. You will be provided with a file that represents the social network (list of users and whom they follow), based upon which you must accomplish the tasks described below.
TASKS
Some general details on Dapper are first given which you should read carefully to understand more about
the network you will be analysing. The individual tasks to complete are then given below.
Assume you have an input file that specifies the social network. Each line in the file represents a person and the people they follow. Specifically, the first name on each line is a person in the network and any remaining names on the line are the people in the network whom they follow (you may assume no person follows themselves). Let’s say the contents of the input are as given the figure below.
This means that Raman follows Abe, Carla, Anwar and Cat; Cat follows Abe; Carla follows Raman and Abe; Abe doesn’t follow anyone; and Anwar follows Abe, Carla and Raman. An input may contain several such lines.
A diagram corresponding to the input in the previous graph input is given below.
12
Figure 5: A representation of a social network that will be the input for your tasks. Each line represents a person and the people they follow.
Figure 6: Representation of the “follows” relation for the social-network file given in Figure 1. Node X -> Node Y means X follows Y.
13
Your tasks are to read the input and write a program that performs the following tasks.
Task 1: Give the density of the graph represented by the social network. Recall that the density of a
directed graph is |E| , where V and E respectively represent the set of nodes and directed edges. |V |(|V |−1)
Task 2: Name a person who has the highest number of followers. In general, more than one person may have the same number of followers. If there is more than one person with the highest number of followers, then the name you give must be the one that is alphabetically first.
Task 3: Name a person who follows the highest number of people. Again, if there is more than one such person, again, the name you give must be the one that is alphabetically first
Task 4: A degree of separation is a measure of social distance between people. For example, people who are friends are separated by one degree. Two people who are not friends, but have a common friend are separated by two degrees.
For a person P in Dapper, we define people at two degrees of separation from P as follows.
-
P’s followers are at one degree of separation from P.
-
Followers of P’s followers who are neither P nor at one degree of separation from P are at two degrees of separation from P.
For the first person who appears in the input (for the input in Figure 1, this person is Raman), give the number of people at two degrees of separation from that person.
Task 5: Give the median value for the number of followers in the network, that is, over the data set whose elements consist of the number of followers for each person in the network. Note that the median value is the middle element in a data set – half the data elements are smaller than the median value and half the data elements are larger. Make sure you handle the case when the number of elements is even, in which case you have no unique middle element, but two middle elements. CLARIFICATION: In such a case, you must average the two middle elements, which means that the answer may not be an integer.
Task 6: In Dapper, a message originating from a person is automatically propagated to their followers and the followers’ followers, and so on (obviously in an acyclic manner; that is, a person doesn’t get the same message more than once). So, based on the social network of Figure 1, if Carla sends a message, then it is propagated to Anwar and Raman because they both follow Carla. Raman is Anwar’s only follower but he
14
has already seen the message; Carla and Anwar are Raman’s only followers but they too have seen the message. So a message sent by Carla propagates to Anwar and Raman.
Imagine you are an advertiser (you yourself are outside the social network) who wants to spread information about a new product to as many people as possible in Dapper. However, the catch is you can enrol only one person in the network to spread information on your behalf. Whom would you enrol? Again, if you determine that two or more people are equally worthy of being enrolled, you must give the name that is alphabetically first.
RUNNING YOUR PROGRAM
You will run your program by invoking at the command line in a terminal:
java Analysis \<inputFile\>
where <inputFile> is a command-line argument that stands for the name of the file that contains the input for your program.
So, for example, if the input file is named social-network.txt, then you would invoke:
java Analysis social-network.txt
Your program must not prompt the user for any input once executed as described above.
REQUIRED OUTPUT
Upon executing the program as described above, it must print in the terminal the answers for all tasks that
you have accomplished. Print sufficiently informative statements such as “The person with the highest number of followers is Abe”, and so on.
The output for all tasks that you accomplish must be printed in one go, that is, without requiring any input from the user.
15
TESTING YOUR PROGRAM
A zip containing some example inputs and the corresponding answers has been made available to you. You
may use them to test your program.
PRACTICING FOR THE IN-LAB EVALUATION
For your in-lab demonstration, you will be required to run the code you submitted to Moodle. Be sure the
zip you upload to Moodle has everything you need in it and that you can compile the code and run it. Make sure you test and practice this before you submit!
MARKING SCHEME
Marks will be awarded according to the marking scheme shown at the start of this document. Marks for the
‘Functionality’ section will be awarded based on individual merit, but the following table gives an indicative
overview of the level of functionality expected for each grade band: A Working program that meets the criteria for a B, plus:
• Meets the requirements of Tasks 6
B Working program that meets the criteria for a C, plus:
• Meets the requirements of Tasks 4 and 5 (Joint majors
(students not taking 131) need only do one of these tasks
C Working program that meets the criteria for a D, plus:
• Meets the requirements of Tasks 2 and 3 (Joints majors need do only one of these tasks)
16
D Working program that:
• Meets the requirements of Task 1
F No working program demonstrated, or program does not meet any requirements listed above
STAR AWARD
To get an A+, in addition to the above tasks, you must create an elegant, interactive visualization of the
social network in which you can clearly highlight a selected person’s (1) followers; (2) whom the person follows; (3) the person’s propagation tree (as described in Task 6).
Visualizing a large social network in limited screen space in a manner that reflects the properties of the social network not easy. Explore away! CLARIFICATION: You must implement the necessary visualization algorithms instead of using off-the-shelf libraries that already do so.
17
PROJECT 3: BUILD YOUR OWN STEP COUNTER (C++ AND ARM ASSEMBLY)
PROJECT OVERVIEW
Smartwatches are a popular platform to measure a user’s level of exercise. They typically utilize
microcontrollers and n accelerometer sensors to enable this. They implement an algorithm to extrapolate the user’s direction and movement from simple acceleration measurements. The goal of this project is to design and implement a secure step tracker using the BBC micro:bit. The micro:bit's accelerometer will be used to detect steps, and the LED panel will display relevant information to the user. You will be using your micro:bit device to code your custom step counter functionality in C, a simple encryption algorithm in assembly.
Figure 7: image showing X axis across front of micro:bit, y axis up and down, z axis running back to front
The primary objective is to create a step tracker that:
-
Count steps using the micro:bit accelerometer sensor.
-
Displays the step count on the LED panel.
18
-
Logs accelerometer data.
-
Implements basic data security principles in assembly to ensure user data are protected.
THE TASK
This project will exercise the knowledge you acquired from modules SCC.111, SCC.121, SCC.131. You willhave to use C++ and assembly to complete this project and you will use the knowledge of the micro:bit CoDAL APIs. To get full marks you are expected to complete the following activities. Marks will be awarded based on the number of tasks you complete.
Task 1: Accelerometer measurements
Figure 8: Sample serial output of the step counter
An accelerometer is a sensor that measures the force of acceleration acting on it in all three spatial dimensions (X, Y, and Z), allowing it to detect orientation, tilt, and motion as well as the rate of change in velocity. A step tracker uses an accelerometer to detect the distinct patterns of movement associated with walking or running. Each step typically generates a specific acceleration signature, characterized by a high downwards acceleration followed by high acceleration upwards. By continuously monitoring the
19
accelerometer data, the software can apply algorithms to filter and interpret these patterns, distinguishing steps from other movements. This capability enables the step tracker to count the number of steps taken by the user by identifying and tallying these unique acceleration signatures, providing a practical tool for monitoring physical activity.
For this first task, you are expected to use the built-in micro:bit accelerometer, accessible by the CoDAL runtime accelerometer class and collect measurements. You must develop code that handles new accelerometer measurements and prints a message of “UP”, when the direction of movement changes from down to up (i.e., acceleration on the y axis changes from negative to positive) and “DOWN” when the direction of acceleration changes from UP to DOWN (i.e., acceleration on the y axis changes from positive to negative). Your solution should process raw accelerometer data and you should not use the built-in gesture API of the accelerometer class.
Hint: The accelerometer offers a dedicated event that can be managed by your program to handle programmability when the accelerometer values change in any of the 3 axes.
You can find the API of the Accelerometer class here and the serial port class here. Task 2: Counting steps
For the second task, you are expected to implement an algorithm for counting steps. The accelerometer returns as measurement the acceleration on each axis in mG (1G = 1000 mG). Your algorithm should count a step as a consecutive up to down or down to up movement in the Y-axis. To reduce the sensitivity of the detection mechanism, you should record the movement only when the acceleration is more than 200 mG. For example, a movement that goes from UP to DOWN will count as one step. If the next measurement registers an UP movement, then this will count as a second step. For each step you should increment a global step counter variable, so that your micro:bit can keep track of the number of steps.
Task 3: Raw Data Logging
For this third task you are expected to develop functionality to improve the interaction with your step counter. Firstly, you are expected to use the CoDAL API to display the number of steps that the user has
uBit.messageBus.listen(MICROBIT_ID_ACCELEROMETER,
MICROBIT_ACCELEROMETER_EVT_DATA_UPDATE, onAccelerometerData);
20
Figure 9: Sample logging page on the micro:bit.
21
taken since the last boot of the system on the LED display. A user should be able to access this information by pressing button A on the micro:bit board. Secondly, we expect you to implement a logging functionality, which stores raw accelerometer data (Y-axis acceleration measurements when an UP or DOWN movement is detected). Specifically, in each movement you code should store in memory the current and the previous measured acceleration on the Y-axis. You code should store data only for the last 30 UP or DOWN movements. To realize this logging functionality, you can use you own data structure and an array or a doubly linked list to store data for the 30 most recent movements. If you already store data for the last 30 measurements, then your code should discard the oldest measurement, before adding a new one. Additionally, your code should log this data into the micro:bit MYDATA.html file when pressing button B. The logging API of the CoDAL platform can help you in this functionality- you can find details about the logging system here.
Task 4: Improve step counting and displaying information
As you might have noticed so far, our simple step counter is far from perfect, and it is prone over records steps. For this last task, you must implement a better step detection algorithm. During a step, the accelerometer will record multiple accelerometer readings (the CPU is fast enough to fetch and process multiple accelerometer readings/sec) and a step will record acceleration changes in all three dimensions. As a result, your code should be able to associate many micro-movements and maintain some memory to avoid double counting steps.
One possible algorithm can be the following:
-
Firstly, your code should analyse acceleration data on all three dimensions and detect direction changes (change of acceleration from positive to negative, or vice-versa). In addition, a step is expected to generate acceleration greater than 400 mG. When these two conditions are true, the measurement should be classed as a micro-movement.
-
Secondly, in order to record a step, you should receive four accelerometer measurements that meet the micro-movement criteria.
-
Once you detect a step, you should allow a cooldown period, until a next step is recorded. The cooldown period should vary depending on the type of steps. If no micro-movements are detected in the next 10 measurements, then you should reset the step counter. This would reflect a slow mild walk.
22
If though, you continue recording micro-movements, then your code should ignore the next 20 micro movement, as these micro-movement are part of the same step. This would reflect an intensive fast passed walk.
• Once the cooldown has elapsed, you should reset the step counter state and start measuring movement for the next step.
MARKING SCHEME
Marks will be awarded according to the marking scheme shown at the start of this document. Marks for the
‘Functionality’ section will be awarded based on individual merit, but the following table gives an indicative
overview of the level of functionality expected for each grade band: A Working program that meets the criteria for a B, plus:
• Meets the requirements of Task 4
B Working program that meets the criteria for a C, plus: • Meets the requirements of Task 3
C Working program that meets the criteria for a D, plus: • Meets the requirements of Task 2
D Working program that:
• Meets the requirements of Task 1
F No working program demonstrated, or program does not meet any requirements listed above
The precision of step counting will not be assessed, so do not worry if you step counting is a bit off. Our focus will be to ensure that you implement the described functionalities.
STAR AWARD
An A* is also available, for students wishing to really push their limits! To attain this, we will be looking
for students who can apply secure data encryption to their recorded data. For this last step, we want you to implement a data encryption mechanism that uses a simple encryption function (XOR with a fixed key)
23
Figure 10: Sample logging page on the micro:bit using xor-based encryption.
24
before storing data in the log to improve user privacy. The encryption algorithm should be implemented in ARM assembly and you should implement a function that has the following input and output parameters:
void encrypt(int val[ ], int key);
25
