Goals: Review understanding and the ability to use arrays.
Part 1 Use pseudo code to describe your add, remove, find, and display options.
Part 2 Answer the following questions
1. What are the inefficiencies associated with using an unordered array if duplicates are not allowed?
2. What are the advantages of using an ordered array?
3. When would using an unordered array be preferred over using an ordered array?
4. Define Big-Oh notation. Explain how z and c in the definition relate to the evaluation of algorithm efficiency.
5. Why does computer science often describe algorithms in terms of lg instead of ln?
6. How do you convert ln(x) to lg(x)?
7. Give an example of algorithm with Big-Oh values of: N^2, N lg N, 1, and N.
8. Why is Big-Oh 2^N represent an algorithm called intractable?
9. How much slower would a linear search be on 1024 items than 16 items?
10. How much slower would a binary search be on 1024 items than on 16 items?
Part 3 Implement the program. Turn in the working program by e-mailing your zipped lab1 folder to harveyd@sou.edu. Include the typed answers to the questions of part 1 and the pseudo-code of part 2 in a file called questions.doc. If this project is the one to contain extra analysis, include the analysis report in the file analysis.doc.
Instructions
1. For all our labs, use the Eclipse IDE. On your own computer, you will need to install MinGW. You will also need to download and install the C development toolkit (CDT). There are many tutorials on the Web to step you through this process. Eclipse is a popular IDE for C development; it includes a good interactive debugger and project control
2. Write a C program that will maintain a list of employees using either ordered or unordered arrays. Each employee in the list should store an identifier number (integer), a name (String char array), and a salary (Double). Allow operations to add, remove, display single, display list, reset the list, create a initial list with randomly populated items, help, and exit.
3. You can choose either an unordered list or an ordered list for your implementation. If you choose an unordered list, sort it before display. For an ordered list, use a binary search instead of a linear search.
4. You don't need to implement a GUI for this project. Just create a menu of selections as listed below:
Employee Maintenance
1) Add Employee
2) Remove Employee
3) Display Employee
4) Display Employee List
5) Reset List
6) Create Initial List
7) Sort
8) Help
9) Quit
Please Select:
Note: The sort option is unnecessary if you implement an ordered list.
5. To add an employee, randomly pick an integer employee number that must be unique. The C function rand() can be used. A list of available employee numbers must also be maintained. Initially, this list can be filled with a sequential list of integers. To add a new employee, randomly pick one of these integers and replace its entry in the list with the final entry. Ask the user for an Employee name and salary. Keep track of the number of item numbers that are available using an integer counter.
6. When you remove an employee, the employee number should be returned to the free list.
7. Make sure to validate that the salary is within a reasonable range. You can use the C scanf function. Recall that scanf(%s*) is needed to clear the input buffer after an error. Always output appropriate error messages when the user types in something illegal. Robust programs should never crash.
8. My implementation contained three files; one for the main program (lab1.c), one for the list of employees (EmployeeList.c), and one for maintaining each employee (Employee.c). I also created a header file (empstructs.h), which contained a structure for the employee items and various symbolic constants (see below).
#ifndef EMPSTRUCTS_H_
#define EMPSTRUCTS_H_
#include < string.h >
#include < stdio.h >
#include < stdlib.h >
#include < time.h >
#define MAX_EMPLOYEES 100
#define EMP_SIZE 30
#define LINE 80
#define OPTIONS 9
#ifndef NULL
#define NULL ((void *) 0)
#endif
#define FALSE 0;
#define TRUE 1;
typedef struct
{
int id;
char name[EMP_SIZE];
double salary;
} EMPLOYEE;
typedef struct
{
int freeCount;
int employeeIndex;
int numEntries;
int freeList[MAX_EMPLOYEES];
EMPLOYEE *employees[MAX_EMPLOYEES];
} EMPLOYEE_LIST;
/* Declared in Employee.c */
void destroyEmployee(EMPLOYEE**);
EMPLOYEE* createEmployee(char*, double, int);
char* employeeToString(EMPLOYEE*, char*);
/* Declared in EmployeeList.c */
void initializeEmployeeList(EMPLOYEE_LIST*);
EMPLOYEE* insert(EMPLOYEE_LIST*, char*, double);
void sort(EMPLOYEE_LIST*);
int delete(EMPLOYEE_LIST*, int);
void deleteAll(EMPLOYEE_LIST*);
EMPLOYEE* find(EMPLOYEE_LIST*, int);
int traverse(EMPLOYEE_LIST*, void (*)(EMPLOYEE*, char*));
#endif /* EMPSTRUCTS_H_ */
9. When you create a new employee, use the malloc command to allocate the appropriate amount of memory. sizeof(EMPLOYEE), assuming your employee structure is called EMPLOYEE, returns the number of bytes needed for the malloc command. When you remove an employee, or if you are resetting the employee list, make sure to call Cs free function when getting rid of employees. C does not include garbage collection, so failing to do this leads to memory leaks.
10. The Create option will use a 'for' loop to automatically add items to the employee list. Random non-duplicate item number values are required (as we described above). Use any algorithm that you choose to generate different values for the names and salaries; duplicate field values are ok. A simple way to choose employee names is to declare an array of possible names. The following statement can then be used to randomly choose a description:
name = names[(int)(Math.Rand()%namesSize)];
For the salary field, (int)(Math.Rand()%RANGE) + MINSALARY can be used to guarantee that a valid dollar and cents value is used.
11. The help command redisplays the menu. Otherwise, it should only display once when the program starts.
Other Hints
1. The C puts and printf functions are quite useful for output. However, make sure to follow the output with a call to fflush(stdout). Otherwise, nothing shows until the output is long enough.
2. Eclipse provides lots of warning messages, that can save debugging time, but sometimes can cause difficulty in getting rid of the warnings and messages. Your final project should be free of all warnings. Sometimes, you will need to rebuild the project, or clean it, for errors to disappear.
3. To copy a substring, use strcpy, but be sure to add a null at the end ( ) of the string. To truncate a string, simply store the null character at the appropriate index.
4. Recall that C uses NULL, not the null of Java.
5. To use scanf to limit the size of an input string to 30 characters, use the template %30s.
6. Standard C does not allow declaring variables in a loop. So for(count=0; count
7. Remember that C has no classes, no exceptions, and no function overloading.
8. C often lets you do things that crash the program when it runs; so be careful.
Extra Analysis
Do this part if this to be your longer project or if you are a graduate student.
Implement the insert, sort, and remove code for both an ordered and unordered list of employees. Using loops, automatically insert a list of employees with random names and time how long it takes. For the unordered array, after the insert, sort the list and time how long that takes. Finally remove all of the elements, one by one, and time how long that operation takes. Make sure that you use a binary search when inserting into the ordered array. Write a one to two page paper comparing the efficiencies of using ordered versus using unordered arrays.
Note: When comparing algorithms, normally large data set sizes are needed. Also, picking array sizes that vary exponentially is useful to capture the attributes of the algorithms. For example, picking array sizes as 100000, 200000, 400000, 800000, etc. would be appropriate (Assuming that C allows array sizes that large). You can use the C clock() for timing purposes, including
clock_t start = clock();
/* do some cool stuff here */
clock_t end = clock();
double time = 1.0*(end - start)/CLOCKS_PER_SEC;
printf("The algorithm took %lf timen", time);
fflush(stdout);