Information about the CPS815 midterm exam
The midterm test will be on
October 20, 2017, Friday, 3-5pm,
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.
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).
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.
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.
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,
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.
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.
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.
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
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
Remove hats while writing the exam unless required by religious
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
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
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.
* 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