AT70.02 Data Structures and Algorithms

Fundamentals, Sorting, Searching, String Processing, Geometric Algorithms, Graph Algorithms, Parallel and Distributed Algorithms, Computational Complexity.CSIM Logo WelcomeCourses
Faculty, Student, Staff
Projects and reports
Conferences, workshop and seminars
Laboratories and reasearch facilities
Information related to CSIM
Information non-related to CSIM
Address, map, phone, etc.
Search

Semester:
August

Rationale:
An algorithm describes how to carry out a problem-solving task implementable by computer programs. The design of an algorithm is tightly coupled with how information to be manipulated by it is organized i.e. data structuring. A course in Algorithm and Data Structure is therefore fundamental to a study in Computer Science.

Catalog Description:
Fundamentals, Sorting, Searching, String Processing, Geometric Algorithms, Graph Algorithms, Parallel and Distributed Algorithms, Computational Complexity.

Credits:
3(3-0)

Prerequisite:
None

Course Outline:
Fundamentals
  1. Elementary Data Structures
  2. Trees
  3. Recursion
  4. Analysis of Algorithms
Sorting
  1. Elementary Sorting Methods
  2. Quicksort
  3. Radix Sorting
  4. Priority Queues
  5. Mergesort
  6. External Sorting
Searching
  1. Elementary Searching Methods
  2. Balanced Trees
  3. Hashing
  4. Radix Searching
  5. External Searching
String Processing
  1. String Searching
  2. Pattern Matching
  3. Parsing
  4. File Compression
  5. Cryptology
Geometric Algorithms
  1. Elementary Geometric Methods
  2. Finding the Convex Hull
  3. Range Searching
  4. Geometric Intersection
  5. Closest-Point Problems
Graph Algorithms
  1. Elementary Graph Algorithms
  2. Connectivity
  3. Weighted Graphs
  4. Directed Graphs
  5. Network Flow
  6. Matching
Parallel and Distributed Algorithms
  1. Model of Parallel Computations
  2. Parallel Graphs Algorithms
  3. Parallel Sorting
  4. Distributed Computation
Computational Complexity

Textbook:
Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching. Addison-Wesley, 2002.
Algorithms in Java, Part 5: Graph Algorithms. Addison-Wesley, 2003.

Reference Books:
E. Horowitz, S. Shani:
Fundamentals of Data Structures, Pittman, 1977.
D.E. Knuth:
The Art of Computer Programming, Vols. 1 to 3, Addison-Wesley, Massachusetts, 1973.
R.L. Kruse:
Data Structures and Program Design, Prentice-Hall, Englewood Cliffs, 1984.
J.P. Tremblay, P.G. Sorenson:
An Introduction to Data Structures with Applications, Second Edition, McGraw-Hill, 1984.
G. Brassard and P. Bratley:
Fundamentals of Algorithms, Prentice Hall, 1996.
M. A. Weiss:
Data Structure and Algorithm Analysis in C, Addison Wesley, 1997.

Journals and Magazines:
Algorithmica
Information Processing Letters (IPL)
Journal of the ACM
Journal of Algorithms

Grading System:
The final grade will be computed from the following constituent parts: mid-semester exam (40%), final exam (50%) and assignments/projects (10%).Closed-book examination is used for both mid-semester and final exam.

Instructor:
Dr. Paul Janecek

CSIM home pageWMailAccount managementCSIM LibraryNetwork test toolsSearch CSIM directories
Contact us: Olivier Nicole CSIM    SET    AIT Last update: Jul 2005