CSC263H1 Lecture Notes - Lecture 1: Big O Notation, Linked List, Data Structure
Document Summary
Abstract data type (adt):= set of objects with set of operations on these objects: two components, object/data, operations, objects: integers; operations: add(x,y), multiply(x,y), etc, stack. Operations: push(s,v), pop(s), isempty(s: adt"s are important for speci cation; provide modularity and reuse since usage is independent of implementation. Data structure:= speci c implementation of an adt: a way to represent the objects and an algorithm for each operation. In general: adt describes what (data and operations, data structure describes how (storing data, performing operations) In this course we will encounter many adts and many data structures for these adts. Use careful analysis (of correctness and complexity) to compare possibilities. Complexity:= the amount of resources required by an algorithm, measure as a function of input size. running time, memory (space) Algorithm analysis (review) (cid:124) (cid:123)(cid:122) (cid:125: input size measured as Graph # vertices: important: measure must be roughly proportional to true bit-size (# of bits required to fully encode input).
