The subject of this course is data structures and algorithms. A
data structure is an arrangement of data in a computer’s memory (or sometimes
in a disk). In this course you will learn ways to structure and arrange data in computer’s memory
that includes array, linked lists, stacks, trees, hashtables, graphs, among
others. Algorithms manipulate that
data in these structures in various ways, such as searching for a data item and
sorting a set of data elements. In this
class you will learn several concepts including how organize data elements, how
to delete, insert, edit and search for a data element in a specific data
structure and how to sort a set of data elements. You will also learn the
differences between different data structures and when to use to use the right
ones to solve problems. An engineer is constantly solving
problems. You will be introduced in this class to practical problems to solve
using data structures such as utilizing data structures such as
linked-lists and arrays to implement a course registration tool, storing and
sorting courses and students’ information data, modeling social network data
using a graph data structure, and applying sorting and graph algorithms to
analyze social network data (e.g. potential online community detection) The programming language adopted in this
class is Java, at the beginning of the semester you will have a review of the
object oriented programming paradigm and some of its features such as
inheritance, abstraction, encapsulation and polymorphism.
Motivation. Importance of understanding data structures and
algorithms, the emerging field of data science and its intersection with data
structures in computer science, the job market and acquiring a skill of
computer programming.
Introduction. Overview of data structures, Overview of
algorithms. Overview of Software Engineering lifecycle. Review of basic object oriented programming
using Java.
Features of the Object Oriented Paradigm and Related Concepts. Abstraction.
Encapsulation. Inheritance. Polymorphism. Interfaces including comparable
interfaces. Abstract Classes. Abstract
data types (ADT). ADT for list, stack, queue. Array-based implementation of
lists, stack and queue. Algorithms:
Prefix, Postfix, Infix notations and expression evaluation. Reading: Class
notes, DJW ch.1, Liang book.
Recursion.
Thinking recursively to solve a problem using
algorithms. Practical recursive algorithms. Stacks data structure. Recursion. Reading: DJW ch. 14, Liang ch. 20.
Introduction to Algorithms Analysis Tools. Big-O
analysis: a methodology to predict the resources that the algorithm requires in
terms of computer memory and computational time. Counting primitive operations.
Algorithm growth rate. Reading Dale,
Joyce, Weems, chapter 10
Exception Handling in Java.Writing your own exception classes. Catching ALL possible exceptions. Reading:
Liang, chapter 14 + notes
Arrays as a data structure. The basics of Arrays in Java. Array’s
creation, initialization and elements’ access. One dimensional, n-dimensional
arrays. Array of objects. The ArrayList class in Java.
Linkedlist as a data structure. The concept of linked data representation. Organic implementation of linkedlist and its
operations (add, delete, and search), implementation of Iterators.. Linkedlist provided in the Java standard
library. Usage of iterators to traverse a linkedlist. Linkedlist implementation
of Stack and Queue data structure.
Tree as a data structure. Trees’ terminology. different types of trees,
different types of traversals. Finding, inserting and searching for a node in a
binary search tree. The efficiency of binary search tree. Heaps as an instance
of a tree’s data structure. Graph as a data structure. Introduction to Graphs.
Graphs’ terminology. Programmatic Representation of Graphs. Modeling real-world
data as graphs: Social Networks Data as a graph, Airport & flight
connections as a graph. Graph traversals: depth first search and breath first
search. Graph connectivity. Algorithms to find paths between two nodes.
Bi-connected Components (application: potential communities in a social graph).
Articulation Points (important individuals in a social graph). Topological
sort.
Hash Table. Different
types of conflict resolution and different choices for hash functions.
Optional (if time
permits): Balancing binary search
trees and self-balancing binary search trees. Priority queues and heaps.
Grading
25% Programming assignments
and homeworks 35% Midterm 30% Final Exam 5% Quizzes 5% Recitation
attendance, class attendance and exercises