School of Computer Science
University of Guelph
CIS*3490 The Analysis and Design of Algorithms
Winter 2023
Instructor: Fangju Wang
Assignment 3 Guide
You can develop your programs using any C system, as long as your programs can be
correctly compiled and executed on the SoCS Linux server.
You are allowed to use standard library functions. Your programs should be submitted as
a tar file containing files like
readme.txt, P11.c, P12.c, P21.c, P22.c, P23.c, makefile.
Any compilation warning will result in a mark deduction. There will be some marks allocated
for documentation.
Each file should have a comment at the beginning containing your name, ID, date, and the
assignment number.
The readme file should contain the following:
• Name, ID and assignment number
• A brief and clear description of how to compile and run your programs.
• Comparison and analysis for Q2.4.
Each function should have a brief comment describing its purpose. Also, any section of code
where it is not easily apparent what the code does should have a short comment.
Hints for individual questions:
1 You may visualize the example in the handout by drawing the integer line at the bottom,
and above it a short line representing an interval. Visualizing the example may help you
understand the problem and develop algorithms.
1.1 Find the minimum and maximum endpoints (integers) of all the intervals. Scan the integer
line between the minimum and maximum. For each of the points, check all the intervals
to see how many intervals include it.
1.2 You may sort the endpoints of all the intervals, and also find the minimum and maximum
of the endpoints. By scanning the sorted endpoints of intervals you can find the maximum
number.
1
1.1, 1.2 The output could be something like:
Brute force program for finding max number of intervals
The maximum number of intervals: 15057
The intervals include point: 21713
Time for finding the maximum number: 6236 ms
2.1, 2.2, 2.3 You can follow the algorithms in the text. The output could be something like:
A Brute force program for string search.
Enter a pattern: maintain
Count: 137
Shifts: 2988194
Execution time = 14 ms
In searching a pattern, the counts of different algorithms must be the same. The numbers
of shifts of different implementations of the same algorithm could differ slightly.
2