2 assignments

Assignment #1:

Objectives : In this assignment students will practice manipulating lists of data and arranging items in an ascending/descending order. Students will also explore storing lists/arrays using different sorting algorithms including, the selection sort, bubble sort, and insertion sort algorithm. Comparison between the three algorithms are made based on the number of comparisons and item assignments (basic operations) each algorithms executes.

Important notes:

1. This assignment should be implemented during the lab time of this week.

1. The assignment will be marked at the end of your lab period for this week.

1. Any submission after the lab time will not be accepted for marking.

1. Please note that this assignment only worth a 30 marks.

Background: Ordering the elements of a list is a problem that occurs in many computer science contexts for example, in a telephone directory it is necessary to alphabetize the names of subscribers. Similarly, creating a dictionary requires words be put in alphabetical order. While there are multiple sorting algorithms, some are better than others depending on the information being sorted. One thing in common which all sorting algorithms have is the sorting parameter. This “function” is what decides if two items in a list needs to switch places. While this is easy for the standard data types (int, char, double, …) since the compiler already knows how to compare these, it might be tricky for data types created by you. Structs and classes you create will require implementing comparison functions if you are trying to sort them. For example to compare two dates you can write something like:

bool compDate(Date d1, Date d2){

if (d1.year < d2.year

return true;

else if (d1.year == d2.year && d1.month < d2.month)

return true;

else if (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day)

return true;

else

return false;

}

The selection sort, bubble sort, and insertion sort algorithms are the most widely used algorithms. The section sort repeatedly picks the smallest element to append to the result. The insertion sort algorithm splits the list into two portions (sorted and unsorted) and repeatedly adds new element to the sorted portion of the list. The bubble sort algorithm repeatedly compares neighbor pairs and swap if needed.

Problem Description:

Write a C++ program to create 2 identical arrays, list1, and list2 – each list of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort and outputs the number of comparisons and item assignments made by each sorting algorithm. In addition to the code, write a description of the C++ program in your own words explaining your code and comparison between the sorting algorithms in terms of the number of comparisons and item assignments.

Hint : You need to create a random array and then copy it to end up with two identical lists (List1, List2). These two lists must be identical. You will need to sort List1 using bubble sort, and sort the second list List2 using the selection sort algorithm. Finally, you will need to output the number of comparisons and item assignments made by each sorting algorithm. Please note that the array should be randomly generated and you can do that by using the random function: rand() from the <cstdlib> library.

____________________________________________________________________________

Assignment #2:

Objective: The main objective of this assignment is to prepare students for the final project. The students will need to implement a program that involves two ADTs and communication among them.

Description: You will need to create a simple ADT called Buffer, which allows users to write and edit “text”, and another ADT called Interpreter, to interpret the user’s commands (insert text, delete text, and append text) and invoke the Buffer’s appropriate methods to complete those actions.

Note: If you are interested in more robust approaches for data structures that hold text buffers, check Ropes and Gap Buffers, which are used in real open source and commercial software.

Task 1 - Create the Buffer ADT

1. The text must be stored in a dynamic array of characters. This array will be expanding when inserting/appending text and shrinking when deleting text.

2. A variable to indicate the index position of a cursor

3. Constructor/Destructor

4. Delete: Deletes “n” characters starting from some index “i”. Even when deleting all characters, a single empty char will remain in the buffer to allow further actions. Similarly, your program should not allow the last empty character to be deleted.

5. Append: Add text at the end of the buffer’s dynamic character array, leaves empty character at end of buffer.

6. Insert: text to add, index position of where to add. Note that we never replace or delete content when using the “insert operation”. Thus, in Figure 1, if we insert text at index 4, the ‘o’ will not be deleted but shifted to the right.

7. Print Buffer (Figure 1)

Print the character array and the indices on top to make inserting and deleting easier

Print the size of the buffer

Add “^” below the position of the cursor

Print the index of the cursor

The buffer must be automatically initialized with the text “Hello World! “

note the trailing empty character

Figure 1

Cursor

The cursor indicates where text can be appended and thus it always points to the end of the buffer.

Task 2 - Create the Interpreter ADT

This ADT must provide access to the Buffer’s methods via a Menu as indicated in Figure 2.

Figure 2

1. The interpreter must not contain Buffer as an attribute, use a pointer variable to the Buffer instead as a private attribute

2. Constructor

3. Must not allow illegal input i.e. inserting at invalid index, deleting characters that are not there, etc.

You are free to design the rest of the program in any manner as long as the requirements are met.

Note: Requirements are demonstrated in supplied video

Additional Requirements

1. Separate header and source files for the two ADTs.

2. No memory leaks must be present (delete arrays that are not needed).

3. After selecting action, the user should be able to cancel before supplying required info (where to insert, what to delete, etc.)

4. The menu should include an exit option

Sample Output

Figure 3 Before Append

Figure 4 After Append

Figure 5 Before Delete

Figure 6 After Delete