Applied Data Structures and Algorithms: CPE 593

Instructor:

Dr. Narayan Ganesan
Classroom: Babbio Center(BC) 304.
Contact: nganesan@stevens.edu.
Tu: 3:00-5:30p

Summary:

Course Objectives

  • This course will introduce and familiarize the students with data structures and algorithms for solving real problems that arise frequently in a variety of practical applications.
  • Principles and techniques of computational complexity.
  • Design and analyze new algorithms, via dynamic programming, greedy strategy, approximation methods

Prerequisites


Knowledge of C++ programming and CPE 360
OR
an equivalent undergraduate-level course of data structures and algorithms

Textbook

Introduction to Algorithms, 2nd Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press.

Reference Books

Data Structures, Algorithms, and Applications in C++, 2nd Edition, Sartaj Sahni, Silicon Press.

Main Topics

  • Methods for expressing and comparing complexity of algorithms: worst and average cases lower bounds on algorithm classes, verification of correctness
  • Application of such analysis to sorting: heap sort, merge sort, bubble sort, quick sort, shell sort, insertion sort, radix sorting
  • Elementary data structures: arrays, stacks, queues, linked lists, heaps, trees, hashing
  • Advanced data structures: binary search trees, B-trees, AVL trees, binomial heaps, Fibonacci heaps
  • Graph algorithms: breadth-first search, depth-first search, minimum spanning trees, single-source shortest paths
  • NP-complete and NP-hard problems
  • Algorithm design: greedy algorithms, dynamic programming, divide and conquer, approximation algorithms.

Grading

Homework(5 homeworks, 10% each): (50%) There will be regular homework assignments including theory problems and programming assignments.
Midterm: (20%) There will be one midterm exam.
Final Exam: (25%) There will be a final exam. The final exam is comprehensive.
Class Attendance: (5%) It is important to attend lectures and provide course evaluation at the end.
All exams are close book and close notes.

Expected Work

Students are expected to attend all lectures and perform all reading assignments in the course notes and textbook. Students will be evaluated according to their performance on class attendance, homework, midterm and final exam.

Working Together and Academic Honesty

Cheating on homework and exams will not be tolerated. We want to protect the fairness and integrity of the class. The students can discuss about the course materials and homework problems together. But each student needs to write his/her own solutions so that to make sure everyone fully understand the concepts introduced in this course.

Lecture Schedule – (Subject to Change):

Week1 (08/28): Review of C++, arrays, pointers, functions, templates, exceptions. Introduction to greedy algorithms CodeSample1
CodeSample2
CodeSample3
Week2 (09/04): Greedy Algorithms, Performance, lower bounds, Linear Lists, Linked Lists, Matrices and Sparse Matrices Assignment 1
Week3 (09/11): Stacks, Queues
Week4 (09/18): Priority Queues, Hashing
Week5 (09/25): Sorting, quicksort, radix sort Assignment 2
Week6 (10/02): Heaps, trees, graphs
Week7 (10/09): No Class
Week8 (10/16): Introduction to Dynamic programming - I Assignment 3
Week9 (10/23): Dynamic programming - II, complexity analysis, optimal substructure
Week10 (10/30): Midterm Examination Assignment 4
Week11 (11/06): Algorithmic time-Complexity analysis
Week12 (11/13): Polynomial, NP hard, NP complete
Week13 (11/20): Approximation Algorithms Assignment 5
Week14 (11/27): Approximation Algorithms II- Adversery Strategies
Week15 (12/04): Final Examination(Tentative Schedule)