COE428 Course Outline spring 2016 


Introduction

Engineering Algorithms & Data Structures (COE 428) deals with the fundamental means to approach the design and analysis of algorithms in an effective and methodologically correct manner. The student will acquire knowledge about general techniques for the design and analysis of algorithms as well as a collection of significant examples of solutions to representative problems. Furthermore, the student will have the opportunity to supplement the theory by writing actual programs in the C language  during laboratory sessions.

Course Objectives

At the conclusion of this course the student will have learned the following:
  1. Structured methods for engineering software design
  2. Process of the problem-to-program and an introduction to "big O" and "big Omega" notation.
  3. Principal internal sorting algorithms: quicksort, heapsort, binsort, and the simpler, less efficient methods such as insertion sort. Linear-time algorithms are also covered.
  4. Traditional list, stack and queue structures. Also, mapping an abstract data type based on the mathematical notion of a function.
  5. Introduction to abstract data types based on the mathematical model of a set. Implementations of stacks and queues. Introduction to hash tables and binary search trees.
  6. Graphs, including directed and undirected graphs, for the implementation of graph algorithms. Introduction to data structures for graph representation. Presentation of a number of graph algorithms, including depth-first search, generating minimal spanning trees, shortest paths, etc.
  7. Asymptotic analysis of recursive procedures, including recurrence relations.
 

8. Introduction to designing algorithms, dynamic programming, local search algorithms, and various forms of tree searching.

 

9. Analysis of algorithm complexity.

Course Outline

The following table gives a brief overview of the course topics and assignments.

 

 

Week

Topic

Lab

1 (Jan 9)

Introduction. Course overview. Introduction to algorithms 

 

2 (Jan 16)

Recursion 

Lab 1

3 (Jan 23)

Complexity analysis

Lab 2

4 (Jan 30)

 Data Structure 

Lab 3

5 (Feb 6)

Stacks and queues

Lab

6 (Feb 13)

Hashing

Lab

    

 Study week

Lab

7 (Feb 27)

 Trees and Priority Queues
 Mid term

Lab

8 Mar 6)

Binary Search Trees

 Lab

9 (Mar 13)

Balanced BSTs (including Red-Black Trees)

Lab

10 (Mar 20)

Graphs

Lab

11 (Mar 27)

Elementary Graph Algorithm

Lab

  12 (April 3)  Elementary Graph Algorithm

Lab

13 (April 10)

Review

Lab

Marking Scheme

The following table summarizes the marking scheme for the course.

 

Projects:

30%

Midterm:

25%

Final exam:

45%

You must pass both the lab and theoretical portions of the course to get credit for the whole course. Late projects will not be accepted and will receive a mark of 0

Instructors

References

Textbooks

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms, MIT, 2002, ISBN: 0-07-013151-1 (McGraw-Hill)


Other References

3. Knuth, Donald Ervin, The Art Of Computer Programming (3 volumes) Addison-Wesley, 1977. This is the classic book on computer programming, algorithms, and data structures. It is very mathematical and also has extensive problems and solutions.

4. Brian W. Kernighan and Rob Pike, The Practice of Programming, Addison-Wesley, 1999, ISBN:0-201-61586-X, 267 pages. This excellent book will help you hone your programming skills in any language (although the emphasis is on C).

5. Standish, Thomas A., Data Structures, Algorithms and Software Principles in C, Addison-Wesley 1995, ISBN: 0-201-59118-9

6.Brian W. Kernighan, Dennis Ritchie, The C Programming Language, Prentice-Hall, 2nd edition 1988. This is the classic book on C, written by the language developers.


R. Sedaghat