NBIT 209 Data Structures and Algorithm

Course Description:

• You know the basics of programming. You're proficient in variables, functions, control flow, basic defined data structures, and file IO. With these concepts, you can train a computer to complete nearly any task you can imagine. So what's next?

• Writing large programs! You will learn how to write and organize large pieces of software focusing on Unit Testing or Test Driven Development, Object-Oriented Concept and Data Structures & Algorithms

• This course will cover abstract data types and basics of algorithms, Linked lists, stacks, queues, hash tables, trees, heaps, and graphs. Students will also be taught how to derive big-Oh analysis of basic algorithms. All assignments will be in Java as way to introduce you to a new language. Programming languages are just tools to translate our ideas in practice, so students are encourage to use any language of choice to implement their ideas.

Course Outline:

• Introduction, Java Basics(Knowing Java Syntax) and Unit Testing
• OOP Concepts in Java
• Linked lists
• Reversing a linked list, introducing stacks and checking parentheses
• Using stacks for recursion, printing all substrings
• Introduction to asymptotic analysis and big-Oh notation
• Analysis of selection and insertion sort running times in asymptotic notation
• Analysis of binary search, starting discussion of binary heaps
• Detailed analysis of binary heaps [http://btv.melezinek.cz/binary-heap.html]
• Binary Search Trees [http://btv.melezinek.cz/binary-search-tree.html]
• Tree traversals, starting self-balancing trees and rotations
• AVL trees [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html]
• Range searching on BST, hash tables
• Algorithms questions: Part I
• Algorithms questions: Part II
• Introduction to graphs, starting BFS [https://algo.uni-trier.de/demos/]
• BFS on graphs, quick intro to Single Source Shortest Paths
• Single Source Shortest Paths: Bellman-Ford and Dijkstra's algorithms
• DFS and topological sorting of DAGs

Course Textbook

• Introduction to Algorithms, Third Edition by Cormen, Leiserson, Rivest and Stein
• Introduction to Algorithms, Fourth Edition by Cormen, Leiserson, Rivest and Stein
• Algorithms by Robert Sedgewick, Kevin Wayne
• Data Structures and Algorithm Analysis in Java by Mark A. Weiss
• Data Structures and the Java Collections Frameworks by William J. Collin
• Introduction to Java Programming and Data Structures, Comprehensive Version by Y. Daniel Liang