Question 1 (Counting) – 10 marks
A class has 2n students. We want to pair up the students for their assignments.
- (2 marks) How many unique pairs of students are there? Express as a function of n.
- (2 marks) Suppose that each pair is made up of a leader and a member. Now what is the total number of unique pairs?
- (3 marks) A pairing is made up of n pairs of students that match all students in the class (with no distinction between leaders and members). How many possible pairings are there?
- (3 marks) Tabulate the values for parts a-c for n=3,…,10. (You are encouraged to use either a spreadsheet or write a program to generate these values. There is no need to submit the spreadsheet/program)
Question 2 (Divide and Conquer) – 10 marks
A real-estate investor is planning to purchase a cluster of shop houses for redevelopment. Due to redevelopment restrictions, this investor needs to secure consecutive shop houses in a single cluster. With careful evaluation, this investor has obtained good evaluations on the revenue potentials of all shop houses under consideration. Naturally, his goal is to identify the cluster so that the aggregate revenue potential can be maximized. An example instance can be seen in the figure below, where each rectangle represents a shop house, and the number inside denotes its earning potential (in thousands of dollars). This investor can choose a cluster with any number of consecutive shop houses. Of all possible combinations, the best cluster is denoted as the dotted rectangle.
To describe the problem abstractly, let array a store the revenue potentials of all shop houses. For example, for the above figure, a=[31, -41, 62, 26, -54, 58, -13]. The maximum can be achieved by choosing a cluster that spans from elements 3 to 6. When all numbers are positive, the entire array is the answer; while when all numbers are negative, the empty array maximizes the total at 0.
- (4 marks) Design a simple and straightforward O(n2)-time algorithm to find the maximum cluster for a given array a. You may use pseudo-code to present your design. Briefly explain why your designed algorithm has a complexity of O(n2).
- (6 marks) Design a divide-and-conquer algorithm with complexity O(n log n). Briefly explain why your designed algorithm has a complexity of O(n log n). (Hint: You could follow the steps we used to argue that mergesort has a time complexity of O(n log n).)
Question 3 (Data Structures, Searching and Sorting) – 10 marks
You are given the following files for Q3:
| File name | Description | Comments |
| datasample.txt | A list of 20 actors and the movies that they have acted in. Use this list for testing. | Do not modify this file |
| dataactors1.txt | A larger list of 18,630 actors and the movies that they have acted in. | Do not modify this file |
| main.rb | The main file that you run to perform your task. This code will invoke the load and search methods that are in q3.rb. load will only be invoked once, followed by the search methods several times with different parameters. | You may modify this file for testing purposes, but your final q3.rb must be able to run with the original main.rb. |
| utility.rb | Contains helper methods used by main.rb (e.g. read_file) | Do not modify this file |
| q3.rb | Contains the load and search_by_actor and search_by_movie methods. | You need to modify and submit this file |
Browse through the files given above and attempt to run main.rb to familiarize yourself with the programs. q3.rb contains a method called load that opens one of the text files and reads the content. q3.rb also contains two search methods called search_by_actor and search_by_movie.
The first method takes in an actor’s name and returns a list of movies that the actor has acted in. Likewise, the second method takes in a movie name and returns a list of actors involved in the movie. In both cases, the returned list should be sorted alphabetically (0, 1, 2… 9, A, B, C… Z, a, b, c… z). Currently these two search methods are incomplete. Searching is case-sensitive and only exact string matches are considered.
Your task:
- You need to modify the two search methods in rb so that they return the correct search results. Refer to the comments in the code for more details.
- You may modify the load method or include any other methods to rb if necessary.
- You may make use of any of the RubyLab libraries (from the textbook) – just include the necessary files in your code. No other libraries may be used.
To submit:
- A concise and clear explanation of how you completed your task in order to reach your assessment objectives. Diagrams are usually useful and you may include them. Word limit: one A4-page in your Word document (including diagrams, but excluding references, if any).
- Your modified rb. You will need to upload this file to the Submission Server. See the appendix for uploading instructions.
- severely penalized if your solution returns incorrect results! There isn’t much point if your solution is incorrect but lightning fast.
- Originality – the novelty and uniqueness of your solution
- Explanation – your explanation (in the Word document) needs to be clear and match your code submission.
- Speed– how fast your solution takes to return. Your solution will be benchmarked against other submissions on the same server in order to determine your speed. The submission server may use different test sets besides the two provided in order to perform this benchmarking, so your solution should work well with other possible data sets.
Question 4 (Data Structures and Algorithms) – 10 marks
You are given the following files for Q4:
| File name | Description | Comments |
| datasample.txt | Similar to that for Q3 | Do not modify this file |
| dataactors1.txt | Similar to that for Q3 | Do not modify this file |
| main.rb | The main file that you run to perform your task. This code will invoke the load and get_common_movies method that are in q4.rb. load will only be invoked once, followed by get_common_movies several times with different parameters. | You may modify this file for testing purposes, but your final q4.rb must be able to run with the original main.rb. |
| utility.rb | Contains helper methods used by main.rb (e.g. read_file) | Do not modify this file |
| q4.rb | Contains the load and get_common_movies methods. | You need to modify and submit this file |
This question is similar to, but independent from Q3. You need to write the get_common_movies method in q4.rb that takes in the names of two actors and returns the list of movie that both of them have acted in, sorted alphabetically (0, 1, 2… 9, A, B, C… Z, a, b, c… z). Actor names and movie names are case-sensitive and only exact string matches are considered.
Your task:
- You need to modify the get_common_movies method in rb so that they return the correct results. Refer to the comments in the code for more details.
- As with Q3, you may modify the load method or include any other methods to rb if necessary, and include any RubyLab libraries.
To submit:
- Like Q3, you need to submit a single-page explanation and q4.rb to the submission server.
Assessment:
- Like Q3, your solution will be scored on correctness, originality, explanation and speed.