• 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 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.