Information about the CPS815/CP8201 midterm exam
The midterm test will be on
Friday, February 16, 2024, 10am-11:40am, 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 TMU 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(Min)-Heap,
Max(Min)-heapify, Max(Min)-Heap-Insert, Heap-Increase-Key, Heap-Extract-Max(Min).
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.
For what problems they can find an optimal solution?
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.
-
How to show that a greedy algorithm is not correct for some input?
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 (textbook, Section 4.2),
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.
-
Divide-and-conquer: for what kind of problems it can be useful?
An efficient multiplication of polynomials using a Fast Fourier Transform and
its running time: the main algorithmic ideas only, without mathematical details.
Other well-known examples of divide-and-conquer algorithms mentioned in class.
-
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:
-
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
CPS815 announcements.