Information about the CPS815 midterm exam

The midterm test will be on October 20, 2017, Friday, 3-5pm, in class.
The test will be 1h40min long. Aids: you can bring 1 page of hand-written notes. You can use only 1 side of a page. These notes must be written by your hand, printed notes or photocopies are NOT allowed. You can use either a pencil or a pen to write your notes. You must hand in this page together with your exam paper at the end of the midterm test. Write your name and student number at the top-right corner of your page with hand-written notes. You CANNOT use any other aids during the midterm test. In particular, do not bring calculators (you will not need them).

Remember to bring your Ryerson student card, a pen/pencil and an eraser. Do NOT detach pages from your exam paper.

The midterm exam may include short essay questions, designing and writing algorithms in pseudocode, doing analysis of algorithms, tracing any of the algorithms discussed in class or mentioned in your home assignment, as well as solving problems. You will not be asked to write actual code during the exam.

You have to study the textbook, and your notes. You might wish to review also problems from the 1st Assignment and problems from quizzes. You can try to solve problems from the sample midterm test posted online as a PDF file (login to D2L to download) in a Course Documents folder. When you practice, watch how much time it takes you to answer questions from this previous midterm test.

 

Here are some highlights, but remember, everything talked about in class or mentioned in the 1st assignment is a possibility.

  1. Introduction to algorithm analysis. Review of asymptotic notations: O, Omega, Theta. Providing the tight upper bound on the running time of an algorithm given a pseudocode description of the algorithm (similar to Quiz 1.) You must provide a detailed explanation: write for each line the tight Big-Oh estimate on the number of operations and explain how did you get it. You lose marks if you do not explain. If algorithm is recursive estimate how many calls it will do before termination; if it includes while-loop, estimate the number of iterations before termination. Simple properties of asymptotic notation Big-Oh, Big-Omega, Big-Theta (similar to slides from the 1st class).

  2. Heaps and priority queues: properties of heaps, building a heap, extracting an element from a heap. Representing heaps using arrays and using binary trees. All algorithms related to heaps that we discussed in class and that you used in the 1st assignment: Build-Max-Heap, Max-heapify, Max-Heap-Insert, Heap-Increase-Key, Heap-Extract-Max. Of course, you are also expected to know the similar algorithms for Min-Heaps. You have to know also the Big-Oh upper bound on the running time of all these algorithms. What are the 2 main differences between heaps and binary search trees? What is a priority queue, what operations are supported by priority queues? What are the main advantages of priority queues in comparison to other data structures that support dynamic sets (such as stacks and queues). You should be able to trace all these algorithms on simple examples. Practice on examples from Section 2.5 in the textbook.

  3. Fundamental algorithm design techniques: greedy algorithms, divide-and-conquer. Similarities and differences between these techniques. Characterize greedy algorithms in generic terms. Describe the main idea of the divide-and-conquer strategy, and how it is usually implemented. Typical asymptotic worst case running times of greedy algorithms and divide-and-concur algorithms. Read your lecture notes, the textbook, and a handout on proving correctness of greedy algorithms.

  4. Greedy algorithms: for which problems they can find optimal solutions? Structure of optimization problems that can be solved using greedy algorithms. What are the main steps in designing a greedy algorithm? Examples: the activities selection problem (scheduling the max number of compatible requests), scheduling all jobs on the minimal number of identical processors, scheduling jobs to minimize lateness, fractional knapsack, Dijkstra's algorithm and its implementation based on priority queues, the problem of optimal coin-change, greedy algorithms from the 1st assignment. Simple knapsack problem: greedy algorithms for solving it, whether they are optimal or not. Optimality of greedy algorithms that can find an optimal solution for any input: why should we prove optimality (correctness) by induction? How to prove a greedy algorithm is optimal by induction: typical structure of the proofs. What is a partial solution, when an optimal solution extends a partial solution, what is a promising solution. What is an exchange argument (an exchange lemma)? When and how it can be useful? Counterexamples, when a greedy method does not produce an optimal solution.

  5. Divide-and-conquer: for what kind of problems it can be useful? The merge-sort, the problem of multiplying big integers. Karatsuba's algorithm for fast multiplication of long integers. An efficient multiplication of polynomials using a fast Fourier transform (main concepts in this algorithm without technical details) and its running time. Other well-known examples of divide-and-conquer algorithms: binary search and merge-sort.

  6. The recurrence equations, the iterative substitution method (including proofs by induction). Writing a recurrence equation from the given algorithm in pseudocode and then solving this equation using iterative substitution.

General Exam Related Rules

In order to ensure the academic integrity of exams, students are asked to: All forms of academic dishonesty are considered serious offences within the University community and if you commit such an offence you run the risk of a range of sanctions including a failure in the course, a disciplinary notice on your academic record/transcript, a disciplinary suspension, withdrawal or expulsion from the University. It is important that you read and understand the Student Code of Conduct.
PLEASE NOTE:
* IT IS STRONGLY RECOMMENDED THAT YOU NOT BRING ANY VALUABLES TO THE EXAM
    THAT YOU DO NOT WISH TO LEAVE IN YOUR BAG.
* IF AN ELECTRONIC DEVICE IS FOUND ON YOUR PERSON DURING AN EXAM, IT WILL BE
    CONFISCATED AND RETURNED TO YOUR DEPARTMENT/SCHOOL.
*YOU WILL NOT BE PERMITTED TO BEGIN YOUR EXAM UNTIL YOU COMPLY WITH THE
    RULES.  NOTE: YOU MUST STOP WRITING YOUR EXAM WHEN THE EXAM IS COMPLETED.
* FAILURE TO COMPLY WITH THE RULES MAY RESULT IN BEING CHARGED WITH ACADEMIC MISCONDUCT


CPS815 announcements.