Difference between revisions of "Data Structures and Algorithms for Engineers Lecture Schedule 2"
From David Vernon's Wiki
| Line 14: | Line 14: | ||
| Introduction & The Software Development Life Cycle | | 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. | |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. | ||
| − | |[http://www.vernon.eu/04-630/04- | + | |[http://www.vernon.eu/04-630/04-630_Lecture_01_Intro_and_SW_Dev_Life_Cycle.pdf Lecture 1 Slides]. Harel 2004, Chapter 13. [http://agile.csc.ncsu.edu/SEMaterials/AgileMethods.pdf Williams 2007]. Optional: [http://www.vernon.eu/04-630/Software_Development_Life_Cycle.pdf Software Development Life Cycle], [http://www.vernon.eu/wiki/The_CINDY_Cognitive_Architecture#Software_Engineering_Standards Software Standards] |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 21: | Line 21: | ||
| Formalisms for Representing Algorithms | | 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. | | Definition of an algorithm. Modelling software. Relational modelling. State modelling. Practical representations. Pseudo code. Flow charts. Finite state machines. UML. Predicate logic. Analysis. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_02_Formalisms_for_Representing_Algorithms.pdf Lecture 2 Slides]. Harel 2004, Chapters 1 and 2. |
| [http://www.vernon.eu/04-630/04-630_Assignment_1.pdf Assignment 1] | | [http://www.vernon.eu/04-630/04-630_Assignment_1.pdf Assignment 1] | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 28: | Line 28: | ||
| Analysis of Complexity I | | Analysis of Complexity I | ||
| 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. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_03_Analysis_of_Complexity_I.pdf Lecture 3 Slides]. Aho et al. 1983, Chapter 1. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 35: | Line 35: | ||
| Analysis of Complexity II | | Analysis of Complexity II | ||
| 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. | | 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- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_04_Analysis_of_Complexity_II.pdf Lecture 4 Slides]. Aho et al. 1983, Chapter 1. |
| [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;" | ||
| Line 42: | Line 42: | ||
| Searching and Sorting Algorithms I | | Searching and Sorting Algorithms I | ||
| Linear and binary search (iterative and recursive). In-place sorts: bubblesort (efficient and inefficient), selection sort, insertion sort. | | Linear and binary search (iterative and recursive). In-place sorts: bubblesort (efficient and inefficient), selection sort, insertion sort. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_05_Searching_and_Sorting_Algorithms_I.pdf Lecture 5 Slides]. Aho et al. 1983, Chapter 8. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 49: | Line 49: | ||
| Searching and Sorting Algorithms I | | Searching and Sorting Algorithms I | ||
| 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. | | 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- | + | |[http://www.vernon.eu/04-630/04-630_Lecture_06_Searching_and_Sorting_Algorithms_II.pdf Lecture 6 Slides]. Aho et al. 1983, Chapter 8. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 56: | Line 56: | ||
| Abstract Data Types (ADT) | | Abstract Data Types (ADT) | ||
| <!-- Vector example exercise. History of abstraction. --> Abstract Data Types (ADT). Information hiding. Types and typing. <!-- Encapsulation. Efficiency. --> Design Goals. Design practices. | | <!-- 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- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_07_Abstract_Data_Types.pdf Lecture 7 Slides]. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 63: | Line 63: | ||
| Containers, Dictionaries, and Lists I | | Containers, Dictionaries, and Lists I | ||
| Container and dictionaries: mechanisms for accessing data in a list. List ADT. Implementation with arrays. | | Container and dictionaries: mechanisms for accessing data in a list. List ADT. Implementation with arrays. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_08_Containers_Dictionaries_and_Lists_I.pdf Lecture 8 Slides]. |
| [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;" | ||
| Line 70: | Line 70: | ||
| Containers, Dictionaries, and Lists II | | Containers, Dictionaries, and Lists II | ||
| List ADT. Implementation with linked lists. Doubly linked lists and circular lists. Performance considerations. | | List ADT. Implementation with linked lists. Doubly linked lists and circular lists. Performance considerations. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_09_Containers_Dictionaries_and_Lists_II.pdf Lecture 9 Slides]. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 77: | Line 77: | ||
| Stacks | | 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. | | 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- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_10_Stacks.pdf Lecture 10 Slides]. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 84: | Line 84: | ||
| Queues | | Queues | ||
| Queue (FIFO ADT). Implementation using List ADT (array and linked-list). Comparison of order of complexity. Dedicated ADT. Circular queues. Queue applications. | | 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- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_11_Queues.pdf Lecture 11 Slides]. [http://www.vernon.eu/04-630/poisson.pdf On the Simulation of Random Events]. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 91: | Line 91: | ||
| Trees I | | 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 | | 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- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_12_Trees_I.pdf Lecture 12 Slides]. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 98: | Line 98: | ||
| Trees II | | Trees II | ||
| Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder. | | Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_12_Trees_II.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;" | ||
| Line 105: | Line 105: | ||
| Trees III | | Trees III | ||
| Height-balanced trees: AVL Trees, RR, RL, LR, LL rotations. | | Height-balanced trees: AVL Trees, RR, RL, LR, LL rotations. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_14_Trees_III.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;" | ||
| Line 112: | Line 112: | ||
| Trees IV | | Trees IV | ||
| Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring. | | Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_15_Trees_IV.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;" | ||
| Line 119: | Line 119: | ||
| Trees V | | Trees V | ||
| Tree applications. Fixed-length codes & variable length codes. Optimal code trees. Huffman's algorithm. <!-- and implementation. --> | | Tree applications. Fixed-length codes & variable length codes. Optimal code trees. Huffman's algorithm. <!-- and implementation. --> | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_16_Trees_V.pdf Lecture 16 Slides]. |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 126: | Line 126: | ||
| Heaps | | 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. <!-- Operating systems heaps. d-ary heaps. Leftist 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. <!-- Operating systems heaps. d-ary heaps. Leftist heaps. --> | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_17_Heaps.pdf Lecture 17 Slides]. |
| [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;" | ||
| Line 133: | Line 133: | ||
| Graphs I | | 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. | | Types of graphs: directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, non-simple, implicit, explicit, embedded, topological. Adjacency matrix representation. Adjacency list representation. | ||
| − | | [http://www.vernon.eu/04-630/04- | + | | [http://www.vernon.eu/04-630/04-630_Lecture_18_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;" | ||
| Line 140: | Line 140: | ||
| Graphs II | | Graphs II | ||
| Graph traversal: breadth-first search and depth-first search; implementation and application. Topological sort. <!-- Euler's theorem. --> | | Graph traversal: breadth-first search and depth-first search; implementation and application. Topological sort. <!-- Euler's theorem. --> | ||
| − | | | + | | [http://www.vernon.eu/04-630/04-630_Lecture_19_Graphs_II.pdf Lecture 19 Slides] |
| [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] | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 147: | Line 147: | ||
| Graphs III | | Graphs III | ||
| Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm. | | Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm. | ||
| − | | | + | | [http://www.vernon.eu/04-630/04-630_Lecture_20_Graphs_III.pdf Lecture 20 Slides] |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
| Line 154: | Line 154: | ||
| Graphs IV | | Graphs IV | ||
| Dijkstra's shortest path algorithm. Floyd-Warshall's all-pairs algorithm. | | Dijkstra's shortest path algorithm. Floyd-Warshall's all-pairs algorithm. | ||
| − | | | + | | [http://www.vernon.eu/04-630/04-630_Lecture_21_Graphs_IV.pdf Lecture 21 Slides] |
| | | | ||
|- style="vertical-align: top;" | |- style="vertical-align: top;" | ||
Revision as of 10:43, 26 March 2017
| Date | Lecture | Topic | Material covered | Reading | Assignments |
|---|---|---|---|---|---|
| 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 I | 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. | Lecture 3 Slides. Aho et al. 1983, Chapter 1. | |
| Mon. 30 Jan. | 4 | Analysis of Complexity II | 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 4 Slides. Aho et al. 1983, Chapter 1. | Assignment 2 |
| Mon. 6 Feb. | 5 | Searching and Sorting Algorithms I | Linear and binary search (iterative and recursive). In-place sorts: bubblesort (efficient and inefficient), selection sort, insertion sort. | Lecture 5 Slides. Aho et al. 1983, Chapter 8. | |
| Wed. 8 Feb. | 6 | Searching and Sorting Algorithms I | 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 6 Slides. Aho et al. 1983, Chapter 8. | |
| Mon. 13 Feb. | 7 | Abstract Data Types (ADT) | Abstract Data Types (ADT). Information hiding. Types and typing. Design Goals. Design practices. | Lecture 7 Slides. | |
| Wed. 15 Feb. | 8 | Containers, Dictionaries, and Lists I | Container and dictionaries: mechanisms for accessing data in a list. List ADT. Implementation with arrays. | Lecture 8 Slides. | Assignment 3 |
| Mon. 20 Feb. | 9 | Containers, Dictionaries, and Lists II | List ADT. Implementation with linked lists. Doubly linked lists and circular lists. Performance considerations. | Lecture 9 Slides. | |
| Wed. 22 Feb. | 10 | 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 10 Slides. | |
| Mon. 27 Feb. | 11 | Queues | Queue (FIFO ADT). Implementation using List ADT (array and linked-list). Comparison of order of complexity. Dedicated ADT. Circular queues. Queue applications. | Lecture 11 Slides. On the Simulation of Random Events. | |
| Wed. 1 Mar. | 12 | 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 | Lecture 12 Slides. | |
| Mon. 6 Mar. | 13 | Trees II | Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder. | Lecture 13 Slides. | Lab Exercise 1 |
| Wed. 8 Mar. | 14 | Trees III | Height-balanced trees: AVL Trees, RR, RL, LR, LL rotations. | Lecture 14 Slides. | Assignment 4 |
| Mon. 13 Mar. | 15 | Trees IV | Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring. | Lecture 15 Slides. | Lab Exercise 2 |
| Wed. 15 Mar. | 16 | Trees V | Tree applications. Fixed-length codes & variable length codes. Optimal code trees. Huffman's algorithm. | Lecture 16 Slides. | |
| Mon. 20 Mar. | 17 | 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 17 Slides. | Lab Exercise 3 Lab Exercise 3 Alternative |
| Wed. 22 Mar. | 18 | 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. | Lecture 18 Slides | Assignment 5 |
| Mon. 27 Mar. | 19 | Graphs II | Graph traversal: breadth-first search and depth-first search; implementation and application. Topological sort. | Lecture 19 Slides | Lab Exercise 4 |
| Wed. 29 Mar. | 20 | Graphs III | Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm. | Lecture 20 Slides | |
| Mon. 3 Apr. | 21 | Graphs IV | Dijkstra's shortest path algorithm. Floyd-Warshall's all-pairs algorithm. | Lecture 21 Slides | |
| Wed. 5 Apr. | 22 | Complex Networks | Complex systems and large networks. Random networks. Degree distribution. Clustering. Small world phenomena. Scale free networks. Community detection. Network evolution. | ||
| Mon. 17 Apr. | 23 | Hashing | Using keys to address data. Mappings: injection, surjection, bijection. Hash functions. Hash tables: current value tables, direct access tables. Managing collisions: chaining, overflow areas, re-hashing, linear probing, quadratic probing. | ||
| Wed. 19 Apr. | 24 | 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. | ||
| Mon. 24 Apr. | 25 | 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. |
||
| 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. |
