CSC2720 Final Exam Review PDF

CSC2720 Final Exam Review  Final Exam – Schedule and Policies Wed, Dec 11, 2024, 11:00am-1:00pm Urban Life Building Room 100 General Policies: - 30% of the total grade. - The exam is closed book. Laptops/cellphones/headphone...

CSC2720 Final Exam Review  Final Exam – Schedule and Policies Wed, Dec 11, 2024, 11:00am-1:00pm Urban Life Building Room 100 General Policies: - 30% of the total grade. - The exam is closed book. Laptops/cellphones/headphones etc. are not allowed during the exam. - You can bring one A4-size (copy paper size) handwritten double-sided note for the exam. PRINTED NOTES WILL NOT BE ALLOWED. - Please bring your Panther ID card (or your driver's license) for identity verification. When you submit the exam, please show your ID. Composite function: c.O(f(x)) Big O notation: O(f(x)) Example: def print10times(arr): for i in range(10): #runs 10 times © 10.O(N) ~ O(N) for num in arr: #O(n) print(num, end=' ') print() Composite function: c + O(f(x)) Big O notation: O(f(x)) Example: def fn(arr): 10 + O(N) ~ O(N) for i in range(10): # 10 times print(len(arr)) for num in arr: # n times print(num, end=' ') Composite function: g(x).O(f(x)) Big O notation: O(g(x).O(f(x))) def f(x): # O(n^2) res = 0 Example: for i in range(len(x)): for j in range(len(x)): G(x) = N res += (x[i]*x[j]) F(x) = N return res N.O(N) ~ O(N2) def composite_function(x): #O(n^3) for i in range(len(x)): #n operations print(f(x)) #O(n^2) composite_function([1,2,3])  def g(x): #O(n) Composite function: g(x) + O(f(x)) sum = 0 Big O notation: O(g(x) + O(f(x))) for num in x: sum += num print(sum) Example: def f(x): # O(n^2) N + O(N) ~ O(N+N) ~ O(N) res = 0 for i in range(len(x)): for j in range(len(x)): res += (x[i]*x[j]) print(res) def composite_function(x): #O(n^2) g(x) #O(n) f(x) #O(n^2) O(n+n^2) composite_function([1,2,3])  Practice questions: Given a python function, apply the rules for finding Big o notation for composite function.  Python List  An elegant built-in type in Python  Represents a collection of items  Python Lists are ordered, mutable  List items can be of different types Syntax: sample_list = [item1, item2, item3, …, itemN] Examples: list1 = [] # a list can be empty list2 = [1, 2, 3] # homogeneous list list3 = [1, 'a', True] # heterogeneous list list3 = False # lists are mutable  Python List Built-in methods to review: - Append() vs insert() - Remove() vs pop() - Sort() vs sorted() - index(), count() Things to know: -Properties of python list -Above methods - Time complexity and reasons Python List Big-O Efficiency of common Python List Operators and Methods Operation Efficiency index [] O(1) index assignment O(1) append, pop() O(1) pop(index) O(n) insert(index, item) O(n) contains(n), reverse O(n) Sort O(nlogn) Review the reasons for these time complexity too…  Python Dictionary Performance of Python Data Structures – Dictionary eview the reasons for these time complexity too… Low-level Arrays - Representation Python internally represents each Unicode character with 16 bits (i.e., 2 bytes) Therefore, a six-character string, such as 'SAMPLE', would be stored in 12 consecutive bytes of memory. A Python string embedded as an array of characters We will refer to each location within an array as a cell We will use an integer index to describe its location within the array A higher-level abstraction Low-level Arrays  Each cell of an array must use the same number of bytes  This requirement is what allows an arbitrary cell of the array to be accessed in constant time based on its index  If one knows the memory address at which an array starts, the number of bytes per element, and a desired index within the array, the appropriate memory address can be computed using the calculation start + cell_size * index  Low-level Arrays start + cell_size * index Example: start = 2146 cell_size = 2 Memory address of arr = 2146 + 2 * 3 = 2152 Memory address of arr = 2146 + 2 * 5 = 2156 n the start address and cell size, can you find out the memory address of nth ite  What is a reference? Review the id() method. Referential Arrays primes = [2, 3, 5, 7, 11, 13, 17, 19] tmp = primes[3:6] print([id(i) for i in primes]) print([id(i) for i in tmp]) Output: [4383023408, 4383023440, 4383023504, 4383023568, 4383023696, 4383023760, 4383023888, 4383023952] [4383023568, 4383023696, 4383023760] Output: (after running the script for second time) [4313325872, 4313325904, 4313325968, 4313326032, 4313326160, 4313326224, 4313326352, 4313326416] Why are the outputs [4313326032, 4313326160, 4313326224] different? Note: The id() function returns a unique id for the specified object. All objects in Python has its own unique id Referential Arrays primes = [2, 3, 5, 7, 11, 13, 17, 19] tmp = primes[3:6] tmp = 15 Referential Arrays – More examples counters = * 8 counters += 1 counters = counters Amortized analysis of dynamic arrays new_capacity = current_capacity * 2 Amortized analysis of dynamic arrays Growth Strategy: Doubling the array capacity The amortized running time of each append operation is O⁡(1); hence, the total running time of n append operations is O⁡(n) Growth Strategy: Geometric increase in capacity (E.g. 1.25, 1.75, 2.5 etc.) The amortized running time of each append operation is still O⁡(1); hence, the total running time of n append operations is O⁡(n) as well. Amortized analysis of dynamic arrays Beware of arithmetic progression new_capacity = current_capacitynew_capacity +2 = current_capacity + 3 Amortized analysis of dynamic arrays Beware of arithmetic progression Performing a series of n append operations on an initially empty dynamic array using a fixed increment with each resize takes Ω(n2) time.  2. Evaluating Postfix Expressions Postfix (Reverse Prefix (Polish) Infix Polish) The operator is The operator is The operator is placed before its placed between placed after its operands the operands operands Example 1 +AB A+B AB+ Example 2 +A*BC A+B*C ABC*+ Example 2 *+AB+CD (A + B) * (C + D) AB+CD+* Parentheses Observati Parentheses not required for Parentheses not on required! correct required! evaluation! 2. Evaluating Postfix Expressions Properties of a postfix expression: - The operator is placed after the operands - Thus, for any operator, the operands are already there on the left side of the operator. Infix: (A + B) * (C + D) Postfix: A B + C D + * Example: Example: (1 + 2) * ( 3 + 4) 12+34+* =3*7 =334+* = 21 =37* = 21 2. Evaluating Postfix Expressions  Infix expressions can be ambiguous, parentheses will be required to resolve the ambiguity.  Parentheses defines the precedence of the operators.  In contrast, postfix expressions are unambiguous. So, parentheses and precedence is not required to evaluate postfix expressions. 2. Evaluating Postfix Expressions Steps:  Create a stack  Read the expression from left to right  If an operand is encountered, push it onto the stack.  If an operator is encountered: o pop the required number of operands o Apply the operator o Push the result back to the stack  The result of the expression will be the last value in the stack 2. Evaluating Postfix Expressions Example: 1 2 + 3 4 + * Token read Action taken Stack status 1 stack.push(1) 2 stack.push(2) [1, 2] + op1 = stack.pop() op2 = stack.pop() stack.push(op1 + op2) 3 stack.push(3) [3, 3] 4 stack.push(4) [3, 3, 4] + stack.push(st.pop() + [3, 7] st.pop()) * stack.push(st.pop() * Example code # cont. def doMath(op, op1, op2): if op == "*": from utils import ArrayStack return op1 * op2 def postfixEval(postfixExpr): elif op == "/": stack = ArrayStack() return op1 / op2 tokens = postfixExpr.split() elif op == "+": return op1 + op2 for token in tokens: else: if token.isnumeric(): return op1 - op2 stack.push(int(token)) else: print(postfixEval('1 2 + 3 4 + *')) operand2 = stack.pop() operand1 = stack.pop() result = doMath(token,operand1,operand2) stack.push(result) return stack.pop() Exercise: Evaluate a prefix expression using stack. Prefix Infix Postfix Example 1 +A*BC A+B*C ABC*+ Example 2 *+AB+CD (A + B) * (C + D) AB+CD+* Stack and Queues Have not been included What is a Deque?  A queue-like data structure that supports insertion and deletion at both the front and the back of the queue. What is a Deque?  A queue-like data structure that supports insertion and deletion at both the front and the back of the queue. The Deque ADT Common Deque Operations:  add_rear(item)  add_front(item)  remove_rear()  remove_front()  front()  rear()  is_empty()  size() Implementation of these methods - Array based A Deque (dQ) as an adaptation of Python List (L) Realization with Deque method Python List dQ.add_rear(item) L.append(item) dQ.add_front() L.insert(0, item) dQ.remove_rear(item) L.pop() dQ.remove_first() L.pop(0) dQ.size() len(L) dQ.is_empty() len(L) == 0 front(), rear() L, L[-1] Deque – Array Based Implementation utils.py class ArrayDeque: def __init__(self): self.items = [] def is_empty(self): from utils import ArrayDeque return self.items == [] def add_rear(self, item): dq = ArrayDeque() self.items.append(item) dq.add_rear(1) def add_front(self, item): dq.add_front(2) self.items.insert(0, item) dq.add_rear(3) def remove_rear(self): dq.remove_front() return self.items.pop() print(dq.front()) def remove_front(self): print(dq.rear()) return self.items.pop(0) def size(self): return len(self.items) def front(self): return self.items def rear(self): return self.items[-1] Summary: - Deque has properties of both Stack and Queue Built-in support in Python - Python’s ‘collection’ module – deque - You can use this type both as a ‘stack’ and a ‘queue’ Please refer to: https://docs.python.org/3/library/collections.html#collec tions.deque Why Linked List?  Memory efficient – no need to allocated a fixed block of contiguous memory in advance  No overhead of - ‘Dynamic Array/List Resizing’  Efficient Insertions and Deletions O(1) – just need adjust the ‘next’ pointers  Can be used as underlying structure for other data structures such as stacks and queues. Review linked list implementation/methods: iCollege > Content > Coding Demo > linked_list_implementation.p - Practice implementing the methods - Study time complexity of different methods and underlying reason Doubly Linked Lists  In a doubly linked list, each node keeps an explicit reference to: - the node before it (prev) - the node after it (next)  Keeping track of ‘prev’ and ‘next’ improves the time complexity of different operations.  For example, deleting the last node of a singly linked list takes O(n).  Avoiding Special Cases  Operations at the boundary of a list is slightly different.  For example, addFirst() and addLast() method works differently compared to adding a node at any other valid index. new_node new_node head (k-1) th node Avoiding Special Cases – how header and trailer nodes help?  To avoid such special cases, we can add two special nodes: o a header node at the beginning of the list, and o a trailer node at the end of the list  These dummy nodes are called sentinels or guards.  Those nodes do not store elements of the primary sequence  The header serves as the ‘prev’ of the head node  The trailer servers as the ‘next’ of the tail node A doubly linked list with sentinels  current def delete(self, k): if k < 0 or k >= self.size: raise IndexError('Index is out of bounds') … … current = self.header.next successor for i in range(k): # Walk to k th node predecessor current = current.next predecessor = current.prev successor = current.next predecessor.next = successor … … successor.prev = predecessor self.size -= 1 predecessor successor return current.value Hash Tables Hash Tables One of the practical data structures for implementing a map The simplest representation: - Use a lookup table of length N - Store the value associated with key k at index k - Basic map operations (get/put etc.) can be implemented in O(1) Hash Tables  The novel concept for a hash table is the use of a hash function to map general keys to corresponding indices in a table.  Ideally, keys will be well distributed in the range from 0 to N−1 by a hash function  In practice there may be two or more distinct keys that get mapped to the same index  As a result, we will conceptualize the table as a bucket array  Hash Tables A bucket array of capacity 11 with items, using a simple hash function* *index/hash value of a key ~ key % N Hash Tables - Collision  If there are two or more keys with the same hash value, then two different items will be mapped to the same bucket (collision)  A hash function is "good" if it sufficiently minimize number of collisions  For practical reasons, we also would like a hash function to be fast and easy to compute.  It is common to view the evaluation of a hash function, h(k), as consisting of two portions: - A hash code - A compression function  Hash Functions maps a key k to an integer Maps hash code to a range of indices Two parts of a hash function: a hash code and a compression function. The advantage of separating the hash function into two such components is that the hash code portion of that computation is independent of a specific hash table size.  Hash Codes An arbitrary key (k)  The hash code need not to be in range [0, N-1]  It may even be negative! Hash Function An integer hash code Hash Codes – Treating the bit representation as the hash code Assumption: The desired hash code length is H bits. For any data type X that can be represented using the desired hash code length (H)  The previous conversion scheme is not immediately applicable for such types.  For example, when H = 32 and we want to get the hash code of a 64-bit floating point number.  One possibility is to use only the high-order 32 bits (or the low- order 32 bits)  Hash Codes – Treating the bit representation as the hash code Example: hash code for 64-bit floating point number 10.23 Key 01000000 00100100 01110101 11000010 10001111 64-bit binary 01011100 00101000 11110110 or 10001111 01011100 00101000 11110110 01000000 00100100 01110101 11000010 1076131266or 2405181686 Integer / hash code Hash Codes – Treating the bit representation as the hash code Disadvantages of this approach: - Ignores half of the information present in the original key - If many of the keys in our map only differ in these bits, the hash codes will collide - For example, if we consider only the low-order bits, the following two 64-bit representation are going to have same hash code. - However, their high-order bits are significantly different. - Thus, even if the keys are significantly different, their hash codes are is going to collide, which is not desired. 01000000 00100100 01110101 11000010 10001111 01011100 00101000 11110110 01111111 01111111 01110101 11111111 10001111 01011100 00101000 11110110 Hash Codes – Treating the bit representation as the hash code A better approach: - Combine the high-order and low-order portions of a 64-bit key to form a 32-bit hash code - Thus, take all the original bits into consideration - Ideas: - Add the high and low order bits (ignoring overflow) 0 xor 0 = 0 - Take the exclusive-or/xor of the high and low order bits 0 xor 1 = 1 1 xor 0 = 1 1 xor 1 = 0  Hash Codes – Treating the bit representation as the hash code A better approach - XOR the high and low order bits high-order low-order 01000000 00100100 01110101 11000010 10001111 01011100 00101000 11110110 01000000 00100100 01110101 11000010 10001111 01011100 00101000 11110110 (xor) Example 1 __________________________________ 11001111 01111000 01011101 00110100 (hash code = 3480771892) high-order low-order 01111111 01111111 01110101 11111111 10001111 01011100 00101000 11110110 01111111 01111111 01110101 11111111 Example 2 10001111 01011100 00101000 11110110 (high-order (xor) bits are different) _________________________________ 11110000 00100011 01011101 00001001 (hash code = 2014424708) Hash Codes – Treating the bit representation as the hash code A better approach - XOR the high and low order bits Summary: Considering all the original bits helps to minimize collision. 01000000 00100100 01110101 11000010 10001111 01011100 00101000 11110110 hash code = 3480771892 01111111 01111111 01110101 11111111 10001111 01011100 00101000 11110110 hash code = 2014424708  Hash Codes of Variable-length objects  The summation and exclusive-or hash codes are not good choices for character strings or other variable-length objects when the order of the elements is significant.  For example, consider a 16-bit hash code for a character string s that sums the Unicode values of the characters in s.  This hash code unfortunately produces lots of unwanted collisions for common groups of strings.  Examples, - hash codes of temp10 / temp01 will collide - hash codes of stop / tops / pots / spot will collide This is because the summation/xor approach doesn’t take the relative position into account! Hash Codes of Variable-length objects Solution: Consider elements at different positions with different weights! The variable length object: (x0 , x1 ,…, xn-2 ,xn-1 ) Hash code: (x0a0 + x1a1 +…+ xn-2an-2 + xn-1an-1 ) % m where, a is a non-zero constant & a != 1 m is a large prime number to avoid overflow! Polynomial Hash Code! Hash Codes of Variable-length objects Polynomial Hash Code - Example Key = “hello” a = 31 m = 109+9 Hash code = (h×310 + e× 311 +l× 312 +l× 313 +o× 314) mod (109+9) = 14222002 (x0a0 + x1a1 +…+ xn-2an-2 + xn-1an-1 ) % Practice similar questions! m  Hash Codes of Variable-length objects A sample python program to compute polynomial hash code def compute_hash(str): a = 31 m = int(1e9 + 9) hash_value = 0 pow = 1 # initial power a^0 or 1 for c in str: hash_value += ((ord(c) - ord('a') + 1) * pow) % m # e.g. a -> 1, b -> 2 etc. pow = (pow * a) % m return hash_value print(compute_hash('hello')) print(compute_hash('stop')) print(compute_hash('spot')) Hash code: (x0a0 + x1a1 +…+ xn-2an-2 + xn- an-1 ) % m Hash code in Python Hashing Instances of user-defined classes  A function to compute hash codes can be implemented as the __hash__ method in a class.  The returned hash code should reflect the immutable attributes of an instance Hash code in Python class Car: def __init__(self, mk, md, yr, owners = []): self.make = mk self.model = md self.year = yr self.owners = owners def __hash__(self): # consider only the immutable attributes while # computing the hash code of an object return hash((self.make, self.model, self.year)) car1 = Car('Honda', 'Accord', 2019) print(hash(car1))  Sample question: Given a UML class diagram, can you write the __hash__ method based on different combinations of the data attributes? - Write the __hash__ method based on pantherid?Student - Write the __hash__ method based on pantherid and email? pantherid Email - What are the expected outputs? Name address Limitation of division method as a compression function? Index = (hash_code%N) A More Sophisticated Compression Function The Multiply-Add-and-Divide (MAD) Method - helps eliminate repeated patterns in a set of integer keys Hash code (i) hash index (j, 0 N - 0 = end: return 0 elif start == end-1: return S[start] else: mid = (start + end) // 2 return binary_sum(S, start, mid) + binary_sum(S, mid, end) arr = [1, 2, 3, 4] print(binary_sum(arr,0, len(arr))) Binary Recursion Recursion trace for the execution of binary_sum(0, 8).  How recursion works def count(n): if n == 0: >> 3 print('Go!') >> 2 else: count(0) >> 1 print(n) >> Go! count(n - 1) count(1) count(3) count(2) count(3) Stack Output  How recursion works def count(n): if n == 0: >> 3 print('Go!') >> 2 else: count(0) >> 1 print(n) >> Go! count(n - 1) count(1) >> 1 print(n) count(2) >> 2 count(3) >> 3 count(3) Stack Output Practice question: Given a recursive method. Can you show the Stack status for a sample call? Binary Search recursive implementation Terminology Complete binary trees A complete binary tree is a binary tree in which every level, except the last, is completely filled, and all nodes are as far left as possible. A binary tree T of height h is complete if All nodes at level h – 1 and above have two children each, and When a node at level h has children, all nodes to its left at the same level have two children each, and When a node at level h has one child, it is a left child Figure 11-8 A complete binary tree © 2011 Pearson Addison-Wesley. All rights reserved 11 A-82 Properties The maximum number of nodes at level ‘L’ of a binary tree is 2L. © 2011 Pearson Addison-Wesley. All rights reserved 11 A-83 Properties Level: 0 Max # of nodes: 20 = 1 Level: 1 Max # of nodes: 21 = 2 Level: 2 Max # of nodes: 22 = 4 © 2011 Pearson Addison-Wesley. All rights 11 A-84 reserved Properties Maximum number of nodes in a binary tree of height ‘h’ is 2h+1−1. © 2011 Pearson Addison-Wesley. All rights reserved 11 A-85 Examples Maximum number of nodes in a binary tree of height ‘h’ is 2h+1−1 Height = 0 Max # of nodes = 1 Height = 1 Height = 3 Max # of nodes = 3 Max # of nodes = 7 © 2011 Pearson Addison-Wesley. All rights reserved 11 A-86 Examples © 2011 Pearson Addison-Wesley. All rights reserved 11 A-87 Terminology Balanced binary trees A binary tree is balanced if the height of any node’s right subtree differs from the height of the node’s left subtree by no more than 1 Full binary trees are complete Complete binary trees are balanced © 2011 Pearson Addison-Wesley. All rights reserved 11 A-88 Examples © 2011 Pearson Addison-Wesley. All rights 11 A-89 reserved. Binary Tree – Array based Implementation a - Binary tree is stored in an array - Each element of the array represents a node - For any node i, b c - Left child is at index 2*i+1 - Right child is at index 2*i+2 - It’s parent is at index (i-1)/2 d e f g A binary tree arr a b c d e f g index 0 1 2 3 4 5 6 nary Tree – Array based Implementation ArrayBinaryTree - arr : list + __init__(size : int) + set_root(value : Object) + set_left(i : int, value : Object) + set_right(i : int, value : Object) + get_left(i : int) + get_right(i : int) + get_parent(i : int) UML Class Diagram + print_tree() Pros and Cons of Array-based implementation + memory efficient and simple implementation + uses a contiguous block of memory - Works well only for complete binary trees - insertion, deletion, and traversal is less efficient Binary Search Tree - Deletion  A node to be deleted may have  0 children (the node is a leaf)  1 child  2 children Delete a leaf We need to delete 8 1 2 1 3 4 1 2 0 8 3 5 2 1 6 Delete a leaf We need to delete 8 8 Coding Demo > Heaps.py Carefully review the methods! Priority Queue in Python Module: heapq This module provides an implementation of the heap queue / priority queue in Python. By default – a min heap eapq built-in methods / common operations: eapq.heappush(heap, item): Adds an item to the heap. eapq.heappop(heap): Removes and returns the smallest item from the heap. eapq.heappushpop(heap, item): Pushes a new item onto the heap and then p d returns the smallest item from the heap. eapq.heapify(x): Converts a list into a heap (in-place). argest: Return a list with the n largest elements mallest: Return a list with the n largest elements import heapq arr = [50, 10, 30, 40, 20] # Convert the array into a heap in-place heapq.heapify(arr) print("Heapified array:", arr) # Push new elements onto the heap heapq.heappush(arr, 35) print("Heap after pushing 35:", arr) # Get the n smallest elements n_smallest = heapq.nsmallest(3, arr # Pop the smallest element print(n_smallest) smallest = heapq.heappop(arr) print("Heap after popping:", arr) # Get the n largest elements n_largest = heapq.nlargest(2, arr) print(n_largest) import heapq Find k-th smallest element def k_smallest(array, k): min_heap = [] for num in array: heapq.heappush(min_heap, num) # Remove the smallest elements k-1 times for _ in range(k - 1): heapq.heappop(min_heap) # Return the k-th smallest element return min_heap # Example usage array = [3, 1, 5, 12, 2] k = 4 print(k_smallest(array, k)) K-Way Merge O(kN) solution – exercise List 1: [1, 4, 5] List 1: [1, 3, 5] List 1: [2, 6] List 1: [0, 7, 8] result: [?] *find the smallest number from the first column *remove it from the list and add to the result K-Way Merge: A better solution using Heap Previous Idea: Step1: Iterate over the input lists and find the smallest item. >> O(k) … … Idea: If we use a heap, step 1 can be performed in O(logk) Thus, using a heap, K-Way Merge can be done in O(Nlogk) iCollege > Content > Coding Demo > kWayMerge.py  Adjacency matrix  A square Boolean* matrix  Elements on the main diagonal are zeros  Other elements indicate if pairs of nodes are adjacent  Often denoted as  *In an unweighted graph  Very important: understand the Complexity reasons for these time complexities.  Time  Space  Add a node  Remove a node  Add an edge  Remove an edge  Are two nodes adjacent?  Find neighbors of a node Adjacency list  A collection (an array / a hash map) of (linked) lists / arrays  Each list  corresponds to a node  stores a list of nodes that are adjacent to the node  Adjacency list: example 0 1 4 2 0 1 1 0 2 2 0 1 3 3 2 4 5 4 5 0 5 4 Complexity  Time  Space  Add a node  Remove a node Very important: understand the  Add an edge reasons for these time complexities.  Remove an edge  Are two nodes adjacent?  Find neighbors of a node  Time complexity: summary Adjacency Adjacency list matrix Store a whole graph Add a node Remove a node Add an edge Remove an edge Are two nodes adjacent? Find neighbors of a node Slow to Slow to remove add/remove nodes and edges Comments nodes as the because it must find Review Graph Traversal implementations: 1. iCollege > Content > Coding Demo > BFS.py 2. iCollege > Content > Coding Demo > DFS_recursive.py 3. iCollege > Content > Coding Demo > DFS_iterative.py  Topological sort  Topological in computer science means pertaining the network topology, in our case, the order of nodes  Takes as an input a directed acyclic graph only  Returns a list of nodes  Each node in the output appears before all the nodes it points to  Multiple sortings are possible Topological sort – Simple Examples 0 0 res1: 0, 1, 2 1 2 res2: 1, 0, 2 1 res1: 0, 1 0 3 res1: 0, 1, 2, 3, 4 2 res2: 0, 1, 2, 4, 3 res3: 1, 0, 2, 3, 4 1 4 res4: 1, 0, 2, 4, 3 Note: Each node in the output appears before all the nodes it points Topological sort – Simple Examples 0 1 0 1 2 res1: 0, 1, 2 res1: 0, 1 1 0 2 res2: 1, 0, 2 res1: 0, 1, 2, 3, 4 0 1 2 3 4 res2: 0, 1, 2, 4, 3 0 1 2 4 3 … Topological sort - examples  Several sorting are 0 1 possible: 3  5,2,4,0,1,3  2,5,4,0,1,3 2 4 5  5,2,4,0,3,1  2,5,4,0,3,1 ... many other ways  Topological Sorting - Stack based Implementation iCollege > Content > Coding Demo > TopologicalSortingUsingStack.py Dijkstra’s algorithm iCollege > Content > Coding Demo > Dijkstra.py - Study the working principles of the algorithm - Given a graph and a start node, can you find the shortest path to all other nodes? - Given a graph and a start node, can you find the minimum cost to reach all other nodes? Trie Implementation - Python implementation, delete method is exclude - Only study the idea, insert method, and find method Sorting Algorithms 1. Merge Sort – Idea, Implementation, Time & Space Complexity 2. Quick Sort - Idea, Implementation, Time & Space Complexity Note: Two more sorting algorithms will be added after the thanksgiving break.