Data Structures and Algorithms: An Overview

Course Objectives

• The course focuses on data structures and algorithms
• Data structures covered include primitive and non-primitive types
• Non-primitive data structures are examined based on their usage, creation, management and JAVA implementation
• Algorithm analysis will cover methods, recursion, sorting, and searching techniques

Data structure types

• Primitive data structures include integer, float, character, and boolean
• Non-primitive data structures are divided into linear and non-linear types
• Linear data structures can be static (array) or dynamic (linked list, stack, queue)
• Non-linear data structures include trees and graphs and hash tables

Course Material and Software

• Textbook chapters form the basis
• Additional handouts are available in the GCR
• Netbeans for JAVA code implementation

Getting Started with JAVA

• Methods are executable statements inside functions and belong to class definitions
• All code in a Java program is part of a class
• Reserved words cannot be used as identifiers

Identifiers

• An identifier is the name of a class, method, or variable
• An identifier must start with a letter and can include characters, numbers, and underscores

Comments

• Comments are useful for code structure and understanding
• Use "//" for single-line comments and "/* comment */" for multi-line comments

Primitive Data Types in JAVA

• Boolean: true or false
• Char: 16-bit Unicode character
• Byte: 8-bit signed two's complement integer
• Short: 16-bit signed two's complement integer
• Int: 32-bit signed two's complement integer
• Long: 64-bit signed two's complement integer
• Float: 32-bit floating-point number (IEEE 754-1985)
• Double: 64-bit floating-point number (IEEE 754-1985)

Classes and Objects

• A JAVA Class defines a new type or reference type of Objects
• A class has instance variables, fields, or properties as well as methods such as constructor, accessor methods and update methods
• Classes are used as part of larger programs
• A class cannot run as a complete program unless it has a main method

Reference Variables

• Reference variables store the location of an object of the declared type
• With Student s;, no object is created yet, and the value of s is "null"
• new operator returns a reference (memory address) to the newly created object (instance of class) and this reference will be assigned to a reference variable.
• The "dot" is used to access object members

Dot Operator and Object References

• If the dot operator is used on a reference that is currently null, the Java runtime environment will throw a NullPointerException
• Student d=s; creates a new reference variable (pointer) to the Student object created, so we can use d or s to access the object member
• d and s are aliases for the same object

Method Signatures and Overloading

• Every defined method in a class has a signature, which includes the method name and parameter list
• A class may contain multiple methods of the same name but different signature
• Java does not allow two methods with the same signature but different return types

Modifiers for Visibility

• Public: accessible from any class
• Protected: accessible from the same class, package, and subclass
• Default: accessible from the same class and package
• Private: accessible only from the same class

More Modifiers

• Static modifier is used for memory management
• A static variable refers to a common property of all objects and gets memory once in the class area at the time of class loading

Static method

• Static method belongs to the class rather than the object of a class
• Method is not invoked on a particular instance of the class using the traditional dot notation.
• A static method can be invoked without creating an instance of a class, using the name of the class as a qualifier.

Abstract class

• Abstract methods don't have bodies, they just have method signatures as shown.
• If a class has an abstract method it should be declared abstract because it is essentially incomplete.
• An Abstract class doesn't need to have an abstract method
• If a regular class extends an abstract class, then the class must have to implement all the abstract methods of abstract parent class or it has to be declared abstract as well.

Final

• A final variable is initialized once and never assigned a new value
• If final is a base type, then it is a constant
• If a reference variable is final, then it always refers to the same object
• If class variable is declared as final, it must be declared as static as well.
• A final method cannot be overridden by a subclass
• A final class cannot be subclassed

Method Return Values

• JAVA methods can return only one value
• Multiple values can be combined into a compound object (e.g., Pair, Array, List) and a reference to that object can be returned
• An object can be changed that is passed with the values you want to return.

Method Parameters

• All parameters in Java are passed by value, meaning a copy of that parameter is used within the method body
• The method can change the copy but not the original
• If passing an object reference, the reference is copied as well
• Reassigning the internal reference variable inside a method will not change the reference that was passed in

Classes with Main Method

• Classes with main method serve as a self-standing program
• The application in Java must begin in some class with the execution of a special method named main
• This main method must be public, static and do not return any value and is able to take command line arguments

Compiling and Running JAVA in CMD

• Compile a JAVA Class using javac filename.java in the directory containing the class
• Run the .class file using java classname input_arguments and ensure correct directory

Wrapper, Array, and Enum

• Wrapper types: A Wrapper class is a class whose object contains primitive data types.
• Within an object of a wrapper class, primitive data types can be stored. In other words, we can wrap a primitive value into a wrapper class object.

Boxing and Unboxing in JAVA

• Java provides implicitly converts between base types and their wrapper types through a process known as automatic boxing and unboxing.

Arrays in JAVA

• An array is treated as an object
• Array variables are reference variables
• Arrays can be created using initializers or with new operator
• Array elements are assigned default values when arrays are created

Enum

• Enum is a special "class" that represents a group of constants (unchangeable variables, like final variables).
• Used when values aren't going to change

Expressions

• Increment -Decrement Operators: If it is used after a variable reference, then the value is first read and then the variable is incremented or decremented by 1.

Type Conversion

• Explicit casting must be indicated with parenthesis and the type
• Implicit casting has the potential for loss of precision

Simple Output and Input

• Output: use System.out.print() and System.out.println()
• Input: The Scanner class reads the input stream dividing it into tokens separated by delimiters

Pseudocode

• Pseudocode is not a computer program, but is more structured than usual prose that uses natural language mixed with standard programming language constructs