CSC263H5- Final Exam Guide - Comprehensive Notes for the exam ( 35 pages long!)
29 Mar 2018
School
Department
Course
Professor
Document Summary
Adt is fixed and you can have various data structures implemented. Example: stack is an adt (stores list of numbers, supports push(), pop(), is_empty()) Data structures that can be used to implement stack (ie. linked list) Amount of resource required by an algorithm, measured as a function of the input size. Number of steps executed by the program/algorithm. : running time of algorithm a with input x. When a is understood, we simply write t(x) The worst-case running time t(n) is defined as: is an input size n} (n) max{t(x) The running time is distributed between the best and worst. Average-case running time is the expectation of the running time which is distributed between 1 and n+1. tn. = random variable for the running time on inputs of length n. n+1. [t ] t=1 t p n = t r(t. , we need know the probability distribution of the inputs. (ie. how inputs are generated)
