Information about the CPS616 midterm exam
The midterm test will be on
February 28, Friday, 46pm,
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 handwritten 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 topright corner of your page with handwritten 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 BigOh
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 whileloop,
estimate the number of iterations before termination.
Simple properties of asymptotic notation BigOh, BigOmega, BigTheta
(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): BuildMaxHeap,
Maxheapify, MaxHeapInsert, HeapIncreaseKey, HeapExtractMax,
and of course, the similar algorithms for MinHeaps.
You have to know also the BigOh 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,
divideandconquer. 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 coinchange, 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.

Divideandconquer: for what kind of problems it can be useful?
The mergesort, the problem of multiplying big integers.
Karatsuba's algorithm for fast multiplication of long integers and its
running time. Other examples of divideandconquer 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.