The BRADLEY DEPARTMENT of ELECTRICAL and COMPUTER ENGINEERING

Undergraduate PROGRAMS

Course Information

Description

Introduces fundamental data structures, algorithms, and abstract data types. Main topics include data structures such as arrays, linked lists, stacks, queues, graphs, and trees, and algorithms such as those that are used for list manipulation, graph searches, sorting, searching, and tree traversals. Implementation of data structures and algorithms in C++.

Why take this course?

This is the second course in computer programming for Computer Engineering (CpE) majors and is based on the recommended curriculum of the Association for Computing Machinery (ACM). It provides the foundation for other courses in the CpE curriculum such as Object-Oriented Design, Data Structures and File Management, and Operating Systems. The course covers the fundamentals of computer programming including data structures such as arrays, lists, stacks, queues, and trees, and algorithms such as list manipulation, sorting, graph searches, and tree traversals. The course thus provides a foundation for CpE students in computer programming.

Required for all CPE majors

Prerequisites

C- or better in 1574

This course presupposes the ability to program in the beginning language C++; completion of prerequisites would suffice.

Major Measurable Learning Objectives

  • design algorithms for solving problems that use data structures such as arrays, linked lists, stacks, queues, graphs, and trees, and algorithms such as those that are used for list manipulation, graph manipulation (e.g., depth-first search), sorting, searching, and tree traversals
  • implement algorithms in C++ using good programming style.

Course Topics

Topic

Percentage of Course

Algorithm Design Methodology
  • Top-down design
  • Hierarchical modularization
  • Stepwise refinement
5%
Abstract Data Types
  • Information hiding
  • Encapsulation
  • Physical vs. Logical abstraction
  • Design and implementation of list ADTs using arrays and linked lists
20%
Recursion in Programming and Problem Solving
  • Recursive valued functions: Factorial
  • Classical problems: Ackermann’s function, 8-Queens problem,
  • Towers of Hanoi, detecting palindromes
  • Relation to mathematical induction
10%
Stacks
  • Stack ADT
  • Implementation using arrays, linked lists, and list ADTs
  • Applications: Checking balanced braces, recognizing strings, depth-first searches on graphs
10%
Queues
  • Queue ADT
  • Implementation using arrays, linked lists, and list ADTs
  • Applications: breadth-first searches, recognizing palindromes
10%
Searching Techniques
  • Sequential search
  • Binary search
5%
Sorting Algorithms
  • Selection sort, Bubble sort, Insertion sort, Mergesort
  • Non-comparison-based sorting: Counting sort
15%
Introduction to Algorithm Analysis
  • Algorithm comparison
  • Big O notation
  • Orders of magnitude
  • Analysis of sorting and searching algorithms
10%
Trees
  • Introduction, Terminology
  • Binary Trees
  • Tree Traversals
  • Applications: Huffman’s algorithm
15%