Information about the CPS616 midterm exam

The midterm test will be on February 28, Friday, 4-6pm, in the VIC building, on the 3rd floor. Students can write this tests only in the rooms specified below.
Students with family names starting with letters from A to G will write this test in the room VIC305.
Students with family names starting with letters from H to O will write this test in the room VIC306.
Students with family names starting with letters from P to Z will write this test in the room VIC300.

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 and a pen. You have to write your midterm test using a black or blue ink pen only. 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 Labs, from the 1st Assignment and problems from quizzes. You can try to solve problems from the previous midterm test posted online as a PDF file (login to Blackboard to download) in a Course Documents folder. When you practice, watch how much time it takes you to answer questions from previous midterm tests.

Here are some highlights, but remember, everything talked about in class or included in labs is a possibility.

Introduction to algorithm analysis. 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, Quiz 2, Lab 1 and to the 1st assignment.) 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 a question from the 1st assignment).
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 studied in Lab 2): Build-Max-Heap, Max-heapify, Max-Heap-Insert, Heap-Increase-Key, Heap-Extract-Max, and of course, 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).
Fundamental algorithm design techniques: greedy algorithms, divide-and-conquer. Similarities and differences between these techniques. Read your lecture notes, the textbook, and a handout on proving correctness of greedy algorithms.
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), fractional knapsack, 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.
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 and its running time. Other examples of divide-and-conquer algorithms: binary search, the closest pair of points in the plane.
The recurrence equations, the iterative substitution method (including proofs by induction). The Master theorem. 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:

Place all cell phones/ personal audio equipment and other electronic devices in bags
Place all bags, and personal belongings in a designated area in the room. No personal belongings can be brought to the exam desk.
Place student ID on the upper right hand corner of the desk for verification
Have no pencil cases on desks, only writing materials
Have no food or drink during the exam unless medically required
Water in transparent bottles, without any labels attached, may be brought into the exam room. (No water will be supplied as was done in previous years).
Remove hats while writing the exam unless required by religious observance
Conduct the exam in silence
Be enrolled in the course to write the exam
Raise their hands to ask a question, use washroom, or request additional supplies
In the case of an emergency, leave all exam materials on the desk and follow the instructions of the invigilator
Maintain all academic integrity standards during an exam (see Academic Integrity for details)
Not leave the exam within the first 30 minutes, not enter the exam more than 30 minutes after it has begun or leave the exam within the last 15 minutes
Not have any materials on the desk other than those designated by the instructor.

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

CPS616 announcements.