CSCI.UA.0102  Data Structures 

Detailed Syllabus and Course Website

  •  Course Description

    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.

  • Pre-requisits

    Passing CSCI.UA.0101 with a grade of C or better.

  • Books

  • Agenda & Topics

    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.

    Searching & sorting. Linear search. Binary search.
    Bubble sort. Selection sort. Insertion sort. Quick sort. Merge sort. Radix sort.

    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