Teknologi Informasi: Maret 2021

Data Structures and Algorithms in Java, 2nd Edition
Robert Lafore

1. Overview.

What Are Data Structures and Algorithms Good For? Overview of Data Structures. Overview of Algorithms. Some Definitions. Object-Oriented Programming. Software Engineering. Java for C++ Programmers. Java Library Data Structures. Summary. Questions.

2. Arrays.

The Array Workshop Applet. The Basics of Arrays in Java. Dividing a Program into Classes. Class Interfaces. The Ordered Workshop Applet. Java Code for an Ordered Array. Logarithms. Storing Objects. Big O Notation. Whay Not Use Arrays for Everything. Summary. Questions. Experiments. Programming Projects.

3. Simple Sorting.

How Would You Do It. Bubble Sort. Selection Sort. Insertion Sort. Sorting Objects. Comparing the Simple Sorts. Summary. Questions. Experiments. Programming Projects.

4. Stacks and Queues.

A Different Kind of Structure. Stacks. Queues. Priority Queues. Parsing Arithmetic Expressions. Summary. Questions. Experiments. Programming Projects.

5. Linked Lists.

Links. The LinkList Workshop Applet. A Simple Linked List. Finding and Deleting Specified Links. Double-Ended Lists. Linked-List Efficiency. Abstract Data Types. Sorted Lists. Doubly Linked Lists. Iterators. Summary. Questions. Experiments. Programming Projects.

6. Recursion.

Triangular Numbers. Factorials. Anagrams. A Recursive Binary Search. The Towers of Hanoi. Mergesort. Eliminating Recursion. Some Interesting Recursive Applications. Summary. Questions. Experiments. Programming Projects.

7. Advanced Sorting.

Shellsort. Paartitioning. Quicksort. Radix Sort. Summary. Questions. Experiments. Programming Projects.

8. Binary Trees.

Why Use Binary Trees? Tree Terminology. An Analogy. How Do Binary Search Trees Work. Finding a Node. Inserting a Node. Traversing the Tree. Finding Maximum and Minimum Values. Deleting a Node. The Efficiency of Binary Trees. Trees Represented as Arrays. Duplicate Keys. The Complete tree.java Program. The Huffman Code. Summary. Questions. Experiments. Programming Projects.

9. Red-Black Trees.

Our Approach to the Discussion. Balanced and Unbalanced Trees. Using the RBTree Workshop Applet. Experimenting with the Workshop Applet. Rotations. Inserting a New Node. Deletion. The Efficiency of Red-Black Trees. Red-Black Tree Implementation. Other Balanced Trees. Summary. Questions. Experiments.

10. 2-3-4 Trees and External Storage.

Introduction to 2-3-4 Trees. The Tree234 Workshop Applet. Java Code for a 2-3-4 Tree. 2-3-4 Trees and Red-Black Trees. Efficiency of 2-3-4 Trees. 2-3 Trees. External Storage. Summary. Questions. Experiments. Programming Projects.

11. Hash Tables.

Introduction to Hashing. Open Addressing. Separate Chaining. Hash Functions. Hashing Efficiency. Hashing and External Storage. Summary. Questions. Experiments. Programming Projects.

12. Heaps.

Introduction to Heaps. The Heap Workshop Applet. Java Code fo Heaps. A Tree-based Heap. Heapsort. Summary. Questions. Experiments. Programming Projects.

13. Graphs.

Introduction to Graphs. Searches. Minimum Spanning Trees. Topological Sorting with Directed Graphs. Connectivity in Directed Graphs. Summary. Questions. Experiments. Programming Projects.

14. Weighted Graphs.

Minimum Spanning Tree with Weighted Graphs. The Shortest-Path Problem. The All-Pairs Shortest-Path Problem. Efficiency. Intractable Problems. Summary. Questions. Experiments. Programming Projects.

15. When to Use What.

General-Purpose Data Structures. Special-Purpose Data Structures. Sorting. Graphs. External Storage. Onward.

Syllabus

Week 1: 1D array, list and vector, 2D matrices and tables of objects
Week 2: Java implementation of 1D and 2D arrays and its operations
Week 3: Linked lists and its various operations, stack and queue
Week 4: Java implementation of linked lists, stack and queue
Week 5: Binary trees: Representation and operations. Variations of binary tree: Binary search tree, Height balanced search tree, Heap tree
Week 6: Java implementation of binary trees and its variations
Week 7: Graph : Structure, representation and operations
Week 8: Java implementations of graph data structures
Week 9: Algorithms (Part-I): Searching and sorting algorithms
Week 10:Java implementation of Part-I algorithms
Week 11:Algorithms (Part-II): Greedy algorithms, shortest path algorithms
Week 12:Java implementation of Part-II algorithms