CSEN 703 Analysis and Design of Algorithms


Midterm material...

Lectures 1 to 5 including their practice assignment. Midterm has 5 questions. Asymptotics (8/80), Analysis using Summations (12/80), Amortized Analysis (20/80), Randomized Analysis (20/80), Recurrence Analysis (20/80) Copy of midterm aid sheet is avilable here: https://drive.google.com/open?id=12olM_NTJQS9RD-lx5SrUQXMa2elojNb6

A1 tips...

Assignment 1.6 This is like the hashtable example in the lecture except that the growth here is a power of 3 (1,3,9,27,...). So, your answer has to be expressed in that. Assignment 1.7 It is ok to put a term including an n in the bank as the money saved. Assignment 1.8 Consider the regions as bins and the points as balls. You should start by thinking about the probability that two points fall in the same region . Assignment 1.9 If you believe that the random step has no influence on the overall asymptotic, justify that. For sure, the randomness causes different choices to be picked -- discuss that. Assignment 1.10e If the exponent has an n, the base can be a constant 2^n (2 power n), 2 is a constant - same is c^n.

A1 extended

to Saturday Oct 20th, 2018, 11:55PM.

A2 & A3 udpated!

with test cases.

A2 & A3 posted!

check materials section

Assignment 1 solution

Available here: https://drive.google.com/open?id=1qT47iq12hssGNl7gMp_oGTkC2HpJny5D

Latest Material

Course Staff

Teaching assistant

Course Meetings

Office Hours

  • On Tuesday 5th slot , for Amal Yassien
  • On Wednesday 3rd slot , for Esraa