Rob Howe's fall2017 Journal
I'm back. You have me for 3 classes now data…, data…,and da.. er discrete. This is my last semester here at CCC. I'm looking forward to this Semester and quote on quote being lit on fire. I'm looking forward to more difficult projects that can actually prepare me for future work and more advanced classes at a 4 year university.
infix means that there the computer processes computation in a set order ie (2+1)*4 “=12”
if operations are prefix the operators preceed their operands ie *+214 “=12”which could be interpreted as the multiplication of (the sum of 2 and 1 and) 4
if postfix the operands preceed their operators 21+4* “=12”
in order traversal of a tree would be going from a parent then the left child then to the right child
preorder traversal goes through the left child the parent then the right child,this will process the tree from least to greatest
postorder traversal goes through the list right then the parent then the left child, processing the tree from greatest to least
when obtaining a node from the tree the saftest thing to do is to grab either the greatest value in the left subtree or the least in the right subtree
For Discrete this week and with yol0 I struggled to truly find an algorithmic approach with out using any conditional statements what so ever, I could not seem. The one thing I have thought of would be to massively increase the size of my arrays so that the value of each 17 characters would be stored at that array index. but that just seems like that does not fully go for the intent of the project, which I dont want to be untrue to. It really wont hurt me to lose some points with all the bonus points I have. I also am at a point where the Eoce will take greater importance for me.
Essentially it is really good to basically be autistic when it comes to programming and day to day problem solving and and awareness. stacks don't necessarily be based on lists. they can be looked at as arrays, and that is how the stacks in computer architecture are interpreted. Stacks and Queues can looked at as peers, both being based on lists but only differing in FILO vs FIFO. with a stack the only node that one needed to be aware of was the top of the stacks, but with the queue one needs to be aware of the front and back of the queue. With the Queue vs the stack I noticed that the queue required a little more care than the stack due to the additional node pointer, and I looked at the queue to being more like a list rather than the stack, even thought they were both lists.
Trees are also another list type implementation that clearly can be much faster for searching for the largest/smallest elements or even searching for specific elements in large data lists due to the branching data sets.
This week the project is yol0 which appears like it will work much like how nbm0 did for me, with planninng out arrays
Big O notation is used to describe the best case/ worst case for the time or space used for an algorithm. for example O(1) means that time or space used is always constant
O(N) means that the cost is proportional to the data set
O(N^2) means that the cost grows at square of the data
O(2^N) means that the cost doubles for every element in the data
O(logN) means that it behave very fast intially and then later begins to taper out with larger and larger data sets
also big O notations are also contingent upon the variable with the largest exponent ex. O(n^3+50n^2) == o(n^3) as these are only looked at for when data sets get larger.
With the dll projects the header provided by Matt could be considered the specification or standard the actual written code could be considered the protocol or implementation.
But often the implementations of the standards can vary and go beyond what was specified within the standard.
Data is not about learning how to make linked lists and write functions for them, but rather learning how to manipulate data how you need to arrange it and how can we access our data
stacks are an example of “Last In First Out”(LIFO)/“First In Last Out”(FILO) stacks can limited in size buffer overflow/underuns are an example of this. Queue are the opposite of a stack “First in First Out”(FIFO)/“Last In Last Out”(LILO)
Even though this is for data, in the cycle check for the dll2 bonus I have found an algorithm referred to as “the hare and tortoise” algorithm in which two nodes cycle through the list, but one, “the hare” , moves twice as fast as the other, “the tortoise”, but if there is a cycle eventually they will become the same node, proving that the list is cyclical. other wise they would just reach the end of the list. This has a O(n) time complexity which means that its speed is constant to the size of the list and will not be faster or slower with larger or smaller data sets. Apparently this algorithm can then be used to find the start of the cycle by then incrementing the hare at the same rate as the tortoise, and starting the tortoise at the start of the list, that way the next time they meet it will be at the start of the list
rewriting code is very important for truly conceptualizing and understanding what is going on and happening in the program. It would be truly productive to do so, but In all probability will never happen out of sheer laziness
writing list functions should not be reinventing the wheel, Re-use previous implementations and make the list look cleaner
with writing libraries and calling functions, it is slower, but it makes the functions more modular and can be used to make greater changes in the library by changing one individual function.
I need to learn that when you free a variable to set that pointer to null, I knew that the operating system deallocates the memory when it actually gets around to it. Also using functions makes digestibility to understand the code in a file much more simple. Also with DLL2 I am trying to actually make use of the status code to confirm the that calls to other functions worked properly.
The point of the projects is not explicitly about primes or encoding, but rather looking at the algorithms and understanding the algorithms and making them better. Its about looking a things long term vs short terms, how abstract vs how concrete something is, and the direct and indirect outcomes.
The one thing I learned from the dcf2 project is that it seems so often the best and most efficient solution is sometimes the much simpler solution. I found this when the control byte occurred naturally in the data where originally my big long-winded line of code gave me a serious of errors and incorrect output, but when I simplified this by a large margin the solution came much more easily.
coming back from break much has changed. Matt has updated the hardware and software for lab46. first off all the known host file needs to be edit by either editing the line in question or deleting the known_host files altogether
Also know there are quotas for for how much memory each user has available to them which can be checked by running “quota” to save lots of memory clean out binary and object files especially when done with a project
also there is a new directory called info in the home directory that contains symbolic links to the files available in the website (ie. journal, status , wiki, coursenotes)
unions are syntactically the same as a struct. in a struct the memory is allocated for all members, but in a union memory is allocated
when doing dcf2 if the control by is encountered in the program just treat it as an encoded byte and check for repetition and then print it
for bdt1 The whole file io thing is getting much easier and second nature. I am curious though that if with all files being treated as binary files on the unix systems, would it be a better practice to open and read the files with the binary modifer/tag in fopen for the sake of portability. of Also with bdt1 I am starting to be less stupid and release the value of using functions more often instead of copy/pasting lines or rewriting the whole thing. This was very valuable with writing a function to write to the arrays I used and display the contents of the file, especially with me opting in for the extra credit with the modes. overall my mine was like 20 lines and 300 lines overall instead of the likely possibility of it being 600 plus lines.
Filler text- your entry goes here; remove this line to receive full credit.
Filler text- your entry goes here; remove this line to receive full credit.
when using printf/scanf the %h<whatever> modifier represents reading in a value half the size of that data type. ie %hhd is a int the quarter of the size of an int, ie. 1 byte.
when accessing the member of a struct array using pointer notation use the format (*(struct+index)).member to avoid compiler errors – when in doubt use more parentheses.
sll3 and sll4 finish the class work involving singly linked lists
so far we have just been making lists of singly linked nodes and but starting with sll3 there will be singly linked lists of singly linked nodes
through using our libraries of groups that access lists that access nodes behaves in a way that is very similar to object oriented design/ programming with the abstract-ness of things doing individual specific things.
The concept of discrete is not just getting something done, but getting it done in the most effective ways.
two dimensional arrays are just one dimensional arrays that have arrays hanging off of its indexes
a 2d array would be a pointer of pointer. when allocating the array allocate the first collumn and then allocate the memory for the rows hanging off of it, and do the reverse when deallocating the memory.
np problems take a long time and can be completed by the computer,but the predictability of when it will complete is extremely difficult to determine
with compression the best results occur when looking at files on the bit level rather than the bytes level which is what has been used in the dcf projects.
also over the break week there is a bonus project for writing a NES game genie, that will involve encoding/decoding on the bit levels
This class has provided experiences with make files, header files, libraries, debugger, version control
compares char return will do a bitwise or of the status codes
memory leaks are when there is when a reference to a portion of memory is lost and was not properly deallocated. do not allocate a pointer that will be pointed to null
strtol is the parent function for the wrapper function atoi. it allows you to convert a c-string into a long int in the base of your choosing and will also store chars found after a number provided in the string.
Journaled file systems do not immediately write to disk. it first writes to a transaction log.
the system will not immediately deallocate memory when free is called. it does that when the os has time available to do that
All ascii is binary, but not a binary is ascii. Binary can also include jpeg mp3 etc.
all strings are char arrays, but not all char arrays are strings as they do not have null terminators to indicate
where dcf0/1 was more conceptually challenging and syntactically simpler bdt0 will be the opposite
always make sure when opening files and allocating memory always close said files and free said memory at the end of the program
terminals do colors based on escape sequences
for the sieve algorithm for finding prime numbers it is unnecessary to continue marking numbers off after the square root of then end of the range. also it is unnecessary to to start marking off multiples of a number for any number factor less the the current number
4 Types of errors encountered syntax errors, chair to keyboard, logical errors, and runtime errors(divide by 0, seg faults, etc..).
a wrapper is a function that is used to call another function (ie printf() is a wrapper for fprintf(stdout,…)).
to compile with the debugger add “-g” modifier anywhere that is not immediately following an “-o”.
files compiled with the debug are a lot bigger and slower than a regularly compiled file. these files can be ran just normally. to use the debugger pre-ppend with gdb to the debugger file.
break point is a marker the debugger sets which will stop running the program where you set that break marker.
*s will debug by step moving to the next step *n will debug by step moving into next step in same scope(not going into a fuction) *print/display <variable> will output the contents of a variable *running display will always output through every step. * c will continue running as the program * watch can be used to continue the program until a the watchpoint condition is executed.
The language doesn't matter when algorithms are understood and used well enough Java has poorer performance than a c/C++.
less control over the program environment using dynamic access and letting the computer do what it needs to do, makes our programs run faster.
sprintf and sscanf deal with functions using strings strings are terminated by null terminator all strings are char arrays but not all char arrays are strings sprintf can make it easy to convert other types to string sprintf(string,“%s-%d”, “word”, int j); for example
the implementation of the prime calculation can either take up small amounts of memory and takes a long time to calculate, or large amounts of memory and take significantly less time to calculate.
for the space based approach memory caps will be put in place to prevent eating up all the memory on lab46
alaways check to see if malloc has allocated memory
when comparing or copying non null terminated char arrays the strcmp and strcpy function will not correctly read a 00 byte. the mem variants compare bytes vs char and will read in the 00 bytes along with others.
the functions like mknode have no idea of what to do with the node and have no concept of the list
there will be 5 singly linked list projects. huge piece of accessing something is adding restrictions. Linked lists limit how we manipulate nodes.
multiple variations of linked lists are possible. we are currently using a list of singly linked nodes
when using (*)alloc memory is not guaranteed so if there is no memory to allocate check to see if null was returned.
functions can take void as a parameter to indicate that there are no parameters for a function
different states of a list- undefined(if mklist hasnt been implemented) -null(mylist=null) - empty( mklist has been ran, but engine and caboose =null)
any program compiled with gcc or g++ can have a debugger added by using -g modifier
using gdb debuger- “gdb <path to program>” enter cli args or enter “run”, type “backtrace” and it should tell you where the program may be segfaulting.
the more patterns encountered the better fluency in problem solving. trying to have excessive control of a program can make the program not as strong. The computer should be allowed to do its own thing from the start to the end of the program(ie. monitoring uneeded info byte by byte). ie direct access(everything has a named variable) or indirect access(2 variables for a 1000 items).
a flag/status value can be something that is set or unset once an action has happened(ie. my hastested for primeregm).
using ftell and fseek to determine the size of a file is very taxing(essentially a for loop to count the number of bites) much more efficient to just keep a track of byte count when processing data.
the more times you implement something the more intelligent decisions you can make with those ideas(dcf0 to dcf1).
“computer science is thinking about thinking” - Matthew Haas
Nodes are structures that contain data and also can point and “link” to another node, creating a list. Nodes do not necessarily need to be a named variable, but rather can be pointed to by variables that can be moved depending if the list has been changed.(ie. start&tmp)
Ternary statements consist of (condition)? statementiftrue: statementiffalse;.
scalar variables, only one single piece to the variable(ie simple types: int,char,double)
composite varaibles, made of multiple components(arrays and structs);
to access a struct member use '.' if it is a static struct or '→' if the struct is dynamic(pointer).
the '.' operator can be used on a dynamic struct using (*[struct name]).[member name]
array=1 and *(array+1)=1 are functionally the same
typedef allows a varaible to have two individual names
preprocessor symbols prevent header files from being used more than once and keep the compiler from yelling at you:
*** added to class wiki
when using fprintf/fscanf the format “%c”, <value to be cnvted to char>
Logical operations based on two boolean values , p and q
operation:|Contradiction|Logical|Converse |Negation|Material p|q |(False) |NOR |nonimplication|(P) |Negation|nonimplication|(q) T|T| |F |F |F |F |F |F T|F| |F |F |F |F |T |T F|T| |F |F |T |T |F |F F|F| |F |T |F |T |F |T
operation:|Exlcusive(XOR)|Logical|Logical(AND)|Logical(XNOR)|Projection |Material p|q| |disjunction |NAND |conjunction|biconditional|function(q) |implication T|T| |F |F |T |T |T |T T|F| |T |T |F |F |F |F F|T| |T |T |F |F |T |T F|F| |F |T |F |T |F |T
operation:|Projection |converse |Logical |Tautology p|q| |function(p)|implication|disjunction|(True) T|T| |T |T |T |T T|F| |T |T |T |T F|T| |F |F |T |T F|F| |F |T |F |T
maximum value value for a char is 255 this becomes an issue when encoding a file and it occurs over 255 times
stride values represent the number of bytes to be read to be encoded at a time
make debug to make the debugger. Run “gdb [binary file path]”. type command line arguments. if a seg fault happened run “bt”(backtrace). this will tell you the line where the segfault will happen.
feof returns a non-0 value until it reaches the EOF marker.
RLE compression is mainly useful on files with lots of repetition like in image files. It will make files without much repetition larger.
In a unix system all files are treated as binary so when reading and writing from them the modes do not need to be in a binary read or write.
fscanf can be used to gather formatted data into 1 or more variables.
The class Data Structures will involve creating structures to manipulate data. these structures will be created often using C pointers and structs. I should memorize 0-15 in binary, hex, and octal, to be able to be better at converting between the various number bases used in computing. pointers can be considered memory variables. every variable will have a name, content, and address. cant use the referencing(*) operator on variables that have not been declared as pointers.
Q:asked about about addition to status C: mentioned about the use of address(&) and dereferencing(*) operator C: mentioned that 2^32 is 4 billion.
drawing pictures can help visualize problems and make them easier to solve assigning a pointer to the value of another pointer, will make it so both pointers point to the same address
C: mentioned that start→to→to…. pointed to an address rather than
Filler text- your entry goes here; remove this line to receive full credit.
Discrete is a branch of branch of mathematics concerning the study of finite or countable discrete structures. calculus is also involved as it is a particular method or system of calculation or reasoning, also tartar.
sent email about intializing the sqrt value for primerega, and mentioned it in the class irc.
encryption is a 1 way encoding, cannot be reversed compression is encoding to make files smaller jpeg and flac file compression are lossy
header byte valuse for dcf0 are in hex Ascii data is a form of binary Binary=.wav .mp4 .png files, etc common mistake when dealing with binary. do not use %x, use as %c when using functions like scanf