IT-Universitetet

Introduction to Algorithms and Data Structures, Spring 2005, Episode 1

Spring 2005 Course Description Schedule Resources

Lecture, February 4

Subject : Introduction (Slides). Sorting. InsertionSort. Correctness proofs with loop invariants. Running time estimates. Growth rates of functions. Theta-, Big-Oh-, and Omega-notation.

Text : Browse pages 3–4, CLRS Chapter 1, Sections 2.1 and 2.2. Chapter 3. Browse Appendix A.1.

Comment : In chapter 2 the algorithmic concepts are the most important. Focus in chapter 3 should be on the Big-Oh-notation.

Time : Friday, February 4, 9:00 - 12:00.

Room : 2A12


Assignments

  • CLRS exercises 1.2-2 (M), 1.2-3, page 13.
  • CLRS problems 1-1 excluding row 4 and 8, and excluding minute, hour, month, and year (M), page 13. Note that 1 microsecond = 1/1000000 second
  • CLRS exercises 2.1-1 (M), 2.1-2 (H), 2.1-3, pages 20-21.
  • CLRS exercises 2.2-1, 2.2-2 (H), 2.2-3, page 27.
  • CLRS problems 2-2, page 38.
  • Arrange the functions n2, lg n, 2n, n1/2, n·lg n, and n in ascending order of growth.
  • CLRS exercises 3.1-1 (D), 3.1-4, page 50.

The mandatory assignments should be handed in no later than February 16 at 13.00.

The mandatory assigments should be placed in your teaching assistent box, or send to the TA by email.

Programming assignments

Assignment 1.1

This assignment deals with an experimental study of the performance time of InsertionSort. In Java the performance can me measured using the method System.currentTimeMillis().

Example:

...
long t= System.currentTimeMillis();
sort(A);
t = System.currentTimeMillis()-t;
System.out.println("T= "+t);
...

Here you find the program source for a program that measures the performance time for sorting 1000 integers.
  1. Use the program to measure the performance time for sorting 1000, 2000, 5000, and 10000 integers.
  2. Modify the program to make it count the number of comparisons (i.e. the number of evaluations of the expression "((i >= 0) && (A[i] > key))". Use the modified program to measure the number of comparisons for sorting 1000, 2000, 5000 and 10000 integers.
  3. Make a graph illustrating the results of 1. and 2.
If the file containing the program Insertion-Sort is named InsertionSort.java, the program can be translated in JDK (Java Development Kit) using the command "javac InsertionSort.java". If the translation is succesful, a file "InsertionSort.class" is generated. You can then run the program by writing "java InsertionSort".

Assignment 1.2

[see also exercise CLRS 2.1-3 p. 21]

In the lecture we have claimed that sorted data is more easy to handle automatically than unordered data. Exercises 1.2 and 1.3 let you perform an evaluation of this claim.

Implement a function int linear_search(const int[] A, int x) which takes two arguments: an unsorted array of integers A and a single number n. The function should return an index of a cell in A such that

A[linear_search(A,x)]==x

if n is in A and -1 otherwise. How many comparisons are performed by your function in the latter case?

You should not modify the array during execution. Remember that numbers in the array are unsorted.

Assignment 1.3

[see also exercise CLRS 2.3-5 p. 37]

A BINARY-SEARCH is an efficient method of searching in the sorted array of elements a1,...,am. We begin searching from the middle element of the array. Let j be the index of this element. If aj equals the desired element x then return j and terminate. Otherwise if aj is greater than x then search recursively in the left sub-array: a1,...,aj-1. If aj is smaller than x then search recursively in the right sub-array: aj-1,...,am. If the sub-array to search is empty, then terminate returning -1. This algorithm serves as a foundation for many data structures, which we will be studied in the course later on.

Implement a function binary_search of the same type as linear_search, but exploiting the fact that the input data is sorted, using the algorithm presented above. What is the maximum number of comparisons that your function needs to perform, if the desired element x is not in the array?

Remember that you should not modify the array during search. Also you should avoid copying fragments of arrays. Use recursion, or better, a while loop and two integer variables l and r to indicate the area of the array which is searched in a given iteration. Initially l==1 and r==m.

Finally run linear_search and binary_search on randomly generated arrays of various sizes (including huge arrays) and draw a graph of execution times. Evaluate the results.



last updated February 3, 2005
Anna Pagh, Andrzej Wąsowski
til top