Recursion and Data Structures

• Notes on Recursion and Data Structures in Computer Science

Recursion

• Recursion is a computer science approach to problem solving.
• The solution is based on smaller instances of the same problem.
• In programming, a procedure calls itself until a terminating condition is met.
• Recursion doesn't require specific repetition constructs like while or for loops.
• It breaks down a problem into smaller, manageable subtasks.
• Most algorithms presented recursively can also be presented iteratively.

Stack ADT Features

• Stacks consist of a "chain" of data.
• Elements are "pushed" onto the top of the stack for storage.
• Elements are "popped" from the top of the stack for retrieval.
• Stacks operate on the LIFO (Last-In, First-Out) principle.
• Attempting to access an element from an empty stack results in an error, which should be avoided.

Queue ADT Features

• Queues are made of a "chain" of data.
• Elements are "enqueued" at the back of the queue.
• Elements are "dequeued" from the front of the queue.
• Queues operate on the FIFO (First-In, First-Out) principle.
• Trying to access an element from an empty queue causes an error and should be avoided.

Binary Tree ADT Features

• Trees are made of nodes with two pointers.

• One pointer is to a smaller element node, and one to a greater element node.

• Trees assemble from the root node.

• The root node contains the middle value of the whole set in a balanced tree.

• Trees are naturally sorted.

• Searching is done in a binary manner.

• Standards and Conventions in Programming

Importance of Standards and Conventions

• Standards and conventions simplify processes, enabling international collaboration.
• A common understanding prevents miscommunication and makes it easier to work together.
• Lack of uniformity can lead to difficulties in understanding and communication.
• International conventions allow for a common language.

Standards in Programming

• Programming has its own conventions for global collaboration and code exchange.
• Following coding conventions reduces costs of software, especially during maintenance.
• Code is easier to understand, alter, and maintain when using standards as most maintenance is done by someone other than the author.

Common Coding Conventions

• Language conventions use English to remove language barriers.

• Comment conventions include "block" (or prologue) and "line" (or inline) comments.

• Block comments in Java use /* and */ delimiters and can span multiple lines.

• Line comments in Java are marked with //.

• Comments are used to summarize code.

• Object-Oriented Programming (OOP) Concepts

Object and Class

• An object is an abstract entity with data and actions.
• It can correspond to real-world entities and follows OOP's design practices.
• Instantiation is the process of creating a specific object from a class template.

Class

• A class defines abstract object entities.
• It does not use memory until an object is created.
• A specific object of a class needs to be built before usage.

Calling Methods

• Called methods send messages to an object to perform actions in OOP.
• An object has data that is specific and accompanies the execution of a program.
• Classes (from which specific objects are instantiated) do not occupy memory in a program; they are blueprints.
• A specific object from the class makes use of data and actions.

Unified Modeling Language (UML)

• UML is a way to visualize software design.
• It has become the standard for modeling object-oriented programs.
• Used to define different types of diagrams but the class diagram is mainly used.
• UML activity diagram is a modern extension of flow charts.
• The goal of the UML class diagram is to depict classes and their collaborations in an object-oriented program.
• Classes are shown as three-tier compartments that illustrate classes as rectangles divided into compartments.

UML Class Diagram Compartments

• The top compartment signifies the name of the class.

• The middle lists all the data that the object will hold.

• The last lists all the actions an object can perform.

• DataType: dataName describes the data.

• Action Presentation and Class Associations

Action Presentation

• Actions are presented in "returnType: actionName(inputType)" form.
• Input type is the type of data required by the specific action.
• Return type is the data type returned by the action after completion.
• If missing, depicts action that doesn't return any data.

Class Relationships and Diagrams

• UML class diagrams also show how classes collaborate.
• Associations are connections between classes, represented by a line.
• UML class diagrams can be complex due to increasing size and incorporating more information.
• Each association has two roles, each with a direction.

Roles

• Roles don't have to be named, but names clarify.

Multiplicities

• Associations have multiplicities at each end, indicating the objects linked to another class.

Inheritance

• Inheritance uses likeness to an advantage.

• It's displayed with a hollow arrow.

• UML class diagrams can use just the names of the classes.

• It can focus on the associations, roles, multiplicities, and inheritance.

• UML Relationships: Association, Dependency, Aggregation, and Inheritance

Association

• The simplest relationship between 2 or more objects.
• One or two role labels signify type of association.

Dependency

• Dependency is a "USES" relationship.

Aggregation

• Aggregation signifies that one object belongs to another exclusively.
• There's a parent and child object.
• Lifecycles of parent and child objects are independent.
• Aggregation is a "has" relationship.
• A hollow diamond indicates an aggregation relationship.

Inheritance

• Inheritance is where one object is a specialized form of another.
• A subclass is a specialized form of a superclass.
• Indicated by a hollow triangle for inheritance relationships.

Object Dependency

• Dependencies are directional.

• Solution finding involves dealing with interdependent objects.

• Dependencies decrease code reuse and increase maintenance overheads.

• Data Classification in Programming

Example Scenario: Vehicle Classification

• A store that sells different types of vehicles is used as an example.
• The computer program classifies vehicles as a tree structure
• VehicleType object inherits properties from the Vehicle class.
• The Automobile class is associated with the VehicleType object through a member variable.

Data Types

• Data types allow the programs to classify data into different types.
• Common data types include integer numbers, real numbers, Booleans, and strings.

Integer Numbers

• Represent a finite subset of the mathematical integers.
• Depending on the system, every integer is represented by a specific number of bits.

Real Numbers

• Real numbers contain fractional values.
• Real numbers are approximated, balancing range and precision.
• Two data types: float and double allow representation of floating points.
• Double is more precise and represents larger values than float.

Booleans

• Booleans are data that represent only two values: True or False.

Strings

• Strings are a series of characters mainly used to display information.

Data types

• Data items must be represented by different data types.

• Integer, floating point, string and Boolean data types represent data.

• Parameters in Object Actions

Objects and Actions

• Objects have data and actions.
• The Vehicle class relies on the Engine class; Gas and Electric Engine classes are of type Engine.
• The Vehicle class knows how much distance via the action must travel via goForward(int d).
• The Vehicle class calls the start() action from the Engine so that the goForward(int d) action takes place.

Actions

• The values from actions can be passed as parameters as discussed in Chapter 4.

• Different language terms like procedure, function, method, and subroutine refer to actions.

• An implemented object action is a sequence of instructions doing a specific task.

• In Java, methods signify subprograms that return values or pass variables.

• Name of Parameter describes what is used; the Argument is the data passed into actions.

• OOP Features: Encapsulation and Inheritance

Encapsulation

• Encapsulation puts both data and action as a single component.
• Classes structure is made unmodifiable and accessed via methods.
• Encapsulation is similar to using encapsulation when accessing salary.

Inheritance

• Refers to an object that is a parent, and how they are passed down.

• OOP uses inheritance widely in order to make derived classes from existing classes.

• Derived classes inherit the existing classes.

• Both student and professor classes inherit from parent classes as parent classes make the former.

• Polymorphism, Static vs, Dynamic Polymorphism

Introduction to Polymorphism

• Polymorphism means "many" where it takes many forms.
• Multiple forms include int and float.

Static Polymorphism

• The compiler determines the method to be called based on method signatures and parameters.

Dynamic Polymorphism

• A subclass overrides actions of the superclass.
• Subclasses can alter parent class actions to be specific to their needs.

Abstract Methods

• Primitive datatypes are datatypes that are predefined.
• Complex datatypes are complex.
• There is standardization and implementation.

– Encapsulation, Inheritance and Polymorphism in Detail ###Encapsulation

• Plays the role of protection to prevent data and actions being accessed from unwanted behavior
• Data and actions are only accessible in specific, predefined ways.

Advantages of Encapsulation

• Data in a class can be made read only.
• Classes can alter how data is stored.
• The system is easier to maintain due to classes taking place without external changes.

Advantages of Inheritance

• Inheritance means an object is specialized from another object
• Extensibility: All child classes inherit the actions and data of a parent class
• Reusability: Child classes inherit actions and data that won't need to be re-altered.
• Information is hidden to specify which actions and data are available in child classes.
• Classes can override their actions to improve on parent actions.

Advantages of Abstraction

• An object action in subclasses can improve on the original.

Polymorphism and the Reuse of code

• Object actions can have the same parameter lists and processes
• Subclasses can alter their parent class actions.
• Inheritance and polymorphism helps polymorphism be compatible.

Collections and Classes

• Libraries of objects are collections of classes for a programmer developing a program.

• Object-Oriented Programming: Object reuse with team management and disadvantages

Team building

• When working as individuals (solo) , the process from development , testing, and development cycle helps developers be aware the project
• This helps developers get feedback and quicker changes compared to those working as teams

Cons

• One may have to oversee multiple projects needing more time than dedicated time

Benefits of team

• Helps better for larger project.
• Team members bring to the table ideas vs solo
• Some offset others
• Teams need well mannered communications
• Team meetings are slow

Modularity

• Process involving separate subprograms before construction

• When something increases in size, design is tough

• This provides re-usability

• Less needs for more codes to be written

• Team support provides team that can work on these programs separately The program is comprised of simple code • Box functions change without others.

• OOP Concepts: Classes and Objects

Class Definitions

• Classes in OOP define a template for objects, setting the blueprint. These include data and functions.

Identifier

• An identifier names an entity, using alphanumeric sequences and underscores, without starting with digits.

Primitive

• Functions of primitive is to set values to objects.

• Class Terminology and Primitive Types

Class Definition and Instantiation

• A class defines a template (blueprint) through which objects are is created from.
• Classes provide data and actions

Identifiers

• Identify data and actions and are used for code
• Alphanumeric codes do not begin with code

Primitive Data Types

• They are used as defined as a base.

Instance Variables

• Defined as a Class object for the purpose of the class' definition
• This lets objects alter without object change

Parameter Variables

• Data that is passed, an integer named hours, is named the sleep
• Sleep takes values that need to go to sleep action

Local Variable-

• -Defined inside code, used with action

• Objects: Actions and Methods

Methods

• Methods are classes for actions
• Methods describe objects
• Accessor methods help find code data
• Mutator methods can find code change

Constructors and signatures

• Constructor Methods find code values so it initializes those

Local, protected and public methods

• Signatures and methods are needed to find code

Protected methods

• They are only accessible in code and subclasses

Public commands

• This can be accessed by any code.

Inheritance and Static Variables

• Extending

  • Sections on inheritance have looked and have looked on how one can improve from one

• Student

  • Student extends data to to professors class, professor and students need to be in the same level

  • Classes share properties

  • Can change with affecting change in all