Difference between revisions of "Data Structures and Algorithms for Engineers Lecture Schedule"
From David Vernon's Wiki
| Line 11: | Line 11: | ||
| Wed. 18 Jan. | | Wed. 18 Jan. | ||
| 1 | | 1 | ||
| − | | | + | | Introduction: The Software Development Life Cycle |
| − | | | + | | Motivation. Goals of the course. Topic areas. Preview of course material. Overview of labs, assignments, and exercises. Levels of abstraction in information processing systems. The software development life cycle. Static, dynamic, physical structures. Architectural design: components of design, internal vs external aspects. Top down design and structured design. Yourdon Structured Analysis: data flow diagrams (DFD), data dictionaries, process specification, entity relationship (ER) diagrams, state transition diagrams. Software development tools for assignments. |
| | | | ||
| | | | ||
| Line 18: | Line 18: | ||
| Mon. 23 Jan. | | Mon. 23 Jan. | ||
| 2 | | 2 | ||
| − | | | + | | Representation of Algorithms |
| − | | | + | | Definition of an algorithm. Modelling software. Representation, communication, and analysis of algorithms. Relational modelling. State modelling. Pseudo code. Flow charts. Finite state machines. UML. Predicate logic. Analysis. |
| | | | ||
| | | | ||
| Line 25: | Line 25: | ||
| Wed. 25 Jan. | | Wed. 25 Jan. | ||
| 3 | | 3 | ||
| − | | | + | | Algorithmic Complexity |
| − | | | + | | Complexity analysis. Performance of algorithms, time and space tradeoff, worst case and average case performance. Big O notation. Recurrence relationships. Analysis of complexity of iterative and recursive algorithms. Recursive vs. iterative algorithms: runtime memory implications. Complexity theory: tractable vs intractable algorithmic complexity. Example intractable problems: travelling salesman problem, Hamiltonian circuit, 3-colour problem, SAT, cliques. Determinism and non-determinism. P, NP, and NP-Complete classes of algorithm. |
| | | | ||
| | | | ||
| Line 32: | Line 32: | ||
| Mon. 30 Jan. | | Mon. 30 Jan. | ||
| 4 | | 4 | ||
| − | | | + | | Searching and Sorting Algorithms |
| − | | | + | | Linear and binary search (iterative and recursive). In-place sorts: bubblesort (efficient and inefficient), selection sort, insertion sort. Not-in-place sorts: Quicksort, merge sort. Complexity analysis |
| + | Characteristics of a good sort. Speed, consistency, keys, memory usage, length & code complexity, stability. Other sorts ordered by complexity. | ||
| | | | ||
| | | | ||
| Line 39: | Line 40: | ||
| Mon. 6 Feb. | | Mon. 6 Feb. | ||
| 5 | | 5 | ||
| − | | | + | | Abstract Data Types (ADT) |
| − | | | + | | Vector example exercise. History of abstraction. Abstract Data Types (ADT). Information hiding. Types and typing. Encapsulation. Efficiency. Design practices. |
| | | | ||
| | | | ||
| Line 46: | Line 47: | ||
| Wed. 8 Feb. | | Wed. 8 Feb. | ||
| 6 | | 6 | ||
| − | | | + | | Containers, Dictionaries, and Lists |
| − | | | + | | Basic operations. Implementation with arrays and linked lists. Singly linked lists. Doubly linked lists. Performance considerations. |
| | | | ||
| | | | ||
| Line 53: | Line 54: | ||
| Mon. 13 Feb. | | Mon. 13 Feb. | ||
| 7 | | 7 | ||
| − | | | + | | Stacks |
| − | | | + | | Stack (LIFO): push, pop, peek, size, numItems operations. Array implementation in pseudo-code (directly and array of pointers to data). Stack applications, including evaluation of infix, prefix, and postfix expressions. |
| | | | ||
| | | | ||
| Line 60: | Line 61: | ||
| Wed. 15 Feb. | | Wed. 15 Feb. | ||
| 8 | | 8 | ||
| − | | | + | | Queues |
| − | | | + | | Queue (FIFO): enqueue, dequeue, peek, size, numItems operations. Array implementation in pseudo-code (directly and array of pointers to data). Linked list implementation. Circular queues. Performance considerations. Deque. |
| | | | ||
| | | | ||
| Line 67: | Line 68: | ||
| Mon. 20 Feb. | | Mon. 20 Feb. | ||
| 9 | | 9 | ||
| − | | | + | | Trees I |
| − | | | + | | Concepts and terminology: level, height, external and internal nodes, skinny, fat, complete, left-complete, perfect, multi-way, d-ary. Types of tree: binary, binary search, B-tree, 2-3 tree, AVL, Red-Black |
| + | Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder. Fixed-length codes, variable length codes, optimal code trees, Huffman's algorithm and implementation | ||
| | | | ||
| | | | ||
| Line 74: | Line 76: | ||
| Wed. 22 Feb. | | Wed. 22 Feb. | ||
| 10 | | 10 | ||
| − | | | + | | Trees II |
| − | | | + | | Height-balanced trees: AVL Trees, RR, RL, LR, LL rotations. Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring. Non-search trees: parse trees, array implementation, linked list implementation. Forests |
| | | | ||
| | | | ||
| Line 81: | Line 83: | ||
| Mon. 27 Feb. | | Mon. 27 Feb. | ||
| 11 | | 11 | ||
| − | | | + | | Heaps I |
| − | | | + | | Heap basics. Types of heap: min heaps and max heap. Heap characteristics. Heap operations: delete max/min, down heap, up heap, merge, construct, heapify; complexity of operations. |
| | | | ||
| | | | ||
| Line 88: | Line 90: | ||
| Wed. 1 Mar. | | Wed. 1 Mar. | ||
| 12 | | 12 | ||
| − | | | + | | Heaps II |
| − | | | + | | Priority queues. Operating systems heaps. Implementation of heap. Heap sort. d-ary heaps. Leftist heaps. |
| | | | ||
| | | | ||
| Line 95: | Line 97: | ||
| Mon. 6 Mar. | | Mon. 6 Mar. | ||
| 13 | | 13 | ||
| − | | | + | | Graphs I |
| − | | | + | | Types of graphs: directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, non-simple, implicit, explicit, embedded, topological. Adjacency matrix representation. Adjacency list representation. Topological sort. Euler's theorem. Graph traversal: breadth-first and depth-first, uses of. Depth-first search and maze traversal. |
| | | | ||
| | | | ||
| Line 102: | Line 104: | ||
| Wed. 8 Mar. | | Wed. 8 Mar. | ||
| 14 | | 14 | ||
| − | | | + | | Graphs II |
| − | | | + | | Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm. Dijkstra's shortest path algorithm. Floyd-Warshall's all-pairs algorithm. Graphs problems: routes, Hamilton paths, network flows, covering problems, museum guard problem. Fleury's Euler circuit algorithm. |
| | | | ||
| | | | ||
| Line 109: | Line 111: | ||
| Mon. 13 Mar. | | Mon. 13 Mar. | ||
| 15 | | 15 | ||
| − | | | + | | Complex Networks I |
| − | | | + | | Complex systems and large networks. Random networks. Degree distribution. Clustering. Small world phenomena. |
| | | | ||
| | | | ||
| Line 116: | Line 118: | ||
| Wed. 15 Mar. | | Wed. 15 Mar. | ||
| 16 | | 16 | ||
| − | | | + | | Complex Networks II |
| − | | | + | | Scale free networks. Community detection. Network evolution. |
| | | | ||
| | | | ||
| Line 123: | Line 125: | ||
| Mon. 20 Mar. | | Mon. 20 Mar. | ||
| 17 | | 17 | ||
| − | | | + | | Hashing I |
| − | | | + | | Using keys to address data |
| + | Mappings: injection, surjection, bijection | ||
| + | Map ADT | ||
| + | Hash functions | ||
| + | Hash tables: current value tables, direct access tables. Managing collisions: chaining, overflow areas, re-hashing, linear probing, quadratic probing | ||
| | | | ||
| | | | ||
| Line 130: | Line 136: | ||
| Wed. 22 Mar. | | Wed. 22 Mar. | ||
| 18 | | 18 | ||
| − | | | + | | Hashing II |
| − | | | + | | Evaluating hash functions: prime division, mid-square, folding, load factor. Example application: dictionaries. Generating hash functions and using hash structures. |
| | | | ||
| | | | ||
| Line 137: | Line 143: | ||
| Mon. 27 Mar. | | Mon. 27 Mar. | ||
| 19 | | 19 | ||
| − | | | + | | Algorithmic Strategies |
| − | | | + | | Classes of algorithms. Brute force. Divide and conquer. Branch and bound. Dynamic programming. Greedy algorithms. Heuristics and heuristic algorithms. Probabilistic algorithms. |
| | | | ||
| | | | ||
| Line 144: | Line 150: | ||
| Wed. 29 Mar. | | Wed. 29 Mar. | ||
| 20 | | 20 | ||
| − | | | + | | Analysis of Correctness |
| − | | | + | | Types of software defects. Code module design. Syntactic, semantic, logical defects. (Semi-)formal verification: partial vs. total correctness. Invariant assertion method. Simple proof strategies: by contradiction, counterexample, induction. Dynamic testing: unit tests, test harness, stubs, drivers, integration testing, regression testing. Static tests: reviews, walkthroughs, inspections, reviewing algorithms and software. |
| + | Pair programming. Verification and validation strategies. | ||
| | | | ||
| | | | ||
| Line 151: | Line 158: | ||
| Mon. 3 Apr. | | Mon. 3 Apr. | ||
| 21 | | 21 | ||
| − | | | + | | Databases |
| − | | | + | | Relational databases, hierarchical databases, NoSQL databases. Relational databases: entity relationship modelling, relational algebra, SQL. |
| | | | ||
| | | | ||
| Line 158: | Line 165: | ||
| Wed. 5 Apr. | | Wed. 5 Apr. | ||
| 22 | | 22 | ||
| − | | | + | | Databases II |
| − | | | + | | Normalization. Compression strategies, dictionary algorithm, LZ algorithm. File structure strategies. |
| | | | ||
| | | | ||
| Line 165: | Line 172: | ||
| Mon. 17 Apr. | | Mon. 17 Apr. | ||
| 23 | | 23 | ||
| − | | | + | | Programming Paradigms I |
| − | | | + | | Imperative programming. Object-oriented programming. Logic programming. Functional programming. |
| | | | ||
| | | | ||
| Line 172: | Line 179: | ||
| Wed. 19 Apr. | | Wed. 19 Apr. | ||
| 24 | | 24 | ||
| − | | | + | | Programming Paradigms II |
| − | | | + | | OO programming; classes; type, operational and functional polymorphism; inheritance, attributes, methods, instantiations, abstract classes, object-oriented languages. |
| | | | ||
| | | | ||
| Line 179: | Line 186: | ||
| Mon. 24 Apr. | | Mon. 24 Apr. | ||
| 25 | | 25 | ||
| − | | | + | | Programming Paradigms III |
| − | | | + | | OO design methodology: UML class diagram, composite-structure diagram, architecture diagram, package diagram, object diagram, component diagram, deployment diagram, activity diagram, sequence diagram, communication diagram, interaction diagram, timing diagram, use case diagram, state machine diagram. OO design principles: open/close principle, design by contract principle, dependency inversion principle, other design principles, documentation |
| | | | ||
| | | | ||
| Line 186: | Line 193: | ||
| Wed. 26 Apr. | | Wed. 26 Apr. | ||
| 26 | | 26 | ||
| − | | | + | | Automata Theory |
| − | | | + | | Regular Languages. Finite Automata. Nondeterminism. Regular Expressions. Nonregular Languages. Context-free Languages. Context-free Grammars. Pushdown Automata. Deterministic Context-Free Languages. |
| | | | ||
| | | | ||
| Line 193: | Line 200: | ||
| Wed. 3 May | | Wed. 3 May | ||
| 27 | | 27 | ||
| − | | | + | | Computability Theory |
| − | | | + | | The Church-Turing Thesis. Turing Machines. Variants of Turing Machines. The Definition of Algorithm. Decidability. Decidable Languages. Undecidability. Reducibility |
| | | | ||
| | | | ||
Revision as of 04:48, 27 December 2016
| Date | Lecture | Topic | Material covered | Pre-class reading | Assignments |
|---|---|---|---|---|---|
| Wed. 18 Jan. | 1 | Introduction: The Software Development Life Cycle | Motivation. Goals of the course. Topic areas. Preview of course material. Overview of labs, assignments, and exercises. Levels of abstraction in information processing systems. The software development life cycle. Static, dynamic, physical structures. Architectural design: components of design, internal vs external aspects. Top down design and structured design. Yourdon Structured Analysis: data flow diagrams (DFD), data dictionaries, process specification, entity relationship (ER) diagrams, state transition diagrams. Software development tools for assignments. | ||
| Mon. 23 Jan. | 2 | Representation of Algorithms | Definition of an algorithm. Modelling software. Representation, communication, and analysis of algorithms. Relational modelling. State modelling. Pseudo code. Flow charts. Finite state machines. UML. Predicate logic. Analysis. | ||
| Wed. 25 Jan. | 3 | Algorithmic Complexity | Complexity analysis. Performance of algorithms, time and space tradeoff, worst case and average case performance. Big O notation. Recurrence relationships. Analysis of complexity of iterative and recursive algorithms. Recursive vs. iterative algorithms: runtime memory implications. Complexity theory: tractable vs intractable algorithmic complexity. Example intractable problems: travelling salesman problem, Hamiltonian circuit, 3-colour problem, SAT, cliques. Determinism and non-determinism. P, NP, and NP-Complete classes of algorithm. | ||
| Mon. 30 Jan. | 4 | Searching and Sorting Algorithms | Linear and binary search (iterative and recursive). In-place sorts: bubblesort (efficient and inefficient), selection sort, insertion sort. Not-in-place sorts: Quicksort, merge sort. Complexity analysis
Characteristics of a good sort. Speed, consistency, keys, memory usage, length & code complexity, stability. Other sorts ordered by complexity. |
||
| Mon. 6 Feb. | 5 | Abstract Data Types (ADT) | Vector example exercise. History of abstraction. Abstract Data Types (ADT). Information hiding. Types and typing. Encapsulation. Efficiency. Design practices. | ||
| Wed. 8 Feb. | 6 | Containers, Dictionaries, and Lists | Basic operations. Implementation with arrays and linked lists. Singly linked lists. Doubly linked lists. Performance considerations. | ||
| Mon. 13 Feb. | 7 | Stacks | Stack (LIFO): push, pop, peek, size, numItems operations. Array implementation in pseudo-code (directly and array of pointers to data). Stack applications, including evaluation of infix, prefix, and postfix expressions. | ||
| Wed. 15 Feb. | 8 | Queues | Queue (FIFO): enqueue, dequeue, peek, size, numItems operations. Array implementation in pseudo-code (directly and array of pointers to data). Linked list implementation. Circular queues. Performance considerations. Deque. | ||
| Mon. 20 Feb. | 9 | Trees I | Concepts and terminology: level, height, external and internal nodes, skinny, fat, complete, left-complete, perfect, multi-way, d-ary. Types of tree: binary, binary search, B-tree, 2-3 tree, AVL, Red-Black
Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder. Fixed-length codes, variable length codes, optimal code trees, Huffman's algorithm and implementation |
||
| Wed. 22 Feb. | 10 | Trees II | Height-balanced trees: AVL Trees, RR, RL, LR, LL rotations. Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring. Non-search trees: parse trees, array implementation, linked list implementation. Forests | ||
| Mon. 27 Feb. | 11 | Heaps I | Heap basics. Types of heap: min heaps and max heap. Heap characteristics. Heap operations: delete max/min, down heap, up heap, merge, construct, heapify; complexity of operations. | ||
| Wed. 1 Mar. | 12 | Heaps II | Priority queues. Operating systems heaps. Implementation of heap. Heap sort. d-ary heaps. Leftist heaps. | ||
| Mon. 6 Mar. | 13 | Graphs I | Types of graphs: directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, non-simple, implicit, explicit, embedded, topological. Adjacency matrix representation. Adjacency list representation. Topological sort. Euler's theorem. Graph traversal: breadth-first and depth-first, uses of. Depth-first search and maze traversal. | ||
| Wed. 8 Mar. | 14 | Graphs II | Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm. Dijkstra's shortest path algorithm. Floyd-Warshall's all-pairs algorithm. Graphs problems: routes, Hamilton paths, network flows, covering problems, museum guard problem. Fleury's Euler circuit algorithm. | ||
| Mon. 13 Mar. | 15 | Complex Networks I | Complex systems and large networks. Random networks. Degree distribution. Clustering. Small world phenomena. | ||
| Wed. 15 Mar. | 16 | Complex Networks II | Scale free networks. Community detection. Network evolution. | ||
| Mon. 20 Mar. | 17 | Hashing I | Using keys to address data
Mappings: injection, surjection, bijection Map ADT Hash functions Hash tables: current value tables, direct access tables. Managing collisions: chaining, overflow areas, re-hashing, linear probing, quadratic probing |
||
| Wed. 22 Mar. | 18 | Hashing II | Evaluating hash functions: prime division, mid-square, folding, load factor. Example application: dictionaries. Generating hash functions and using hash structures. | ||
| Mon. 27 Mar. | 19 | Algorithmic Strategies | Classes of algorithms. Brute force. Divide and conquer. Branch and bound. Dynamic programming. Greedy algorithms. Heuristics and heuristic algorithms. Probabilistic algorithms. | ||
| Wed. 29 Mar. | 20 | Analysis of Correctness | Types of software defects. Code module design. Syntactic, semantic, logical defects. (Semi-)formal verification: partial vs. total correctness. Invariant assertion method. Simple proof strategies: by contradiction, counterexample, induction. Dynamic testing: unit tests, test harness, stubs, drivers, integration testing, regression testing. Static tests: reviews, walkthroughs, inspections, reviewing algorithms and software.
Pair programming. Verification and validation strategies. |
||
| Mon. 3 Apr. | 21 | Databases | Relational databases, hierarchical databases, NoSQL databases. Relational databases: entity relationship modelling, relational algebra, SQL. | ||
| Wed. 5 Apr. | 22 | Databases II | Normalization. Compression strategies, dictionary algorithm, LZ algorithm. File structure strategies. | ||
| Mon. 17 Apr. | 23 | Programming Paradigms I | Imperative programming. Object-oriented programming. Logic programming. Functional programming. | ||
| Wed. 19 Apr. | 24 | Programming Paradigms II | OO programming; classes; type, operational and functional polymorphism; inheritance, attributes, methods, instantiations, abstract classes, object-oriented languages. | ||
| Mon. 24 Apr. | 25 | Programming Paradigms III | OO design methodology: UML class diagram, composite-structure diagram, architecture diagram, package diagram, object diagram, component diagram, deployment diagram, activity diagram, sequence diagram, communication diagram, interaction diagram, timing diagram, use case diagram, state machine diagram. OO design principles: open/close principle, design by contract principle, dependency inversion principle, other design principles, documentation | ||
| Wed. 26 Apr. | 26 | Automata Theory | Regular Languages. Finite Automata. Nondeterminism. Regular Expressions. Nonregular Languages. Context-free Languages. Context-free Grammars. Pushdown Automata. Deterministic Context-Free Languages. | ||
| Wed. 3 May | 27 | Computability Theory | The Church-Turing Thesis. Turing Machines. Variants of Turing Machines. The Definition of Algorithm. Decidability. Decidable Languages. Undecidability. Reducibility |
