Data Structures - Lecture notes 1-8 PDF

Preview

Summary

lecture notes for 1-8...

Description

LECTURE/OFFICE HOURS LINK: https://meet.google.com/trf-yuuk-kiw REF BOOK (IN PYTHON): https://runestone.academy/runestone/books/published/pythonds3/index.html GITHUB FOR CLASS: https://github.com/CSCI2010U DISCORD: https://discord.com/channels/744955549959061583/ https://github.com/CSCI2010U/sample-assignment-maia-johnson UML Guide: https://www.dummies.com/programming/java/diagram-java-classes-uml/ Course Outline

3

GitHub and Gradle

4

Lecture 1: The Java Programming Language

6

Lecture 6: Arrays

10

Lecture 6: Analysis I

10

Lecture 7: Analysis II Counting Primitive Operations 7 Important Functions

12 13 14

Why Growth rate matters Big-Oh Notation Big-Oh and Growth Rate Big-Oh Rules

17 18 20 21

Asymptotic Algorithm Analysis Relatives of Big-Oh

21 21

Lecture 8

22

Course Outline Data Structures and Algorithms I https://openjdk.java.net/projects/jdk/14/ https://github.com/CSCI2010U/LectureExamples https://classroom.github.com/a/v4zytBEG eclipse theia Office Hours

Lab Schedule - Done over discord

Topics of the Course: 1. The Java programming language 2. Arrays, linked lists, doubly-linked lists 3. Algorithm analysis 4. Recursion 5. Divide and conquer 6. MergeSort and QuickSort 7. Linear Sorting 8. Trees, binary search trees 9. AVL trees 10. Splay trees 11. Maps, hashing 12. Graphs, depth-first search, breadth-first search, digraphs Assignment 1: java based First 3 labs: java based Github classroom Midterm and exam: probably open book 3070 courses help with interview questions

GitHub and Gradle https://gradle.org/install/ https://www.freecodecamp.org/news/learn-the-basics-of-git-in-under-10-minutes-da548267cc91/ https://git-scm.com/docs/gittutorial https://git-scm.com/docs/user-manual - how to clone a GitHub repository (e.g. git clone https://github.com/CSCI2010U/LectureExamples) - how to add any new files to the repository (e.g. git add folder1/myfile.cpp, or git add --all) - how to commit that code to your local copy (e.g. git commit -m "Fixed the repeating decimal error") - how to push that code to the remote (e.g. GitHub) repository (git push origin main) git clone https://github.com/CSCI2010U/sample-assignment-YOURNAME cd sample-assignment-YOURNAME gradle run gradle test

Git Workflow Diagram

If you consider a file in your Working Directory, it can be in three possible states. 1. It can be staged. Which means the files with the updated changes are marked to be committed to the local repository but not yet committed. 2. It can be modified. Which means the files with the updated changes are not yet stored in the local repository. 3. It can be committed. Which means that the changes you made to your file are safely stored in the local repository. Commands ● git add is a command used to add a file that is in the working directory to the staging area. ● git commit is a command used to add all files that are staged to the local repository. ● git push is a command used to add all committed files in the local repository to the remote repository. So in the remote repository, all files and changes will be visible to anyone with access

● ● ●

to the remote repository. git fetch is a command used to get files from the remote repository to the local repository but not into the working directory. git merge is a command used to get the files from the local repository into the working directory. git pull is a command used to get files from the remote repository directly into the working directory. It is equivalent to a git fetch and a git merge .

$ git config --global user.name "YOUR_USERNAME" https://stackoverflow.com/questions/17909277/accidentally-set-remote-master-url-cannot-get-rid-of-itanymore Accidentally set the remote incorrectly? You can try to rename it: git remote rename master origin here 'master' is just the name of a remote, it is a key referring to a value (the remote url). If remote origin still exists, then: git remote remove master git remote set-url origin [email protected]:myaccount/myrepo.git

you can get documentation for a command such as git log --graph with: $ man git-log $ git help log Introduce yourself to Git with your name and public email address before doing any operation. The easiest way to do so is: $ git config --global user.name "Your Name Comes Here" $ git config --global user.email [email protected]

Lecture 1: The Java Programming Language JAVA I (FOR REFERENCE) Java is a compiled language Source code: file that the code is saved in (.java) - a (.class) file is created by the compiler All code in java MUST belong to a class Program Example: public class Universe{ public static void main(String[ ] args) { system.out. println(“Hello Universe”); } } In the above example: ● The parameters passed to main is an array of strings ● Void means it returns nothing ● Static means the method belongs to the class not an object ● Public means that anyone can run the method (as in public static void) ● Public class Universe means anyone can run the program Components of a Java Program ● Executable statements are placed in functions aka methods that belong to class definitions ● When running a java program, main is run first ● { junk in the curly boys define… } a coding block Identifiers The name of a class, method or variables. Can be any string of characters that begins in a letter and consists of letters Reserved exceptions:

Program Example: Base Types ● Basic ways of storing information

● ●

An identifier variable can be declared to hold any base type ○ Can also be later reassigned to hold another value of the same type Types and examples below

Classes and Objects ● Every object is the instance of a class ○ The class is the type of object it is and serves as a blueprint for objects ■ Defines the type of data the object holds and the methods for holding, accessing and modifying the data Critical Members of classes in Java: Instance Variables ● Also called fields ● Represent data associated with an object of a class ● Must have a type ○ Can be a base type (ex. int) or any class type Methods ● Blocks of code that perform actions ● Can take parameters as arguments ● Behaviour may depend on the object they are called on and the values of parameters that are passed ● Accessor Method: returns information to the caller without changing any instance variables ● Update Method: may change one or more instance variables when called Example: ● This class includes one instance variable, count, which has a default value of zero, unless otherwise initialized. ● Includes two special methods known as constructors, one accessor method, and three update methods.

Creating and Using Objects ● Classes are reference types and variables of this type are known as reference variables ● Reference variables can hold the location (memory address) of an object of the declared class ○ Might make it reference an existing instance or a newly created instance

○

● ●

Can also store the null value ■ Represents the lack of an object A new object is created by using the new operator followed by a call to a constructor of the desired class Constructor: a method that always shares the same name as its class ○ The new operator returns a reference to the newly created object ○ The returned reference is usually assigned to a variable for further use

Example continued: ● There is a new constructor on line 4; its reference is assigned to variable c ● Relies on a form of the Counter constructor that takes no arguments (in the parenthesis)

The Dot Operator ● One of the primary uses of an object reference variable is to access members of the object’s class ● You get access to these using the dot operator ○ ( . ) a period is the dot operator ● Methods associated with the object are called using the variable.methodName(parameters) Wrapper Types ● There are many data structures and algorithms that only work with object types ○ Not primitives ● To get around this java defines a wrapper class for each base type ○ Java provides support for implicitly converting between base types and their wrapper types ■ Through automatic boxing and unboxing

Example Wrapper Types

Signatures ● If there are multiple methods with the same name that defines a class ○ Java runtime runs the one with the amount of parameters sent as arguments (and their respective types) ● A method’s signature: the method name with the number and types of its parameters ○ Because it takes all of these parts to determine the actual method to perform for a method call ● A reference variable v can be seen as a pointer to some object o Defining Classes ● Class definition: a block of code delimited by { ... } ○ In the curly braces are declarations of instance variables and methods ■ These are the members of the class ● Immediately before the definition of a class, instance variable or method modifiers can be placed to convey additional information about the class Access Control Modifiers ● Public: says that all classes may access the defined aspect ● Protected: access to a defined aspect is only granted to classes that are subclasses of the given class through inheritance or a package ● Private: access to a defined member of a class is only given to code within the class ● When a variable or method of a class is static it is associated with the class as a whole and not each instance of the class Parameters ● A method’s parameters are define (in parentheses) after name of method

Lecture 6: Arrays Memory structure: implemented using adjacency memory spaces Address i+1 = address i + element_size Cannot redimension the array after making it. ● Arraylists resizes for you Capacity - max number of elements in the array -> called length in java Length - the current number of elements in the array Length...