Algorithm design and problem-solving (3)
Resources |
Revision Questions |
Computer Science
Login to see all questions
Click on a question to view the answer
1.
An algorithm is designed to sort a list of numbers in ascending order. You are given the following algorithm:
Algorithm SortList(list)
Input: A list of numbers
Output: The list sorted in ascending order
1. Create an empty list called 'sortedList'.
2. For each number in 'list':
3. If 'sortedList' is empty, add the number to 'sortedList'.
4. Otherwise, while 'sortedList' is not empty and the number is less than the first element of 'sortedList':
5. Remove the first element of 'sortedList'.
6. Add the number to 'sortedList'.
7. End
a) Explain, in plain English, what the algorithm does. (2 marks)
b) Create a trace table to show how the algorithm would sort the following list: [5, 2, 8, 1, 9]. (4 marks)
| Iteration | list | sortedList | Explanation |
| 1 | [5, 2, 8, 1, 9] | [] | sortedList is empty, so 5 is added. |
| 2 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
| 3 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
| 4 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
| 5 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
| 6 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
| 7 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
| 8 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
| 9 | [5, 2, 8, 1, 9] | [5] | 5 is less than the first element (5) of sortedList, so 5 is removed and 5 is added. |
c) What is the time complexity of this algorithm in terms of the number of operations it performs? (2 marks)
The worst-case time complexity is O(n2), where n is the number of elements in the list. This is because, in the worst case, for each element in the input list, the algorithm might have to remove elements from the sorted list. The number of removals can be proportional to the number of elements already in the sorted list, leading to a quadratic time complexity.
The algorithm takes a list of numbers as input and sorts them in ascending order. It iterates through the input list, adding each number to an initially empty sorted list. If the sorted list is not empty and the current number is smaller than the first number in the sorted list, it repeatedly removes the first element from the sorted list until either the sorted list is empty or the current number is no longer smaller than the first element. Finally, it adds the current number to the sorted list. This process ensures that the sorted list always contains the smallest elements encountered so far.
2.
Question 3
You are tasked with designing a system to manage library books. The system needs to allow users to search for books by title, author, or ISBN, and to track the availability of each book. Describe a solution to this problem, including the data structures and algorithms you would use. Consider how you would handle multiple copies of the same book.
Solution Design:
A suitable solution would involve a database with a well-designed schema. The core components would be:
- Data Structure: A relational database with at least two tables:
- Books Table: This table would store information about each book. Columns would include: BookID (primary key, auto-incrementing), Title, Author, ISBN (unique key), PublicationYear, Genre.
- Copies Table: This table would track individual copies of a book. Columns would include: CopyID (primary key, auto-incrementing), BookID (foreign key referencing Books table), Status (e.g., 'Available', 'Borrowed', 'Lost', 'Damaged'), Location (e.g., shelf number).
- Algorithms:
- Searching for Books: The application would use SQL queries to search the Books table based on the user's input (title, author, ISBN). Indexing the ISBN and Title columns would improve search performance.
- Tracking Availability: The Status field in the Copies table would indicate whether a copy of a book is available. When a book is borrowed, the Status of the corresponding copy would be updated to 'Borrowed'. When a book is returned, the Status would be updated to 'Available'.
- Handling Multiple Copies: The Copies table allows for tracking multiple copies of the same book. Each copy has its own CopyID and Status. This allows the system to accurately track the availability of each individual copy.
- Borrowing/Returning Books: The application would use SQL INSERT and UPDATE statements to record borrowing and returning events in the Copies table. It would also update the Status of the relevant copy.
Technology Considerations:
This solution could be implemented using:
- Backend: Python (with Flask/Django), Node.js, PHP.
- Database: MySQL, PostgreSQL, SQLite.
- Frontend: HTML, CSS, JavaScript (with React, Angular, Vue.js).
| Books Table: |
| BookID (PK, Auto-incrementing) | Title | Author | ISBN (Unique Key) | PublicationYear | Genre |
| Copies Table: |
| CopyID (PK, Auto-incrementing) | BookID (FK) | Status | Location |
3.
Describe the advantages of using system decomposition and sub-systems when designing a large software project. Provide at least three distinct advantages with brief explanations.
System decomposition and the use of sub-systems offer several advantages in large software projects:
- Improved Manageability: Breaking down a large system into smaller, independent parts makes the project easier to understand, design, develop, and test. Each sub-system can be worked on by a separate team or individual, reducing complexity.
- Increased Reusability: Sub-systems can often be reused in other projects or different parts of the same project. This reduces development time and effort, and promotes consistency. For example, a user authentication sub-system could be used in multiple applications.
- Enhanced Maintainability: If a problem occurs in one sub-system, it is less likely to affect other parts of the system. This makes it easier to isolate and fix errors. Changes to one sub-system can be made without significantly impacting other parts of the system, as long as the interfaces between sub-systems remain consistent.
- Improved Teamwork: Decomposition allows different teams to work concurrently on different parts of the system, improving overall project efficiency. Each team can focus on a specific sub-system, leading to better specialization and expertise.