Algorithms and data structure

1. Algorithms and data structure 2. MCQs mainly, and a couple of questions 3. about 2 hours 4. the exam will be open on january 7. 5. it will be one time Algorithmic basics: pseudo-code conventions analysing algorithms using RAM worst case analysis best case analysis express the time complexity using asymptotic notations solving recurrences via recursion tree ALL sorting algorithms covered in this module. Stacks: LIFO S.top basic operations (O(1)) PUSH(S, x) POP(S) STACK-EMPTY(S) Queues: FIFO tail & Q.head 2 basic operations (O(1)) ENQUEUE(Q, x) DEQUEUE(Q) Linked list: head basic operations: LIST-SEARCH (L, k) O(n) LIST-INSERT(L, x) – front O(1) LIST-DELETE(L, x) O(1) for doubly linked list, O(n) for singly linked list Direct-addressing tables: Search, insert and delete take O(1) Problem: waste space Hash tables: hash functions: multiplication division hashing with chaining: dictionary operations: expected O(1) search: worst case O(n) delete: O(n) for single linked list hashing with open addressing: linear, quadratic: delete needs to be lazy operations: expected in O(1) assume no deletion worst case for search and insert is O(n) load factor: concept relations to time cost Binary search trees: properties operations: in order tree walk: Ө(n) insert, search, delete, predecessor, successor, minimum, maximum: O(h) O(n) for a skew tree Red-black trees (guarantee O(lgn)) red-black properties black height maximum (& minimum) # of internal nodes rotation: right rotation left rotation insertion: double red Huffman trees: priority queues: heap min-priority queue operations: INSERT: O(lgn): MINIMUM: O(1): EXTRACT-MIN: O(lgn): DECREASE-KEY: O(lgn): max-priority has the symmetric operations huffman codes: fixed length code variable length code prefix code binary tree as encoding tree huffman algorithm takes O(nlgn) Graphs and graph representations: graph basics: types terminologies relations with trees representations: adjacency list adjacency matrix weakness and strength of the two representations. data structure and alogrithm