Queens University
ELEC 379
Queen's University
Smith Engineering
Department of Electrical and Computer Engineering
ELEC 379 Algorithms with Engineering Applications
Fall 2023
SHORT PRACTICE Final Examination
(approximately ¹⁄₃ shorter than actual exam)
Student ID (please print clearly)
• To reflect actual exam conditions, try this practice
...[Show More]
Queen's University
Smith Engineering
Department of Electrical and Computer Engineering
ELEC 379 Algorithms with Engineering Applications
Fall 2023
SHORT PRACTICE Final Examination
(approximately ¹⁄₃ shorter than actual exam)
Student ID (please print clearly)
• To reflect actual exam conditions, try this practice exam with no aids.
• For this short exam, use a 2-hour limit (actual exam is 3 hours.)
• There are seven sections (questions) – same as actual exam.
• The pages of the actual examination must remain stapled together.
• At the actual exam, proctors are unable to respond to queries about
the interpretation of exam questions. Do your best to answer exam
questions as written.
1 /15
2 /12
3 /15
4 /13
5 /20
6 /10
7 /15
Total /100
This practice exam is copyrighted by Dr. N. Manjikian and intended for students in ELEC 379.
FOR STYLE OF QUESTIONS
AND FOR PRACTICE
The distribution of marks per question
on the longer actual exam is the same
as shown in this table.
ELEC 379 Fall 2023 – Short Practice Exam page 2 of 10
Question 1: Algorithmic Concepts and Algorithm Analysis (15 marks)
(a) An algorithm =
(b) Briefly indicate the relationship between algorithms and data structures.
(c) Provide a complete proof of correctness for the following loop-based code.
min = a[0]
for i = 1 to n-1 do
if (a[i] < min) then
min = a[i]
end if
end for
…………………………………
ELEC 379 Fall 2023 – Short Practice Exam page 3 of 10
Question 2: Order of Growth and Mathematical Recurrences (12 marks)
(a) Mathematically describe the meaning of “T(n) is W(f(n)).”
(b) Use the master method to solve the recurrence T(n) = 8T(n/2) + Q(1).
(c) Use the substitution method to solve the recurrence in part (c) above.
…………………………………
ELEC 379 Fall 2023 – Short Practice Exam page 4 of 10
Question 3: Algorithm Design Techniques (15 marks)
(a) Briefly describe the general manner of how divide-and-conquer is applied.
(b) Identify the technique that makes top-down dynamic programming efficient
and briefly describe the general manner in which it is implemented.
[Show Less]