ADS103: Algorithms and Data Structures - IT Assignment Help

Assessment Task

Implement the sorting algorithm and C++ Standard Library tasks below to demonstrate your understanding of the development and utilisation of important algorithms and data structures.

Please refer to the Instructions for details on how to complete each task.

Context

The two tasks below seek to examine your conceptual and practical understanding of some key algorithms and data structures.

Task 1 focuses on comparing the performance of sorting algorithms against each other, and the impact of the data’s ordering on performance. You likely won't need to implement many searching algorithms in the industry but crafting them yourself will give you firsthand practical experience at seeing which types of algorithms perform better under different types of conditions. As a software engineer, you will need to create algorithms here and there to solve unforeseen problems; therefore, familiarity with multiple approaches will help.

Task 2 focuses on utilising pre-built data structures from the C++ Standard Library to store and retrieve sets of data. In any given coding language, there are likely to be existing container structures. You will practise with some common ones used in C++, but the use of these containers is similar in approach in most languages.

Instructions

Task 1

You will write a program to retrieve a data set from a text file at a time and measure the time taken to sort it with two different sorting algorithms. You can choose which sorting algorithms to write from the provided options.

Provided are two text files, a2_task1_input1.txt and a2_task1_input2.txt. They are formatted similar to the below example but with much more data:

100 628 234 581 595 968 285 42 775 353 109 862 101 117 598 291 276 767 69 919 264 98 683 582 510 656 927 200 507 580 822 408 330 662 842 362 474 199 137 873 875 791 525 842 304 157 351 789 708 384 667 309 398 281 997 100 12 279 834 100 68 185 295 329 98 232 883 284 67 607 981 767 705 478 844 753 992 245 755 826 493 803 520 221 36 975 997 964 992 349 347 657 698 347 539 951 337 506 287 25 762

Line 1 of the input file is the number of data elements to sort. Line 2 is the data elements to be sorted.

Your Learning Facilitator may test with their own supplied input file reading any number of data elements; therefore, ensure your code can be flexible. a2_task1_input1.txt contains completely random numbers; a2_task1_input2.txt contains sorted data with only the first number out of sequence.

1.1 Open a2_task1_input1.txt for reading (using, say, std::ifstream).

1.2 Using the count value in line one of the file, read the number from line 2 into either a dynamically allocated array or std::vector.

1.3 Write either an insertion or bubble sort algorithm and sort the data.

1.4 Measure the time taken to complete the sort (in milliseconds).

1.5 Read the file contents once again into another dynamically allocated array or vector. You’re going to be sorting this fresh copy of the original file data—you don’t want to inadvertently sort the already-sorted vector from step 1.3.

1.6 This time, write a quick sort or merge sort algorithm and measure how long it takes to sort the data (in milliseconds).

1.7 Compare the times taken for the two sort operations and output. Which algorithm was the quickest sorting this particular data set to the screen? 

Repeat the above steps with a2_task1_input2.txt, this time to compare how the two algorithms compete on a mostly sorted set of data.

Task 2

This task requires you to implement a simple book management system utilising the C++ Standard Library.

• Step 1

Write a menu screen that presents the user with these options: What would you like to do:

• List all books you have on loan
• Return a book
• List all books in the library
• Borrow a book
• Exit

Enter choice (1–5):

If the user enters a number from 1–4, the program moves on to that functionality. After it’s complete (say, listing books on loan, or a user completes borrowing a book), the program should loop back to the main menu.

Step 2

2.1 Include std::vector and std::map libraries into the project. Create a map of books for the library with int as the key and string as value pair. Store at least 10 books, e.g. books.insert(pair(5, "Moby Dick"));

2.2 Create a vector of ints to store book IDs of borrowed books.

Step 3

Implement the menu actions as follows

• List all books you have on loan: Output all the borrowed book IDs currently in your vector alongside book name, which will need to retrieved from the books map. Here’s an example:

5: Moby Dick

22: The Wizard of Oz

2: Charlie and the Chocolate Factory etc.

• Return a book: User is asked to input the ID of the book to return and if it exists in the vector, remove that book from the book’s borrowed vector
• List all books in the library: Output all IDs and book titles in the books map, e.g.

5: Moby Dick 

 22: The Wizard of Oz

9: Three Musketeers etc.

• Borrow a book: User is asked which book ID to borrow from the library. If it exists, add the title to the user’s books borrowed vector
• Exit: quits the program

Step 4 Add in any relevant functions or classes to maintain the project.

This MBA404:  IT Assignment Help has been solved by our IT experts at onlineassignmentbank. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.