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

From David Vernon's Wiki
Jump to: navigation, search
 
(40 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
<!-- __NOTOC__ -->
 +
<div style="float:right;">__TOC__</div>
 +
<span style="color:#AB0000" ><span style="font-size:10px">|</span></span><span style="color:#000000" ><span style="font-size:10px"><span style="text-decoration:underline">CARNEGIE MELLON UNIVERSITY AFRICA</span></span></span><span style="color:#AB0000" ><span style="font-size:10px">|</span></span>
 +
 
<small>
 
<small>
 
{| class="wikitable"
 
{| class="wikitable"
Line 7: Line 11:
 
! 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 19: Line 16:
 
| 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-630_DSAE_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]
+
|[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 26: Line 23:
 
| 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-630_DSAE_02_Formalisms_for_Representing_Algorithms.pdf Lecture 2 Slides]. Harel 2004, Chapters 1 and 2.
+
| [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;"
 
| Wed. 25 Jan.
 
| Wed. 25 Jan.
 
| 3
 
| 3
| Analysis of Complexity
+
| 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. 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.
+
| 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-630_DSAE_03_Analysis_of_Complexity.pdf Lecture 3 Slides]. Aho et al. 1983, Chapter 1.
+
| [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;"
 
| Mon. 30 Jan.
 
| Mon. 30 Jan.
 
| 4
 
| 4
| Searching and Sorting Algorithms
+
| Analysis of Complexity II
| 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.
+
| 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_04_Searching_and_Sorting_Algorithms.pdf Lecture 4 Slides]. Aho et al. 1983, Chapter 8.
+
| [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;"
 
| Mon. 6 Feb.
 
| Mon. 6 Feb.
 
| 5
 
| 5
| Abstract Data Types (ADT)
+
| Searching and Sorting Algorithms I
| <!-- Vector example exercise. History of abstraction. --> Abstract Data Types (ADT). Information hiding. Types and typing. <!-- Encapsulation. Efficiency. --> Design Goals. Design practices.
+
| 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-630_DSAE_05_Abstract_Data_Types.pdf Lecture 5 Slides].
+
| [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;"
 
| Wed. 8 Feb.
 
| Wed. 8 Feb.
 
| 6
 
| 6
| Containers, Dictionaries, and Lists
+
| Searching and Sorting Algorithms I
| Basic operations. Implementation with arrays and linked lists. Singly linked lists. Doubly linked lists. Performance considerations.
+
| 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_06_Containers_Dictionaries_and_Lists.pdf Lecture 6 Slides].
+
|[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;"
 
| Mon. 13 Feb.
 
| Mon. 13 Feb.
 
| 7
 
| 7
| Stacks
+
| Abstract Data Types (ADT)
| 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.
+
| <!-- 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_Lecture_07_Abstract_Data_Types.pdf Lecture 7 Slides].
|  
+
|
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 15 Feb.
 
| Wed. 15 Feb.
 
| 8
 
| 8
| Queues
+
| Containers, Dictionaries, and Lists I
| 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.
+
| Container and dictionaries: mechanisms for accessing data in a list. List ADT. Implementation with arrays.
|  
+
| [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]] -->
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 20 Feb.
 
| Mon. 20 Feb.
 
| 9
 
| 9
| Trees I
+
| Containers, Dictionaries, and Lists II
| 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
+
| List ADT.  Implementation with linked lists. Doubly linked lists and circular lists. Performance considerations.
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
+
|  [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;"
 
| Wed. 22 Feb.
 
| Wed. 22 Feb.
 
| 10
 
| 10
| Trees II
+
| Stacks
| 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
+
| 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_Lecture_10_Stacks.pdf Lecture 10 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 27 Feb.
 
| Mon. 27 Feb.
 
| 11
 
| 11
| Heaps I
+
| Queues
| 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.
+
| 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_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;"
 
| Wed. 1 Mar.
 
| Wed. 1 Mar.
 
| 12
 
| 12
| Heaps II
+
| Trees I
| Priority queues. Operating systems heaps. Implementation of heap. Heap sort. d-ary heaps. Leftist 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
|
+
|  [http://www.vernon.eu/04-630/04-630_Lecture_12_Trees_I.pdf Lecture 12 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 6 Mar.
 
| Mon. 6 Mar.
 
| 13
 
| 13
| Graphs I
+
| Trees 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. Topological sort. Euler's theorem. Graph traversal: breadth-first and depth-first, uses of. Depth-first search and maze traversal.
+
| Binary trees and binary search trees. Tree traversals: inorder, preorder, postorder.  
|
+
|  [http://www.vernon.eu/04-630/04-630_Lecture_13_Trees_II.pdf Lecture 13 Slides].
|
+
| [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
| Graphs II
+
| Trees III
| 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.
+
| Height-balanced trees: AVL Trees, RR, RL, LR, LL rotations.
|  
+
| [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]] -->
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 13 Mar.
 
| Mon. 13 Mar.
 
| 15
 
| 15
| Complex Networks I
+
| Trees IV
| Complex systems and large networks. Random networks. Degree distribution. Clustering. Small world phenomena.
+
| Height-balanced trees: Red-Black Trees, single promotion, zig-zag promotion, recolouring and restructuring.
|  
+
|  [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]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 15 Mar.
 
| Wed. 15 Mar.
 
| 16
 
| 16
| Complex Networks II
+
| Trees V
| Scale free networks. Community detection. Network evolution.
+
| Tree applications. Fixed-length codes & variable length codes. Optimal code trees. Huffman's algorithm. <!-- and implementation. -->
|  
+
| [http://www.vernon.eu/04-630/04-630_Lecture_16_Trees_V.pdf Lecture 16 Slides].
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 20 Mar.
 
| Mon. 20 Mar.
 
| 17
 
| 17
| Hashing I
+
| Heaps
| Using keys to address data
+
| 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. -->
Mappings: injection, surjection, bijection
+
| [http://www.vernon.eu/04-630/04-630_Lecture_17_Heaps.pdf Lecture 17 Slides].
Map ADT
+
| [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]
Hash functions
+
Hash tables: current value tables, direct access tables. Managing collisions: chaining, overflow areas, re-hashing, linear probing, quadratic probing
+
|  
+
|  
+
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 22 Mar.
 
| Wed. 22 Mar.
 
| 18
 
| 18
| Hashing II
+
| Graphs I
| Evaluating hash functions: prime division, mid-square, folding, load factor. Example application: dictionaries. Generating hash functions and using hash structures.
+
| 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-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]] -->
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 27 Mar.
 
| Mon. 27 Mar.
 
| 19
 
| 19
| Algorithmic Strategies
+
| Graphs 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.
+
| 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]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 29 Mar.
 
| Wed. 29 Mar.
 
| 20
 
| 20
| Analysis of Correctness
+
| Graphs III
| 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.
+
| Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm.
Pair programming. Verification and validation strategies.
+
|  [http://www.vernon.eu/04-630/04-630_Lecture_20_Graphs_III.pdf Lecture 20 Slides]
|
+
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Mon. 3 Apr.
 
| Mon. 3 Apr.
 
| 21
 
| 21
| Databases
+
| Graphs IV
| Relational databases, hierarchical databases, NoSQL databases. Relational databases: entity relationship modelling, relational algebra, SQL.
+
| 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]
|  
+
| [http://www.vernon.eu/04-630/04-630_Lab_Exercise_5.pdf Lab Exercise 5]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
 
| Wed. 5 Apr.
 
| Wed. 5 Apr.
 
| 22
 
| 22
| Databases II
+
| Complex Networks I
| Normalization. Compression strategies, dictionary algorithm, LZ algorithm. File structure strategies.
+
| Euler's theorem: the Bridges of Königsberg. Networks vs. graphs. Degree, average degree, and degree distribution. Bipartite networks. Path length, BFS, Connectivity, Components.  Clustering coefficient.  Random graph model. Small world phenomena. Scale free networks. 
|  
+
| [http://www.vernon.eu/04-630/04-630_Lecture_22_Complex_Networks_I.pdf Lecture 22 Slides]
|  
+
|   [http://www.vernon.eu/04-630/04-630_Assignment_6.pdf Assignment 6] <!-- <BR> [[Assignment 6 Status]] -->
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
| Mon. 17 Apr.
+
| Wed. 19 Apr.
 
| 23
 
| 23
| Programming Paradigms I
+
| Complex Networks II
| Imperative programming. Logic programming. Functional programming. OO programming; classes; type, operational and functional polymorphism; inheritance, attributes, methods, instantiations, abstract classes, object-oriented languages.  
+
| Communities. Fundamental Hypothesis. Connectedness and Density Hypothesis. Strong and weak communities. Graph partitioning. Community detection. Hierarchical clustering. Girvan-Newman Algorithm. Modularity. Random Hypothesis. Maximum Modularity Hypothesis. Greedy algorithm for community detection by maximizing modularity. Overlapping communities. Clique percolation algorithm and CFinder.
|  
+
| [http://www.vernon.eu/04-630/04-630_Lecture_23_Complex_Networks_II.pdf Lecture 23 Slides]
 
|  
 
|  
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
| Wed. 19 Apr.
+
| Mon. 24 Apr.
 
| 24
 
| 24
| Programming Paradigms II
+
| Algorithmic Strategies
| 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
+
| Classes of algorithms. Brute force. Divide and conquer. Greedy algorithms. Dynamic programming. Combinatorial search. Backtracking.  Pruning. Branch and bound. <!-- Heuristics and heuristic algorithms. Probabilistic algorithms. -->
|
+
|  [http://www.vernon.eu/04-630/04-630_Lecture_24_Algorithmic_Strategies.pdf Lecture 24 Slides]
|  
+
| [http://www.vernon.eu/04-630/04-630_Lab_Exercise_6.pdf Lab Exercise 6]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
| Mon. 24 Apr.
+
| Wed. 26 Apr.
 
| 25
 
| 25
| Automata Theory
+
| Hashing
| Regular Languages. Finite Automata. Nondeterminism. Regular Expressions. Nonregular Languages. Context-free Languages. Context-free Grammars. Pushdown Automata. Deterministic Context-Free Languages.
+
|Dictionaries. Hashing. Hash functions. Collision resolution. Complexity. Applications. <!-- 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. -->
|  
+
| [http://www.vernon.eu/04-630/04-630_Lecture_25_Hashing.pdf Lecture 25 Slides]
|  
+
| [http://www.vernon.eu/04-630/04-630_Assignment_7.pdf Assignment 7]
 
|- style="vertical-align: top;"
 
|- style="vertical-align: top;"
| Wed. 26 Apr.
+
| Wed. 3 May
 
| 26
 
| 26
| Computability Theory
+
| Analysis of Correctness
| The Church-Turing Thesis. Turing Machines. Variants of Turing Machines. The Definition of Algorithm. Decidability. Decidable Languages. Undecidability. Reducibility.
+
|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.
 +
|  [http://www.vernon.eu/04-630/04-630_Lecture_26_Analysis_of_Correctness.pdf Lecture 26 Slides]
 
|  
 
|  
|
+
<!-- |- style="vertical-align: top;"
|- style="vertical-align: top;"
+
 
| Wed. 3 May
 
| Wed. 3 May
 
| 27
 
| 27
| Final Presentations
+
| Automata & 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.
 
|  
 
|  
 
|  
 
|  
 +
-->
 
|}
 
|}
 
</small>
 
</small>

Latest revision as of 09:23, 28 April 2017

|CARNEGIE MELLON UNIVERSITY AFRICA|

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 Lab Exercise 5
Wed. 5 Apr. 22 Complex Networks I Euler's theorem: the Bridges of Königsberg. Networks vs. graphs. Degree, average degree, and degree distribution. Bipartite networks. Path length, BFS, Connectivity, Components. Clustering coefficient. Random graph model. Small world phenomena. Scale free networks. Lecture 22 Slides Assignment 6
Wed. 19 Apr. 23 Complex Networks II Communities. Fundamental Hypothesis. Connectedness and Density Hypothesis. Strong and weak communities. Graph partitioning. Community detection. Hierarchical clustering. Girvan-Newman Algorithm. Modularity. Random Hypothesis. Maximum Modularity Hypothesis. Greedy algorithm for community detection by maximizing modularity. Overlapping communities. Clique percolation algorithm and CFinder. Lecture 23 Slides
Mon. 24 Apr. 24 Algorithmic Strategies Classes of algorithms. Brute force. Divide and conquer. Greedy algorithms. Dynamic programming. Combinatorial search. Backtracking. Pruning. Branch and bound. Lecture 24 Slides Lab Exercise 6
Wed. 26 Apr. 25 Hashing Dictionaries. Hashing. Hash functions. Collision resolution. Complexity. Applications. Lecture 25 Slides Assignment 7
Wed. 3 May 26 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. Lecture 26 Slides



Back to Data Structures and Algorithms for Engineers