Data Structures and Algorithms Lab Exercises

These outline notes are intended briefly to indicate tutorial contents. Making these notes available does not replace the learning support which can only be provided during tutorial sessions. Students are also reminded that a significant proportion of the coursework marks depend upon the presence of students at tutorials in order to demonstrate completed coursework soon enough to obtain useful feedback. Feedback is provided in connection with logbook work when programs are demonstrated.

1. Week 1 - Complex Calculator Program

1.1 The source code calculat.c is used as a basis. calculat.c implements the specification for this weeks exercise but for simple non-complex numbers. Students will need to modify this program so that it performs arithmetic on complex numbers.

1.2 The practical exercise involves designing and building a complex number calculator program using a structure called complex, consisting of 2 floating point numbers for the real and imaginary components. Students will write functions which add, subtract, multiply and divide 2 complex numbers and return the (complex) result of this operation. A suitable prototype is of the form:


where COMPLEX is a previously defined typedef for a struct complex e.g.

typedef struct complex COMPLEX;

and a struct complex is previously defined as something like:

struct complex {
  float real,imag; /* real and imaginary components
                      of complex number */

1.3 Menu options include add, subtract, multiply, divide and quit. If the user chooses an arithmetic operation the real and imaginary components of both complex numbers will be prompted for and input by the user. The relevant function will then be called and the result displayed. This menu will operate inside a loop until the quit option is selected; use either switch case or nested if, else if, else within a suitable loop. An error message can be displayed for invalid menu selection input.

1.4 Equations for complex number arithmetic

add: (a + bi) + (c + di) = (a + c) + (b+d)i

subtract: (a + bi) - (c + di) = (a - c) + (b-d)i

multiply: (a + bi)(c + di)
= (ac) + (dbi2 ) + (bc+da)i {as i2 = -1 this is same as:}
(ac-db) + (bc+da)i

divide: (a + bi)/(c + di) =
((a + bi)(c-di))/((c + di)(c-di)) {multiplying both sides by (c-di)} =
((ac + bd) + (bc - ad)i ) / (c2 + cdi -cdi + d2) { (cd - cd)i components cancel} =
(ac + bd)/(c2 + d2) + ((bc - ad)/(c2 + d2))i

2. Week 2

2.1 Write a simple program which writes 10 integers or floats to different binary files using fwrite() in the MSDOS environment. Look at the MSDOS directories using the DIR command and explain the displayed file sizes (4 bytes per float, 2 bytes per int).

2.2 Write a program which uses fread() to read these binary files created above into arrays declared within their programs. Display the average and total values for these numbers.

2.3 Write programs which create and read the same data but as text files instead of binary files (E.G. using fprintf and fscanf and compare and explain the difference in file sizes and data representation between binary and text files.

2.4 This exercise is useful preparation for assignment 1 exercise 3. You will find this program easier to develop and debug if you try to keep it modular, with appropriate data and processing in different functions, with suitable choices for parameters, return types and global data.

2.4.1 Create a text file using Notepad which contains 2 lines of text:

John 2345
Jaz 7984

2.4.2 Develop your program using seperate global, main and function components:

2.4.3 When you have done this run your program. Reload the text file into Notepad and check if the original 2 records and the extra record added are all there. Run the program again and check that all 3 records are displayed in the table.

3. Week 3

3.1 The practical exercise involves declaring an array of pointers to char. You may use one fixed length buffer to copy input. All other data to store the wordlist must be allocated dynamically using malloc().

3.2 Write a program using the above techniques which store a list of 10 words input from the keyboard and display these on the screen in reverse order.

3.3 Develop this program so that it:

a. opens an external text file in read mode. b. inputs 10 words from this file (has to exist first, create it with a text editor beforehand). c. closes this file. d. opens the same file in write mode. e. writes 10 words to this file in reverse order

4. Week 4

4.1 Write a program which declares a global array of ints in ascending sorted order. Your main function prompts the user to input an int value and then calls a search function to search for the int within the array. Your search function returns the index within the array where the value is present or -1 if the value is not present within the array.

4.2. Upgrade the above program so that´┐Ż a binary split search algorithm is used.

5. Week 5

5.1 Use project facilities in Borland 'C' to split a program consisting of multiple functions into multiple source files so that source becomes more modular, compilation of large projects can be limited to changed files and function source codes can be maintained in one place and accessed by multiple programs.

5.2 Declare an array of global floats or ints in unsorted order. Write a program which calls a sort function to
sort this array. Your main function then prints out the list of numbers in sorted order.

6. Week 6

6.1 Develop the program started in 2.4.1 and 2.4.2 above. This program should be modified to read a text file contacts.txt created using a text editor containing 10 lines, each line is a record containing a persons first name followed by a phone short dial code or extension number in the range 1-9999. E.G:
Pete 1234
Raj 2468
Mary 8765
Sukwinder 2222
Harry 3344

Your program will use a CONTACT record:

typedef struct contact{
   char name[20];
   int phone;

and an array of 10 CONTACTS .

CONTACT list[10];

Your program will, using seperate functions:
a. Open contacts.txt in read mode, read data into array, close contacts.txt
b. Display contact records in the order in which they were input.
c. Ask user whether to sort in name or phone number order.
d. Sort the array in the required order.
e. Open contacts.txt in write mode, write sorted data back to contacts.txt and close it.

6.2 Modify this program so that sort and display functions can be called from a menu selection using an event handling loop similar to that used in the complex calculator program (see week 1).

7. Weeks 7 onwards

Completing the coursework assignment will require (in addition to study, logical thought, careful observations and persistent effort) all of the skills and techniques learned in previous excercises togther with the knowledge presented during the lectures.