SYDE 322 Lectures
Topic | Related Readings | Related Material |
---|---|---|
Introduction - Algorithmic Problem Solving (AD) - The Stable-Marriage Problem (AD) - Some Types of Problems (AD) - Introduction to C++ (SD) |
1.2, 1.3 (AD) |
Algorithm for Stable-Marriage Introduction to C++ |
Algorithm Analysis - Analysis Framework - Asymptotic Notations - Non-recursive Algorithms - Recursive Algorithms - Fibonacci Numbers - Empirical Analysis |
2.1-2.6 (AD) | Algorithm Analysis |
Abstraction Mechanisms - Data Structures - Container Classes (C++ STL) |
1.4 (AD) 2.12, 2.18 (SD) |
|
Algorithm Design Techniques - Sorting - Exhaustive Search: Traveling Salesman Problem Knapsack Problem Assignment Problem |
3.1, 3.4 (AD) | |
Algorithm Design Techniques Divide-and-Conquer: - Merge Sort - Counting Inversions - Multiplication of Large Integer - Closest Pair (computational geometry problem) |
4.1, 4.3, 4.5, 4.6 (AD) | Divide-and-Conquer |
Generic Programming - Templates - Iterators - Generic Algorithms |
||
Algorithm Design Techniques Dynamic Programming: - Transitive Closure of a Digraph - Knapsack - Maximum Subsequence Sum - Sequence Alignment |
8.2, 8.4 (AD) | |
Object Oriented Programming (Abstraction, Encapsulation, Class Hierarchy) - Inheritance |
Prof Harder Testers | |
Algorithm Design Techniques Greedy Algorithms - Minimum Spanning Tree - Huffman Trees - Scheduling - Application of Heaps |
9.1, 9.3, 9.4 (AD) | |
Software Modelling Unified Modelling Language (UML) - Class Diagrams - Relationships between classes (Association, Aggregation, Generalization, Composition) |
||
Algorithm Design Techniques Iterative Improvement: - Maximum Bipartite Matching and Network Flow Algorithm - Stable Marriage Problem |
10.2, 10.3, 10.4 (AD) | Max Flow Algorithm |
Software Design Patterns - Creational (Factory Method) - Structural (Adaptor/Wrapper) - Behavioral (Iterator, Strategy, Template Method) |
||
P, NP, and NP-complete Problems | 11.1, 11.3 (AD) | Independent Set Problem |
Software Testing - Unit Tests - Test Cases, Test Suites, Test Case Evaluation - Regression Testing - Black Box and White Box Testing - Test Automation |