Difference between revisions of "Data Structures and Algorithms for Engineers Lecture Schedule 2"

From David Vernon's Wiki
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
 
−
 
 
<small>
 
<small>
 
{| class="wikitable"
 
{| class="wikitable"
Line 9: Line 7:
 
! scope="col" style="width: 13%;" | Reading
 
! scope="col" style="width: 13%;" | Reading
 
! scope="col" style="width: 13%;" | Assignments
 
! scope="col" style="width: 13%;" | Assignments
 +
|- style="vertical-align: top;"
 +
| Tue. 17 Jan.
 +
| -
 +
| Lab A and B
 +
| This lab class will be used to cover the first half of Lecture 1.
 +
|[http://www.vernon.eu/04-630/04-630_DSAE_01_Intro_and_SW_Dev_Life_Cycle.pdf Lecture 1 Slides 1-95]
 +
|
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 18 Jan.
 
| Wed. 18 Jan.
Line 26: Line 31:
 
| Wed. 25 Jan.
 
| Wed. 25 Jan.
 
| 3
 
| 3
−
| Analysis of Complexity I
+
| Analysis of Complexity
−
| 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.
+
| 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.
 
| [http://www.vernon.eu/04-630/04-630_DSAE_03_Analysis_of_Complexity.pdf Lecture 3 Slides]. Aho et al. 1983, Chapter 1.
 
| [http://www.vernon.eu/04-630/04-630_DSAE_03_Analysis_of_Complexity.pdf Lecture 3 Slides]. Aho et al. 1983, Chapter 1.
 
|  
 
|  
Line 33: Line 38:
 
| Mon. 30 Jan.
 
| Mon. 30 Jan.
 
| 4
 
| 4
−
| Analysis of Complexity II
+
| Searching and Sorting Algorithms
−
| 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.
+
| 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.
−
| [http://www.vernon.eu/04-630/04-630_DSAE_03_Analysis_of_Complexity.pdf Lecture 4 Slides]. Aho et al. 1983, Chapter 1.
+
| [http://www.vernon.eu/04-630/04-630_DSAE_04_Searching_and_Sorting_Algorithms.pdf Lecture 4 Slides]. Aho et al. 1983, Chapter 8.
 
|  [http://www.vernon.eu/04-630/04-630_Assignment_2.pdf Assignment 2]
 
|  [http://www.vernon.eu/04-630/04-630_Assignment_2.pdf Assignment 2]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 6 Feb.
 
| Mon. 6 Feb.
 
| 5
 
| 5
−
| Searching and Sorting Algorithms I
+
| Abstract Data Types (ADT)
−
| Linear and binary search (iterative and recursive). In-place sorts: bubblesort (efficient and inefficient), selection sort, insertion sort.  
+
| <!-- Vector example exercise. History of abstraction. --> Abstract Data Types (ADT). Information hiding. Types and typing. <!-- Encapsulation. Efficiency. --> Design Goals. Design practices.
−
| [http://www.vernon.eu/04-630/04-630_DSAE_04_Searching_and_Sorting_Algorithms.pdf Lecture 5 Slides]. Aho et al. 1983, Chapter 8.
+
| [http://www.vernon.eu/04-630/04-630_DSAE_05_Abstract_Data_Types.pdf Lecture 5 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 8 Feb.
 
| Wed. 8 Feb.
 
| 6
 
| 6
−
| Searching and Sorting Algorithms I
+
| Containers, Dictionaries, and Lists
−
| 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.
+
| Container and dictionaries: mechanisms for accessing data in a list. List ADT. Implementation with arrays and linked lists. Doubly linked lists and circular lists. Performance considerations.
−
|[http://www.vernon.eu/04-630/04-630_DSAE_04_Searching_and_Sorting_Algorithms.pdf Lecture 6 Slides]. Aho et al. 1983, Chapter 8.
+
| [http://www.vernon.eu/04-630/04-630_DSAE_06_Containers_Dictionaries_and_Lists.pdf Lecture 6 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 13 Feb.
 
| Mon. 13 Feb.
 
| 7
 
| 7
−
| Abstract Data Types (ADT)
+
| Stacks
−
| <!-- Vector example exercise. History of abstraction. --> Abstract Data Types (ADT). Information hiding. Types and typing. <!-- Encapsulation. Efficiency. --> Design Goals. Design practices.
+
| Stack (LIFO) ADT. Implementation using List ADT (array and linked-list). Comparison of order of complexity. Stack applications, including token matching, evaluation of postfix expressions, and conversion of infix expressions to postfix.
−
| [http://www.vernon.eu/04-630/04-630_DSAE_05_Abstract_Data_Types.pdf Lecture 7 Slides].
+
| [http://www.vernon.eu/04-630/04-630_DSAE_07_Stacks.pdf Lecture 7 Slides].
 
|
 
|
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 15 Feb.
 
| Wed. 15 Feb.
 
| 8
 
| 8
−
| Containers, Dictionaries, and Lists I
+
| Queues
−
| Container and dictionaries: mechanisms for accessing data in a list.  List ADT.  Implementation with arrays.
+
| Queue (FIFO ADT). Implementation using List ADT (array and linked-list).  Comparison of order of complexity.  Dedicated ADT. Circular queues.  Queue applications.
−
|  [http://www.vernon.eu/04-630/04-630_DSAE_06_Containers_Dictionaries_and_Lists.pdf Lecture 8 Slides].
+
|  [http://www.vernon.eu/04-630/04-630_DSAE_08_Queues.pdf Lecture 8 Slides]. [http://www.vernon.eu/04-630/poisson.pdf  On the Simulation of Random Events].
 
|  [http://www.vernon.eu/04-630/04-630_Assignment_3.pdf Assignment 3] <!-- <BR> [[Assignment 3 Status]] -->
 
|  [http://www.vernon.eu/04-630/04-630_Assignment_3.pdf Assignment 3] <!-- <BR> [[Assignment 3 Status]] -->
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 20 Feb.
 
| Mon. 20 Feb.
 
| 9
 
| 9
−
| Containers, Dictionaries, and Lists II
+
| Trees I
−
| List ADT. Implementation with linked lists. Doubly linked lists and circular lists. Performance considerations.
+
| 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
−
|   [http://www.vernon.eu/04-630/04-630_DSAE_06_Containers_Dictionaries_and_Lists.pdf Lecture 9 Slides].
+
Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder.  
 +
| [http://www.vernon.eu/04-630/04-630_DSAE_09_Trees_I.pdf Lecture 9 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 22 Feb.
 
| Wed. 22 Feb.
 
| 10
 
| 10
−
| Stacks
+
| Trees II
−
| Stack (LIFO) ADT. Implementation using List ADT (array and linked-list). Comparison of order of complexity. Stack applications, including token matching, evaluation of postfix expressions, and conversion of infix expressions to postfix.
+
| 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
−
| [http://www.vernon.eu/04-630/04-630_DSAE_07_Stacks.pdf Lecture 10 Slides].
+
| [http://www.vernon.eu/04-630/04-630_DSAE_10_Trees_II.pdf Lecture 10 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 27 Feb.
 
| Mon. 27 Feb.
 
| 11
 
| 11
−
| Queues
+
| Trees III
−
| Queue (FIFO ADT). Implementation using List ADT (array and linked-list).   Comparison of order of complexity.  Dedicated ADT. Circular queues.  Queue applications.
+
| Tree applications. Fixed-length codes & variable length codes. Optimal code trees.  Huffman's algorithm. <!-- and implementation. -->
−
|  [http://www.vernon.eu/04-630/04-630_DSAE_08_Queues.pdf Lecture 11 Slides]. [http://www.vernon.eu/04-630/poisson.pdf  On the Simulation of Random Events].
+
|  [http://www.vernon.eu/04-630/04-630_DSAE_11_Trees_III.pdf Lecture 11 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 1 Mar.
 
| Wed. 1 Mar.
 
| 12
 
| 12
−
| Trees I
+
| Heaps
−
| 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
+
| Priority queues. Heap basics. Types of heap: min heaps and max heap. Heap characteristics.  Implementation of heap. Heap operations: delete max/min, down heap, up heap, merge, construct, heapify. Complexity of operations.  Heap sort.  <!-- Operating systems heaps.  d-ary heaps. Leftist heaps. -->
−
|  [http://www.vernon.eu/04-630/04-630_DSAE_09_Trees_I.pdf Lecture 12 Slides].
+
|  [http://www.vernon.eu/04-630/04-630_DSAE_12_Heaps.pdf Lecture 12 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 6 Mar.
 
| Mon. 6 Mar.
 
| 13
 
| 13
−
| Trees II
+
| Graphs I
−
| Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder.  
+
| 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.
−
| [http://www.vernon.eu/04-630/04-630_DSAE_09_Trees_I.pdf Lecture 13 Slides].
+
| [http://www.vernon.eu/04-630/04-630_DSAE_13_Graphs_I.pdf Lecture 13 Slides]
 
| [http://www.vernon.eu/04-630/04-630_Lab_Exercise_1.pdf Lab Exercise 1]
 
| [http://www.vernon.eu/04-630/04-630_Lab_Exercise_1.pdf Lab Exercise 1]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 8 Mar.
 
| Wed. 8 Mar.
 
| 14
 
| 14
−
| Trees III
+
| Graphs II
−
| Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring.
+
| 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.
−
| [http://www.vernon.eu/04-630/04-630_DSAE_10_Trees_II.pdf Lecture 14 Slides].
+
|
−
| [http://www.vernon.eu/04-630/04-630_Assignment_4.pdf Assignment 4] <!-- <BR> [[Assignment 4 Status]] -->
+
| [http://www.vernon.eu/04-630/04-630_Assignment_4.pdf Assignment 4] <BR> [[Assignment 4 Status]]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 13 Mar.
 
| Mon. 13 Mar.
 
| 15
 
| 15
−
| Trees IV
+
| Complex Networks I
−
| Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring.
+
| Complex systems and large networks. Random networks. Degree distribution. Clustering. Small world phenomena.
−
|  [http://www.vernon.eu/04-630/04-630_DSAE_10_Trees_II.pdf Lecture 15 Slides].
+
|
 
| [http://www.vernon.eu/04-630/04-630_Lab_Exercise_2.pdf Lab Exercise 2]
 
| [http://www.vernon.eu/04-630/04-630_Lab_Exercise_2.pdf Lab Exercise 2]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 15 Mar.
 
| Wed. 15 Mar.
 
| 16
 
| 16
−
| Trees V
+
| Complex Networks II
−
| Tree applications. Fixed-length codes & variable length codes. Optimal code trees. Huffman's algorithm. <!-- and implementation. -->
+
| Scale free networks. Community detection. Network evolution.
−
| [http://www.vernon.eu/04-630/04-630_DSAE_11_Trees_III.pdf Lecture 16 Slides].
+
|  
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 20 Mar.
 
| Mon. 20 Mar.
 
| 17
 
| 17
−
| Heaps
+
| Hashing I
−
| Priority queues. Heap basics. Types of heap: min heaps and max heap. Heap characteristics.  Implementation of heap. Heap operations: delete max/min, down heap, up heap, merge, construct, heapify. Complexity of operations.  Heap sort.  <!-- Operating systems heaps.  d-ary heaps. Leftist heaps. -->
+
| Using keys to address data
−
| [http://www.vernon.eu/04-630/04-630_DSAE_12_Heaps.pdf Lecture 17 Slides].
+
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
 +
|  
 
|  [http://www.vernon.eu/04-630/04-630_Lab_Exercise_3.pdf Lab Exercise 3] <BR> [http://www.vernon.eu/04-630/04-630_Lab_Exercise_3_Alternative.pdf Lab Exercise 3 Alternative]
 
|  [http://www.vernon.eu/04-630/04-630_Lab_Exercise_3.pdf Lab Exercise 3] <BR> [http://www.vernon.eu/04-630/04-630_Lab_Exercise_3_Alternative.pdf Lab Exercise 3 Alternative]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 22 Mar.
 
| Wed. 22 Mar.
 
| 18
 
| 18
−
| Graphs I
+
| Hashing II
−
| Types of graphs: directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, non-simple, implicit, explicit, embedded, topological. Adjacency matrix representation. Adjacency list representation.
+
| Evaluating hash functions: prime division, mid-square, folding, load factor. Example application: dictionaries. Generating hash functions and using hash structures.
−
| [http://www.vernon.eu/04-630/04-630_DSAE_13_Graphs_I.pdf Lecture 18 Slides]
+
|  
 
| [http://www.vernon.eu/04-630/04-630_Assignment_5.pdf Assignment 5] <!-- <BR> [[Assignment 5 Status]] -->
 
| [http://www.vernon.eu/04-630/04-630_Assignment_5.pdf Assignment 5] <!-- <BR> [[Assignment 5 Status]] -->
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 27 Mar.
 
| Mon. 27 Mar.
 
| 19
 
| 19
−
| Graphs II
+
| Algorithmic Strategies
−
| Graph traversal: breadth-first search and depth-first search; implementation and application.   Topological sort. <!-- Euler's theorem. -->
+
| Classes of algorithms. Brute force. Divide and conquer. Greedy algorithms. Dynamic programming. Combinatorial search and backtracking. Branch and bound. Heuristics and heuristic algorithms. Probabilistic algorithms.
 
|  
 
|  
 
|  [http://www.vernon.eu/04-630/04-630_Lab_Exercise_4.pdf Lab Exercise 4]  
 
|  [http://www.vernon.eu/04-630/04-630_Lab_Exercise_4.pdf Lab Exercise 4]  
Line 145: Line 155:
 
| Wed. 29 Mar.
 
| Wed. 29 Mar.
 
| 20
 
| 20
−
| Graphs III
+
| Analysis of Correctness
−
| Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm.
+
| 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 152: Line 163:
 
| Mon. 3 Apr.
 
| Mon. 3 Apr.
 
| 21
 
| 21
−
| Graphs IV
+
| Databases
−
| Dijkstra's shortest path algorithm. Floyd-Warshall's all-pairs algorithm.
+
| Relational databases, hierarchical databases, NoSQL databases. Relational databases: entity relationship modelling, relational algebra, SQL.
 
|  
 
|  
 
|  
 
|  
Line 159: Line 170:
 
| Wed. 5 Apr.
 
| Wed. 5 Apr.
 
| 22
 
| 22
−
| Complex Networks
+
| Databases II
−
| Complex systems and large networks. Random networks. Degree distribution. Clustering. Small world phenomena. Scale free networks. Community detection. Network evolution.
+
| Normalization. Compression strategies, dictionary algorithm, LZ algorithm. File structure strategies.
 
|  
 
|  
 
|   
 
|   
Line 166: Line 177:
 
| Mon. 17 Apr.
 
| Mon. 17 Apr.
 
| 23
 
| 23
−
| Hashing
+
| Programming Paradigms 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. <!-- Evaluating hash functions: prime division, mid-square, folding, load factor. Example application: dictionaries. Generating hash functions and using hash structures. -->
+
| Imperative programming. Logic programming. Functional programming. OO programming; classes; type, operational and functional polymorphism; inheritance, attributes, methods, instantiations, abstract classes, object-oriented languages.  
 
|  
 
|  
 
|  
 
|  
Line 173: Line 184:
 
| Wed. 19 Apr.
 
| Wed. 19 Apr.
 
| 24
 
| 24
−
| Algorithmic Strategies
+
| Programming Paradigms II
−
| Classes of algorithms. Brute force. Divide and conquer. Greedy algorithms. Dynamic programming. Combinatorial search and backtracking. Branch and bound. Heuristics and heuristic algorithms. Probabilistic algorithms.
+
| 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 180: Line 191:
 
| Mon. 24 Apr.
 
| Mon. 24 Apr.
 
| 25
 
| 25
−
| Analysis of Correctness
+
| Automata Theory
−
| 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.
+
| Regular Languages. Finite Automata. Nondeterminism. Regular Expressions. Nonregular Languages. Context-free Languages. Context-free Grammars. Pushdown Automata. Deterministic Context-Free Languages.
−
Pair programming. Verification and validation strategies.
+
 
|  
 
|  
 
|  
 
|  
Line 188: Line 198:
 
| Wed. 26 Apr.
 
| Wed. 26 Apr.
 
| 26
 
| 26
−
| Automata Theory
+
| Computability Theory
−
| Regular Languages. Finite Automata. Nondeterminism. Regular Expressions. Nonregular Languages. Context-free Languages. Context-free Grammars. Pushdown Automata. Deterministic Context-Free Languages.
+
| The Church-Turing Thesis. Turing Machines. Variants of Turing Machines. The Definition of Algorithm. Decidability. Decidable Languages. Undecidability. Reducibility.
 
|  
 
|  
 
|  
 
|  
Line 195: Line 205:
 
| Wed. 3 May
 
| Wed. 3 May
 
| 27
 
| 27
−
| Computability Theory
+
| Review
−
| The Church-Turing Thesis. Turing Machines. Variants of Turing Machines. The Definition of Algorithm. Decidability. Decidable Languages. Undecidability. Reducibility.
+
|  
 
|  
 
|  
 
|  
 
|  
 
|}
 
|}
 
</small>
 
</small>
−
 
+
−
 
+
 
----
 
----
 
Back to [[Data Structures and Algorithms for Engineers]]
 
Back to [[Data Structures and Algorithms for Engineers]]

Latest revision as of 01:25, 27 March 2017

Date Lecture Topic Material covered Reading Assignments
Tue. 17 Jan. - Lab A and B This lab class will be used to cover the first half of Lecture 1. Lecture 1 Slides 1-95
Wed. 18 Jan. 1 Introduction & The Software Development Life Cycle Motivation. Goals of the course. Syllabus and lecture schedule. Course operation. Preview of course material. Overview of labs, assignments, and exercises. Software development tools for assignments. Levels of abstraction in information processing systems. The software development life cycle: Yourdon Structured Analysis - functional, data, and behavioural models (hierarchical decomposition trees, architecture diagrams, data flow diagrams DFD, data dictionaries, entity relationship ER diagrams, state transition diagrams). Software process models: waterfall, evolutionary, formal transformation, re-use, hybrid, spiral. Lecture 1 Slides. Harel 2004, Chapter 13. Williams 2007. Optional: Software Development Life Cycle, Software Standards
Mon. 23 Jan. 2 Formalisms for Representing Algorithms Definition of an algorithm. Modelling software. Relational modelling. State modelling. Practical representations. Pseudo code. Flow charts. Finite state machines. UML. Predicate logic. Analysis. Lecture 2 Slides. Harel 2004, Chapters 1 and 2. Assignment 1
Wed. 25 Jan. 3 Analysis of Complexity 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. Lecture 3 Slides. Aho et al. 1983, Chapter 1.
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. Lecture 4 Slides. Aho et al. 1983, Chapter 8. Assignment 2
Mon. 6 Feb. 5 Abstract Data Types (ADT) Abstract Data Types (ADT). Information hiding. Types and typing. Design Goals. Design practices. Lecture 5 Slides.
Wed. 8 Feb. 6 Containers, Dictionaries, and Lists Container and dictionaries: mechanisms for accessing data in a list. List ADT. Implementation with arrays and linked lists. Doubly linked lists and circular lists. Performance considerations. Lecture 6 Slides.
Mon. 13 Feb. 7 Stacks Stack (LIFO) ADT. Implementation using List ADT (array and linked-list). Comparison of order of complexity. Stack applications, including token matching, evaluation of postfix expressions, and conversion of infix expressions to postfix. Lecture 7 Slides.
Wed. 15 Feb. 8 Queues Queue (FIFO ADT). Implementation using List ADT (array and linked-list). Comparison of order of complexity. Dedicated ADT. Circular queues. Queue applications. Lecture 8 Slides. On the Simulation of Random Events. Assignment 3
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.

Lecture 9 Slides.
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 Lecture 10 Slides.
Mon. 27 Feb. 11 Trees III Tree applications. Fixed-length codes & variable length codes. Optimal code trees. Huffman's algorithm. Lecture 11 Slides.
Wed. 1 Mar. 12 Heaps Priority queues. Heap basics. Types of heap: min heaps and max heap. Heap characteristics. Implementation of heap. Heap operations: delete max/min, down heap, up heap, merge, construct, heapify. Complexity of operations. Heap sort. Lecture 12 Slides.
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. Lecture 13 Slides Lab Exercise 1
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. Assignment 4
Assignment 4 Status
Mon. 13 Mar. 15 Complex Networks I Complex systems and large networks. Random networks. Degree distribution. Clustering. Small world phenomena. Lab Exercise 2
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

Lab Exercise 3
Lab Exercise 3 Alternative
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. Assignment 5
Mon. 27 Mar. 19 Algorithmic Strategies Classes of algorithms. Brute force. Divide and conquer. Greedy algorithms. Dynamic programming. Combinatorial search and backtracking. Branch and bound. Heuristics and heuristic algorithms. Probabilistic algorithms. Lab Exercise 4
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. Logic programming. Functional programming. OO programming; classes; type, operational and functional polymorphism; inheritance, attributes, methods, instantiations, abstract classes, object-oriented languages.
Wed. 19 Apr. 24 Programming Paradigms II 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
Mon. 24 Apr. 25 Automata Theory Regular Languages. Finite Automata. Nondeterminism. Regular Expressions. Nonregular Languages. Context-free Languages. Context-free Grammars. Pushdown Automata. Deterministic Context-Free Languages.
Wed. 26 Apr. 26 Computability Theory The Church-Turing Thesis. Turing Machines. Variants of Turing Machines. The Definition of Algorithm. Decidability. Decidable Languages. Undecidability. Reducibility.
Wed. 3 May 27 Review

Back to Data Structures and Algorithms for Engineers

Retrieved from "http://www.vernon.eu/w/index.php?title=Data_Structures_and_Algorithms_for_Engineers_Lecture_Schedule_2&oldid=1400"