EE221 Extra Credit Assignment 14

Program 1 (Extra Credit up to 40pts.)

Implement binary insertion sort sorting algorithm that is described in Chapter 13, Exercise 13.1.11 on page 735. Test your sorting function using this test program.

Run your program a few times and make sure that it always sorts correctly. Please provide printout of at least one run for at least eight elements. (One run of a test program executes sorting five times for each of the two methods.)

binary insertion sort hint:

    // this is inside the outer loop.
    elem=a[i];
    int low=0;
    int high=i-1;
    int move;
    if (elem<a[low]) move=low;
    else if (elem>=a[high]) move=high+1;
    else {
        for (;;) {
            move=(high+low)/2;
            if (high-low<=1) { move=high; break; }
            if (a[move]>elem) high=move; else low=move;
        }
    }
    // now shift everything between [move] and [i] by one
    // and insert the elem at [move] position

Program 2 (Extra Credit up to 40pts.)

The sorting algorithms that were discussed in class operate on C-style array. Convert the code of one of the discussed algorithms so that it can operate on Iterators. Use the provided test program to test your work.

Program 3 (Extra Credit up to 40pts.)

Based on information from the lectures, textbook Chapter 14 sections 2-3 and the example discussed in class: create a child class to list that would be called unique_list and would ignore every attempt to add an element of the value that is already included in the list. Otherwise, it should add new elments as requested by appropriate functions (push_front(..), push_back(..), insert(..,..), insert(..,..,..)). In case of insertion that fails return the iterator that points to the value that already is in the data collection.

Make sure that, in necessary, you implement a default constructor, a copy construtor, and a conversion constructor from list<t>. Also implement an assignment operator.

Write a short program to test all amended features of your list. You may use either the list from your previous homework, or preferably the list from STL library.

Program 4 (Extra Credit up to 40pts.)

Based on information from the lectures, textbook Chapter 14 sections 2-3 and the example discussed in class: develop and test a specialized stack library that could be useful with the maze simluator that we used earlier during this semester. This assignment actually is not linked to the "maze" programs. Those programs merely give the rationale for this library. This stack can be utiliez in the manual walk thorugh the maze program. You do not have to connect it to that program though.

The stack should be a stack of integers or chars. You can use either out old "Stack.h" or <stack>. The altered functionality is as follows:

When someone pushes 'R' and top is already 'R' then instead of pushing the second 'R' the first 'R' should be removed from the stack and 'B' should be pushed instead.
When someone pushes 'L' and top is already 'L' then instead of pushing the second 'L' the first 'L' should be removed from the stack and 'B' should be pushed instead.
When someone pushes 'B' and top is already 'B' then instead of pushing the second 'B' the first one should be removed.
The most recently discussed 'B' functionality should be linked to 'R' and 'L'. You can do it either by checking for a 'B' in each case or by calling the child class push recursivly.
When someone pushes 'L' and top is already 'R' then instead of pushing 'L' the 'R' should be removed.
When someone pushes 'R' and top is already 'L' then instead of pushing 'R' the 'L' should be removed.

Test your program in a small test program by pushing the following sequence: LFRFLRFRLFLRRLFFFRRFFFLLFFFBLLFFFBRRFFFLLLLFFFFRRRRFFFF. Investigate the result by printing the content of the stack and examining against expected values. Use the provided test program to test your work.

Program 4 (Extra Credit up to 40pts.)

Extra Credit Scope

Doing any of the problems listed above improves some of the skills that may be tested during the third exam. It pays to do this extra credit now and get some points instead just before the exam as preparation.

Extra Credit Limit

Extra credit is subject to certain limits: The problem with most points will be recorded at 100% of points received. The next problem will be recorded at 75% of points received, the third with 50%, and and the forth only 25%.

Study Day

Please make sure that you submit this and any late assignments by 11:59pm on Tuesday before the day the Study Day to make sure that you could receive credit for your work. If the instructor is not in his office please slide the homework under the door. Homework is accepted until the moment the instructor comes back to his office after leaving for home on Tuesday evening.

visitor counter