This course builds upon knowledge aquired within previous courses on computer programming and basic algorithms and data structures.
There is no strict requirement about the programming language to be used for the implementation of the programming assignments. However, when pieces of code will be provided for illustration purposes, they will be given mainly in Java.
It is highly recommended that in your programming assignments you make use of standard libraries providing fundamental data structures such as lists, queues, etc and basic algorithms such as sorting, and, if not explicitly otherwise required, do not implement these from scratch, but focus on the new techniques that will be studied.
This set of exercises is a review of basic programming and experimental analysis of algorithms.
Topics to review:
Classroom activity: do one of the following exercises.
Implement the operation CountTripletsSum that, given an array of distinct integers and a value V, finds how many triplets of elements from this array have the sum V.
For example, CountTripletsSum({24, 10, -7, 13, 21, 3, 4, -5, -16, 0}, 0)=3. This is because there are 3 triplets that have the sum of their elements equal with V=0: (-16, -5, 21), (-16, 3, 13) and (-7, 3, 4)
Write a program that reads the elements of the array from a text file and uses the function to count triplets for the value of V=0. The format of the input files is the following: the first line contains the number of integers, and the next lines contain the integers, one on each line.
Measure and display the runtime of the count function. Do not include the time for reading the file in the measurement.
Run your program taking as inputs files having from 1000 to 100000 elements. Data files to be used as inputs are available here
Implement an efficient version of the count function such that you are able to run it in reasonable time even on the big input sizes ! The simple brute-force approach of testing all possible triplets will not do well on the bigger input sizes. Draw a graph representing the measured runtime of the count function vs. the number of elements, compare the brute-force algorithm times vs. the efficient algorithm.
Implement the operation CountSmallerTriplets which, given an array of distinct integers and a value V, finds how many triplets of elements from this array have the sum less than V.
=== similar measurements as for exercise 1 ===
Run your program taking as inputs files having from 1K to 100K elements. Data files to be used as inputs are available here
Implement the operation ExistTriplet which, given the arrays A, B and C and a value V, determines if there exists a triplet of numbers (a, b, c) having the sum V, where a is from A, b from B and c from C.
=== similar measurements as for exercise 1 ===
Run your program taking as inputs files having from 1K to 100K elements. Data files to be used as inputs are available here
Implement the operation CountPossibleArrays that takes an array A of positive integers and determines how many triplets formed by array elements represent possible triangles. A triplet (a,b,c) represents a possible triangle if the sum of any two numbers is bigger than the third one: (a+b>c)&&(a+c>b)&&(b+c>a).
Example: CountPossibleArrays({5, 3, 6, 2})=2. The triplets (2, 5, 6) and (3, 5, 6) can be triangles.
=== similar measurements as for exercise 1 ===
Run your program taking as inputs files having from 1K to 100K positive integers as elements. Data files to be used as inputs are available here
Implement the operation CountPythagoreanTriplets that takes an array A of positive integers and determines how many triplets formed by array elements represent pythagorean triplets. A triplet (a,b,c) is pythagorean if a^2 = b^2 + c^2.
Example: CountPythagoreanTriplets({5, 3, 6, 2})=0. CountPythagoreanTriplets({5, 3, 6, 4})=1.
=== similar measurements as for exercise 1 ===
Run your program taking as inputs files having from 1K to 100K positive integers as elements. Data files to be used as inputs are availab$ here