Data Structures and Algorithms for Engineers Lecture Schedule

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.
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. Greedy algorithms. Dynamic programming. Combinatorial search and backtracking. Branch and bound. 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. 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	Final Presentations

---

Back to Data Structures and Algorithms for Engineers