Reference no: EM133184588

ADS103 Algorithms and Data Structures - Laureate International Universities

Programming Assignment

Learning Outcome 1: Identify and utilise appropriate algorithms to solve software engineering problems.

Learning Outcome 2: Identify and utilise appropriate data structures to solve software engineering problems.

Learning Outcome 3: Design and develop functions and classes to manage levels of code complexity.

Learning Outcome 4: Demonstrate an understanding of recursive algorithms through appropriate application.

Learning Outcome 5: Demonstrate the ability to read and interpret moderately complex code, describe its purpose, and systematically debug for issues in syntax or logic.

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:

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.

Open a2_task1_input1.txt for reading (using, say, std::ifstream).
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.
Write either an insertion or bubble sort algorithm and sort the data.
Measure the time taken to complete the sort (in milliseconds).
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.
This time, write a quick sort or merge sort algorithm and measure how long it takes to sort the data (in milliseconds).
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:

1) List all books you have on loan
2) Return a book
3) List all books in the library
4) Borrow a book
5) 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
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<int, string>(5, "Moby Dick"));
Create a vector of ints to store book IDs of borrowed books.

Step 3
Implement the menu actions as follows
1) 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.
2) 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

3) 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.
4) 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

5) Exit: quits the program

Step 4

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

Referencing
It is essential that you use appropriate APA style for citing and referencing research.

Attachment:- Algorithms and Data Structures.rar