CS 1332 – Data Structures and Algorithms

 

Overview:

The purpose of this course is to give students a thorough introduction to computer data structures and algorithms in the context of object-oriented programming. It is also expected that students will gain experience and practice with sophisticated object-oriented programming. The focus in the course is on developing skills and experience in individual person software development.

 

Prerequisites:

The course assumes that students enter with a thorough understanding of programming in an object-oriented language (currently, Java), including knowledge of polymorphism, exception handling, graphical user interfaces, and algorithm complexity analysis.

 

Course Objectives:

Data Structures and Algorithms

Students will gain an understanding of fundamental and important data structures and algorithms (noted in course description below). This knowledge will include how the data structures and algorithms are constituted and work, when to use particular data structures and algorithms, how to code the data structures and algorithms, and informal understanding of their algorithm complexity.

Algorithm Design

Students will be introduced to advanced topics in algorithm design, including parallel programming (utilizing multiple threads of control), heuristic algorithms, and divide-and-conquer techniques.

 

Object-Oriented Programming—Concepts

Students will gain additional experience and become skilled with object-oriented programming concepts such as classes, objects, data abstraction, inheritance, polymorphism, dynamic binding, and exception handling.

 

Object-Oriented Programming—Practice

Students will be able to write object-oriented programs given an algorithm or design document as the basis of the implementation. Students will become more skilled at developing algorithms and programs given only problem statements. Students will be able to write, test, and debug moderate size (500-1000 lines of code) programs. The primary focus will be individual skills and abilities.

 

Problem Solving

Students will gain additional abilities and sophistication in being able to take a written problem statement, determine the nature of the data provided and the results expected, produce a well-documented program that satisfies this specification, and systematically test their program. Students will produce modular programs, using good abstraction and with limited coupling between program elements.

 

Prerequisites:

Programming Language	(Currently) Java
Programming Concepts	References vs. pointers, activation stacks, dynamic memory allocation (heaps)
Object Oriented Programming	Objects, methods, class vs instance variables, inheritance, polymorphism, I/O, exceptions, GUIs, sockets
Elementary Data Structures	Arrays, linked lists, circular and doubly-linked lists, binary trees
Algorithms	Complexity analysis, asymptotic notation (big-oh), binary search, O(n2) sorting, text processing

 

Course Topics:

Linked Data Structures	Queues, stacks, trees, recursive and iterative tree traversal (pre, in, post, level order)
Searching	Binary search trees (BSTs), balanced BSTs (AA trees), n-ary trees (B trees), priority queues, hash tables
Sorting	O(n lg n) sorts (heapsort, mergesort, quicksort), bucket sort, why you can’t sort faster than O(n lg n)
Graphs	Graph concepts, brute force search (depth-first, breadth-first), heuristic search (best-first, least-cost, greedy (hill climbing, beam search), optimal-admissable (A*)), Dijsktra’s algorithm, minimal spanning tree (Prim’s, Kruskal’s), maximal flow
Text Processing	Tries, data compression (Huffman encoding), string matching (KMP algorithm)
Cryptography	Encryption, decryption, numerical algorithms, digital signatures, public key cryptography (RSA)
Networking	Sockets, network I/O (reading URLs), basic client-server model
Parallel Programming	Threads, concurrency
Advanced Algorithm Design	Included in above topics: Parallel programming, heuristic and greedy algorithms, backtracking, divide-and-conquer. Optional special topics: genetic algorithms, neural networks, dynamic programming, simulated annealing, randomized algorithms, quantum computing, vector spaces, …