algorithms midterm

waterfall model

identify, design, implement, test, maintain

identify step

understand requirements, abstract idea of end result, follow software specifications

design step

considers low level requirements, determines data types and operations

implementation step

realization of an application, execution of a plan, idea, design, specification, selects language for coding procedure

testing/executing/debugging step

testing in real environments, finding and reducing bugs or errors in program

maintenance step

adding any modifications to handle new sw or hw components, cope with new problems or requirementst

three different abstractions

procedural abstraction, data abstraction, abstract data type

procedural abstraction

using subroutines, subfunctions, or submethods, writing subprograms as black boxes, hides details of process under a method name with parameters, breaks code into pieces, reusable

data abstraction

collections of data containing data + operations as abstract entities, uses class keyword to hide the detailed implementation, represents needed information without presenting details, abstract and extends keywords

abstract data type

separated object from an implementation, uses new keyword to create an object, considers one object whose behavior is defined by a set of data and operations

object oriented analysis

a method of analysis that examines requirements from the perspective of the classes and objects found in the problem domain, identifies and defines problem, requirements, and conceptual model of a software system, base model

object oriented design

process of planning a system of interacting objects for the purpose of solving a software problem, defines objects and interactions, can use UML to help model system

object oriented programming

software implementation technique to support analysis and design, supports inheritance and polymorphism, uses practice of abstraction and encapsulation

use case diagram

describes functional requirements of a system by showing the interactions between users (actors) and systems functionalities (use cases)

class diagram

represents classes, attributes, and methods, and the relationships between them, visually depicts encapsulation, inheritance hierarchies, and the static structure of a system

sequence diagram

illustrates dynamic interactions between objects over time, shows the ordering of messages exchanged between them, helps visualize how objects collaborate to achieve a specific functionality, demonstrates the flow of control and communication

encapsulation

grouping operations and attributes together into a single object, using classes

information hiding

hiding the details and implementation of data and methods for changing an objects state by presenting only an object’s behavior, using access identifiers

inheritance

a relationship among classes where one class shares the structure and/or behavior defined in one or more other classes, using derived classes (single, multiple, multilevel)

polymorphism

allows for a single interface to be used for different types of entities, allows an object to be treated as instances of their base class, overloading, overriding

constructor

used to initialize objects, ex: public class test {…}, every class inherently has a constructor

default/no argument constructor

constructor that takes no parameters

ex: class SRU {

int num;

string name;

}

SRU () {….}

paramterized constructor

a constructor that has parameters

ex: class SRU {

int num;

string name;

}

SRU (String name, int id) {..}

copy constructor

creates a new object by copying the field values of an existing object of the same class that is passed as an argument

ex: class Person {

Person (Person another_object) {

..}

…}

shallow copy

does not create a real object, set of the same memory location

deep copy

the ability to copy a composed objects values to another new object, creates new memory space

static polymorphism

compile time, fast speed since already linked, less flexible since requires a certain load time, uses method overloading

method overloading

allows more than one method to have the same name but they have different parameters or different data types

dynamic polymorphism

anything that is created can be changed during runtime, flexible since links are dynamic, slower because of additional linking process, method overriding

method overriding

runtime polymorphism, a child class can access and inherit the implementation of methods provided by the parent class, for objects of same type method is invoked via parent reference

primitive data type

pre-defined types of data, int, float, character, boolean

non-primitive data type

not defined by the programming language but instead are created by the programmer/user, class, string, object, array

overflow

an error that occurs when there are not enough bits to express the value,

underflow

values too close to zero to be represented

negative overflow

very small integers, < -2³²

positive overflow

very large integers, > 2³²

negative underflow

a value is too small negative number to be stored, -2^-127 <= very small negative number < 0

positive underflow

a value is too small positive number to be stored, 0 < (very small positive number close to 0) <= 2^-127

round off error

most real numbers do not have final exact binary representations, may be compounded in a sequence of operations, (0.7)¹⁰⁰⁰⁰⁰

class

user defined data type that is used to create objects, contains a set of properties and methods that are common and exhibited by all the objects of the class, body and members, class name, access modifiers, superclass

interface

a tool to achieve abstraction, and it can define abstract class without a method body, specifies a set of methods that the class has to implement, blueprint of a class

string

non-primitive, holds a sequence of characters in a single variable, a class and type that encapsulates a set of characters and provides additional feature

arrays

non-primitive, used to store elements of the same data type in a contiguous manner, users declare and intialize, stored in an indexed manner

pointer

a variable whose value is a memory address, used as an indirect reference

address operator

&, returns memory address of operand

*

indicates a variable is a pointer, dereferencing/indirection

typedef

reserved keyword to create an alias name for a specific data type

typedef syntax

typedef <existing_name> <alias_name>;

enum

A special data type that represents a group of constraints

enum example

enum Color = { RED, ORANGE, YELLOW,

GREEN, BLUE, INDIGO, VIOLET };

generic method

uses angle brackets to represent type parameters, specifically defined as a method that declares its own parameters, cannot replace a primitive data type

generic method syntax

public static <T> void methodName (T element)

{ ....... }

generic method with array

public static <E> void print (E[] list)

{ .....}

generic class

includes a type parameter in class declaration by < > syntax to specify the parameter type, looks like a normal class declaration, except that the class name is followed by a type parameter section < >

generic class syntax

ClassName <Type> obj = new ClassName <Type> ();

generic class with primitive data type

// client code

public class Generic {

public static void main(String[] args) {

Room <Integer> myRoom = new Room <Integer>();

...... }

// make a generic class

public class Room <T>

{ .........

.........

}

generic class with object

independent, Object as the type parameter, without relying on limiting yourself to wrapper classes such as Integer, double, character, string

ClassName <Object> obj = new ClassName <> ();

generic advantages

stronger type checks at compile time, elimination of cast, generic algorithms, code reuse

generic programming

allows one piece of data to have multiple data types rather than being dependent on a specific data type

stronger type check at compile time

allows errors to be detected at compile time rather than at runtime, Provide early information on program errors about whether an object is an acceptable type or not,

elimination of cast

no need for a type-casting process for object as required for Java

instead of this: String s = (String) list.get(0);

use this: String s = list.get(0);

generic algorithms

work on different types of objects, can be customized, and are type safe and easier to read

code reuse

can write a method, class, or interface once and use for any type again

array types

static arrays and dynamic arrays

static array

once the number of locations to store in the computer is specified, that number cannot be changed unless the instructions are changed. Compiler determines how memory is allocated at compile time

dynamic array

programmers designated the number of array locations as variable, which means that the memory allocations can be expanded or contracted at runtime

one dimensional array

simplest array structure, consists of one column of memory location, collection of similar data type, fixed size, stores value on basis of index value

two dimensional array

a block of memory locations associated with a single memory variable designated by “row” and “column” numbers, a table which has row and column number, row # is first then column #