======Part 3====== =====Entries===== ====Month Day, Year==== This is a sample format for a dated entry. Please substitute the actual date for "Month Day, Year", and duplicate the level 4 heading to make additional entries. As an aid, feel free to use the following questions to help you generate content for your entries: * What action or concept of significance, as related to the course, did you experience on this date? * Why was this significant? * What concepts are you dealing with that may not make perfect sense? * What challenges are you facing with respect to the course? Remember that 4 is just the minimum number of entries. Feel free to have more. ====Month Day, Year==== This is a sample format for a dated entry. Please substitute the actual date for "Month Day, Year", and duplicate the level 4 heading to make additional entries. As an aid, feel free to use the following questions to help you generate content for your entries: * What action or concept of significance, as related to the course, did you experience on this date? * Why was this significant? * What concepts are you dealing with that may not make perfect sense? * What challenges are you facing with respect to the course? Remember that 4 is just the minimum number of entries. Feel free to have more. ====Month Day, Year==== This is a sample format for a dated entry. Please substitute the actual date for "Month Day, Year", and duplicate the level 4 heading to make additional entries. As an aid, feel free to use the following questions to help you generate content for your entries: * What action or concept of significance, as related to the course, did you experience on this date? * Why was this significant? * What concepts are you dealing with that may not make perfect sense? * What challenges are you facing with respect to the course? Remember that 4 is just the minimum number of entries. Feel free to have more. ====Month Day, Year==== This is a sample format for a dated entry. Please substitute the actual date for "Month Day, Year", and duplicate the level 4 heading to make additional entries. As an aid, feel free to use the following questions to help you generate content for your entries: * What action or concept of significance, as related to the course, did you experience on this date? * Why was this significant? * What concepts are you dealing with that may not make perfect sense? * What challenges are you facing with respect to the course? Remember that 4 is just the minimum number of entries. Feel free to have more. =====cprog Topics===== ==== Constant/Volatile ==== const: a variable that is defined and cannot be altered. volatile: can be modified in ways the compiler is not aware of. ==== Templates ==== allows a function or class to work on many different data types without being rewritten for each one. ==== This Pointer ==== ... this.var = var ... ==== Standard Template Library ==== is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. ==== Namespaces ==== using namespace std; is an example so one does not always have to use std::cout, std::cin, etc to use any of the std "commands" or function calls from other classes and makes access a lot more efficient in terms of writing code ====Keyword 6==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you want to demonstrate something on the command-line, you can do so as follows: lab46:~$ cd src lab46:~/src$ gcc -o hello hello.c lab46:~/src$ ./hello Hello, World! lab46:~/src$ ====Keyword 7==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you wish to aid your definition with a code sample, you can do so by using a wiki **code** block, an example follows: /* * Sample code block */ #include int main() { return(0); } ====Keyword 8==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you want to demonstrate something on the command-line, you can do so as follows: lab46:~$ cd src lab46:~/src$ gcc -o hello hello.c lab46:~/src$ ./hello Hello, World! lab46:~/src$ ====Keyword 9==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you wish to aid your definition with a code sample, you can do so by using a wiki **code** block, an example follows: /* * Sample code block */ #include int main() { return(0); } ====Keyword 10==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you want to demonstrate something on the command-line, you can do so as follows: lab46:~$ cd src lab46:~/src$ gcc -o hello hello.c lab46:~/src$ ./hello Hello, World! lab46:~/src$ ====Keyword 11==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you wish to aid your definition with a code sample, you can do so by using a wiki **code** block, an example follows: /* * Sample code block */ #include int main() { return(0); } ====Keyword 12==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you want to demonstrate something on the command-line, you can do so as follows: lab46:~$ cd src lab46:~/src$ gcc -o hello hello.c lab46:~/src$ ./hello Hello, World! lab46:~/src$ ===== Data Topics ===== ==== Hash Tables ==== is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number). Thus, a hash table implements an associative array. The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought. Ideally, the hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after it is created). Instead, most hash table designs assume that hash collisions—different keys that map to the same hash value—will occur and must be accommodated in some way. Also are used for FileSystems on hard drives that map inodes etc ==== Sorting Algorithms ==== a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions: The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order); The output is a permutation, or reordering, of the input. ==== Big-O, Theta, Bounds ==== big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. ==== Bubble Sort ==== is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, it is not efficient for sorting large lists; other algorithms are better. ==== Computational Complexity ==== is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty. ==== Selection Sort ==== The algorithm works as follows: Find the minimum value in the list Swap it with the value in the first position Repeat the steps above for the remainder of the list (starting at the second position and advancing each time) Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array. ==== Insertion Sort ==== Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm. Sorting is typically done in-place. The resulting array after k iterations has the property where the first k + 1 entries are sorted. ==== Quick Sort ==== makes O(nlog n) (big O notation) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(nlog n) algorithms.[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented as an in-place sort, requiring only O(log n) additional space. ==== Merge Sort ==== is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm. ==== Trees, Binary Trees (nodes, parents, children) ==== in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. ==== Bucket Sort ==== is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the O(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets. ==== Spaghetti (Poll) Sort ==== For simplicity, assume you're sorting a list of natural numbers. The sorting method is illustrated using uncooked rods of spaghetti: For each number x in the list, obtain a rod of length x. (One practical way of choosing the unit is to let the largest number m in your list correspond to one full rod of spaghetti. In this case, the full rod equals m spaghetti units. To get a rod of length x, simply break a rod in two so that one piece is of length x units; discard the other piece.) Once you have all your spaghetti rods, take them loosely in your fist and lower them to the table, so that they all stand upright, resting on the table surface. Now, for each rod, lower your other hand from above until it meets with a rod--this one is clearly the longest! Remove this rod and insert it into the front of the (initially empty) output list (or equivalently, place it in the last unused slot of the output array). Repeat until all rods have been removed. ==== Resources ==== http://en.wikipedia.org/wiki/Sorting_algorithm ===== Sysprog Topics ===== ==== Pipes ==== a set of processes chained by their standard streams, so that the output of each process (stdout) feeds directly as input (stdin) to the next one ==== I/O Redirection ==== Redirection is usually implemented by placing certain characters between commands. Typically, the syntax of these characters is as follows: command1 > file1 ==== Coroutines ==== are well-suited for implementing more familiar program components such as cooperative tasks, iterators, infinite lists and pipes. ==== Distributed Systems ==== consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal. ==== Semaphores ==== is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment. ==== File locks ==== restricts access to a computer file by allowing only one user or process access at any specific time. ==== Shared Memory ==== is simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies ==== Named pipes ==== FIFO behavior, is an extension to the traditional pipe concept on Unix and Unix-like systems, and is one of the methods of inter-process communication ==== Inter Process Communication ==== a set of methods for the exchange of data among multiple threads in one or more processes ==== Shell Variables and the Environment ==== are a set of dynamic named values that can affect the way running processes will behave on a computer ==== UNIX domain sockets ==== a data communications endpoint for exchanging data between processes executing within the same host operating system =====cprog Objective===== ====Objective==== State the course objective; define what that objective entails. ===Method=== State the method you will use for measuring successful academic/intellectual achievement of this objective. ===Measurement=== Follow your method and obtain a measurement. Document the results here. ===Analysis=== Reflect upon your results of the measurement to ascertain your achievement of the particular course objective. * How did you do? * Room for improvement? * Could the measurement process be enhanced to be more effective? * Do you think this enhancement would be efficient to employ? * Could the course objective be altered to be more applicable? How would you alter it? =====data Objective===== ====Objective==== State the course objective; define what that objective entails. ===Method=== State the method you will use for measuring successful academic/intellectual achievement of this objective. ===Measurement=== Follow your method and obtain a measurement. Document the results here. ===Analysis=== Reflect upon your results of the measurement to ascertain your achievement of the particular course objective. * How did you do? * Room for improvement? * Could the measurement process be enhanced to be more effective? * Do you think this enhancement would be efficient to employ? * Could the course objective be altered to be more applicable? How would you alter it? =====sysprog Objective===== ====Objective==== State the course objective; define what that objective entails. ===Method=== State the method you will use for measuring successful academic/intellectual achievement of this objective. ===Measurement=== Follow your method and obtain a measurement. Document the results here. ===Analysis=== Reflect upon your results of the measurement to ascertain your achievement of the particular course objective. * How did you do? * Room for improvement? * Could the measurement process be enhanced to be more effective? * Do you think this enhancement would be efficient to employ? * Could the course objective be altered to be more applicable? How would you alter it? =====Experiments===== ====Experiment 1==== ===Question=== What is the question you'd like to pose for experimentation? State it here. ===Resources=== Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment. ===Hypothesis=== Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment. State your rationale. ===Experiment=== How are you going to test your hypothesis? What is the structure of your experiment? ===Data=== Perform your experiment, and collect/document the results here. ===Analysis=== Based on the data collected: * was your hypothesis correct? * was your hypothesis not applicable? * is there more going on than you originally thought? (shortcomings in hypothesis) * what shortcomings might there be in your experiment? * what shortcomings might there be in your data? ===Conclusions=== What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made. ====Experiment 2==== ===Question=== What is the question you'd like to pose for experimentation? State it here. ===Resources=== Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment. ===Hypothesis=== Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment. State your rationale. ===Experiment=== How are you going to test your hypothesis? What is the structure of your experiment? ===Data=== Perform your experiment, and collect/document the results here. ===Analysis=== Based on the data collected: * was your hypothesis correct? * was your hypothesis not applicable? * is there more going on than you originally thought? (shortcomings in hypothesis) * what shortcomings might there be in your experiment? * what shortcomings might there be in your data? ===Conclusions=== What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made. ====Retest==== If you're doing an experiment instead of a retest, delete this section. If you've opted to test the experiment of someone else, delete the experiment section and steps above; perform the following steps: ===State Experiment=== Whose existing experiment are you going to retest? Prove the URL, note the author, and restate their question. ===Resources=== Evaluate their resources and commentary. Answer the following questions: * Do you feel the given resources are adequate in providing sufficient background information? * Are there additional resources you've found that you can add to the resources list? * Does the original experimenter appear to have obtained a necessary fundamental understanding of the concepts leading up to their stated experiment? * If you find a deviation in opinion, state why you think this might exist. ===Hypothesis=== State their experiment's hypothesis. Answer the following questions: * Do you feel their hypothesis is adequate in capturing the essence of what they're trying to discover? * What improvements could you make to their hypothesis, if any? ===Experiment=== Follow the steps given to recreate the original experiment. Answer the following questions: * Are the instructions correct in successfully achieving the results? * Is there room for improvement in the experiment instructions/description? What suggestions would you make? * Would you make any alterations to the structure of the experiment to yield better results? What, and why? ===Data=== Publish the data you have gained from your performing of the experiment here. ===Analysis=== Answer the following: * Does the data seem in-line with the published data from the original author? * Can you explain any deviations? * How about any sources of error? * Is the stated hypothesis adequate? ===Conclusions=== Answer the following: * What conclusions can you make based on performing the experiment? * Do you feel the experiment was adequate in obtaining a further understanding of a concept? * Does the original author appear to have gotten some value out of performing the experiment? * Any suggestions or observations that could improve this particular process (in general, or specifically you, or specifically for the original author).