default picture

Welcome to the NEW COE428 Homepage!

 

COE 428 Engineering Algorithms and Data Structures

 

Basic data structures (arrays, pointers), abstract data structures (trees, lists, heaps), searching, sorting, hashing, recursive algorithms, parsing, space-time complexity, NP-complete problems, software engineering and project management, object-oriented data structures, case studies and lab exercises will be implemented using the C programming language.

 

Lect: 3 hrs./Lab: 2 hrs.

Prerequisite: All required first year courses.

 

 

This course provides the student with the fundamental means to approach the design and analysis of algorithms in an effective and methodologically correct manner. The student will acquire knowledge of general techniques for the design and analysis of algorithms and will be provided with a collection of significant examples of representative problems. Furthermore, the student will have the opportunity to supplement the theoretical concepts with programming in the C language during laboratory sessions.
 
Data structure describes an arrangement of data in a computer's  memory, i.e. disk storage. Arrays, linked lists, queues, stacks, binary  trees, and hash tables are examples of common data structures.

Algorithms are implemented for the manipulation of data contained in these data structures. Many algorithms can be applied directly to a specific data structure. When working with certain data structures the ability to insert new data, search for and/or delete a specific item is essential.

Common algorithms are applied in order to search for a particular data item (or record)
  • sort the data using, for example, simple sorting or advanced sorting
  • iterate through all the items in a data structure. (visit each item in turn so as to display it or perform some other action on each item)

The foundation of the course consists of:
  • the concepts of algorithm, time, and space complexity
  • methods and subject of analysis
  • dependence on input: best case, worst case, average case
  • divide and conquer
  • asymptotic notation

Building upon this foundation, the main topics covered in the course include:

 

  • Recurrence equations, which are solved using the iterative, substitution, master and recursion tree methods.

 

  • Sorting is one of the problems in computer science for which the most algorithms including Heapsort, Mergesort, Quicksort, etc. seem to have been developed.
 
  • Elementary data structures can include dynamic sets, basic operations. stack, queue, lists, doubly linked lists, etc.

 

A further topic will include binary trees, including binary search trees, (properties and operations) as well as red-black search trees (properties and operations).
Finally, the properties and representation of graphs will be presented. Graph algorithms such as Breadth-first search, Depth-first search, Single source shortest paths in graphs with non negative weights (Dijkstra), etc. will also be discussed. Many computer engineering problems such as chip design & test, and networking problems can be solved by modeling the problem as a graph and optimized using different graph algorithms.