04-630   Data Structures and Algorithms for Engineers

Location: Africa

Units: 12

Semester Offered: Spring

 Course description

This course will provide engineers with a background in algorithms, data structures, and their practical uses. An engineer who may already know programming will be able to learn the foundational aspects of how to design more efficient code that can reduce memory and CPU footprint. 
 
The course begins by delving into a few algorithms and data structures that are routinely used by programmers. We then explore more efficient implementations of these constructs. Abstract data types are introduced, and the course provides an in-depth treatment of applications like searching, sorting, lists, stacks, and queues. The course will also cover trees, graphs, and algorithmic strategies. Performance analysis and tractability of algorithms, time/space complexity, automaton, and computability will also be discussed. Time permitting, the course will touch upon multi-threading, logging, testing, verification, and validation.
 
The course will be graded primarily on the basis of several programming assignments given during the semester, surprise quizzes, and two programming exams. All programming assignments will be in C++, and the lectures would involve studying C++ code.

Learning objectives

  • Recognize and analyze critical computational problems, generate alternative solutions to problems, and assess their relative merits.
  • Understand factors that influence algorithmic performance and memory consumption.
  • Design, implement, and document appropriate, effective, and efficient data structures & algorithms for a variety of real-world problems.

Outcomes

The successful student will be able to:
  • Write computer programs in C++ and use CMake/GCC to compile code.
  • Create algorithm solutions to a variety of problems that can be solved on computational devices.
  • Explain solutions using pseudo code, flowcharts, and other tools.
  • Optimize a solution for run-time, memory, or both.
  • Explain the theoretical and practical aspects of a variety of computer algorithms.

Content details

  • Representing algorithms
  • Complexity theory, tractability, and decidability.
  • Asymptotic complexity analysis
  • Sorting and searching algorithms
  • Abstract data types
  • Arrays, lists, stacks, & queues
  • Trees- binary trees, binary search trees, height-balanced trees.
  • Graphs- graph representation, graph traversal, topological sorting, shortest path algorithms, minimum spanning tree algorithms
  • Hashing: hash functions, collision resolution, complexity, applications
  • Heaps and priority queues
  • Matrix operations, B-trees, Fibonacci heaps
  • Algorithmic strategies: brute force, divide and conquer, greedy algorithms, dynamic programming, combinatorial search and backtracking, branch and bound
  • Algorithm correctness, testing, verification, and validation

Prerequisites 

Prior knowledge of coding in C or C++ would help greatly.

Faculty

George Okeyo