Data Structures and Algorithms for Engineers
David Vernon
Carnegie Mellon University Africa in Rwanda
vernoncmu.edu
Course Description 
Learning Objectives 
Content 
Lecture Notes 
Course Textbook 
Recommended Reading 
Software 
Useful Links
Course Description
The primary objective of the course is to provide engineers without formal training in computer science, a solid background in the key principles of computer science, in general, and of the algorithms and datastructures, in particular. The key purpose of this course is to complement the experience that engineers may already have in writing software with formal computer science underpinnings, making those engineers more capable in developing software intensive systems.
The course begins by considering the main phases of the software development lifecycle, from requirements elicitation, to computational modelling, system specification, software design, implementation, and software quality assurance, including various forms of testing, verification, and validation. Then, building on the concept of abstract data types, the course provides an in indepth treatment of the key elements of algorithms and datastructures, beginning with the fundamentals of searching, sorting, lists, stacks, and queues, but quickly progressing to more advanced topics, including trees, graphs, and algorithmic strategies. It also covers the analysis of the performance and tractability of algorithms, finishing with automata theory and computability theory. A key focus of the course is on effective implementation and good design principles.
Back to Top
Learning Objectives
After completing this course, students should be able to:
 Recognize and analyze critical computational problems, generate alternative solutions to problems, and assess their relative merits.
 Understand, analyze, and characterize those factors that influence algorithmic computational performance and memory consumption.
 Design, implement, and document appropriate, effective, and efficient data structures & algorithms for a variety of realworld problems.
 Understand detailed software structures and their underlying strengths and weaknesses.
 Perform detailed, codelevel design and document the design in an understandable way.
Back to Top
Course Content
Introduction & The Software Development Life Cycle
 Goals, outcomes, and syllabus. Assignments, labs, and exercises. Software development tools for assignments.
 Levels of abstraction.
 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, reuse, hybrid, spiral.
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.
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, 3colour problem, SAT, cliques.
 Determinism and nondeterminism.
 P, NP, and NPComplete classes of algorithm.
Searching and Sorting Algorithms
 Linear and binary search (iterative and recursive).
 Inplace sorts: bubblesort (efficient and inefficient), selection sort, insertion sort.
 Notinplace 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.
Abstract Data Types (ADT)
 Astract Data Types (ADT).
 Information hiding.
 Types and typing.
 Design Goals.
 Design practices.
Containers, Dictionaries, and Lists
 Container and dictionaries: mechanisms for accessing data in a list.
 List ADT. Implementation with arrays.
 List ADT. Implementation with linked lists.
 Doubly linked lists and circular lists.
 Performance considerations.
Stacks
 Stack (LIFO) ADT.
 Implementation using List ADT (array and linkedlist).
 Comparison of order of complexity.
 Stack applications, including token matching, evaluation of postfix expressions, and conversion of infix expressions to postfix.
Queues
 Queue (FIFO ADT).
 Implementation using List ADT (array and linkedlist).
 Comparison of order of complexity.
 Dedicated ADT.
 Circular queues. Queue applications.
Trees
 Concepts and terminology: level, height, external and internal nodes, skinny, fat, complete, leftcomplete, perfect, multiway, dary.
 Types of tree: binary, binary search, multiway, dary, ab.
 Binary tree ADT.
 Binary trees and binary search trees.
 Tree traversals: inorder, preorder, postorder
 Heightbalanced trees: AVL Trees, RR, RL, LR, LL rotations.
 Heightbalanced trees: RedBlack Trees, single promotion, zigzag promotion, recolouring and restructuring.
 Fixedlength codes & variable length codes. Optimal code trees. Huffman's algorithm.
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.
Graphs
 Types of graph: directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, nonsimple, implicit, explicit, embedded, topological.
 Adjacency matrix representation.
 Adjacency list representation.
 Graph traversal: breadthfirst search (BFS); implementation and application.
 Application of BFS.
 Graph traversal: depthfirst search (DFS); implementation and application.
 Topological sort.
 Spanning trees and minimum spanning trees, Kruskal's algorithm, Prim's algorithm.
 Dijkstra's shortest path algorithm.
 FloydWarshall's allpairs algorithm.
Algorithmic Strategies
 Classes of algorithms.
 Brute force.
 Divide and conquer.
 Greedy algorithms.
 Dynamic programming.
 Combinatorial search.
 Backtracking.
 Pruning.
 Branch and bound.
Complex Networks
 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.
 Communities.
 Fundamental Hypothesis.
 Connectedness and Density Hypothesis.
 Strong and weak communities.
 Graph partitioning.
 Community detection.
 Hierarchical clustering.
 GirvanNewman Algorithm.
 Modularity.
 Random Hypothesis.
 Maximum Modularity Hypothesis.
 Greedy algorithm for community detection by maximizing modularity.
 Overlapping communities.
 Clique percolation algorithm and CFinder.
Hashing
 Dictionaries.
 Hashing.
 Hash functions.
 Collision resolution.
 Complexity.
 Applications.
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 Notes
Lecture 1: Introduction & The Software Development Life Cycle
Lecture 2: Formalisms for Representing Algorithms
Lecture 3: Analysis of Complexity I
Lecture 4: Analysis of Complexity II
Lecture 5: Searching and Sorting Algorithms I
Lecture 6: Searching and Sorting Algorithms II
Lecture 7: Abstract Data Types (ADT)
Lecture 8: Containers, Dictionaries, and Lists I
Lecture 9: Containers, Dictionaries, and Lists II
Lecture 10: Stacks
Lecture 11: Queues
Lecture 12: Trees I
Lecture 13: Trees II
Lecture 14: Trees III
Lecture 15: Trees IV
Lecture 16: Trees V
Lecture 17: Heaps
Lecture 18: Graphs I
Lecture 19: Graphs II
Lecture 20: Graphs III
Lecture 21: Graphs IV
Lecture 22: Graphs V
Lecture 23: Algorithmic Strategies
Lecture 24: Complex Networks I
Lecture 25: Complex Networks II
Lecture 26: Complex Networks III
Lecture 27: Hashing
Lecture 28: Analysis of Correctness
Back to Top
Course Textbook
Alfred V. Aho, Jeffrey D. Ullman, and John E. Hopcroft, Data Structures and Algorithms.
David Harel and Yishai Feldman, Algorithmics: The Spirit of Computing, Third Edition.
Back to Top
Recommended Reading
S. Skiena, The Algorithm Design Manual, 2nd Edition, Springer (2012). (a selection of examples will be taken from this book).
T. Cormen et al., Introduction to Algorithms, 3rd Edition, MIT Press (2009).
Back to Top
Software Development Environment
Click here for a stepbystep guide to downloading, installing, and using the software required to run examples and complete the assignments.
Back to Top
Useful Links
Algorist.com
This is Steven Skiena's website with lots of resources related to his book, The Algorithm Design Manual, including teaching material and sample programs.
Back to Top
David Vernon's Personal Website
